Abstract:Online bipartite matching, where agents are known in advance but items arrive sequentially and must be irrevocably assigned, is fundamental to problems ranging from ride-sharing to online advertising. When agents belong to classes such as demographic groups or geographic regions, fairness demands equitable treatment across these groups. Recent work introduced class envy-freeness (CEF), a natural extension of the classical fair division notion: an algorithm is $\alpha$-CEF if each class receives value at least an $\alpha$ fraction of what it could extract from any other class's bundle. However, all known algorithms achieving constant-factor CEF guarantees attain utilitarian social welfare (total matching value) of at most $\frac{1}{2}$ times the optimum, far below the $1-\frac{1}{e} \approx 0.632$ achievable without fairness constraints.
We resolve the open question of whether fairness necessitates this efficiency loss, by introducing threshold-based algorithms parameterized by $\gamma \in [0,1]$ that equalize allocations across classes until threshold $\gamma$, then maximize efficiency. For divisible matching, this yields simultaneous $(1-e^{-\gamma})$-CEF and $(1 - \frac{e^{\gamma-1}}{\gamma+1})$-USW guarantees; for indivisible matching, $\frac{\gamma}{2}$-CEF with the same USW. Setting $\gamma > 0$ produces the first algorithms beating $\frac{1}{2}$-USW while maintaining constant CEF. We complement this with a novel upper bound construction, proving no non-wasteful $\alpha$-CEF algorithm can exceed $\frac{1 +\alpha - e^{\alpha-1}}{1+\alpha}$-USW and correcting prior bounds that were vacuous for $\alpha < 0.58$. Our upper bound nearly matches our algorithms' performance, giving the first substantive characterization of the price of fairness in online class matching.
| Subjects: | Computer Science and Game Theory (cs.GT); Data Structures and Algorithms (cs.DS) |
| Cite as: | arXiv:2605.23408 [cs.GT] |
| (or arXiv:2605.23408v1 [cs.GT] for this version) | |
| https://doi.org/10.48550/arXiv.2605.23408 arXiv-issued DOI via DataCite (pending registration) |
From: Sander Borst [view email]
[v1]
Fri, 22 May 2026 09:17:48 UTC (32 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。