| paper | On Optimal Tradeoffs between EFX and Nash Welfare* |
| authors | — |
| venue | AAAI 2024 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 2
statement extracted from the paper’s text layer
Given rational masses \(p_t\) over additive valuation types, rational supplies \(q_g\) of indivisible item kinds, and \(\alpha \in [0, \varphi-1]\), compute a complete mass allocation \(y_{tB}\) over bundles \(B\) such that the type-mass and item-capacity constraints hold, every occupied bundle pair satisfies support-wise \(\alpha\)-EFX and EF1, and \(\mathrm{NW}_\infty(y)\) is at least \(1/(\alpha+1)\) times the maximum continuous Nash welfare over feasible complete mass allocations.
A high-multiplicity fair-division market with finitely many valuation types, population masses, repeated indivisible item kinds, configuration-mass variables \(y_{tB}\), support-wide EFX constraints, and a logarithmic Nash-welfare objective.
The nondegenerate formulation scales the inventory into repeated item copies, so it is an extension rather than a literal population-only limit of the fixed-inventory model; support-wide EFX also creates a nonconvex configuration problem.
fatal: False
The mirror covers the additive guarantees in Theorems 1 and 2 and can test the tradeoff frontier suggested by Theorem 4; it leaves the subadditive results, maximin-share guarantees, and cited MNW hardness largely untouched.
The honest caveat is that this paper has no numbered theorem explicitly stating “in P,” “NP-hard,” or similar. Its named results are existence, approximation, and impossibility theorems. I would therefore anchor the mirror on Theorems 1, 2, and 4, while making clear that the computational remarks elsewhere provide the algorithmic content.
The natural regime is a large market of indivisible item copies. There are \(N\) agents but only \(\tau\) valuation types, with \(\tau\ll N\). Agents of type \(t\) have the same additive valuation vector \(a_{tg}\) over \(m\) item kinds. Item kind \(g\) has \(Nq_g\) individually indivisible copies, where \(q_g\) is a rational supply density. This models, for example, a public allocation system distributing many copies of a small catalogue of housing units, aid packages, licenses, or compute slots to a large population with a small number of preference profiles.
The continuous object is the population, not the goods. A type-\(t\) agent still receives an integral bundle \(B\subseteq[m]\); no agent receives a fraction of an item. Let \(p_t\) be the mass of type \(t\), with \(\sum_t p_t=1\). The decision variable is
\[ y_{tB}\ge 0, \]
the mass of type-\(t\) agents receiving bundle \(B\). It must satisfy
\[ \sum_B y_{tB}=p_t, \qquad \sum_{t,B:g\in B}y_{tB}\le q_g. \]
Equality in the second constraint gives a complete allocation. For additive valuations,
\[ u_t(B)=\sum_{g\in B}a_{tg}. \]
The continuous Nash welfare is the exact high-multiplicity limit of the discrete geometric mean:
\[ \operatorname{NW}_\infty(y) = \exp\left(\sum_{t,B}y_{tB}\log u_t(B)\right). \]
The continuous EFX condition is imposed on the support of \(y\): whenever \(y_{tB}>0\), \(y_{sB'}>0\), and \(g\in B'\),
\[ u_t(B)\ge \alpha\,u_t(B'\setminus\{g\}). \]
Thus every positive-mass agent must satisfy the same pairwise EFX condition as an individual discrete agent. A rational solution \(y\) with denominator \(N\) expands exactly to a finite allocation with \(Np_t\) agents of type \(t\) and \(Nq_g\) indivisible copies of item \(g\). This is the required two-way high-multiplicity dictionary.
My lead anchor is Theorem 2, proved in this paper:
Every instance with additive valuations admits a complete allocation that is \(\alpha\)-EFX, EF1, and \(1/(\alpha+1)\)-MNW, for every \(0\le\alpha\le\phi-1\).
The corresponding continuous problem is:
Complete Type-Mass EFX–MNW\(_\infty\). Given rational type masses \(p\), item supplies \(q\), additive valuations \(a_{tg}\), and \(0\le\alpha\le\phi-1\), output a complete mass allocation \(y\) satisfying continuous \(\alpha\)-EFX and EF1, and
\[ \operatorname{NW}_\infty(y) \ge \frac{1}{\alpha+1} \operatorname{NW}^*_\infty, \]
where \(\operatorname{NW}^*_\infty\) is the maximum continuous Nash welfare over feasible allocations.
This is recognisably the authors’ problem: the goods are still indivisible, the fairness condition is still EFX, and efficiency is still the Nash-welfare benchmark. Only the repeated population has been aggregated by valuation type. The completion step is also faithful: the continuous analogue of the envy-cycle procedure reallocates bundle mass among anonymous types while assigning every remaining item copy.
I expect this to be a Class A candidate, at least in the natural high-multiplicity regime with a modest valuation catalogue. The mass and supply constraints are linear, additive bundle values are explicit, and the paper’s Algorithm 1 and Lemmas 1–3 manipulate bundles and envy relations in a way that should be aggregable by type and bundle configuration. The central algorithmic question is whether the exponentially many bundle configurations admit efficient separation or pricing. That is exactly the kind of continuous-optimization question ChoCo is meant to expose.
The second anchor is Theorem 1, also proved here:
Every instance with additive valuations admits a partial allocation that is \(\alpha\)-EFX, EF1, and \(1/(\alpha+1)\)-MNW, for every \(0\le\alpha\le1\).
Its mirror is:
Partial Type-Mass EFX–MNW\(_\infty\). Given the same input and \(0\le\alpha\le1\), output a partial mass allocation \(y\) satisfying continuous \(\alpha\)-EFX and EF1, with
\[ \operatorname{NW}_\infty(y) \ge \frac{1}{\alpha+1} \operatorname{NW}^*_\infty. \]
Here item capacities may be slack. This is arguably the cleaner computational mirror because it omits the completion phase. The paper explicitly says that the algorithm proving Theorem 1 is polynomial-time once a maximum-Nash-welfare allocation is supplied. In the continuous version, the analogous task is to transform a supplied continuous MNW allocation into a type-mass allocation with the stated guarantees.
I expect the transformation itself to be Class A. The end-to-end problem may instead inherit hardness from computing the MNW benchmark: the paper notes that maximum Nash welfare is NP-hard even for additive valuations, although that result is cited rather than stated as a numbered theorem here. Thus the continuous mirror separates two questions: whether the EFX repair becomes easy under high multiplicity, and whether the MNW starting point remains hard.
The useful negative anchor is Theorem 4, proved here:
For every \(0<\alpha\le1\) and \(\beta>1/(\alpha+1)\), there exists an additive instance admitting no allocation, even partial, that is \(\alpha\)-EFX and \(\beta\)-MNW.
The corresponding decision problem is:
Continuous EFX–MNW Tradeoff Feasibility\(_\infty\). Given \(p,q,a,\alpha,\beta\), decide whether there exists a partial or complete mass allocation \(y\) satisfying continuous \(\alpha\)-EFX and
\[ \operatorname{NW}_\infty(y) \ge \beta \operatorname{NW}^*_\infty. \]
I expect the \(1/(\alpha+1)\) frontier to survive whenever the paper’s impossibility gadget can be represented with finitely many repeated valuation types and repeated item copies. That would put this anchor on the hardness-transfer/boundary side rather than the continuum-specific side: the obstruction is the fairness–welfare tradeoff among bundles, not named-agent identity. But this requires checking the actual construction. If its impossibility relies on one-off goods or unique agents and disappears after high-multiplicity replication, that would itself be an informative Class A phenomenon.
The weakest point is that EFX is pointwise while the population is aggregated. A type may be split across several bundles, and continuous EFX then requires every bundle in its support to be compatible with every bundle in everyone else’s support. That support condition is not automatically convex, so a naïve LP relaxation could silently weaken the paper’s question. The other vulnerability is that the paper’s constructive results take an MNW allocation as input; the full continuous problem may still be hard because of the MNW subproblem.
Even with those qualifications, the mirror is credible: it preserves indivisible bundles, exact EFX comparisons, Nash welfare, and the paper’s approximation frontier. It covers the paper’s additive results emphatically, while leaving subadditive valuations as a natural next question rather than stretching the case beyond what the representation can presently support.
The strongest negative case begins with a mismatch in contribution: this paper contains no numbered computational result. Theorems 1–4 are existence, approximation, and impossibility statements. The “computational remarks” only give polynomial-time transformations conditional on a maximum-Nash-welfare allocation; computing that allocation is explicitly left as a separate NP-hard problem, and the hardness is cited rather than proved here. Thus the proposed anchors are not computational results awaiting continuization. They are qualitative guarantees to which one could attach new computational questions.
Theorem 1 is the weakest such attachment. Its algorithm starts from a named-agent MNW allocation \(X\), then repeatedly shrinks particular bundles and matches them to particular agents. In a type-mass model, agents of the same valuation type may occupy many different bundles, so the state is not described by valuation type alone. One must introduce mass variables for type–bundle configurations and track which portions have been “touched” by the repair process. That is a new configuration-allocation problem, not an aggregation of the paper’s algorithm.
There is also a more basic issue. With the paper’s actual resource model—\(m\) indivisible goods and a growing population—a positive fraction of agents eventually receives no good. Since additive valuations give the empty bundle value zero, the continuum Nash welfare becomes zero, and the MNW approximation guarantee is vacuous. The proposed repair, namely replacing each good by \(Nq_g\) identical copies, avoids this degeneracy, but it changes the resource model. It is a plausible high-multiplicity fair-division model, but it is not the high-multiplicity limit of the paper’s fixed set of indivisible goods.
Even in that repaired model, the continuous allocation is not a convex relaxation of the paper’s problem. EFX imposes pairwise conditions on every pair of bundles in the support of \(y\). Feasible allocations therefore form a union of regions indexed by mutually compatible bundle supports; the mass variables are continuous, but the support-selection problem remains discrete. Given an MNW configuration, the paper’s repair may well lift to mass flows. Without that configuration as input, however, the mirror is a new MNW computation problem. Neither option is a computational theorem supplied by this paper.
Theorem 2 does not improve the case. Its distinctive content is the envy-cycle completion step, but that procedure operates on a finite collection of named bundles. A faithful mass version must again refine the state into type–bundle masses and perform fractional cycle operations with careful preservation of support-wide EFX. That could be an interesting project, but it is a new algorithmic treatment of a copied-goods market. The theorem itself supplies only existence; it does not identify a complexity question whose continuous version would illuminate the paper’s contribution.
Theorem 4 is not a computational anchor at all. It proves that certain fairness–welfare combinations are impossible. The proposed continuous decision problem compares a mass allocation with a continuous MNW optimum, but the paper gives neither a hardness result for that decision problem nor an algorithm for its complement. If the impossibility gadget survives replication, it is simply a repeated finite structural obstruction. If mass-splitting changes the obstruction, then the proposed problem requires a new analysis of compatible bundle supports. Either way, Theorem 4 does not furnish a Class B or Class C computational result.
The proponent’s model is therefore not nonsensical. In fact, the copied-item, finite-valuation-type regime is a legitimate high-multiplicity fair-division setting, and identity itself is no obstruction here: EFX and Nash welfare depend on valuations and bundles, not names. That is the point at which the negative case is genuinely weak. Under a broad interpretation of ChoCo, the resulting configuration problem could be worth studying.
Under the programme’s stricter criterion, however, this paper offers no strong mirror. The natural fixed-good continuum degenerates; the nondegenerate repair changes the resource model; and all three anchors are qualitative theorems rather than computational results. I would therefore reject the proposed mirror as insufficiently anchored, while acknowledging that the copied-goods formulation is a plausible new research problem rather than an impossible one.
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.