IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2602.14816.html

Majoritarian Assignment Rules

Author

Listed:
  • Felix Brandt
  • Haoyuan Chen
  • Chris Dong
  • Patrick Lederer
  • Alexander Schlenga

Abstract

A central problem in multiagent systems is the fair assignment of objects to agents. In this paper, we initiate the analysis of classic majoritarian social choice functions in assignment. Exploiting the special structure of the assignment domain, we show a number of surprising results with no counterparts in general social choice. In particular, we establish a near one-to-one correspondence between preference profiles and majority graphs. This correspondence implies that key properties of assignments -- such as Pareto-optimality, least unpopularity, and mixed popularity -- can be determined solely by the associated majority graph. We further show that all Pareto-optimal assignments are semi-popular and belong to the top cycle. Elements of the top cycle can thus easily be found via serial dictatorships. Our main result is a complete characterization of the top cycle, which implies the top cycle can only consist of one, two, all but two, all but one, or all assignments. By contrast, we find that the uncovered set contains only very few assignments.

Suggested Citation

  • Felix Brandt & Haoyuan Chen & Chris Dong & Patrick Lederer & Alexander Schlenga, 2026. "Majoritarian Assignment Rules," Papers 2602.14816, arXiv.org.
    • Handle: RePEc:arx:papers:2602.14816
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Shapley, Lloyd & Scarf, Herbert, 1974. "On cores and indivisibility," Journal of Mathematical Economics, Elsevier, vol. 1(1), pages 23-37, March.
    2. Niclas Boehmer & Markus Brill & Ulrike Schmidt-Kraepelin, 2025. "Proportional representation in matching markets: selecting multiple matchings under dichotomous preferences," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 64(1), pages 179-220, February.
    3. Bhaskar Dutta & Jean-Francois Laslier, 1999. "Comparison functions and choice correspondences," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 16(4), pages 513-532.
    4. Bordes, Georges, 1983. "On the possibility of reasonable consistent majoritarian choice: Some positive results," Journal of Economic Theory, Elsevier, vol. 31(1), pages 122-132, October.
    5. Atila Abdulkadiroglu & Tayfun Sonmez, 1998. "Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems," Econometrica, Econometric Society, vol. 66(3), pages 689-702, May.
    6. Felix Brandt & Patrick Lederer, 2021. "Characterizing the Top Cycle via Strategyproofness," Papers 2108.04622, arXiv.org, revised Jun 2023.
    7. Eric McDermid & Robert W. Irving, 2011. "Popular matchings: structure and algorithms," Journal of Combinatorial Optimization, Springer, vol. 22(3), pages 339-358, October.
    8. 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.
    9. I. Good, 1971. "A note on condorcet sets," Public Choice, Springer, vol. 10(1), pages 97-101, March.
    10. Georges Bordes & Michel Le Breton & Maurice Salles, 1992. "Gillies and Miller's Subrelations of a Relation over an Infinite Set of Alternatives: General Results and Applications to Voting Games," Mathematics of Operations Research, INFORMS, vol. 17(3), pages 509-518, August.
    11. Smith, John H, 1973. "Aggregation of Preferences with Variable Electorate," Econometrica, Econometric Society, vol. 41(6), pages 1027-1041, November.
    12. Brandt, Felix & Fischer, Felix, 2008. "Computing the minimal covering set," Mathematical Social Sciences, Elsevier, vol. 56(2), pages 254-268, September.
    13. Brandt, Felix & Lederer, Patrick, 2023. "Characterizing the top cycle via strategyproofness," Theoretical Economics, Econometric Society, vol. 18(2), May.
    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. Felix Brandt & Chris Dong, 2022. "On Locally Rationalizable Social Choice Functions," Papers 2204.05062, arXiv.org, revised Mar 2024.
    2. Felix Brandt, 2015. "Set-monotonicity implies Kelly-strategyproofness," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 45(4), pages 793-804, December.
    3. John Duggan, 2011. "Uncovered Sets," Wallis Working Papers WP63, University of Rochester - Wallis Institute of Political Economy.
    4. John Duggan, 2013. "Uncovered sets," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 41(3), pages 489-535, September.
    5. Bettina Klaus & David F. Manlove & Francesca Rossi, 2014. "Matching under Preferences," Cahiers de Recherches Economiques du Département d'économie 14.07, Université de Lausanne, Faculté des HEC, Département d’économie.
    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. repec:hal:pseose:hal-00756696 is not listed on IDEAS
    9. Wesley H. Holliday & Eric Pacuit, 2023. "Split Cycle: a new Condorcet-consistent voting method independent of clones and immune to spoilers," Public Choice, Springer, vol. 197(1), pages 1-62, October.
    10. repec:hal:wpaper:hal-00756696 is not listed on IDEAS
    11. Felix Brandt & Christian Geist & Paul Harrenstein, 2016. "A note on the McKelvey uncovered set and Pareto optimality," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 46(1), pages 81-91, January.
    12. Martin, Mathieu & Merlin, Vincent, 2002. "The stability set as a social choice correspondence," Mathematical Social Sciences, Elsevier, vol. 44(1), pages 91-113, September.
    13. Raúl Pérez-Fernández & Bernard De Baets, 2018. "The supercovering relation, the pairwise winner, and more missing links between Borda and Condorcet," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 50(2), pages 329-352, February.
    14. Daniel Carroll & Jim Dolmas & Eric Young, 2021. "The Politics of Flat Taxes," Review of Economic Dynamics, Elsevier for the Society for Economic Dynamics, vol. 39, pages 174-201, January.
    15. Felix Brandt & Patrick Lederer & René Romen, 2024. "Relaxed notions of Condorcet-consistency and efficiency for strategyproof social decision schemes," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 63(1), pages 19-55, August.
    16. Zhiwei Cui & Yan-An Hwang, 2017. "House exchange and residential segregation in networks," International Journal of Game Theory, Springer;Game Theory Society, vol. 46(1), pages 125-147, March.
    17. Brandt, Felix & Saile, Christian & Stricker, Christian, 2022. "Strategyproof social choice when preferences and outcomes may contain ties," Journal of Economic Theory, Elsevier, vol. 202(C).
    18. Takamiya, Koji, 2001. "Coalition strategy-proofness and monotonicity in Shapley-Scarf housing markets," Mathematical Social Sciences, Elsevier, vol. 41(2), pages 201-213, March.
    19. Ivan Balbuzanov & Maciej H. Kotowski, 2019. "Endowments, Exclusion, and Exchange," Econometrica, Econometric Society, vol. 87(5), pages 1663-1692, September.
    20. Holliday, Wesley H., 2024. "An impossibility theorem concerning positive involvement in voting," Economics Letters, Elsevier, vol. 236(C).
    21. Merlin, Vincent & Valognes, Fabrice, 2004. "The impact of indifferent voters on the likelihood of some voting paradoxes," Mathematical Social Sciences, Elsevier, vol. 48(3), pages 343-361, November.
    22. Ishida, Wataru & Park, Changwoo, 2026. "Group incentive-compatible allocation of discrete resources when ownership is partitioned," Games and Economic Behavior, Elsevier, vol. 155(C), pages 287-309.

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    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:2602.14816. 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.