| paper | EF2X Exists for Four Agents |
| authors | Arash Ashuri, Vasilis Gkatzelis, Alkmini Sgouritsa |
| venue | AAAI 2025 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Given four rational type masses \(\mu_r\), a finite set \(M\) of item kinds with rational per-capita supplies \(b_g\), and four rational cancelable valuations \(v_r\) specified by value tables on \(2^M\), decide whether there exists a rational allocation law \(x_{r,B} \ge 0\) satisfying \(\sum_B x_{r,B} = \mu_r\) and \(\sum_{r,B:g \in B} x_{r,B} = b_g\), such that whenever \(x_{r,B} > 0\) and \(x_{s,C} > 0\), \(v_r(B) \ge \max_{D \subseteq C, |D|=2} v_r(C \setminus D)\), with the maximum defined as \(0\) when \(|C| < 2\).
A four-type high-multiplicity configuration model with valuation-type masses, item-kind supplies, allocation variables \(x_{r,B}\), and pairwise support-EF2X feasibility constraints.
Theorem 1 certifies only the one-bundle-per-type replicated slice; the unrestricted allocation-law version introduces a new many-agent support-selection problem and requires an explicit valuation-encoding model.
fatal: False
The mirror covers the four-agent EF2X existence and pseudo-polynomial construction through its replicated slice and extends EF2X to split type masses; it leaves EFX, the unnumbered three-agent result, and intermediate proof lemmas alone.
The strongest anchor is Theorem 1, proved in this work, although many technical details are deferred to the full version:
“For every instance involving four agents with cancelable valuation functions and any number of goods, there exists an EF2X allocation and we can compute one in pseudo-polynomial time.”
I would not add the paper’s three-agent result as a second anchor: in the supplied version it is stated as an unnumbered theorem, and the internal results such as Theorems 17 and 22 are proof components rather than independent computational problems.
My proposed mirror is Mass-EF2X\(_\infty\). The population consists of four valuation types \(r\in\{1,2,3,4\}\), with rational masses \(\mu_r\) summing to one. A type is a complete cancelable valuation function \(v_r:2^M\to\mathbb Q_{\ge 0}\) over a finite set \(M\) of indivisible good kinds. The population may contain millions of agents, but agents of the same type are indistinguishable with respect to the problem.
Goods are also supplied in high multiplicity. For each good \(g\), the input gives a rational per-capita supply \(b_g\). An individual agent may receive an indivisible bundle \(B\subseteq M\), while the aggregate supply is interpreted in the usual high-multiplicity way: for any sufficiently large \(N\), \(N\mu_r\) agents of type \(r\) and \(Nb_g\) copies of good \(g\) exist.
The action variable is an allocation law
\[ x_{r,B}\ge 0, \]
where \(x_{r,B}\) is the mass of type-\(r\) agents receiving the discrete bundle \(B\). It must satisfy
\[ \sum_B x_{r,B}=\mu_r \]
for every type \(r\), and
\[ \sum_{r,B:g\in B}x_{r,B}=b_g \]
for every good \(g\). Thus \(x\) is not fractional ownership by an individual and not a lottery replacing indivisibility. Every rational solution can be realized exactly by a sufficiently large finite replicated instance in which each agent receives an ordinary indivisible bundle.
The EF2X constraint is imposed pointwise on the realized bundles. Define
\[ \operatorname{best}^{(2)}_{r}(C) = \max_{\substack{D\subseteq C\\ |D|=2}}v_r(C\setminus D), \]
with value \(0\) when \(C\) has fewer than two goods. The allocation law is Mass-EF2X if, whenever \(x_{r,B}>0\) and \(x_{s,C}>0\),
\[ v_r(B)\ge \operatorname{best}^{(2)}_r(C). \]
In words, every positive-mass agent must not EF2X-envy any bundle that is actually assigned to positive mass. The computational task is to find such a rational allocation law, or report that none exists. There is no welfare objective in the original theorem, so this is a feasibility/search problem, equivalently an optimization problem with objective \(\min 0\) subject to these constraints.
This has a plausible high-multiplicity interpretation. Consider a national allocation of standardized relief, education, or household-support packages to millions of recipients. There are four recurring preference profiles, each shared by a large cohort; the available goods are mass-produced copies of a moderate number of standardized item kinds; and the policy requirement is that no recipient should envy another recipient’s package after removing any two items. The ratio is \(N\gg 4\), with only four complete valuation types. This is much closer to a genuine population continuum than four named decision makers, while retaining the paper’s indivisible bundles and individual—not average—fairness guarantee.
The bridge to Theorem 1 is exact on an important embedded slice. Take \(\mu_r=1/4\) and \(b_g=1/4\) for every good. Given a four-agent instance with an EF2X partition \((X_1,X_2,X_3,X_4)\), define \(x_{r,X_r}=1/4\). Replicating this law \(4K\) times gives \(K\) copies of each valuation type and \(K\) copies of every good, with every agent receiving an indivisible bundle. Theorem 1 therefore supplies a pseudo-polynomial algorithm for this homogeneous replicated subcase.
The full Mass-EF2X\(_\infty\) question is richer: a type may be split across several bundles, and the EF2X condition must hold between every pair of bundles in the support. I would expect this unrestricted version to be a plausible Class C boundary problem—possibly hard for continuum-specific reasons—rather than assume that Theorem 1 automatically lifts. The mass variables are continuous, but EF2X is a support property, not a linear average constraint. Choosing a mutually compatible family of positive-mass bundle configurations can introduce combinatorics absent from the four-agent proof. A configuration-LP or column-generation algorithm might still succeed for fixed \(\tau=4\), with cancelability providing the needed pricing structure; establishing that would be a genuinely new Class A result.
The weakest point is clear: Theorem 1 is about exactly four agents, whereas Mass-EF2X\(_\infty\) has many agents and only four valuation types. The theorem proves the replicated one-bundle-per-type slice, not the general allocation law. Requiring every type to receive one common bundle would make the problem easier but would be an artificial symmetry restriction; allowing arbitrary bundle distributions is faithful but may change the complexity fundamentally. That is a real limitation, not merely a technicality.
The mirror nevertheless generates substantive questions: whether EF2X existence survives for four high-multiplicity types under arbitrary rational supplies; whether every feasible law has a bounded-support representative; whether its support-selection problem is NP-hard or admits a configuration-LP separation oracle; and how rational continuous solutions round to finite populations while preserving EF2X or an additive violation bound. These are direct population-continuum questions about the paper’s own fairness notion, not outcome-space continuity disguised as a mirror.
The negative case is weaker than the proponent’s case, but there is one serious line of attack.
Theorem 1 is unquestionably a named computational result, so the “no result to mirror” objection is unavailable. Nor is it credible to say that four valuation cohorts are inherently implausible: standardized packages for large recurring groups are a legitimate high-multiplicity regime.
The strongest objection is that the exact bridge offered is almost tautological. If each type receives one common bundle, then the mass allocation is merely a replicated four-agent partition. EF2X is unchanged by duplicating agents, and the population masses do no work in the fairness condition. The continuous instance is just Theorem 1 with repeated copies and different bookkeeping.
The proposed richer version, allowing a type to split across bundles, does make the masses relevant—but it is no longer a continuization of the paper’s theorem in any close structural sense. The paper asks for one partition into four bundles. The proposed problem asks for a measure over exponentially many bundles, inventory constraints, and a support condition: every positive-mass bundle must be acceptable to every type receiving any bundle. Theorem 1 gives no guidance for this support-selection problem beyond the replicated one-bundle-per-type slice. The mass variables therefore conceal a new discrete configuration problem rather than producing the kind of aggregate linear inequalities that motivate ChoCo.
There are also unresolved formal issues. A “cancelable valuation function” over \(2^M\) is not a specified finite input model; the proposal must choose explicit tables, value oracles, or a succinct subclass such as additive valuations. Explicit tables make the valuation description itself exponential, while additive or symmetric copy-valuations substantially change the paper’s general setting. Scaling the goods as well as the population is also necessary for nontriviality, so this is not purely a population continuization.
That said, this does not defeat the best possible mirror. A carefully encoded many-agent, repeated-type EF2X problem with standardized goods could be a worthwhile new fair-division problem, and its support-selection complexity might genuinely be interesting. The honest conclusion is therefore that the negative case cannot establish “no worthwhile mirror in any scenario.” It can show only that the proponent’s exact replication is not itself a substantive continuous result; the stronger proposed mirror remains viable.
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.