Cycles and Intractability in a Large Class of Aggregation Rules

[摘要] We introduce the (j,k)-Kemeny rule -- a generalization of Kemeny's voting rule that aggregates j-chotomous weak orders into a k-chotomous weak order. Special cases of (j,k)-Kemeny include approval voting, the mean rule and Borda mean rule, as well as the Borda count and plurality voting. Why, then, is the winner problem computationally tractable for each of these other rules, but intractable for Kemeny? We show that intractability of winner determination for the (j,k)-Kemeny rule first appears at the j=3, k=3 level. The proof rests on a reduction of max cut to a related problem on weighted tournaments, and reveals that computational complexity arises from the cyclic part in the fundamental decomposition of a weighted tournament into cyclic and cocyclic components. Thus the existence of majority cycles -- the engine driving both Arrow's impossibility theorem and the Gibbard-Satterthwaite theorem -- also serves as a source of computational complexity in social choice.

[学科分类] 人工智能