New Algorithms Beat Half-Approximation in Fair Online Class Matching

Online bipartite matching is fundamental to ride-sharing, online advertising, and resource allocation, where agents (e.g., drivers, ad slots) arrive sequentially and must be matched irrevocably to items. When agents belong to classes—demographic groups or regions—fairness demands equitable treatment across groups, formalized as α-class envy-freeness (CEF): each class gets at least an α fraction of what it could extract from any other class's bundle. Known algorithms achieving constant CEF guarantees could only attain half the optimal total social welfare (1/2-USW), far below the 0.632 achievable without fairness. This left an open question: does fairness inherently force this efficiency loss?

Borst and Springer resolve this question with a family of threshold-based algorithms parameterized by γ ∈ [0,1]. These algorithms equalize allocations across classes up to a threshold γ, then maximize efficiency. For divisible matching (where items can be split), the algorithms yield simultaneous (1−e^{−γ})-CEF and (1 − e^{γ−1}/(γ+1))-USW guarantees. For indivisible matching, they achieve γ/2-CEF with the same USW performance. Setting any γ>0 produces the first algorithms that beat 1/2-USW while maintaining constant CEF—a major theoretical breakthrough. The authors also prove a matching upper bound: no non-wasteful α-CEF algorithm can exceed (1+α − e^{α−1})/(1+α)-USW, correcting prior vacuous bounds for α<0.58. This nearly matches their algorithms' performance, providing the first tight characterization of the price of fairness in online class matching.