| paper | Almost Full EFX Exists for Four Agents |
| authors | Ben Berger, Avi Cohen, Michal Feldman, Amos Fiat |
| venue | AAAI 2022 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper contains no numbered theorem, lemma, or corollary asserting an algorithm, complexity classification, approximation guarantee, or parameterized result. The proposed mass-allocation EFX problem is a plausible new research question, but it adds the computational layer rather than continuizing one supplied by this paper. Thus bit (a) fails even if the high-multiplicity model is recognizable as an EFX extension.
fails bit a — no named computational result to mirror
The proposed mirror covers a high-multiplicity additive EFX allocation problem with replicated item supplies, but none of the paper's named results becomes a computational result; the finite-agent structural proof and related guarantees remain uncovered.
The strongest honest positive case is qualified. This paper has no qualifying computational anchor: Theorem 1, proved here, is an existence theorem; Theorem 4.1, also proved here, is a structural progress theorem; and Lemma 3.4 is a structural implication from a Pareto-improvable cycle to an EFX allocation. None asserts membership in \(P\), NP-hardness, fixed-parameter tractability, or even an algorithm. Thus I cannot honestly claim that this paper demonstrates discrete computational hardness dissolving under continuization.
There is nevertheless a credible population mirror. My lead structural anchor is Theorem 1:
Every setting with four additive agents admits an EFX allocation with at most a single unallocated item, which is not envied by any agent.
A plausible high-multiplicity regime is a large institution assigning standardized indivisible benefits—devices, course places, rooms, or service slots—to a large population. Agents with the same additive value for every item category, and the same relevant constraints, form one type. If \(T\) is the finite set of valuation types, \(\mu_t\) is the fraction of agents of type \(t\), and \(N\) is large while \(|T|\) is small, this is exactly the intended population regime. The individual agents remain distinct in a finite realization, but agents of the same type are interchangeable.
The continuous problem I would propose is Almost-Full EFX\(_\infty\). Its instance consists of a finite item catalogue \(M\), additive valuation vectors \(v_t:M\to\mathbb{Q}_{\ge0}\) for \(t\in T\), a population distribution \(\mu\in\Delta(T)\), per-capita supplies \(q_g\in\mathbb{Q}_{\ge0}\) for \(g\in M\), and a threshold \(\eta\ge0\). A solution is a collection \(x_{t,B}\ge0\), for \(t\in T\) and \(B\subseteq M\), where \(x_{t,B}\) is the mass of type-\(t\) agents receiving bundle \(B\). It must satisfy
\[ \sum_{B\subseteq M}x_{t,B}=\mu_t \]
for every \(t\), and
\[ \sum_{t\in T}\sum_{B\ni g}x_{t,B}\le q_g \]
for every item \(g\). Let \(u_g\) be the unused supply and \(U=\sum_g u_g\). The allocation is EFX if, whenever \(x_{t,B}>0\) and \(x_{t',B'}>0\),
\[ v_{t'}(B\setminus\{g\})\le v_{t'}(B') \]
for every \(g\in B\). The decision question is whether an EFX solution exists with \(U\le\eta\); the optimization version minimizes \(U\).
This is a genuine high-multiplicity relaxation rather than divisible-goods fair division. If all data have denominator \(N\), then \(N\mu_t\) agents and \(Nq_g\) indivisible copies of item \(g\) give a discrete realization, while \(Nx_{t,B}\) gives the number of type-\(t\) agents receiving \(B\). Conversely, a discrete allocation normalizes to such a mass allocation. The analogue of “one unallocated item” is a threshold \(U\le 1/N\), or, in the limit, asking whether \(U=0\).
The original authors would probably recognize this as the same EFX problem: the valuations remain additive, bundles remain indivisible, and the EFX inequalities are unchanged. What changes is only the population representation. The scenario is also plausible: repeated valuation profiles arise naturally when institutions use standardized preference or utility classes.
My expectation is cautiously optimistic but not a claim about the paper’s theorem. With a bounded item catalogue and bounded number of types, the problem is a finite disjunction of linear programs over bundle configurations, hence fixed-parameter tractable by enumerating compatible supports. For unrestricted \(|M|\), the choice of mutually EFX-compatible bundles may retain substantial combinatorial difficulty; the interesting boundary could be either transferred hardness or continuum-specific hardness. A pricing or configuration-LP formulation would be the natural next step.
The weakest point is decisive: Theorem 1 concerns exactly four agents, not a large population, and its proof is existential rather than algorithmic. Replacing four agents by four valuation types with positive mass is not an immediate consequence of the theorem. The normalization also changes “one item” into vanishing unallocated mass. So this is a credible research question motivated by the paper, not a computational result already established by it.
The most relevant follow-up questions are whether Theorem 1 lifts to repeated valuation types, whether the champion-graph and Pareto-improvement arguments can be defined on type–bundle support classes, and whether Almost-Full EFX\(_\infty\) is tractable, hardness-preserving, or genuinely continuum-specifically hard.
The negative case is strongest before modelling begins: this paper has no qualifying computational anchor. Theorem 1 is an existential theorem for exactly four agents; Theorem 4.1 is a progress lemma inside its proof; and Lemma 3.4 is a certificate that a particular finite graph configuration yields a better allocation. None defines a computational problem or asserts a complexity, approximation, or algorithmic result. The proposed continuous problem therefore adds the computational layer itself. That may motivate a new fair-division project, but it is not a continuization of a computational result from this paper.
The proposed mirror also does not preserve the content of Theorem 1. Replacing four agents by four valuation types with positive masses produces many agents, not four agents. If \(N\) clones of each type are present, the instance has \(4N\) agents, and EFX is still quantified over every clone and every bundle it receives. The four-agent theorem does not apply. If all clones of a type are forced to receive one common bundle, that is an additional symmetry restriction, not a high-multiplicity consequence. If clones may split across bundles, as in \(x_{t,B}\), the relevant objects are type–bundle support classes, potentially many of them, rather than the four vertices of the paper’s champion graph.
The proof machinery has the same problem. Its lexicographic potential depends on an arbitrary ordering of four named agents. There is no canonical first agent in a nonatomic population, and a positive-mass type may receive several bundles. One could replace the potential by a mass-weighted, Lorenz, or type-level potential, but that would be a new theorem with new proof obligations, not a continuous form of Theorem 4.1 or Lemma 3.4.
The “one unallocated item” guarantee also degenerates under the proposed normalization. With a fixed finite set \(M\) of indivisible goods, a continuum population leaves almost everyone with the empty bundle, so the population limit is not meaningful. To avoid that, one must replicate each good \(N\) times or introduce per-capita supplies \(q_g\). But then one leftover physical item has normalized mass \(1/N\), which converges to zero. The theorem’s conclusion becomes \(U=0\), namely full EFX, while the accompanying claim that no agent envies the remaining item disappears because the item has vanished from the limit. Choosing a fixed \(\eta>0\) instead permits \(\Theta(N)\) unallocated goods and is a new waste-tolerance problem; choosing \(\eta=1/N\) reintroduces the finite-\(N\) problem rather than a continuous one.
The standardized-device scenario is not nonsensical. Identical valuation types and replicated supplies are a legitimate high-multiplicity regime, and I am not objecting to aggregation losing individual prices or identities. The weakness is that every repaired version changes at least one central ingredient: four agents become an arbitrary population, unique goods become replicated categories, “one item” becomes a per-capita waste threshold, and the existential statement becomes a newly invented optimization problem. That is too much remodelling to count this paper as supplying a worthwhile continuous mirror under the programme’s standard.
So the honest negative verdict is qualified but firm: this paper should not be selected as a continuization anchor. A continuous EFX problem might independently be worth studying, and that is the residual weakness in the negative case. But the paper itself contributes no computational question whose population continuization can be charted.
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.