IDEAS home Printed from https://ideas.repec.org/a/eee/gamebe/v144y2024icp203-224.html
   My bibliography  Save this article

Impartial selection with additive guarantees via iterated deletion

Author

Listed:
  • Cembrano, Javier
  • Fischer, Felix
  • Hannon, David
  • Klimm, Max

Abstract

Impartial selection is the selection of an individual from a group based on nominations by other members of the group, in such a way that individuals cannot influence their own chance of selection. For this problem, we give a deterministic mechanism with an additive performance guarantee of O(n(1+κ)/2) in a setting with n individuals where each individual casts O(nκ) nominations, where κ∈[0,1]. This bound is O(n) for κ=0 and O(n) for κ=1. The latter is trivial, as even a mechanism that never selects provides an additive guarantee of n−1. We show, however, that it is also best possible: for every deterministic impartial mechanism there exists a situation in which some individual is nominated by every other individual and the mechanism either does not select or selects an individual not nominated by anyone.

Suggested Citation

  • Cembrano, Javier & Fischer, Felix & Hannon, David & Klimm, Max, 2024. "Impartial selection with additive guarantees via iterated deletion," Games and Economic Behavior, Elsevier, vol. 144(C), pages 203-224.
    • Handle: RePEc:eee:gamebe:v:144:y:2024:i:c:p:203-224
    DOI: 10.1016/j.geb.2024.01.008
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0899825624000095
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.geb.2024.01.008?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. Shohei Tamura & Shinji Ohseto, 2014. "Impartial nomination correspondences," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 43(1), pages 47-54, June.
    2. Mackenzie, Andrew, 2015. "Symmetry and impartial lotteries," Games and Economic Behavior, Elsevier, vol. 94(C), pages 15-28.
    3. Andrew Mackenzie, 2020. "An axiomatic analysis of the papal conclave," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 69(3), pages 713-743, April.
    4. Axel Niemeyer & Justus Preusser, 2023. "Simple Allocation with Correlated Types," CRC TR 224 Discussion Paper Series crctr224_2023_486, University of Bonn and University of Mannheim, Germany.
    5. de Clippel, Geoffroy & Moulin, Herve & Tideman, Nicolaus, 2008. "Impartial division of a dollar," Journal of Economic Theory, Elsevier, vol. 139(1), pages 176-191, March.
    6. Ron Holzman & Hervé Moulin, 2013. "Impartial Nominations for a Prize," Econometrica, Econometric Society, vol. 81(1), pages 173-196, January.
    Full references (including those not matched with items on IDEAS)

    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. Matthew Olckers & Toby Walsh, 2022. "Manipulation and Peer Mechanisms: A Survey," Papers 2210.01984, arXiv.org, revised May 2024.
    2. Javier Cembrano & Felix Fischer & Max Klimm, 2023. "Optimal Impartial Correspondences," Papers 2301.04544, arXiv.org.
    3. Javier Cembrano & Felix Fischer & Max Klimm, 2023. "Improved Bounds for Single-Nomination Impartial Selection," Papers 2305.09998, arXiv.org.
    4. Andrew Mackenzie, 2020. "An axiomatic analysis of the papal conclave," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 69(3), pages 713-743, April.
    5. Axel Niemeyer & Justus Preusser, 2023. "Simple Allocation with Correlated Types," CRC TR 224 Discussion Paper Series crctr224_2023_486, University of Bonn and University of Mannheim, Germany.
    6. Javier Cembrano & Svenja M. Griesbach & Maximilian J. Stahlberg, 2023. "Deterministic Impartial Selection with Weights," Papers 2310.14991, arXiv.org, revised Aug 2024.
    7. Tamura, Shohei, 2016. "Characterizing minimal impartial rules for awarding prizes," Games and Economic Behavior, Elsevier, vol. 95(C), pages 41-46.
    8. Christoph Carnehl & Marco Ottaviani & Justus Preusser, 2024. "Designing Scientific Grants," NBER Chapters, in: Entrepreneurship and Innovation Policy and the Economy, volume 4, National Bureau of Economic Research, Inc.
    9. Amorós, Pablo, 2022. "Implementation in dominant strategies of quota rules to choose one candidate," Economics Letters, Elsevier, vol. 216(C).
    10. Mackenzie, Andrew, 2015. "Symmetry and impartial lotteries," Games and Economic Behavior, Elsevier, vol. 94(C), pages 15-28.
    11. Amorós, Pablo, 2021. "Using supermajority rules to aggregate judgments of possibly biased experts," Economics Letters, Elsevier, vol. 207(C).
    12. Bloch, Francis & Dutta, Bhaskar & Dziubiński, Marcin, 2023. "Selecting a winner with external referees," Journal of Economic Theory, Elsevier, vol. 211(C).
    13. Amorós, Pablo, 2020. "Using sub-majoritarian rules to select the winner of a competition," Economics Letters, Elsevier, vol. 190(C).
    14. Mackenzie, Andrew, 2018. "A Game of the Throne of Saint Peter," Research Memorandum 015, Maastricht University, Graduate School of Business and Economics (GSBE).
    15. Pablo Amorós, 2020. "Aggregating experts’ opinions to select the winner of a competition," International Journal of Game Theory, Springer;Game Theory Society, vol. 49(3), pages 833-849, September.
    16. Edelman, Paul H. & Por, Attila, 2021. "A new axiomatic approach to the impartial nomination problem," Games and Economic Behavior, Elsevier, vol. 130(C), pages 443-451.
    17. Ruben Juarez & Kohei Nitta & Miguel Vargas, 2020. "Profit-sharing and efficient time allocation," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 70(3), pages 817-846, October.
    18. Shohei Tamura & Shinji Ohseto, 2014. "Impartial nomination correspondences," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 43(1), pages 47-54, June.
    19. Rene van den Brink & Agnieszka Rusinowska, "undated". "The Degree Ratio Ranking Method for Directed Networks," Tinbergen Institute Discussion Papers 19-026/II, Tinbergen Institute.
    20. Gantner, Anita & Horn, Kristian & Kerschbamer, Rudolf, 2019. "The role of communication in fair division with subjective claims," Journal of Economic Behavior & Organization, Elsevier, vol. 167(C), pages 72-89.

    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:eee:gamebe:v:144:y:2024:i:c:p:203-224. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/inca/622836 .

    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.