×

A counterexample to a conjecture of Schwartz. (English) Zbl 1288.91062

Summary: In 1990, motivated by applications in the social sciences, Thomas Schwartz made a conjecture about tournaments which would have had numerous attractive consequences [T. Schwartz, Soc. Choice Welfare 7, No. 1, 19–29 (1990; Zbl 0698.90008)]. In particular, it implied that there is no tournament with a partition \(A\), \(B\) of its vertex set, such that every transitive subset of \(A\) is in the out-neighbour set of some vertex in \(B\), and vice versa. But in fact there is such a tournament, as we show in this article, and so Schwartz’ conjecture is false. Our proof is non-constructive and uses the probabilistic method.

MSC:

91B14 Social choice
91A12 Cooperative games

Citations:

Zbl 0698.90008
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Banks JS (1985) Sophisticated voting outcomes and agenda control. Soc Choice Welf 3: 295–306 · Zbl 0597.90011 · doi:10.1007/BF00649265
[2] Brandt F (2011) Minimal stable sets in tournaments. J Econ Theory 146: 1481–1499 · Zbl 1247.91055 · doi:10.1016/j.jet.2011.05.004
[3] Brandt F, Fischer F, Harrenstein P, Mair M (2010) A computational analysis of the tournament equilibrium set. Soc Choice Welf 34: 597–609 · Zbl 1202.91070 · doi:10.1007/s00355-009-0419-z
[4] Brandt F, Brill M, Fischer F, Harrenstein P (2011) Minimal retentive sets in tournaments. Soc Choice Welf (in press) · Zbl 1302.91075
[5] Dutta B (1988) Covering sets and a new Condorcet choice correspondence. J Econ Theory 44: 63–80 · Zbl 0652.90013 · doi:10.1016/0022-0531(88)90096-8
[6] Dutta B (1990) On the tournament equilibrium set. Soc Choice Welf 7: 381–383 · Zbl 0713.90007 · doi:10.1007/BF01376285
[7] Erdos P, Moser L (1964) On the representation of directed graphs as unions of orderings. Publ Math Inst Hung Acad Sci 9: 125–132 · Zbl 0136.44901
[8] Houy N (2009) Still more on the tournament equilibrium set. Soc Choice Welf 32: 93–99 · Zbl 1184.91085 · doi:10.1007/s00355-008-0311-2
[9] Laffond G, Laslier J-F (1991) Slater’s winners of a tournament may not be in the Banks set. Soc Choice Welf 8: 355–363 · Zbl 0733.90008 · doi:10.1007/BF00183047
[10] Laffond G, Laslier J-F, Le Breton M (1993) More on the tournament equilibrium set. Math Sci Hum 123: 37–44 · Zbl 0806.90002
[11] Laslier J-F (1997) Tournament solutions and majority voting. Springer, Berlin · Zbl 0948.91504
[12] Schwartz T (1990) Cyclic tournaments and cooperative majority voting: a solution. Soc Choice Welf 7: 19–29 · Zbl 0698.90008 · doi:10.1007/BF01832917
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.