| paper | The Frontier of Intractability for EFX with Two Agents |
| authors | Paul W Goldberg, Kasper Høgh, Alexandros Hollender |
| venue | SAGT 2023 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 4.2
statement extracted from the paper’s text layer
Given a succinct monotone submodular valuation \(v:2^M\to\mathbb{Q}_{\ge 0}\) for one unit-mass type and per-capita supply \(b_g=\tfrac12\) for every good \(g\in M\), find an explicitly represented finite-support distribution \(\lambda_X\) over integral bundles \(X\subseteq M\) satisfying \(\sum_X\lambda_X=1\), \(\sum_{X:g\in X}\lambda_X=\tfrac12\), and \(v(X)\ge v(Y\setminus\{g\})\) for every pair of supported bundles \(X,Y\) and every \(g\in Y\).
A one-type high-multiplicity society with mass variables \(\lambda_X\) over integral bundles, indivisible per-agent goods, per-capita catalogue supplies \(b_g=\tfrac12\), and EFX as a support-wide feasibility condition; the task is to find \(\lambda\), with no welfare objective.
A feasible mass distribution need not contain a complementary pair of bundles, so the paper's Kneser reduction does not automatically yield PLS-hardness for the continuous problem.
fatal: False
The mirror covers the EFX search results in Theorems 4.2 and 3.1, including the submodular hardness and weakly well-layered algorithmic cases. It leaves aside the PLS-membership machinery, auxiliary valuation-class lemmas, and the paper's non-mirror background results.
My strongest positive case is a high-multiplicity fair-division mirror in which the agents become continuous, while goods remain indivisible for every individual agent.
Let \(M\) be a finite catalogue of good kinds. A type \(t\) is a complete valuation \(v_t:2^M\to\mathbb{Q}_{\ge 0}\), including all information relevant to that agent. The society is a distribution \(\mu\) over finitely many such types, with \(\mu_t\) the fraction of agents of type \(t\). To scale the goods with the population, let \(b_g\) be the number of copies of good \(g\) per unit population. In a finite realization with \(N\) agents there are \(Nb_g\) indivisible copies of \(g\).
An aggregate allocation is a collection \(\lambda_{t,X}\ge 0\), where \(\lambda_{t,X}\) is the mass of type-\(t\) agents receiving the integral bundle \(X\subseteq M\). It must satisfy
\[ \sum_X\lambda_{t,X}=\mu_t \]
and
\[ \sum_{t,X:g\in X}\lambda_{t,X}=b_g. \]
Thus \(\lambda\) is fractional only at the population level: no individual receives a fractional good.
The allocation is EFX if, whenever \(\lambda_{t,X}>0\) and \(\lambda_{u,Y}>0\),
\[ v_t(X)\ge v_t(Y\setminus\{g\}) \qquad\text{for every }g\in Y. \]
The computational task is to output such a mass allocation, represented by its supported integral bundles. This is a genuine high-multiplicity regime: \(N\) can be enormous while the number of valuation types \(\tau\) is small. A particularly natural case has \(\tau=1\): a large population of exchangeable households with the same valuation over a catalogue of indivisible assets.
My lead anchor is Theorem 4.2, proved in this paper. It states:
Computing an EFX allocation for two identical agents with a submodular valuation function is PLS-hard.
The hardness is for the search problem itself, not merely for evaluating a valuation. The paper constructs a monotone submodular valuation from a local-search instance on an odd Kneser graph, and then obtains the Kneser hardness from the PLS-complete Flip problem. The paper’s Theorem 4.1, also proved here, supplies PLS membership for the circuit-defined Identical-EFX problem, allowing either an EFX allocation or a certificate that the circuit violates monotonicity. Thus the abstract’s PLS-completeness claim is not being inferred from Theorem 4.2 alone; Theorem 4.2 is formally the hardness half.
The corresponding continuous problem is:
Mass-EFX\(_\infty\)-Submodular. Given a monotone submodular valuation \(v:2^M\to\mathbb{Q}_{\ge0}\) represented by a succinct circuit, a unit-mass population of identical agents, and \(b_g=\tfrac12\) copies of every good kind \(g\) per unit population, find a finite-support distribution \(\lambda_X\) over integral bundles such that
\[ \sum_X\lambda_X=1, \qquad \sum_{X:g\in X}\lambda_X=\frac12 \]
for every \(g\), and
\[ v(X)\ge v(Y\setminus\{g\}) \]
for every two supported bundles \(X,Y\) and every \(g\in Y\).
The supply vector is the natural high-multiplicity version of the two-agent instance: in a finite realization with \(N\) even, there are \(N\) identical agents and \(N/2\) copies of every good. A two-bundle allocation \((X,Y)\) from the paper becomes the mass allocation \(\lambda_X=\lambda_Y=\tfrac12\). But the continuous problem does not require support on only two bundles; it permits any population-level mixture of integral bundles. That is precisely why it is a real mirror rather than a restatement.
I would initially expect this problem to be Class B, with hardness transferring. The reduction’s combinatorics live in the goods and in the submodular valuation over bundles, not in the number of agents. Passing from two agents to a large homogeneous population does not obviously remove the Kneser/local-search obstruction. The important open issue is whether an arbitrary mass mixture gives the continuum solver an escape route: can a distribution over many EFX-compatible bundles be found easily even though selecting one discrete pair is PLS-hard? Proving that every legal mass solution yields, or can be rounded to, a locally optimal Kneser solution would establish the transfer.
A second, algorithmic anchor is Theorem 3.1, proved in the paper. It states that if \(v\) is weakly well-layered, then Algorithm 1 produces an EFX allocation for any number of identical agents. The algorithm repeatedly gives a remaining good to a currently least-valued bundle, choosing the good that maximizes the recipient’s resulting value. The theorem also says that cut-and-choose then gives an EFX allocation for two agents with different valuations whenever one valuation is weakly well-layered. By Lemma 1, gross-substitutes valuations are weakly well-layered, and by Corollary 1, budget-additive valuations are as well.
Its continuous counterpart is Mass-EFX\(_\infty\)-WWL, the same mass-allocation problem under the promise that the common valuation is weakly well-layered. Run the paper’s greedy algorithm on two virtual bundles to obtain an EFX partition \((X,Y)\), then assign mass \(\tfrac12\) to \(X\) and mass \(\tfrac12\) to \(Y\). Every physical agent still receives an integral bundle, and all population-level comparisons reduce to the two-bundle EFX inequalities. I therefore expect this promise version to be Class A, with gross substitutes and budget-additive valuations as important tractable subclasses.
The mirror covers only the paper’s EFX search results, especially Theorem 4.2 and Theorem 3.1. It does not claim to continuize EF1, cake cutting, welfare optimization, or the leximin++ objective.
The weakest point is that the mass vector \(\lambda\) may look like outcome-space fractionalization, and the hard two-agent reduction may be hiding inside a vanishingly small part of a large population. I would not claim that PLS-hardness automatically transfers. The case for the mirror is instead that the model keeps individual bundles and EFX comparisons completely discrete, while making only the population multiplicities continuous. Whether mass mixing dissolves the hardness is exactly the substantive computational question the continuization programme should ask.
The strongest case against the proposed mirror is that EFX does not make population mass computationally native. In the hard anchor, there is only one type, so \(\mu=(1)\). The vector \(\lambda\) merely mixes integral bundles across cloned agents. Its magnitudes do not enter fairness: a bundle used by mass \(10^{-12}\) is treated exactly like one used by mass \(1/2\), provided its mass is positive. Thus the continuum contributes a support condition, not a population-level EFX notion.
There is also a genuine limiting ambiguity. If the original finite set of goods is kept fixed while the number of agents grows, agents receiving goods have vanishing mass and an almost-everywhere EFX condition can become vacuous. If goods are scaled proportionally, as the proponent proposes, one has changed the problem into a multi-unit allocation problem with typed copies and an additional restriction that an agent receives at most one copy of each kind. That is a defensible new model, but it is not simply the paper’s two-agent instance viewed continuously. A mass-weighted or almost-everywhere fairness notion would avoid this, but it would no longer be EFX.
This weakens the proposed reading of Theorem 4.2. The PLS reduction concerns choosing one discrete EFX partition. A distribution over many bundles need not contain a complementary pair, so its feasibility is not obviously tied to the Kneser local optimum. The proposed continuous problem is therefore not a clean high-multiplicity form of the theorem; it is a different support-feasibility problem whose connection to the paper’s reduction is unproved.
Theorem 3.1 fares no better as a source of a new continuous problem. Its algorithm already handles arbitrarily many identical agents, and a two-bundle output immediately gives a mass allocation by assigning the two bundles equal mass. The continuous formulation adds no population-sensitive fairness constraint or objective. It is therefore difficult to identify what computational phenomenon from the theorem is being continuized.
That is the best negative case, but it is not decisive under the programme’s rules. The paper explicitly supplies the evidence that identical agents are a sensible high-multiplicity regime, and the typed-copy model can be made perfectly coherent by treating goods as catalogue items with per-agent unit capacity. The question whether allowing a population mixture makes EFX easier is then a legitimate Class A/B question, not an objection based on the answer. Existing many-agent results are supporting evidence, not a collision.
So I cannot honestly sustain the universal claim that no worthwhile mirror exists. The proposed formulation needs sharper semantics for copies, support, and exact output representation, but Theorem 4.2 survives as a credible continuous-population anchor. The negative case is consequently weak.
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.