Tournament solutions

Perhaps one of the most natural ways to aggregate binary preferences from individual agents to a group of agents is simple majority rule, which prescribes that one alternative is socially preferred to another whenever a majority of agents prefers the former to the latter. Majority rule intuitively appeals to democratic principles, is easy to understand and-most importantly-satisfies some attractive formal properties. As seen in Chapter 2, May’s Theorem shows that a number of rather weak and intuitively acceptable principles completely characterize majority rule in settings with two alternatives (May, 1952). Moreover, almost all common voting rules satisfy May’s axioms and thus coincide with majority rule in the two-alternative case. It would therefore seem that the existence of a majority of individuals preferring alternative a to alternative b signifies something fundamental and generic about the group’s preferences over a and b. We will say that alternative a dominates alternative b in such a case. As is well known from Condorcet’s paradox (see Chapter 2), the dominance relation may contain cycles. This implies that the dominance relation may not admit a maximal element and the concept of maximality as such is rendered untenable. On the other hand, Arrow writes that “one of the consequences of the assumptions of rational choice is that the choice in any environment can be determined by a knowledge of the choices in two-element environments” (Arrow, 1951, p. 16). Thus, one way to get around this problem-the one pursued in this chapter-is to take the dominance relation as given and define alternative concepts to take over the role of maximality. More precisely, we will be concerned with social choice functions (SCFs) that are based on the dominance relation only, that is, those SCFs that Fishburn (1977) called C1 functions. Topics to be covered in this chapter include McGarvey’s Theorem, various tournament solutions (such as Copeland’s rule, the uncovered set, the top cycle, or the tournament equilibrium set), strategyproofness, implementation via binary agendas, and extensions of tournament solutions to weak tournaments. Particular attention will be paid to the issue of whether and how tournament solutions can be computed efficiently.