| paper | A Complete Landscape for the Price of Envy-Freeness |
| authors | — |
| venue | AAMAS 2024 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper's numbered contributions establish price and welfare guarantees, but none asserts a complexity classification for a named computational problem. Therefore bit (a) fails under the explicit anchor rule, even though the proposed repeated-inventory population model is a coherent continuous extension. The opponent's fixed-resource objection is not independently fatal, but the missing qualifying anchor is.
fails bit a — no named computational result to mirror
The proposed mirror covers the mixed-goods EFXM/EFM welfare guarantee in Lemma 3.3 and the two-agent scaled ratio in Theorem 3.5; it leaves Theorem 3.1, Theorem 3.4, Theorems 4.1–4.2, and Lemma 4.3 untouched.
The strongest honest positive case is a high-multiplicity mirror of the paper’s mixed-goods fair-division problem. There is, however, an important qualification: the paper contains no numbered theorem stating an NP-hardness, polynomial-time, W[1]-hardness, or FPT result. If that is the anchor rule literally, there are no eligible complexity anchors. The closest named computational results are the constructive Lemma 3.3 and the quantitative Theorem 3.5, both proved in this paper.
My lead anchor is Lemma 3.3, which states that Algorithm 1 computes an EFXM allocation with social welfare at least \( \bigl(u_1(M\cup D)+u_2(M\cup D)\bigr)/2 \), and an EFX allocation when \(D=\varnothing\).
A natural continuous mirror is the following. Let \(G\) be a finite catalogue of indivisible-good classes and \(D\) a finite catalogue of divisible goods. There is a finite set \(T\) of valuation types, with distribution \(\mu\). A type \(t\) has additive utility \(u_t(S,x)=\sum_{g\in S}a_{tg}+\sum_{d\in D}b_{td}x_d\). The supply of good \(g\) is \(q_g\), interpreted as \(Nq_g\) whole copies in an \(N\)-agent approximation; divisible good \(d\) has supply \(q_d\).
A solution is a mass allocation \(\lambda_t\) over bundles \(B=(S,x)\). Its total mass is \(\mu_t\); indivisible capacities satisfy \(\sum_t\int 1[g\in S]\,d\lambda_t\le q_g\), and divisible capacities satisfy \(\sum_t\int x_d\,d\lambda_t\le q_d\). Social welfare is \( \sum_t\int u_t(B)\,d\lambda_t(B) \). EFXM is imposed agentwise: for every bundle in the support of type \(t\) and every bundle in the support of type \(t'\), the same EFXM inequalities from Definition 2.5 must hold. Thus this is not average envy or an outcome-fraction model; it is the original fairness condition lifted to a continuum of agents.
The continuous problem is:
Continuous EFXM-Gap\(_\infty\). Given rational \(T,\mu,G,D,q\), additive utilities, and \(\varepsilon>0\), output a feasible partial EFXM mass allocation with social welfare at least \(U_{\mathrm{all}}/2-\varepsilon\), where \(U_{\mathrm{all}}=\sum_t\mu_t u_t(Q)\) is the aggregate value of the available resource catalogue \(Q\). When \(D=\varnothing\), require EFX instead. The exact version asks for a welfare-maximizing EFXM mass allocation.
The regime is a large population of households receiving standardized indivisible packages and divisible credits, with only a few valuation templates—for example, several million households but two or five recurring preference profiles. Each type contains the complete valuation vector, so idiosyncratic prices are represented by distinct types rather than being discarded. The number of agents grows while \(|T|\) remains small and supplies grow proportionally.
This is plausibly the authors’ problem: the goods, additive utilities, EFXM criterion, and utilitarian objective are unchanged. Only the agent population is aggregated. The population part should be Class A: mass allocation is naturally a configuration LP or transportation problem. The likely obstruction is pricing over indivisible bundle patterns; with unrestricted \(G\), that combinatorics may give Class B hardness inherited from the goods side. That is precisely the useful computational question: does high multiplicity remove only the population difficulty, leaving the item-side difficulty?
A second, weaker anchor is Theorem 3.5, proved here, which establishes that for two agents with scaled utilities the price of EFM and EFXM is exactly \(3/2\). Its continuous counterpart is:
Continuous Price-of-EFM\(_\infty\). For two valuation types \(T=\{t_1,t_2\}\), distribution \(\mu\), scaled utilities, and mixed-good supplies \(q\), compute the maximum unconstrained welfare \(OPT_\infty\), the maximum EFM or EFXM welfare \(F_\infty\), and the ratio \(OPT_\infty/F_\infty\). Then determine the supremum of this ratio over all such rational high-multiplicity instances.
The natural conjecture is that the two-agent \(3/2\) bound survives for type-homogeneous instances. In the unrestricted continuous problem, however, agents of one type may receive different bundles, so mass-splitting could improve upon the two-agent lower-bound gadget. The honest prediction is therefore Class A for fixed type complexity, with the exact worst-case ratio itself a substantive question: it may remain \(3/2\), or fall below it for continuum-specific reasons. Any remaining hardness should come from indivisible bundle structure, not from population multiplicity.
The weakest point is indivisibility. With finitely many one-off goods and a continuum of agents, the goods have measure zero and the model degenerates. The mirror therefore requires copy-rich resources: \(Nq_g\) whole copies of each good class in the finite approximation. That is a legitimate high-multiplicity regime, but it is narrower than the paper’s arbitrary finite-good model. A second weakness is that Theorem 3.5 concerns exactly two agents, so its numerical \(3/2\) bound cannot simply be asserted for a population of two types.
Still, the mirror covers the paper’s central mixed-goods fairness question, produces an explicit mass-allocation optimization problem, and exposes a meaningful boundary: population continuity may make aggregation tractable while leaving the indivisible-goods pricing problem hard. The paper’s own divisible-goods and limiting arguments are outcome-space continuity, not population continuization, so they do not preempt this mirror.
The strongest negative case begins before modelling: this paper has no qualifying named computational anchor. Lemma 3.3 is a constructive welfare guarantee, but it gives no complexity statement, encoding, running time, or computational problem whose complexity is classified. Theorem 3.5 is a worst-case price ratio, not an algorithmic or complexity result. Defining a new optimization problem and calling it “Continuous EFXM-Gap\(_\infty\)” manufactures the computational anchor rather than continuizing one from the paper.
There is also a substantive population–resource obstruction. If the population is cloned while the paper’s finite set of indivisible goods is held fixed, only finitely many agents can receive those goods. After normalization by population size, their contribution to social welfare is zero. The one-copy phenomena driving EF1, EFXM, and the mixed-goods examples disappear in the limit; what remains is essentially a divisible-goods allocation problem. This is especially fatal to the \(3/2\) construction in Theorem 3.5, whose lower bound depends on the single contested good \(g_1\).
The proponent’s repair—scaling supplies to \(Nq_g\) copies—is the best available version, but it is no longer a population-only continuization of the paper. It replaces each unique indivisible good by a repeated inventory of exchangeable copies and changes the scarcity structure. If the good remains unique, its normalized effect vanishes; if it is replicated proportionally, the resource ontology and the fairness comparison change. The latter is a legitimate high-multiplicity fair-division model, but it is a new repeated-inventory problem, not the high-multiplicity limit of the paper’s instances.
This matters particularly for Lemma 3.3. Cut-and-choose is a procedure for two named agents: one partitions the entire resource set and the other chooses one of two bundles. With positive masses of two valuation types, one must instead choose a distribution of whole bundles for each type and impose EFXM between every pair of bundles in the supports. The proponent’s \(\lambda_t\) formulation is coherent, but it is a new configuration problem, potentially measure-valued because of the divisible goods. The paper proves nothing about its exact optimization problem, its separation problem, or its complexity. Restricting each type to one bundle restores a simpler analogue only by excluding precisely the mass-splitting allocations that make the continuum formulation different.
Theorem 3.5 fails as an anchor for the same reason. “Two agents” cannot simply become “two types”: the objective becomes type-mass-weighted, each type contains many mutually comparable agents, and the single indivisible good can either remain an atom of vanishing normalized importance or become a population-wide stock of copies. In neither case is the paper’s two-agent price being computed. A continuous price over two types and repeated supplies may be interesting, but it is a newly posed extremal theorem. Whether its ratio remains \(3/2\) is not the objection; the objection is that the object whose ratio is bounded is no longer the one established by Theorem 3.5.
No identity objection is available here: valuation types can legitimately include all relevant prices and utilities. Nor is existing high-multiplicity work a collision. The narrower point is that the only nondegenerate construction the proponent offers is an author-recognizable extension requiring new resource scaling, new bundle-support semantics, and new computational results. Under ChoCo’s anchor discipline, that is not a worthwhile continuous mirror of this paper.
The negative case is therefore strong on source fidelity and on the fixed-resource limit, though not logically airtight as a modelling claim. A repeated-household, repeated-package fair-division programme could be worthwhile in its own right. What this paper does not provide is a named computational result whose continuous population version that programme would actually be studying.
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.