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

Two-Sided Fairness in Many-to-One Matching

Author

Listed:
  • Ayumi Igarashi
  • Naoyuki Kamiyama
  • Yasushi Kawase
  • Warut Suksompong
  • Hanna Sumita
  • Yu Yokoi

Abstract

We consider a classic many-to-one matching setting, where participants need to be assigned to teams based on the preferences of both sides. Unlike most of the matching literature, we aim to provide fairness not only to participants, but also to teams using concepts from the literature of fair division. We present a polynomial-time algorithm that computes an allocation satisfying team-justified envy-freeness up to one participant, participant-justified envy-freeness, balancedness, Pareto optimality, and group-strategyproofness for participants, even in the possible presence of ties. Our algorithm generalizes both the Gale-Shapley algorithm from two-sided matching as well as the round-robin algorithm from fair division. We also discuss how our algorithm can be extended to accommodate quotas and incomplete preferences.

Suggested Citation

  • Ayumi Igarashi & Naoyuki Kamiyama & Yasushi Kawase & Warut Suksompong & Hanna Sumita & Yu Yokoi, 2025. "Two-Sided Fairness in Many-to-One Matching," Papers 2509.24111, arXiv.org.
    • Handle: RePEc:arx:papers:2509.24111
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Varian, Hal R., 1974. "Equity, envy, and efficiency," Journal of Economic Theory, Elsevier, vol. 9(1), pages 63-91, September.
    2. Monique De Haan & Pieter A. Gautier & Hessel Oosterbeek & Bas van der Klaauw, 2023. "The Performance of School Assignment Mechanisms in Practice," Journal of Political Economy, University of Chicago Press, vol. 131(2), pages 388-455.
    3. Wu, Qingyun & Roth, Alvin E., 2018. "The lattice of envy-free matchings," Games and Economic Behavior, Elsevier, vol. 109(C), pages 201-211.
    4. Eric Budish, 2011. "The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes," Journal of Political Economy, University of Chicago Press, vol. 119(6), pages 1061-1103.
    5. Demange, Gabrielle & Gale, David, 1985. "The Strategy Structure of Two-sided Matching Markets," Econometrica, Econometric Society, vol. 53(4), pages 873-888, July.
    6. Hervé Moulin, 2019. "Fair Division in the Internet Age," Annual Review of Economics, Annual Reviews, vol. 11(1), pages 407-441, August.
    7. Haris Aziz & Rupert Freeman & Nisarg Shah & Rohit Vaish, 2024. "Best of Both Worlds: Ex Ante and Ex Post Fairness in Resource Allocation," Operations Research, INFORMS, vol. 72(4), pages 1674-1688, July.
    8. Naoyuki Kamiyama, 2014. "A New Approach to the Pareto Stable Matching Problem," Mathematics of Operations Research, INFORMS, vol. 39(3), pages 851-862, August.
    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. Th`anh Nguyen & Alexander Teytelboym & Shai Vardi, 2025. "Efficiency, Envy, and Incentives in Combinatorial Assignment," Papers 2509.13198, arXiv.org, revised Oct 2025.
    2. Fedor Sandomirskiy & Erel Segal-Halevi, 2022. "Efficient Fair Division with Minimal Sharing," Operations Research, INFORMS, vol. 70(3), pages 1762-1782, May.
    3. Hadi Hosseini & Zhiyi Huang & Ayumi Igarashi & Nisarg Shah, 2022. "Class Fairness in Online Matching," Papers 2203.03751, arXiv.org.
    4. Ioannis Caragiannis & Panagiotis Kanellopoulos & Maria Kyropoulou, 2025. "On Interim Envy-Free Allocation Lotteries," Mathematics of Operations Research, INFORMS, vol. 50(4), pages 3257-3282, November.
    5. Igarashi, Ayumi & Kawase, Yasushi & Suksompong, Warut & Sumita, Hanna, 2024. "Fair division with two-sided preferences," Games and Economic Behavior, Elsevier, vol. 147(C), pages 268-287.
    6. Bhaskar Ray Chaudhury & Jugal Garg & Peter McGlaughlin & Ruta Mehta, 2023. "A Complementary Pivot Algorithm for Competitive Allocation of a Mixed Manna," Mathematics of Operations Research, INFORMS, vol. 48(3), pages 1630-1656, August.
    7. Luofeng Liao & Christian Kroer, 2024. "Statistical Inference and A/B Testing in Fisher Markets and Paced Auctions," Papers 2406.15522, arXiv.org, revised Mar 2025.
    8. Bhaskar Ray Chaudhury & Jugal Garg & Kurt Mehlhorn & Ruta Mehta & Pranabendu Misra, 2024. "Improving Envy Freeness up to Any Good Guarantees Through Rainbow Cycle Number," Mathematics of Operations Research, INFORMS, vol. 49(4), pages 2323-2340, November.
    9. Anna Bogomolnaia & Hervé Moulin, 2023. "Guarantees in Fair Division: General or Monotone Preferences," Mathematics of Operations Research, INFORMS, vol. 48(1), pages 160-176, February.
    10. Ortega, Josué, 2020. "Multi-unit assignment under dichotomous preferences," Mathematical Social Sciences, Elsevier, vol. 103(C), pages 15-24.
    11. Shende, Priyanka & Purohit, Manish, 2023. "Strategy-proof and envy-free mechanisms for house allocation," Journal of Economic Theory, Elsevier, vol. 213(C).
    12. Sandomirskiy, Fedor & Ushchev, Philip, 2024. "The geometry of consumer preference aggregation," CEPR Discussion Papers 19100, Centre for Economic Policy Research.
    13. Georgios Amanatidis & Georgios Birmpas & Philip Lazos & Stefano Leonardi & Rebecca Reiffenhäuser, 2025. "Round-Robin Beyond Additive Agents: Existence and Fairness of Approximate Equilibria," Mathematics of Operations Research, INFORMS, vol. 50(4), pages 2717-2737, November.
    14. David Pérez-Castrillo & Marilda Sotomayor, 2023. "Constrained-optimal tradewise-stable outcomes in the one-sided assignment game: a solution concept weaker than the core," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 76(3), pages 963-994, October.
    15. Cole, Richard & Tao, Yixin, 2021. "On the existence of Pareto Efficient and envy-free allocations," Journal of Economic Theory, Elsevier, vol. 193(C).
    16. Hadi Hosseini, 2023. "The Fairness Fair: Bringing Human Perception into Collective Decision-Making," Papers 2312.14402, arXiv.org.
    17. Tierney, Ryan, 2019. "The problem of multiple commons: A market design approach," Games and Economic Behavior, Elsevier, vol. 114(C), pages 1-27.
    18. Mackenzie, Andrew & Komornik, Vilmos, 2023. "Fairly taking turns," Games and Economic Behavior, Elsevier, vol. 142(C), pages 743-764.
    19. Anna Bogomolnaia & Herv'e Moulin, 2024. "Tight Guarantees in the Commons," Papers 2406.14198, arXiv.org, revised May 2026.
    20. Priyanka Shende & Manish Purohit, 2020. "Strategy-proof and Envy-free Mechanisms for House Allocation," Papers 2010.16384, arXiv.org.

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