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

Fairness in Repeated Matching: A Maximin Perspective

Author

Listed:
  • Eugene Lim
  • Tzeh Yuan Neoh
  • Nicholas Teh

Abstract

We study a sequential decision-making model where a set of items is repeatedly matched to the same set of agents over multiple rounds. The objective is to determine a sequence of matchings that either maximizes the utility of the least advantaged agent at the end of all rounds (optimal) or at the end of every individual round (anytime optimal). We investigate the computational challenges associated with finding (anytime) optimal outcomes and demonstrate that these problems are generally computationally intractable. However, we provide approximation algorithms, fixed-parameter tractable algorithms, and identify several special cases whereby the problem(s) can be solved efficiently. Along the way, we also establish characterizations of Pareto-optimal/maximum matchings, which may be of independent interest to works in matching theory and house allocation.

Suggested Citation

  • Eugene Lim & Tzeh Yuan Neoh & Nicholas Teh, 2025. "Fairness in Repeated Matching: A Maximin Perspective," Papers 2510.04624, arXiv.org.
    • Handle: RePEc:arx:papers:2510.04624
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Wu, Qingyun & Roth, Alvin E., 2018. "The lattice of envy-free matchings," Games and Economic Behavior, Elsevier, vol. 109(C), pages 201-211.
    2. Soares, João & Lezama, Fernando & Faia, Ricardo & Limmer, Steffen & Dietrich, Manuel & Rodemann, Tobias & Ramos, Sergio & Vale, Zita, 2024. "Review on fairness in local energy systems," Applied Energy, Elsevier, vol. 374(C).
    3. Anna Bogomolnaia & Herve Moulin, 2004. "Random Matching Under Dichotomous Preferences," Econometrica, Econometric Society, vol. 72(1), pages 257-279, January.
    4. Thomson, William, 1983. "Problems of fair division and the Egalitarian solution," Journal of Economic Theory, Elsevier, vol. 31(2), pages 211-226, December.
    5. H. W. Lenstra, 1983. "Integer Programming with a Fixed Number of Variables," Mathematics of Operations Research, INFORMS, vol. 8(4), pages 538-548, November.
    6. Hylland, Aanund & Zeckhauser, Richard, 1979. "The Efficient Allocation of Individuals to Positions," Journal of Political Economy, University of Chicago Press, vol. 87(2), pages 293-314, April.
    7. Demko, Stephen & Hill, Theodore P., 1988. "Equitable distribution of indivisible objects," Mathematical Social Sciences, Elsevier, vol. 16(2), pages 145-158, October.
    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. Hougaard, Jens Leth & Moreno-Ternero, Juan D. & Østerdal, Lars Peter, 2014. "Assigning agents to a line," Games and Economic Behavior, Elsevier, vol. 87(C), pages 539-553.
    2. Ortega, Josué, 2020. "Multi-unit assignment under dichotomous preferences," Mathematical Social Sciences, Elsevier, vol. 103(C), pages 15-24.
    3. Chang, Hee-In & Chun, Youngsub, 2017. "Probabilistic assignment of indivisible objects when agents have the same preferences except the ordinal ranking of one object," Mathematical Social Sciences, Elsevier, vol. 90(C), pages 80-92.
    4. Aziz, Haris & Hougaard, Jens Leth & Moreno-Ternero, Juan D. & Østerdal, Lars Peter, 2017. "Computational aspects of assigning agents to a line," Mathematical Social Sciences, Elsevier, vol. 90(C), pages 93-99.
    5. YIlmaz, Özgür, 2011. "Kidney exchange: An egalitarian mechanism," Journal of Economic Theory, Elsevier, vol. 146(2), pages 592-618, March.
    6. Jugal Garg & Thorben Trobst & Vijay V. Vazirani, 2020. "One-Sided Matching Markets with Endowments: Equilibria and Algorithms," Papers 2009.10320, arXiv.org, revised Jul 2021.
    7. Haris Aziz & Florian Brandl, 2020. "The Vigilant Eating Rule: A General Approach for Probabilistic Economic Design with Constraints," Papers 2008.08991, arXiv.org, revised Jul 2021.
    8. Fuhito Kojima & M. Ünver, 2014. "The “Boston” school-choice mechanism: an axiomatic approach," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 55(3), pages 515-544, April.
    9. Eirinakis, Pavlos & Mourtos, Ioannis & Zampou, Eleni, 2022. "Random Serial Dictatorship for horizontal collaboration in logistics," Omega, Elsevier, vol. 111(C).
    10. Manjunath, Vikram, 2016. "Fractional matching markets," Games and Economic Behavior, Elsevier, vol. 100(C), pages 321-336.
    11. Thomson, William, 2011. "Chapter Twenty-One - Fair Allocation Rules," Handbook of Social Choice and Welfare, in: K. J. Arrow & A. K. Sen & K. Suzumura (ed.), Handbook of Social Choice and Welfare, edition 1, volume 2, chapter 21, pages 393-506, Elsevier.
    12. Fuhito Kojima & M. Utku Ünver, 2010. "The 'Boston' School-Choice Mechanism," Boston College Working Papers in Economics 729, Boston College Department of Economics, revised 08 Oct 2010.
    13. Katta, Akshay-Kumar & Sethuraman, Jay, 2006. "A solution to the random assignment problem on the full preference domain," Journal of Economic Theory, Elsevier, vol. 131(1), pages 231-250, November.
    14. Kondratev, Aleksei Y. & Nesterov, Alexander S., 2022. "Minimal envy and popular matchings," European Journal of Operational Research, Elsevier, vol. 296(3), pages 776-787.
    15. Xiang Han & Onur Kesten & M. Utku Ünver, 2021. "Blood Allocation with Replacement Donors: A Theory of Multi-unit Exchange with Compatibility-based Preferences," Boston College Working Papers in Economics 1038, Boston College Department of Economics.
    16. Aziz, Haris & Brandl, Florian, 2022. "The vigilant eating rule: A general approach for probabilistic economic design with constraints," Games and Economic Behavior, Elsevier, vol. 135(C), pages 168-187.
    17. Haris Aziz, 2018. "Mechanisms for House Allocation with Existing Tenants under Dichotomous Preferences," The Journal of Mechanism and Institution Design, Society for the Promotion of Mechanism and Institution Design, University of York, vol. 3(1), pages 97-110, December.
    18. Tayfun Sonmez, 2023. "Minimalist Market Design: A Framework for Economists with Policy Aspirations," Papers 2401.00307, arXiv.org, revised Oct 2025.
    19. Dinko Dimitrov & Ruud Hendrickx & Peter Borm, 2004. "Good and bad objects: the symmetric difference rule," Economics Bulletin, AccessEcon, vol. 4(11), pages 1-7.
    20. M. Köppe & M. Queyranne & C. T. Ryan, 2010. "Parametric Integer Programming Algorithm for Bilevel Mixed Integer Programs," Journal of Optimization Theory and Applications, Springer, vol. 146(1), pages 137-150, July.

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