| paper | Improved EFX Approximation Guarantees under Ordinal-based Assumptions |
| authors | — |
| venue | AAMAS 2023 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3.3
statement extracted from the paper’s text layer
Given rational type masses \(\mu_\theta\), item-class supplies \(\sigma_g\), additive valuations \(v_\theta\), and a common top pool \(H\) with \(\sum_{g\in H}\sigma_g=1\), compute a finite-support assignment \(x_{\theta,b}\ge0\) over integral bundles \(b\in\mathbb{Z}_{\ge0}^{G}\) satisfying \(\sum_b x_{\theta,b}=\mu_\theta\), \(\sum_{\theta,b} b_gx_{\theta,b}=\sigma_g\), and \(v_\theta(b)\ge\tfrac{2}{3}v_\theta(b'-e_g)\) whenever \(x_{\theta,b},x_{\theta',b'}>0\) and \(b'_g>0\), with every type ranking \(H\) above \(G\setminus H\).
Complete valuation types \(\theta\) have household mass \(\mu_\theta\); item copies remain indivisible but are grouped into finitely many classes with normalized supplies \(\sigma_g\); and \(x_{\theta,b}\) assigns mass to integral bundles, targeting a \(2/3\)-EFX support condition.
The finite item-class model does not preserve the theorem's full arbitrary item-by-item heterogeneity, and the claimed flow or column-generation realization of the sequential envy-cycle continuation is unproved; this narrows the mirror and its expected tractability but does not kill it.
fatal: False
The mirror covers Theorem 3.3's \(2/3\)-EFX guarantee under a common top-\(n\) set; it leaves the broader approximation framework, other corollaries, and Theorem 4.3's exact EFX result unaddressed.
My strongest positive case is a single anchor: Theorem 3.3, proved in this paper. It states that Algorithm 3 efficiently computes a \(2/3\)-EFX allocation when all agents agree on the set of their top \(n\) items, although they may rank those items differently. I would not claim that the paper’s entire contribution has an equally convincing continuous analogue.
The relevant regime is a high-multiplicity allocation market. There are \(N\) households and \(qN\) indivisible item copies, where \(N\) is large and the households have only \(\tau\ll N\) complete valuation types. A type \(\theta\) includes the household’s value for every item class; households with different values are different types. Let \(\mu_\theta\) be the fraction of households of type \(\theta\). Item copies remain indivisible: the large population is represented only by masses of households receiving particular integral bundles.
To make this precise, let \(G\) be a finite set of item classes, with \(\sigma_g\) copies of class \(g\) per unit population. For a denominator \(N\), the corresponding finite instance has \(N\mu_\theta\) named households and \(N\sigma_g\) distinct indivisible copies of \(g\). Let \(H\subseteq G\) be the common premium pool, satisfying \(\sum_{g\in H}\sigma_g=1\), and suppose every type ranks every copy in \(H\) at least as highly as every copy outside \(H\). This is exactly the normalized version of “the common set of top \(n\) items”: there is one premium item per household on average.
The continuous problem I would call \(\textsc{TopMass-EFX}_{2/3}^{\infty}\) is the following. An instance consists of rational \(\mu\), rational supplies \(\sigma\), additive type valuations \(v_\theta\), and a common top pool \(H\). A bundle is an integral vector \(b\in\mathbb Z_{\ge 0}^{G}\), where \(b_g\) is the number of copies of item class \(g\) received. The decision variable is \(x_{\theta,b}\ge0\), the mass of type-\(\theta\) households receiving bundle \(b\). It must satisfy \(\sum_b x_{\theta,b}=\mu_\theta\) for every \(\theta\), and \(\sum_{\theta,b}b_gx_{\theta,b}=\sigma_g\) for every item class \(g\).
Write \(e_g\) for one copy of \(g\). The allocation is \(\alpha\)-EFX if, whenever \(x_{\theta,b}>0\), \(x_{\theta',b'}>0\), and \(b'_g>0\), it satisfies \(v_\theta(b)\ge \alpha v_\theta(b'-e_g)\). The problem asks for a finite-support \(x\) satisfying these constraints with \(\alpha=2/3\); its natural optimization version maximizes \(\alpha\).
This is not fractional allocation of goods. In a rational instance, multiplying \(x\) by \(N\) gives counts of named households receiving integral bundles, and multiplying \(\sigma_g\) by \(N\) gives distinct item copies. The continuum records the aggregate assignment of many agents; no individual item is split.
The mirror is plausible in applications such as a large public allocation of housing packages, service slots, or educational entitlements. There may be millions of households but only a small number of valuation archetypes. All households may agree that a common pool of premium units is better than the ordinary pool, while disagreeing substantially about which premium unit is best. That is precisely the paper’s assumption, not an easier identical-preferences assumption.
I expect \(\textsc{TopMass-EFX}_{2/3}^{\infty}\) to be Class A. The proof of Theorem 3.3 separates the allocation into a structured initial phase and an envy-cycle-elimination continuation. In the high-multiplicity regime, the initial phase becomes a transportation problem assigning premium mass to valuation types and pairing it with lower-tier mass. The continuation should be expressible as flow over type-and-bundle states, with column generation if the bundle space is large. Thus the theorem supplies genuine structural evidence for tractability, although it does not itself prove a polynomial algorithm in the binary encoding of \(\mu\) and \(\sigma\): simply expanding the instance to \(N\) named agents may be pseudo-polynomial.
The main follow-up questions are whether the \(2/3\) guarantee can be optimized in the continuous model, whether exact EFX becomes feasible after aggregation, and whether a continuous solution can be rounded to \(N\) named agents with only an additive \(O(1/N)\) loss. One should also ask whether the common-top-pool assumption can be weakened to an agreement covering only \(1-\varepsilon\) of the item supply.
The weakest point is that EFX is originally a pointwise condition over named agents, whereas \(x\) forgets identities and retains only positive-mass bundle classes. Exceptional agents of vanishing mass disappear, and rounding an aggregate allocation may reintroduce envy. Also, a nondegenerate limit requires item supply to scale with the population; keeping the paper’s fixed \(m\) items while \(N\to\infty\) is degenerate. I regard that scaling as the correct high-multiplicity regime for indivisible allocation, but it is the point the opposing case can attack most seriously.
The strongest negative case is that the proposed mirror faces a genuine fidelity fork. Theorem 3.3 concerns \(n\) individually named, indivisible goods, and its common top-\(n\) condition permits agents to rank those \(n\) goods differently. If \(N\) grows while the type space remains fixed, retaining arbitrary values for \(N\) named goods makes each valuation type an \(N\)-dimensional object. If instead those goods are collapsed into finitely many classes, the model becomes repeated-item allocation with identical copies, and some of the item-level combinatorics motivating the theorem have been removed.
The same concern affects the proposed continuation. Envy-cycle elimination is a sequential algorithm on named agents and bundles. Its cycle operations do not obviously aggregate into a flow on valuation types: two agents of the same valuation type may hold different bundles and occupy different positions in the envy graph. Thus the claim that the continuation “should be expressible” as a polynomial flow or column-generation model is conjectural, not a consequence of Theorem 3.3.
But this does not defeat the best mirror. The repeated-item version is a legitimate high-multiplicity regime, not an illicit fractional relaxation. Let \(x_{\theta,b}\) denote the mass of type \(\theta\) receiving integral bundle \(b\). Because a type completely determines an agent’s valuation, EFX depends only on \((\theta,b)\), not on personal identity. The support condition
\[ x_{\theta,b}>0,\ x_{\theta',b'}>0 \quad\Longrightarrow\quad v_\theta(b)\ge \frac23 v_\theta(b'-e_g) \]
for every \(g\in b'\) is exactly the finite EFX condition for every realized pair of agents. With rational masses, multiplying by a common denominator recovers a finite allocation of named agents and indivisible item copies. No information relevant to EFX has been lost.
The apparent degeneracy can also be avoided naturally. Scaling the common top pool to \(N\) copies while scaling the population to \(N\) agents preserves the paper’s top-\(n\) premise, and keeping a constant number of items per agent ensures that removing one item remains a nonvanishing operation. A market for repeated housing packages, service slots, or educational entitlements is a credible high-multiplicity setting.
Consequently, none of the decisive objections applies. Theorem 3.3 is a numbered computational result; multiplicity is meaningful in the repeated-item regime; EFX is anonymous once valuation types are complete; and the continuum need not collapse. Whether the aggregate problem is Class A, B, or C is precisely the computational question to investigate. The paper does not prove the continuous algorithm, but that is an open research opportunity, not a reason to reject the mirror.
So the honest negative case can challenge the proposed Class A forecast and the faithfulness of arbitrary item-level heterogeneity, but it cannot support the universal claim that no worthwhile continuous mirror exists. This anchor survives.
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.