Beyond the Half-Approximation: Fair and Efficient Online Class Matching

Max Springer; Sander Borst

arxiv: 2605.23408 · v1 · pith:BVPBA26Qnew · submitted 2026-05-22 · 💻 cs.GT · cs.DS

Beyond the Half-Approximation: Fair and Efficient Online Class Matching

Sander Borst , Max Springer This is my paper

Pith reviewed 2026-05-25 02:56 UTC · model grok-4.3

classification 💻 cs.GT cs.DS

keywords online bipartite matchingclass envy-freenessutilitarian social welfareprice of fairnessthreshold algorithmsfairness-efficiency tradeoffnon-wasteful algorithms

0 comments

The pith

Threshold algorithms achieve over half the optimal welfare while guaranteeing constant class envy-freeness in online class matching.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that constant class envy-freeness in online bipartite matching with grouped agents does not require sacrificing welfare down to half the optimum. It constructs threshold-based algorithms that first equalize class bundles up to a tunable level γ and then maximize total value. For positive γ these algorithms deliver the first constant CEF guarantees paired with strictly better than 1/2 utilitarian social welfare. A new upper-bound construction shows that no non-wasteful α-CEF algorithm can exceed a specific welfare ratio that nearly matches the algorithmic performance, yielding the first quantitative characterization of the price of fairness for this setting.

Core claim

Setting γ > 0 produces the first algorithms beating 1/2-USW while maintaining constant CEF. We complement this with a novel upper bound construction, proving no non-wasteful α-CEF algorithm can exceed (1 + α - e^{α-1})/(1+α)-USW and correcting prior bounds that were vacuous for α < 0.58. Our upper bound nearly matches our algorithms' performance, giving the first substantive characterization of the price of fairness in online class matching.

What carries the argument

Threshold-based algorithms parameterized by γ ∈ [0,1] that equalize allocations across classes until threshold γ, then maximize efficiency.

If this is right

For γ > 0 the algorithms simultaneously achieve constant CEF and USW strictly above 1/2.
In the divisible case the guarantees are exactly (1 - e^{-γ})-CEF and (1 - e^{γ-1}/(γ + 1))-USW.
The upper bound corrects earlier expressions that gave no information for α < 0.58.
The algorithmic and upper-bound curves lie close together across the range of α, characterizing the tradeoff.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If algorithms are allowed to waste assignments, the upper bound no longer applies and higher welfare may be attainable under the same CEF constraint.
The same threshold technique may extend to other online fair-division settings such as online cake cutting or repeated matching with group fairness.
Empirical tests on ride-sharing or ad-allocation logs could reveal whether the predicted welfare gains appear under realistic arrival distributions.

Load-bearing premise

The upper bound applies specifically to non-wasteful α-CEF algorithms; if waste is permitted the claimed limit need not hold.

What would settle it

A concrete non-wasteful α-CEF algorithm on some instance family that achieves strictly higher USW than (1 + α - e^{α-1})/(1+α) would falsify the upper bound.

Figures

Figures reproduced from arXiv: 2605.23408 by Max Springer, Sander Borst.

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Threshold algorithms beat the 1/2-USW barrier with constant CEF and pair it with a nearly matching upper bound, but only for non-wasteful cases.

read the letter

The paper's main contribution is a family of threshold algorithms that achieve better than 1/2 USW while maintaining constant CEF in online class matching. They equalize allocations across classes up to a threshold gamma, then switch to maximizing efficiency. For divisible items this yields (1-e^{-gamma})-CEF and (1 - e^{gamma-1}/(gamma+1))-USW; for indivisible items it is gamma/2-CEF with the same welfare guarantee. Setting gamma above zero gives the first explicit improvement over the prior 1/2-USW ceiling with constant fairness. They also supply a new upper bound showing that no non-wasteful alpha-CEF algorithm can exceed (1+alpha - e^{alpha-1})/(1+alpha) USW, which fixes earlier bounds that were empty for small alpha and comes close to the algorithmic performance. This is the first substantive price-of-fairness characterization in the model. The work is clean on the algorithmic side and directly addresses the stated open question. The clearest limitation is that the upper bound applies only to non-wasteful algorithms, yet the paper does not establish that the new threshold procedures are non-wasteful. If waste is permitted the bound does not hold and the near-tightness claim does not cover the general setting. The abstract supplies no proofs or verification details, so soundness cannot be checked from what is visible here. This is aimed at researchers in online algorithms and fair division who care about simultaneous efficiency and class fairness. A reader working on price-of-fairness bounds or online matching with group constraints would find the concrete guarantees and the corrected upper bound useful. The paper deserves a serious referee to verify the proofs and clarify whether the non-wasteful restriction can be removed or whether the algorithms satisfy it.

Referee Report

1 major / 0 minor

Summary. The paper claims to resolve the open question of whether constant-factor class envy-freeness (CEF) in online bipartite matching with classes necessarily forces utilitarian social welfare (USW) to at most 1/2. It introduces threshold-based algorithms parameterized by γ ∈ [0,1] that equalize allocations across classes up to threshold γ then maximize efficiency. For divisible matchings these yield simultaneous (1-e^{-γ})-CEF and (1 - e^{γ-1}/(γ+1))-USW; for indivisible matchings, γ/2-CEF with the same USW. Setting γ > 0 beats the prior 1/2-USW barrier while retaining constant CEF. The paper complements this with an upper-bound construction showing that no non-wasteful α-CEF algorithm can exceed (1 + α - e^{α-1})/(1+α)-USW, correcting earlier bounds that were vacuous for α < 0.58, and claims the bound nearly matches the algorithmic guarantees.

Significance. If the results hold, the work supplies the first algorithms that simultaneously achieve constant CEF and strictly better than 1/2-USW, together with the first near-tight characterization of the price of fairness in this setting. Explicit credit is due for the clean γ-parameterization that makes the efficiency-fairness tradeoff transparent, for correcting the vacuous prior upper bounds, and for restricting the upper bound to the non-wasteful case where it is meaningful.

major comments (1)

[Abstract (upper-bound paragraph)] Abstract (upper-bound paragraph): the claimed 'substantive characterization of the price of fairness' rests on the upper bound applying to the presented algorithms, yet the manuscript never verifies that the threshold-based algorithms are non-wasteful. The bound is explicitly qualified to non-wasteful α-CEF algorithms; if the algorithms permit waste, the near-matching claim and the characterization do not go through.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for identifying this gap in the presentation of the upper-bound characterization. We address the concern directly below.

read point-by-point responses

Referee: Abstract (upper-bound paragraph): the claimed 'substantive characterization of the price of fairness' rests on the upper bound applying to the presented algorithms, yet the manuscript never verifies that the threshold-based algorithms are non-wasteful. The bound is explicitly qualified to non-wasteful α-CEF algorithms; if the algorithms permit waste, the near-matching claim and the characterization do not go through.

Authors: We agree that the near-matching claim requires the threshold-based algorithms to be non-wasteful. The algorithms first equalize class allocations up to threshold γ (assigning to the current minimum-value class whenever possible) and then switch to welfare-maximizing assignment. This structure ensures that an item is left unassigned only when every class has already reached its threshold or when assigning it would violate the irrevocable online constraint; hence no beneficial assignment is wasted. We will add a short lemma (for both divisible and indivisible settings) formally proving non-wastefulness, after which the upper bound applies directly and the characterization holds. revision: yes

Circularity Check

0 steps flagged

No significant circularity; upper bound and algorithm guarantees independently derived

full rationale

The paper introduces parameterized threshold algorithms and separately proves their CEF/USW guarantees via direct analysis. It then presents an independent upper-bound construction showing no non-wasteful α-CEF algorithm exceeds the stated USW expression, correcting prior vacuous bounds. No quoted step reduces a prediction to a fitted input by construction, invokes a self-citation as load-bearing uniqueness, or renames a known result. The non-wasteful qualifier on the upper bound is an explicit scope limitation rather than a definitional collapse. The derivation chain remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

1 free parameters · 2 axioms · 0 invented entities

Based solely on abstract; limited visibility into full set of assumptions or derivations.

free parameters (1)

gamma
Tunable parameter in [0,1] that trades off CEF level against USW; chosen by algorithm designer rather than fitted to data.

axioms (2)

domain assumption Agents known in advance; items arrive sequentially and must be irrevocably assigned.
Core model of online bipartite matching stated in abstract.
domain assumption Class envy-freeness and utilitarian social welfare defined via alpha-fraction and total value comparisons.
Fairness and efficiency metrics introduced in abstract as extensions of prior notions.

pith-pipeline@v0.9.0 · 5872 in / 1370 out tokens · 36101 ms · 2026-05-25T02:56:00.036356+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages · 1 internal anchor

[1]

Online Fair Division: analysing a Food Bank problem

Martin Aleksandrov, Haris Aziz, Serge Gaspers, and Toby Walsh. Online fair division: Analysing a food bank problem.arXiv preprint arXiv:1502.07571, 2015

work page internal anchor Pith review Pith/arXiv arXiv 2015
[2]

How to make envy vanish over time

Gerdus Benade, Aleksandr M Kazachkov, Ariel D Procaccia, and Christos-Alexandros Psomas. How to make envy vanish over time. InProceedings of the 2018 ACM Conference on Economics and Computation, pages 593–610, 2018

work page 2018
[3]

Multiway Online Correlated Selection

Guy Blanc and Moses Charikar. Multiway Online Correlated Selection. In2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 1277–1284, 2022

work page 2022
[4]

The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes

Eric Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 119(6):1061–1103, 2011

work page 2011
[5]

The unreasonable fairness of maximum nash welfare.ACM Transactions on Economics and Computation (TEAC), 7(3):1–32, 2019

Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum nash welfare.ACM Transactions on Economics and Computation (TEAC), 7(3):1–32, 2019

work page 2019
[6]

Consensus of subjective probabilities: The pari-mutuel method.The Annals of Mathematical Statistics, 30(1):165–168, 1959

Edmund Eisenberg and David Gale. Consensus of subjective probabilities: The pari-mutuel method.The Annals of Mathematical Statistics, 30(1):165–168, 1959. 13

work page 1959
[7]

Edge-Weighted Online Bipartite Matching.Journal of the ACM, 69(6):1–35, 2022

Matthew Fahrbach, Zhiyi Huang, Runzhou Tao, and Morteza Zadimoghaddam. Edge-Weighted Online Bipartite Matching.Journal of the ACM, 69(6):1–35, 2022

work page 2022
[8]

Online ad assignment with free disposal

Jon Feldman, Nitish Korula, Vahab Mirrokni, Shanmugavelayutham Muthukrishnan, and Martin Pál. Online ad assignment with free disposal. InInternational workshop on internet and network economics, pages 374–385. Springer, 2009

work page 2009
[9]

Online Matching with General Arrivals

Buddhima Gamlath, Michael Kapralov, Andreas Maggiori, Ola Svensson, and David Wajc. Online Matching with General Arrivals. In2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 26–37, Baltimore, MD, USA, November 2019. IEEE

work page 2019
[10]

An improved approximation algorithm for maximin shares

Jugal Garg and Setareh Taki. An improved approximation algorithm for maximin shares. InProceedings of the 21st ACM Conference on Economics and Computation, pages 379–380, 2020

work page 2020
[11]

Fair allocation of indivisible goods: Improvements and generalizations

Mohammad Ghodsi, MohammadTaghi HajiAghayi, Masoud Seddighin, Saeed Seddighin, and Hadi Yami. Fair allocation of indivisible goods: Improvements and generalizations. InProceedings of the 2018 ACM Conference on Economics and Computation, pages 539–556, 2018

work page 2018
[12]

Online nash social welfare via promised utilities.arXiv e-prints, pages arXiv–2008, 2020

Artur Gorokh, Siddhartha Banerjee, Billy Jin, and Vasilis Gkatzelis. Online nash social welfare via promised utilities.arXiv e-prints, pages arXiv–2008, 2020

work page 2008
[13]

Fairness and Efficiency in Online Class Matching, October 2023

MohammadTaghi Hajiaghayi, Shayan Chashm Jahan, Mohammad Sharifi, Suho Shin, and Max Springer. Fairness and Efficiency in Online Class Matching, October 2023

work page 2023
[14]

Class fairness in online matching.Artificial Intelligence, 335:104177, October 2024

Hadi Hosseini, Zhiyi Huang, Ayumi Igarashi, and Nisarg Shah. Class fairness in online matching.Artificial Intelligence, 335:104177, October 2024

work page 2024
[15]

Guaranteeing maximin shares: Some agents left behind.arXiv preprint arXiv:2105.09383, 2021

Hadi Hosseini and Andrew Searns. Guaranteeing maximin shares: Some agents left behind.arXiv preprint arXiv:2105.09383, 2021

work page arXiv 2021
[16]

Ordinal maximin share approximation for goods.Journal of Artificial Intelligence Research, 74:353–391, 2022

Hadi Hosseini, Andrew Searns, and Erel Segal-Halevi. Ordinal maximin share approximation for goods.Journal of Artificial Intelligence Research, 74:353–391, 2022

work page 2022
[17]

Online stochastic matching, poisson arrivals, and the natural linear program

Zhiyi Huang and Xinkai Shu. Online stochastic matching, poisson arrivals, and the natural linear program. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 682–693, 2021

work page 2021
[18]

Online Matching: A Brief Survey.ACM SIGecom Exchanges, 22(1):135–158, June 2024

Zhiyi Huang, Zhihao Gavin Tang, and David Wajc. Online Matching: A Brief Survey.ACM SIGecom Exchanges, 22(1):135–158, June 2024

work page 2024
[19]

Online vertex-weighted bipartite matching: Beating 1-1/e with random arrivals.ACM Transactions on Algorithms (TALG), 15(3):1–15, 2019

Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang. Online vertex-weighted bipartite matching: Beating 1-1/e with random arrivals.ACM Transactions on Algorithms (TALG), 15(3):1–15, 2019

work page 2019
[20]

Improved analysis of ranking for online vertex-weighted bipartite matching in the random order model

Billy Jin and David P Williamson. Improved analysis of ranking for online vertex-weighted bipartite matching in the random order model. InInternational Conference on Web and Internet Economics, pages 207–225. Springer, 2021

work page 2021
[21]

An optimal deterministic algorithm for online b-matching.Theoretical Computer Science, 233(1-2):319–325, 2000

Bala Kalyanasundaram and Kirk R Pruhs. An optimal deterministic algorithm for online b-matching.Theoretical Computer Science, 233(1-2):319–325, 2000

work page 2000
[22]

Online bipartite matching with unknown distributions

Chinmay Karande, Aranyak Mehta, and Pushkar Tripathi. Online bipartite matching with unknown distributions. InProceedings of the forty-third annual ACM symposium on Theory of computing, pages 587–596, 2011

work page 2011
[23]

An optimal algorithm for on-line bipartite matching

Richard M Karp, Umesh V Vazirani, and Vijay V Vazirani. An optimal algorithm for on-line bipartite matching. InProceedings of the twenty-second annual ACM symposium on Theory of computing, pages 352–358, 1990

work page 1990
[24]

On approximately fair allocations of indivisible goods

Richard J Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On approximately fair allocations of indivisible goods. InProceedings of the 5th ACM Conference on Electronic Commerce, pages 125–131, 2004

work page 2004
[25]

Online bipartite matching with random arrivals: an approach based on strongly factor-revealing lps

Mohammad Mahdian and Qiqi Yan. Online bipartite matching with random arrivals: an approach based on strongly factor-revealing lps. InProceedings of the forty-third annual ACM symposium on Theory of computing, pages 597–606, 2011. 14

work page 2011
[26]

Online matching and ad allocation.Foundations and Trends®in Theoretical Computer Science, 8(4):265–368, 2013

Aranyak Mehta et al. Online matching and ad allocation.Foundations and Trends®in Theoretical Computer Science, 8(4):265–368, 2013

work page 2013
[27]

Fair enough: Guaranteeing approximate maximin shares

Ariel D Procaccia and Junxing Wang. Fair enough: Guaranteeing approximate maximin shares. InProceedings of the fifteenth ACM conference on Economics and computation, pages 675–692, 2014

work page 2014
[28]

Equity, envy, and efficiency.Journal of Economic Theory, 9(1):63–91, 1974

Hal R Varian. Equity, envy, and efficiency.Journal of Economic Theory, 9(1):63–91, 1974

work page 1974
[29]

Online cake cutting

Toby Walsh. Online cake cutting. InAlgorithmic Decision Theory: Second International Conference, ADT 2011, Piscataway, NJ, USA, October 26-28, 2011. Proceedings 2, pages 292–305. Springer, 2011

work page 2011
[30]

Asymptotic existence of class envy-free matchings

Tomohiko Yokoyama and Ayumi Igarashi. Asymptotic existence of class envy-free matchings. InProceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’25, page 2244–2252, 2025

work page 2025
[31]

Fairness-efficiency tradeoffs in dynamic fair division

David Zeng and Alexandros Psomas. Fairness-efficiency tradeoffs in dynamic fair division. InProceedings of the 21st ACM Conference on Economics and Computation, pages 911–912, 2020. 15 A Appendix A.1 Class Proportionality We now extend the analysis of EFTT to the indivisible setting, showcasing its integrality guarantees after rounding via online correlat...

work page 2020

[1] [1]

Online Fair Division: analysing a Food Bank problem

Martin Aleksandrov, Haris Aziz, Serge Gaspers, and Toby Walsh. Online fair division: Analysing a food bank problem.arXiv preprint arXiv:1502.07571, 2015

work page internal anchor Pith review Pith/arXiv arXiv 2015

[2] [2]

How to make envy vanish over time

Gerdus Benade, Aleksandr M Kazachkov, Ariel D Procaccia, and Christos-Alexandros Psomas. How to make envy vanish over time. InProceedings of the 2018 ACM Conference on Economics and Computation, pages 593–610, 2018

work page 2018

[3] [3]

Multiway Online Correlated Selection

Guy Blanc and Moses Charikar. Multiway Online Correlated Selection. In2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 1277–1284, 2022

work page 2022

[4] [4]

The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes

Eric Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 119(6):1061–1103, 2011

work page 2011

[5] [5]

The unreasonable fairness of maximum nash welfare.ACM Transactions on Economics and Computation (TEAC), 7(3):1–32, 2019

Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum nash welfare.ACM Transactions on Economics and Computation (TEAC), 7(3):1–32, 2019

work page 2019

[6] [6]

Consensus of subjective probabilities: The pari-mutuel method.The Annals of Mathematical Statistics, 30(1):165–168, 1959

Edmund Eisenberg and David Gale. Consensus of subjective probabilities: The pari-mutuel method.The Annals of Mathematical Statistics, 30(1):165–168, 1959. 13

work page 1959

[7] [7]

Edge-Weighted Online Bipartite Matching.Journal of the ACM, 69(6):1–35, 2022

Matthew Fahrbach, Zhiyi Huang, Runzhou Tao, and Morteza Zadimoghaddam. Edge-Weighted Online Bipartite Matching.Journal of the ACM, 69(6):1–35, 2022

work page 2022

[8] [8]

Online ad assignment with free disposal

Jon Feldman, Nitish Korula, Vahab Mirrokni, Shanmugavelayutham Muthukrishnan, and Martin Pál. Online ad assignment with free disposal. InInternational workshop on internet and network economics, pages 374–385. Springer, 2009

work page 2009

[9] [9]

Online Matching with General Arrivals

Buddhima Gamlath, Michael Kapralov, Andreas Maggiori, Ola Svensson, and David Wajc. Online Matching with General Arrivals. In2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 26–37, Baltimore, MD, USA, November 2019. IEEE

work page 2019

[10] [10]

An improved approximation algorithm for maximin shares

Jugal Garg and Setareh Taki. An improved approximation algorithm for maximin shares. InProceedings of the 21st ACM Conference on Economics and Computation, pages 379–380, 2020

work page 2020

[11] [11]

Fair allocation of indivisible goods: Improvements and generalizations

Mohammad Ghodsi, MohammadTaghi HajiAghayi, Masoud Seddighin, Saeed Seddighin, and Hadi Yami. Fair allocation of indivisible goods: Improvements and generalizations. InProceedings of the 2018 ACM Conference on Economics and Computation, pages 539–556, 2018

work page 2018

[12] [12]

Online nash social welfare via promised utilities.arXiv e-prints, pages arXiv–2008, 2020

Artur Gorokh, Siddhartha Banerjee, Billy Jin, and Vasilis Gkatzelis. Online nash social welfare via promised utilities.arXiv e-prints, pages arXiv–2008, 2020

work page 2008

[13] [13]

Fairness and Efficiency in Online Class Matching, October 2023

MohammadTaghi Hajiaghayi, Shayan Chashm Jahan, Mohammad Sharifi, Suho Shin, and Max Springer. Fairness and Efficiency in Online Class Matching, October 2023

work page 2023

[14] [14]

Class fairness in online matching.Artificial Intelligence, 335:104177, October 2024

Hadi Hosseini, Zhiyi Huang, Ayumi Igarashi, and Nisarg Shah. Class fairness in online matching.Artificial Intelligence, 335:104177, October 2024

work page 2024

[15] [15]

Guaranteeing maximin shares: Some agents left behind.arXiv preprint arXiv:2105.09383, 2021

Hadi Hosseini and Andrew Searns. Guaranteeing maximin shares: Some agents left behind.arXiv preprint arXiv:2105.09383, 2021

work page arXiv 2021

[16] [16]

Ordinal maximin share approximation for goods.Journal of Artificial Intelligence Research, 74:353–391, 2022

Hadi Hosseini, Andrew Searns, and Erel Segal-Halevi. Ordinal maximin share approximation for goods.Journal of Artificial Intelligence Research, 74:353–391, 2022

work page 2022

[17] [17]

Online stochastic matching, poisson arrivals, and the natural linear program

Zhiyi Huang and Xinkai Shu. Online stochastic matching, poisson arrivals, and the natural linear program. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 682–693, 2021

work page 2021

[18] [18]

Online Matching: A Brief Survey.ACM SIGecom Exchanges, 22(1):135–158, June 2024

Zhiyi Huang, Zhihao Gavin Tang, and David Wajc. Online Matching: A Brief Survey.ACM SIGecom Exchanges, 22(1):135–158, June 2024

work page 2024

[19] [19]

Online vertex-weighted bipartite matching: Beating 1-1/e with random arrivals.ACM Transactions on Algorithms (TALG), 15(3):1–15, 2019

Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang. Online vertex-weighted bipartite matching: Beating 1-1/e with random arrivals.ACM Transactions on Algorithms (TALG), 15(3):1–15, 2019

work page 2019

[20] [20]

Improved analysis of ranking for online vertex-weighted bipartite matching in the random order model

Billy Jin and David P Williamson. Improved analysis of ranking for online vertex-weighted bipartite matching in the random order model. InInternational Conference on Web and Internet Economics, pages 207–225. Springer, 2021

work page 2021

[21] [21]

An optimal deterministic algorithm for online b-matching.Theoretical Computer Science, 233(1-2):319–325, 2000

Bala Kalyanasundaram and Kirk R Pruhs. An optimal deterministic algorithm for online b-matching.Theoretical Computer Science, 233(1-2):319–325, 2000

work page 2000

[22] [22]

Online bipartite matching with unknown distributions

Chinmay Karande, Aranyak Mehta, and Pushkar Tripathi. Online bipartite matching with unknown distributions. InProceedings of the forty-third annual ACM symposium on Theory of computing, pages 587–596, 2011

work page 2011

[23] [23]

An optimal algorithm for on-line bipartite matching

Richard M Karp, Umesh V Vazirani, and Vijay V Vazirani. An optimal algorithm for on-line bipartite matching. InProceedings of the twenty-second annual ACM symposium on Theory of computing, pages 352–358, 1990

work page 1990

[24] [24]

On approximately fair allocations of indivisible goods

Richard J Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On approximately fair allocations of indivisible goods. InProceedings of the 5th ACM Conference on Electronic Commerce, pages 125–131, 2004

work page 2004

[25] [25]

Online bipartite matching with random arrivals: an approach based on strongly factor-revealing lps

Mohammad Mahdian and Qiqi Yan. Online bipartite matching with random arrivals: an approach based on strongly factor-revealing lps. InProceedings of the forty-third annual ACM symposium on Theory of computing, pages 597–606, 2011. 14

work page 2011

[26] [26]

Online matching and ad allocation.Foundations and Trends®in Theoretical Computer Science, 8(4):265–368, 2013

Aranyak Mehta et al. Online matching and ad allocation.Foundations and Trends®in Theoretical Computer Science, 8(4):265–368, 2013

work page 2013

[27] [27]

Fair enough: Guaranteeing approximate maximin shares

Ariel D Procaccia and Junxing Wang. Fair enough: Guaranteeing approximate maximin shares. InProceedings of the fifteenth ACM conference on Economics and computation, pages 675–692, 2014

work page 2014

[28] [28]

Equity, envy, and efficiency.Journal of Economic Theory, 9(1):63–91, 1974

Hal R Varian. Equity, envy, and efficiency.Journal of Economic Theory, 9(1):63–91, 1974

work page 1974

[29] [29]

Online cake cutting

Toby Walsh. Online cake cutting. InAlgorithmic Decision Theory: Second International Conference, ADT 2011, Piscataway, NJ, USA, October 26-28, 2011. Proceedings 2, pages 292–305. Springer, 2011

work page 2011

[30] [30]

Asymptotic existence of class envy-free matchings

Tomohiko Yokoyama and Ayumi Igarashi. Asymptotic existence of class envy-free matchings. InProceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’25, page 2244–2252, 2025

work page 2025

[31] [31]

Fairness-efficiency tradeoffs in dynamic fair division

David Zeng and Alexandros Psomas. Fairness-efficiency tradeoffs in dynamic fair division. InProceedings of the 21st ACM Conference on Economics and Computation, pages 911–912, 2020. 15 A Appendix A.1 Class Proportionality We now extend the analysis of EFTT to the indivisible setting, showcasing its integrality guarantees after rounding via online correlat...

work page 2020