Fairness in Repeated Matching: A Maximin Perspective
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912630659088384 |
|---|---|
| author | Lim, Eugene Neoh, Tzeh Yuan Teh, Nicholas |
| author_facet | Lim, Eugene Neoh, Tzeh Yuan Teh, Nicholas |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_04624 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fairness in Repeated Matching: A Maximin Perspective Lim, Eugene Neoh, Tzeh Yuan Teh, Nicholas Computer Science and Game Theory Artificial Intelligence Machine Learning Multiagent Systems Theoretical Economics 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. |
| title | Fairness in Repeated Matching: A Maximin Perspective |
| topic | Computer Science and Game Theory Artificial Intelligence Machine Learning Multiagent Systems Theoretical Economics |
| url | https://arxiv.org/abs/2510.04624 |