Abstract
We prove that in almost all large tournaments, the minimal covering set is the entire set of alternatives. That is, as the number of alternatives gets large, the probability that the minimal covering set of a uniformly chosen random tournament is the entire set of alternatives goes to one. In contrast, it follows from a result of (Fisher and Reeves, Linear Algebra Appl 217:83–85, 1995) that the bipartisan set contains about half of the alternatives in almost all large tournaments.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Banks JS (1985) Sophisticated voting outcomes and covering relation. Soc Choice Welfare 1: 295–306
Bell CE (1981) A random voting graph almost surely has a Hamiltonian cycle when the number of alternatives is large. Econometrica 49: 1597–1603
Bollobás B (2001) Random graphs, 2nd edn. Cambridge University Press, Cambridge
Brandt F, Fischer F, Harrenstein P, Mair M (2010) A computational analysis of the tournament equilibrium set. Soc Choice Welfare 34: 597–609
Dutta B (1988) Covering sets and a new Condorcet choice correspondence. J Econ Theory 44: 63–80
Fey M (2008) Choosing from a large tournament. Soc Choice Welfare 31: 301–309
Fisher DC, Reeves RB (1995) Optimal strategies for random tournament games. Linear Algebra Appl 217: 83–85
Fisher DC, Ryan J (1992) Optimal strategies for a generalized “scissors, paper, and stone” game. Am Math Month 99: 935–942
Fisher DC, Ryan J (1995) Tournament games and positive tournaments. J Graph Theory 19: 217–236
Laffond G, Laslier J, Le Breton M (1993) The bipartisan set of a tournament game. Games Econ Behav 5: 182–201
Laslier JF (1997) Tournament solutions and majority voting. Springer-Verlag, Berlin
Miller NR (1977) Graph-theoretical approaches to the theory of voting. Am J Polit Sci 21: 769–803
Miller NR (1980) A new solution set for tournaments and majority voting. Am J Polit Sci 24: 68–96
Miller NR (1983) The covering relation in tournaments: two corrections. Am J Polit Sci 27: 382–385
Moon JW (1968) Topics on tournaments. Rinehart and Winston, Holt
Schwartz T (1972) Rationality and the myth of the maximum. Nous 6: 97–117
Schwartz T (1990) Cyclic tournaments and cooperative majority voting: a solution. Soc Choice Welfare 7: 19–29
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Scott, A., Fey, M. The minimal covering set in large tournaments. Soc Choice Welf 38, 1–9 (2012). https://doi.org/10.1007/s00355-010-0503-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00355-010-0503-4