Asymptotic Existence of Class Envy-free Matchings
Tomohiko Yokoyama, Ayumi Igarashi · 2025
Read Asymptotic Existence of Class Envy-free Matchings by Tomohiko Yokoyama, Ayumi Igarashi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-14371.txt.
Introduction
Tomohiko Yokoyama and Ayumi Igarashi study fair division among groups in a matching market, in a 2025 paper. Agents are split into classes, such as age or ethnic groups, and each class deserves fair treatment when items are handed out. A matching is class envy-free when no class would rather have another class's total haul, judged by its own best use of those items. In the worst case such matchings need not exist unless items are wasted.
The pair instead study a realistic model where utilities are drawn at random from a distribution. Their main result: as the number of agents grows large, a simple round-robin procedure yields a class envy-free matching with high probability. The finding supports fair allocation schemes for housing and medical resources, where worst-case thinking can be paralyzing but typical cases behave well.
Catalog record
| CREATOR | Tomohiko Yokoyama, Ayumi Igarashi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 125 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-14371
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Asymptotic Existence of Class Envy-free Matchings Tomohiko Yokoyama, Ayumi Igarashi Abstract We consider a one-sided matching problem where agents who are partitioned into disjoint classes and each class must receive fair treatment in a desired matching. This model, proposed by Benabbou et al. [ 10 ] , aims to address various real-life scenarios, such as the allocation of public housing and medical resources across different ethnic, age, and other demographic groups. Our focus is on achieving class envy-free matchings, where each class receives a total utility at least as large as the maximum value of a matching they would achieve from the items matched to another class. While class envy-freeness for worst-case utilities is unattainable without leaving some valuable items unmatched, such extreme cases may rarely occur in practice. To analyze the existence of a class envy-free matching in practice, we study a distributional model where agents’ utilities for items are drawn from a probability distribution. Our main result establishes the asymptotic existence of a desired matching, showing that a round-robin algorithm produces a class envy-free matching as the number of agents approaches infinity. 1 Introduction One-sided matching is a fundamental problem that forms the economic foundation of numerous practical applications, spanning from kidney exchange [ 41 ] , assigning drivers to customers [ 9 ] , to house allocation [ 1 , 23 , 51 ] . An instance of the one-sided matching problem consists of a set of agents, a set of indivisible items, and preferences of the agents over the items. The goal is to find an assignment of items to agents while ensuring desirable normative properties. In particular, guaranteeing fairness is of paramount importance in scenarios such as allocating tasks to workers or providing social housing to residents. A substantial body of the literature is dedicated to ensuring fairness among individuals, focusing on concepts such as envy-freeness [ 12 ] . Envy-freeness ensures that no agent prefers another agent’s allocated item to their own. On the other hand, when addressing various real-life resource allocation problems, it becomes increasingly crucial to consider fairness requirements among different classes of agents, particularly when implementing solutions in large-scale systems. For instance, consider the allocation of scarce medical resources to different regions in a country. Another motivating example involves student placement in public schools among different ethnic groups and social housing allocation among different income groups. To gain public acceptance, the social planner must ensure an equitable allocation of resources across various regional groups or classes. The scenarios we consider are effectively captured by a model proposed by Benabbou et al. [ 10 ] . This model consists of m items and n agents, divided into k disjoint classes, with each agent allocated at most one item. A key feature of this framework is the use of assignment valuations to evaluate envy among classes. Assignment valuations quantify the potential value a class could derive from the set of items allocated to another class, determined by the optimal matching between the items and the members of the class. By adapting fairness notions from fair division literature into the one-sided matching problem, Benabbou et al. [ 10 ] introduced the notion of class envy-freeness [ 10 , 22 ] , which requires that no class prefers the set of items assigned to any other class over its own bundle, in the sense of assignment valuations. Unfortunately, a class envy-free matching is not guaranteed to exist without wasting any items. Consider a simple example with one item and two single-agent classes, both valuing the item. In any nonempty matching, one class receives nothing whereas the other class receives one item. However, this strong conflict between fairness and efficiency does not preclude the existence of practical solutions that balance fairness and efficiency. The question then becomes: can we achieve a fair and efficient matching in practical scenarios? In the context of fair division, related works have examined the existence of envy-free allocations in probabilistic settings, where agents’ utilities for items are modeled using probability distributions [ 5 , 8 , 7 , 11 , 16 , 28 , 33 , 34 , 35 , 43 ] . These approaches of asymptotic analysis are not limited to the fair division but have been widely studied in broader economic models; examples include one-to-one house allocation [ 20 , 35 ] , two-sided matchings [ 26 , 27 , 6 ] , and voting theory [ 40 , 49 ] . These studies provide insights into the behavior of mechanisms in large-scale scenarios, and offer both theoretical foundations and practical implications for real-world applications. Our contributions. In this paper, to investigate the asymptotic existence of a matching that is efficient and fair among classes on average, we introduce a distributional model where each agent’s utilities are drawn from a probability distribution. We first prove that when m increases quadratically with respect to n , a welfare-maximizing mechanism, which returns a maximum-weight matching between agents and items, is asymptotically class envy-free. Importantly, this matching is also efficient since it maximizes the total utility of the agents. While this result provides asymptotic fairness and efficiency guarantees, it may not be satisfactory in all scenarios. Specifically, the mechanism may fail to treat classes fairly for worst-case inputs; for example, the welfare-maximizing mechanism could allocate all items to one class if the members of that class assign large values to each item. To address this limitation, we integrate the round-robin algorithm from fair division into our framework. Specifically, in each round of the algorithm, each class selects an item with the highest marginal utility among the remaining items, creating a maximum-weight matching. Our main result establishes that this algorithm asymptotically yields a class envy-free matching as the number of agents approaches infinity, contingent upon milder assumptions regarding the number and sizes of classes. Furthermore, based on the recent result of [ 4 ] , the round-robin algorithm is known to produce a matching that satisfies an approximation of class envy-freeness up to one item (class EF1) for every input. We also prove that it achieves non-wastefulness , satisfying the property that no item can be reallocated to increase one class’s valuation without decreasing another’s. While our algorithm shares similarities with the round-robin algorithm designed for fair division instances with additive agents, the non-additivity of valuations introduces notable distinctions in our analysis compared to the additive setting [ 35 ] . This leads to unique technical challenges. Specifically, analyzing the behavior of the round-robin algorithm becomes complex because the set of items available at each round depends on the selections made in prior rounds. In the case of additive valuations, Manurangsi and Suksompong [ 35 ] utilized a key property: envy between any pair of agents, based on the output of the round-robin algorithm, can be decomposed into the maximum value of an item obtained by another agent and the differences in value between the items each agent received and those received by another agent in consecutive rounds. Exploiting this fact, they showed that these differences can “catch up to” the maximum single-item value when there are sufficiently many items. However, achieving such a decomposition becomes challenging for assignment valuations due to the