IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2301.04544.html
   My bibliography  Save this paper

Optimal Impartial Correspondences

Author

Listed:
  • Javier Cembrano
  • Felix Fischer
  • Max Klimm

Abstract

We study mechanisms that select a subset of the vertex set of a directed graph in order to maximize the minimum indegree of any selected vertex, subject to an impartiality constraint that the selection of a particular vertex is independent of the outgoing edges of that vertex. For graphs with maximum outdegree $d$, we give a mechanism that selects at most $d+1$ vertices and only selects vertices whose indegree is at least the maximum indegree in the graph minus one. We then show that this is best possible in the sense that no impartial mechanism can only select vertices with maximum degree, even without any restriction on the number of selected vertices. We finally obtain the following trade-off between the maximum number of vertices selected and the minimum indegree of any selected vertex: when selecting at most~$k$ vertices out of $n$, it is possible to only select vertices whose indegree is at least the maximum indegree minus $\lfloor(n-2)/(k-1)\rfloor+1$.

Suggested Citation

  • Javier Cembrano & Felix Fischer & Max Klimm, 2023. "Optimal Impartial Correspondences," Papers 2301.04544, arXiv.org.
    • Handle: RePEc:arx:papers:2301.04544
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2301.04544
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Tamura, Shohei, 2016. "Characterizing minimal impartial rules for awarding prizes," Games and Economic Behavior, Elsevier, vol. 95(C), pages 41-46.
    2. 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.
    3. Mackenzie, Andrew, 2015. "Symmetry and impartial lotteries," Games and Economic Behavior, Elsevier, vol. 94(C), pages 15-28.
    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. 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.
    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. Javier Cembrano & Felix Fischer & Max Klimm, 2023. "Improved Bounds for Single-Nomination Impartial Selection," Papers 2305.09998, arXiv.org.
    2. Matthew Olckers & Toby Walsh, 2022. "Manipulation and Peer Mechanisms: A Survey," Papers 2210.01984, arXiv.org, revised Nov 2023.
    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. Amorós, Pablo, 2022. "Implementation in dominant strategies of quota rules to choose one candidate," Economics Letters, Elsevier, vol. 216(C).
    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.
    7. Amorós, Pablo, 2021. "Using supermajority rules to aggregate judgments of possibly biased experts," Economics Letters, Elsevier, vol. 207(C).
    8. Tamura, Shohei, 2016. "Characterizing minimal impartial rules for awarding prizes," Games and Economic Behavior, Elsevier, vol. 95(C), pages 41-46.
    9. Mackenzie, Andrew, 2018. "A Game of the Throne of Saint Peter," Research Memorandum 015, Maastricht University, Graduate School of Business and Economics (GSBE).
    10. Mackenzie, Andrew, 2015. "Symmetry and impartial lotteries," Games and Economic Behavior, Elsevier, vol. 94(C), pages 15-28.
    11. Bloch, Francis & Dutta, Bhaskar & Dziubiński, Marcin, 2023. "Selecting a winner with external referees," Journal of Economic Theory, Elsevier, vol. 211(C).
    12. Amorós, Pablo, 2020. "Using sub-majoritarian rules to select the winner of a competition," Economics Letters, Elsevier, vol. 190(C).
    13. 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.
    14. 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.
    15. 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.
    16. 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.
    17. Rene van den Brink & Agnieszka Rusinowska, "undated". "The Degree Ratio Ranking Method for Directed Networks," Tinbergen Institute Discussion Papers 19-026/II, Tinbergen Institute.
    18. 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.
    19. Gabrielle Demange, 2012. "On the influence of a ranking system," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 39(2), pages 431-455, July.
    20. ,, 2014. "A ranking method based on handicaps," Theoretical Economics, Econometric Society, vol. 9(3), September.

    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:arx:papers:2301.04544. 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: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    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.