| paper | Proportionally Fair Matching via Randomized Rounding |
| authors | Sharmila Duppala, Nathaniel Grammel, Juan Luque, Calum MacRury, Aravind Srinivasan |
| venue | AAAI 2025 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 4.3
Given finite endpoint type sets \(A\) and \(B\), rational masses \(\mu^A\) and \(\mu^B\), compatible type pairs \(E_0\subseteq A\times B\), rational nonnegative weights \(w_e\), a color map \(\chi:E_0\to[\ell]\), and \(0<\beta<1\), choose nonnegative assignment masses \(x_e\) maximizing \(\sum_{e\in E_0}w_ex_e\), subject to \(\sum_{e\ni a}x_e\le\mu^A_a\), \(\sum_{e\ni b}x_e\le\mu^B_b\), and \(\sum_{\chi(e)=c}x_e\le\beta\sum_{e\in E_0}x_e\) for every \(c\in[\ell]\).
A high-multiplicity offline bipartite matching model in which \(A\) and \(B\) are exchangeable endpoint types with masses \(\mu^A\) and \(\mu^B\), each compatible type pair \(e\) has common weight \(w_e\) and color \(\chi(e)\), and \(x_e\) is matched population mass.
The mirror is most meaningful only in a structured block-constant cohort regime, where much of the edge-level combinatorics and the distinctive rounding analysis disappear.
fatal: False
Covers Theorems 4.1 and 4.3 as continuous two-sided and one-sided mass-matching problems; it leaves the cited NP-hardness from prior work, randomized-rounding guarantees, random-order contention resolution, and general-graph future work as finite-population or separate questions.
The strongest positive case is a Class-A mirror of the paper’s bipartite proportional-fair matching results. It is best understood as a high-multiplicity blow-up of the paper’s graph model, not as a claim that every arbitrary named-agent graph has a meaningful continuum limit.
Take finite sets \(A\) and \(B\) of complete endpoint types—for example, rider types and driver types. A type includes every feature relevant to compatibility, edge weight, and fairness color: location zone, protected category, vehicle class, pricing status, and so on. Let \(E_0\subseteq A\times B\) be the compatible type pairs. Each \(e\in E_0\) has a rational weight \(w_e\) and color \(\chi(e)\in[\ell]\). The population is given by rational masses \(\mu^A_a\) and \(\mu^B_b\), with each side normalized to mass \(1\).
The decision variable is \(x_e\ge0\), the mass assigned along type-pair edge \(e\). Writing
\[ X=\sum_{e\in E_0}x_e, \qquad X_c=\sum_{e:\chi(e)=c}x_e, \]
the capacity constraints are
\[ \sum_{e\ni a}x_e\le \mu^A_a \quad\text{and}\quad \sum_{e\ni b}x_e\le \mu^B_b. \]
The objective is to maximize \(\sum_e w_ex_e\), subject to proportional fairness constraints on the matched mass. This is genuinely population continuization: \(x_e\) is the amount of society receiving a type-\(e\) assignment, not a lottery over fractional outcomes.
The natural regime is a large offline batch—say, hundreds of thousands of riders and drivers in a time window—with perhaps tens of endpoint types and a manageable type-pair graph. Each type represents a cohort of exchangeable agents. Clearing denominators gives a literal finite blow-up: \(N\mu^A_a\) copies of type \(a\), \(N\mu^B_b\) copies of type \(b\), with every compatible type pair expanded into a complete bipartite block whose edges share its weight and color. Integral mass flows in this blow-up are exactly ordinary matchings, normalized by \(N\). Thus the continuous formulation is not merely an arbitrary fractional relaxation in this regime; it is the high-multiplicity aggregate of the original matching problem.
My lead anchor is Theorem 4.3, proved in this paper. It states that, when \(\alpha=0\), Algorithm 1 returns a matching satisfying the \(\beta\)-fairness constraints with probability at least
\[ 1-2\exp\!\left(-\frac{\varepsilon^2\beta\sum_{e\in E}x_e}{28}\right), \]
while achieving expected weight at least \(\tfrac12(1-\varepsilon)\mathrm{OPT}\).
The corresponding continuous problem is:
\[ \textsc{One-Sided-PFM}_{\infty} \]
Input: a finite bipartite type graph \((A,B,E_0)\), rational type masses \(\mu^A,\mu^B\), rational nonnegative edge weights \(w_e\), a color map \(\chi:E_0\to[\ell]\), and \(0<\beta<1\).
Question: find a mass matching \(x\) maximizing \(\sum_e w_ex_e\), subject to the endpoint capacities and
\[ X_c\le \beta X \qquad\text{for every }c\in[\ell]. \]
A solution is the complete rational vector \(x\), together with its objective value. This is a polynomial-size linear program, hence expected to be in Class A. It should be solvable in time polynomial in \(|A|+|B|+|E_0|+\ell\) and the input bit length. Theorem 4.3’s randomized rounding becomes the finite-population implementation question: how large must the clone population be to realize a near-optimal mass solution with exact fairness and controlled failure probability?
The paper’s authors should recognize this as their problem in the high-multiplicity regime. The color proportions, matching capacities, weights, and one-sided fairness constraint are unchanged. What disappears is only the indivisibility of individual agents, precisely the feature that high multiplicity is meant to remove. The paper already solves the relevant LP and then studies how to round it.
A second worthwhile anchor is Theorem 4.1, also proved in this paper. It gives a \(1/2\)-approximation in expectation together with \(\delta\)-probable fairness for the full two-sided constraint \(0<\alpha\le\beta<1\).
The corresponding problem is:
\[ \textsc{Two-Sided-PFM}_{\infty} \]
Input: the same finite typed bipartite population, together with rational \(0<\alpha\le\beta<1\).
Question: find a maximum-weight mass matching satisfying
\[ \alpha X\le X_c\le \beta X \qquad\text{for every }c\in[\ell]. \]
Again, the answer is a rational mass-flow vector \(x\). This is also a polynomial-size LP and therefore expected to be Class A. The continuous solution satisfies proportionality exactly; finite clone realizations may require rounding, where the paper’s \(\delta\)-probable fairness analysis becomes relevant. The natural follow-up questions are whether finite realizations achieve the continuous optimum with an additive error tending to \(0\), whether the \(1/2\) factor can be replaced by the paper’s proposed \(1-1/e\) direction, and what happens for general rather than bipartite type graphs.
This case deliberately does not claim to mirror the cited NP-hardness result of Bandyapadhyay et al.; that result is not a numbered theorem of this paper, and the continuous typed version above is expected to be tractable. Nor does it cover the paper’s future work on random-order contention resolution or general graphs. It covers Theorems 4.1 and 4.3 and nothing more.
The weakest point is that the continuous problem bypasses the paper’s most technically distinctive ingredient—randomized rounding—and replaces an arbitrary graph on named vertices by a structured type blow-up. An opponent can reasonably say that this is an extension of the paper’s LP-based problem rather than a direct mirror of its full finite-instance problem. That objection is real. The answer is that the extension is exactly the sensible high-multiplicity regime: after denominator clearing, the mass solution corresponds to an ordinary matching in a replicated colored weighted graph, preserving objective values and fairness proportions. The mirror therefore remains recognizably the paper’s proportional-fair matching problem, while making population mass—not individual identity—the computational object.
The strongest case against is that neither anchor is really a continuous counterpart of the paper’s distinctive results. Theorem 4.1 and Theorem 4.3 are rounding theorems. Their computational object is an integral matching \(M\subseteq E\), and their content lies in contention resolution, martingale concentration, and the probability that a realized matching satisfies edge-count proportions.
The proposed continuous problem retains only the LP already written in Section 3:
\[ \max \sum_{e\in E_0} w_e x_e \]
subject to endpoint capacities and
\[ \alpha X\le X_c\le \beta X. \]
Thus the proposed mirror of both theorems is just \(\mathrm{LP\text{-}FAIR}\) after quotienting identical vertices into types. The \(1/2\) guarantee, the \((1-\varepsilon)\) loss, and the failure exponent disappear. Exact fairness is simply a linear constraint on mass. If one retains the probability of a realized matching, one has returned to finite-population rounding rather than posed a new continuous computational problem.
A stronger version could define a high-multiplicity blow-up: every type pair becomes a complete bipartite block, with common weight and color. But this exposes the fundamental tradeoff. If the graph has arbitrary neighborhoods, weights, and edge colors, then a complete agent type must include its entire neighborhood signature. In a generic graph, almost every vertex has a distinct signature, so there is no meaningful multiplicity. If many agents do share a type, the graph is block-constant, and all the edge-level combinatorics that Theorems 4.1 and 4.3 analyze have deliberately disappeared. The resulting problem is standard fractional matching with proportional side constraints.
One might instead study finite-\(N\) convergence, exact realization, or the smallest clone population needed to implement a mass solution. Those are legitimate questions, but they are rounding and approximation questions about the discrete problem, not computational questions about the continuous society. In the block-constant model, rationality makes the point especially sharply: after clearing denominators, a rational mass flow can be realized exactly by an integral matching in a sufficiently large blow-up. There need not be a persistent continuum phenomenon at all.
This objection does not apply to identity-dependent objectives, and there is no genuine multiplicity obstruction in every plausible application. Riders, drivers, employers, and employees can naturally form cohorts. That is why the negative case is not airtight. A reader who regards a high-multiplicity fractional matching formulation as worthwhile should accept the proponent’s mirror: both Theorem 4.1 and Theorem 4.3 survive as sensible Class-A population models. The only substantial negative is that the mirror is already the paper’s LP relaxation and strips away precisely the finite indivisibility that makes the paper’s named theorems interesting. Under the programme’s stated standards, that is a concern about novelty and scope, not a decisive reason to reject it.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.