| paper | Asymptotic Existence of Class Envy-free Matchings |
| authors | — |
| venue | AAMAS 2025 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Proposition 4.2
statement extracted from the paper’s text layer
Given finite classes \(P\), complete agent types \(T\) with class map \(p:T\to P\), item categories \(J\), rational type masses \(\mu_t\), rational supply masses \(\sigma_j\), and utilities \(u_t(j)\in[0,1]\), find rational class allocations \(b_{pj}\ge0\) with \(\sum_{p\in P}b_{pj}\le\sigma_j\) and within-class transports attaining each assignment valuation \(V_p(b_p)\), such that \(2V_p(b_p)\ge V_p(b_q)\) for every \(p\ne q\), while no positive item-category mass can be transferred between classes to increase the receiving class's valuation without decreasing the giving class's valuation; otherwise report infeasibility.
A high-multiplicity transportation model where \(t\) is a complete class-and-utility type of mass \(\mu_t\), \(j\) is a repeated item category of supply \(\sigma_j\), \(b_{pj}\) is class-assigned mass, and \(V_p\) is the maximum-weight within-class flow value.
The proposition is phrased as a fairness guarantee for a prescribed rule rather than an explicit complexity theorem, so a stricter source gate could reject its computational character.
fatal: False
The mirror covers round-robin's \(1/2\)-CEF1 and non-wastefulness guarantee; it leaves the maximum-weight matching theorem, the random asymptotic theorem, and their probabilistic lemmas untouched.
The strongest honest positive case is narrow. The paper has no named theorem establishing a complexity classification such as membership in \(P\), NP-hardness, or parameterized tractability. Its named results are asymptotic existence and fairness guarantees. The only usable algorithmic anchor is Proposition 4.2, proved in this paper using results from [3,31]:
The matching produced by the round-robin algorithm is \(1/2\)-CEF1 and non-wasteful.
Theorem 3.1 and Theorem 4.1 are also proved here, but they are probabilistic existence statements, not computational results. Thus this is not a fully qualifying ChoCo paper under the strict anchor gate. Nevertheless, Proposition 4.2 supports a credible, author-recognizable continuous extension.
My lead problem would be Typed Class-Fair Mass Matching\(_\infty\). The scenario is a large public-housing or medical-resource market. There are finitely many demographic classes \(P\), finitely many complete agent types \(T\), and finitely many item categories \(J\). A type \(t\) specifies its class \(p(t)\) and its utility \(u_t(j)\in[0,1]\) for every item category. The input gives rational type masses \(\mu_t\), with \(\sum_t\mu_t=1\), and rational item-copy masses \(\sigma_j\).
The item categories represent repeated standardized units: for example, many housing units of the same location-and-size category or many medically equivalent treatment slots. This does not make an individual item divisible. Clearing denominators by \(Q\) produces \(Q\mu_t\) agents of type \(t\) and \(Q\sigma_j\) distinct indivisible item copies of category \(j\). Thus \(\mu\) is a genuine high-multiplicity population representation, while supply is scaled jointly so that matching does not degenerate as the population grows.
An allocation is a bundle-mass vector \(b_{pj}\ge0\), satisfying
\[
\sum_{p\in P} b_{pj}\le \sigma_j.
\]
For a class \(p\) and bundle vector \(b\), define its assignment valuation by
\[
V_p(b)=
\max_z
\left\{
\sum_{\substack{t\in T\\p(t)=p}}\sum_{j\in J}u_t(j)z_{tj}
:
\sum_j z_{tj}\le\mu_t,\
\sum_t z_{tj}\le b_j,\
z_{tj}\ge0
\right\}.
\]
This is exactly the paper’s assignment valuation after grouping identical agents and item copies. With rational data, denominator clearing gives an ordinary maximum-weight matching; integrality follows from the transportation structure.
The continuous problem is:
Given \((P,T,J,p,\mu,\sigma,u)\), output a rational allocation \(b\) and optimal within-class transports attaining \(V_p(b_p)\) such that
\[ 2V_p(b_p)\ge V_p(b_q) \qquad\text{for every }p\ne q, \]
and no positive mass of an item category can be moved to another class while increasing that class’s valuation without decreasing the recipient class’s valuation. The objective is feasibility: find such a class-fair, non-wasteful allocation or report that none exists.
The factor \(2\) is not arbitrary. In a \(Q\)-clone lift, Proposition 4.2 gives
\[
2Q V_p(b_p)\ge
V_p(B_q\setminus\{j\})
\]
for some removed item copy. Since one item changes normalized value by at most \(1/Q\), the limit gives
\[
2V_p(b_p)\ge V_p(b_q).
\]
So the continuous question is the scale limit of the paper’s \(1/2\)-CEF1 guarantee, while preserving indivisible items at every finite lift.
I would expect this problem to be Class A for fixed finite \(T\) and \(J\), because every assignment valuation is a maximum-cost flow and the mass version should admit bulk round-robin steps and configuration-LP formulations. That is a conjectural classification, not a result of this paper. Important follow-up questions are whether the continuous round-robin output can be computed in time polynomial in \(|T|,|J|\) and the encoding length, whether the factor \(2\) can be improved to exact class envy-freeness, and whether finite clone lifts admit controlled rounding from a mass solution.
The weakest point is substantial: the paper’s random utility model deliberately makes agents almost surely distinct, whereas this mirror requires repeated complete utility types. It also replaces individually distinct items by repeated item categories and scales item supply with population. Those changes are plausible for standardized housing or medical slots, but make this an extension rather than a direct mirror. More seriously, if the anchor rule demands a named complexity theorem, Proposition 4.2 does not qualify. The positive case therefore survives only as a credible new Class-A computational extension of the paper’s round-robin result, not as evidence that the paper itself already contains a continuous computational-social-choice result.
The negative case is strongest at the source-gate level. This paper contains no named computational result of the kind ChoCo is meant to continuize. Theorem 3.1 and Theorem 4.1 are probabilistic asymptotic existence statements; their lemmas establish probabilistic estimates. Proposition 4.2 is the closest candidate, but it is a guarantee for a prescribed round-robin algorithm, not a complexity classification or an exact, approximation, or parameterized algorithm for a stated computational problem. The proposed mass-feasibility problem would therefore be new research inspired by the paper, not a continuous mirror of one of its computational results.
The proposed typed model is nevertheless mathematically coherent. Rational masses can be lifted to clones, and assignment valuations become transportation problems. That defeats objections based merely on divisibility or loss of individual identity. But it also changes the substantive source result in both dimensions: agents with repeated utility vectors replace the paper’s almost-surely distinct random agents, and repeated item categories replace its individually random-weighted items. The factor-\(2\) guarantee is only the limit of deleting one item from a finite CEF1 certificate. It is not the continuous form of the paper’s asymptotic exact class-envy-freeness theorem, and the polynomial solvability, exact-fairness improvement, and rounding theory are all conjectural additions.
The stronger possible mirror does not repair this. To preserve Theorem 4.1’s mechanism, one would need the independent, non-atomic edge utilities that make random-assignment and concentration arguments work. With a fixed finite type space, those assumptions disappear: utility vectors have positive-mass atoms and repeated rows. If the full utility vector is made part of the type, almost every agent becomes its own type; if one retains continuously distributed utility vectors, the model has an infinite type space and requires a new representation and computational theory. The same problem affects Theorem 3.1: its proof relies on favorite bundles being uniformly distributed among subsets of named items. Repeated item categories turn that into a different deterministic capacity-allocation model.
A standardized-housing version could be worthwhile as a new high-multiplicity fair-allocation problem. I would not claim otherwise. But it is not a computational mirror of this paper under the programme’s strict standard: its only plausible anchor is a non-complexity fairness guarantee, while the paper’s central asymptotic results lose their defining random-combinatorial mechanism under finite-type aggregation. The honest verdict is therefore negative for ChoCo, with the caveat that the proposed extension might merit separate study if the source-gate requirement is relaxed.
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.