IDEAS home Printed from https://ideas.repec.org/a/spr/sochwe/v54y2020i1d10.1007_s00355-019-01213-6.html
   My bibliography  Save this article

Robust bounds on choosing from large tournaments

Author

Listed:
  • Christian Saile

    (Technical University of Munich)

  • Warut Suksompong

    (University of Oxford)

Abstract

Tournament solutions provide methods for selecting the “best” alternatives from a tournament and have found applications in a wide range of areas. Previous work has shown that several well-known tournament solutions almost never rule out any alternative in large random tournaments. Nevertheless, all analytical results thus far have assumed a rigid probabilistic model, in which either a tournament is chosen uniformly at random, or there is a linear order of alternatives and the orientation of all edges in the tournament is chosen with the same probabilities according to the linear order. In this work, we consider a significantly more general model where the orientation of different edges can be chosen with different probabilities. We show that a number of common tournament solutions, including the top cycle and the uncovered set, are still unlikely to rule out any alternative under this model. This corresponds to natural graph-theoretic conditions such as irreducibility of the tournament. In addition, we provide tight asymptotic bounds on the boundary of the probability range for which the tournament solutions select all alternatives with high probability.

Suggested Citation

  • Christian Saile & Warut Suksompong, 2020. "Robust bounds on choosing from large tournaments," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 54(1), pages 87-110, January.
    • Handle: RePEc:spr:sochwe:v:54:y:2020:i:1:d:10.1007_s00355-019-01213-6
    DOI: 10.1007/s00355-019-01213-6
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s00355-019-01213-6
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s00355-019-01213-6?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Mark Fey, 2008. "Choosing from a large tournament," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 31(2), pages 301-309, August.
    2. Denis Bouyssou, 2004. "Monotonicity of ‘ranking by choosing’: A progress report," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 23(2), pages 249-273, October.
    3. Hudry, Olivier, 2009. "A survey on the complexity of tournament solutions," Mathematical Social Sciences, Elsevier, vol. 57(3), pages 292-303, May.
    4. Alex Scott & Mark Fey, 2012. "The minimal covering set in large tournaments," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 38(1), pages 1-9, January.
    5. Felix Brandt & Markus Brill & Hans Georg Seedig & Warut Suksompong, 2018. "On the structure of stable tournament solutions," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 65(2), pages 483-507, March.
    6. Kenneth J. Arrow & Herve Raynaud, 1986. "Social Choice and Multicriterion Decision-Making," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262511754, December.
    7. I. Good, 1971. "A note on condorcet sets," Public Choice, Springer, vol. 10(1), pages 97-101, March.
    8. Felix Brandt & Hans Georg Seedig, 2016. "On the Discriminative Power of Tournament Solutions," Operations Research Proceedings, in: Marco Lübbecke & Arie Koster & Peter Letmathe & Reinhard Madlener & Britta Peis & Grit Walther (ed.), Operations Research Proceedings 2014, edition 1, pages 53-58, Springer.
    9. Bell, Colin E, 1981. "A Random Voting Graph Almost Surely Has a Hamiltonian Cycle When the Number of Alternatives Is Large," Econometrica, Econometric Society, vol. 49(6), pages 1597-1603, November.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Costa, Matheus & Riella, Gil, 2022. "King-chicken choice correspondences," Mathematical Social Sciences, Elsevier, vol. 120(C), pages 113-118.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Felix Brandt & Markus Brill & Hans Georg Seedig & Warut Suksompong, 2018. "On the structure of stable tournament solutions," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 65(2), pages 483-507, March.
    2. Felix Brandt & Patrick Lederer, 2021. "Characterizing the Top Cycle via Strategyproofness," Papers 2108.04622, arXiv.org, revised Jun 2023.
    3. Felix Brandt & Markus Brill & Hans Georg Seedig & Warut Suksompong, 2020. "On the Structure of Stable Tournament Solutions," Papers 2004.01651, arXiv.org.
    4. Brandt, Felix & Lederer, Patrick, 2023. "Characterizing the top cycle via strategyproofness," Theoretical Economics, Econometric Society, vol. 18(2), May.
    5. Subochev, Andrey & Aleskerov, Fuad & Pislyakov, Vladimir, 2018. "Ranking journals using social choice theory methods: A novel approach in bibliometrics," Journal of Informetrics, Elsevier, vol. 12(2), pages 416-429.
    6. Brandt, Felix, 2011. "Minimal stable sets in tournaments," Journal of Economic Theory, Elsevier, vol. 146(4), pages 1481-1499, July.
    7. Berghammer, Rudolf & Rusinowska, Agnieszka & de Swart, Harrie, 2013. "Computing tournament solutions using relation algebra and RelView," European Journal of Operational Research, Elsevier, vol. 226(3), pages 636-645.
    8. William Gehrlein & Michel Breton & Dominique Lepelley, 2017. "The likelihood of a Condorcet winner in the logrolling setting," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 49(2), pages 315-327, August.
    9. Scott Moser & John W. Patty & Elizabeth Maggie Penn, 2009. "The Structure of Heresthetical Power," Journal of Theoretical Politics, , vol. 21(2), pages 139-159, April.
    10. Csató, László, 2013. "Rangsorolás páros összehasonlításokkal. Kiegészítések a felvételizői preferencia-sorrendek módszertanához [Paired comparisons ranking. A supplement to the methodology of application-based preferenc," Közgazdasági Szemle (Economic Review - monthly of the Hungarian Academy of Sciences), Közgazdasági Szemle Alapítvány (Economic Review Foundation), vol. 0(12), pages 1333-1353.
    11. Luigi Marengo & Davide Pirino & Simona Settepanella & Akimichi Takemura, 2012. "Decidability in complex social choices," LEM Papers Series 2012/12, Laboratory of Economics and Management (LEM), Sant'Anna School of Advanced Studies, Pisa, Italy.
    12. repec:hal:wpaper:hal-00756696 is not listed on IDEAS
    13. Felix Brandt & Markus Brill & Felix Fischer & Paul Harrenstein, 2014. "Minimal retentive sets in tournaments," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 42(3), pages 551-574, March.
    14. Subochev, Andrey & Zakhlebin, Igor, 2014. "Alternative versions of the global competitive industrial performance ranking constructed by methods from social choice theory," MPRA Paper 67462, University Library of Munich, Germany.
    15. Alex Scott & Mark Fey, 2012. "The minimal covering set in large tournaments," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 38(1), pages 1-9, January.
    16. Florian Brandl & Felix Brandt & Christian Stricker, 2022. "An analytical and experimental comparison of maximal lottery schemes," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 58(1), pages 5-38, January.
    17. Felix Brandt & Markus Brill & Paul Harrenstein, 2018. "Extending tournament solutions," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 51(2), pages 193-222, August.
    18. Aleksei Y. Kondratev & Vladimir V. Mazalov, 2020. "Tournament solutions based on cooperative game theory," International Journal of Game Theory, Springer;Game Theory Society, vol. 49(1), pages 119-145, March.
    19. Horan, Sean & Sprumont, Yves, 2016. "Welfare criteria from choice: An axiomatic analysis," Games and Economic Behavior, Elsevier, vol. 99(C), pages 56-70.
    20. Scott Moser, 2015. "Majority rule and tournament solutions," Chapters, in: Jac C. Heckelman & Nicholas R. Miller (ed.), Handbook of Social Choice and Voting, chapter 6, pages 83-101, Edward Elgar Publishing.
    21. László Csató, 2015. "A graph interpretation of the least squares ranking method," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 44(1), pages 51-69, January.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:sochwe:v:54:y:2020:i:1:d:10.1007_s00355-019-01213-6. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.