| paper | EF1 and EFX Orientations |
| authors | Argyrios Deligkas, Eduard Eiben, Tiger-Lily Goldsmith, Viktoriia Korchemna |
| venue | IJCAI 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 a finite set of repeatable item classes \(A\), complete agent types \(\Theta\), rational type masses \(\mu\), rational per-capita inventories \(\rho\), and succinct monotone valuations \(V_t\) on integral bundles of class copies, find a finitely supported rational table \(z_{t,B}\) satisfying \(\sum_B z_{t,B}=\mu_t\) and \(\sum_{t,B}z_{t,B}b_a(B)=\rho_a\), with \(B\subseteq A_t\) whenever \(z_{t,B}>0\), such that every two supported cells satisfy EF1: \(z_{t,B},z_{u,B'}>0\) implies \(\exists a\in B'\) with \(V_t(B)\ge V_t(B'\setminus\{a\})\).
A population-scaled indivisible-goods model in which \(\mu_t\) is the mass of type \(t\), \(z_{t,B}\) is the mass receiving integral bundle \(B\), \(\rho_a\) is per-capita supply, and orientation remains \(B\subseteq A_t\).
With the paper's literal finite set of named goods the continuum is degenerate, while the proposed \(N\rho_a\) copies and valuation-on-multisets lift are additional assumptions, and support-wise EF1 may require exponentially many bundle states rather than a \(\tau\)-type compression.
fatal: False
It directly mirrors Theorem 1 and gives restricted high-multiplicity variants of Corollaries 1 and 3; it leaves Theorem 2, the EFX hardness results in Theorems 3 and 4, and the slim-tree-cut-width result in Theorem 5 aside.
The strongest mirror is for Theorem 1, proved in this paper: when valuations are monotone, an EF1 orientation always exists and can be computed in pseudopolynomial time \(O(mn^3r)\), where \(r\) is the largest valuation range.
The right continuous object is not a fractional allocation of goods. It is a population measure over agents who still receive indivisible bundles. Let \(\Theta\) be a finite set of complete agent types. A type \(t\) specifies its monotone valuation \(V_t\) and its relevant-item set \(A_t\). The society is a rational distribution \(\mu\in\mathbb{Q}_{\ge 0}^{\Theta}\), with \(\sum_t\mu_t=1\). In the intended regime, there are \(N\) agents, \(N\mu_t\) of type \(t\), with \(N\) much larger than \(|\Theta|=\tau\).
To keep the goods indivisible, take a finite catalogue of item classes with a fixed per-capita inventory profile \(\rho\). At scale \(N\), this means \(N\rho_a\) distinct physical copies of item class \(a\); every individual still receives an integral bundle. A continuous allocation is a bundle-frequency table \(z_{t,B}\), where \(z_{t,B}\) is the mass of type-\(t\) agents receiving the whole bundle \(B\). It must satisfy
\[ \sum_B z_{t,B}=\mu_t \]
for every \(t\), and
\[ \sum_{t,B} z_{t,B}\,b_a(B)=\rho_a \]
for every item class \(a\), where \(b_a(B)\) is the number of copies of \(a\) in \(B\). Orientation requires \(B\subseteq A_t\) whenever \(z_{t,B}>0\).
Call this problem Mass-EF1-Orientation\(_\infty\). It asks whether such a table exists in which, for every two positive-mass cells \((t,B)\) and \((u,B')\), there is an item \(a\in B'\) such that
\[ V_t(B)\ge V_t(B'\setminus\{a\}). \]
Thus EF1 is imposed on actual whole bundles, not on fractional goods. If \(z\) is rational, multiplying by a common denominator produces a finite allocation of \(N\) cloned agents and \(N\rho_a\) indivisible goods. Conversely, finite high-multiplicity allocations yield such frequency tables. This is the appropriate high-multiplicity bridge.
A plausible setting is a national benefits or training allocation: millions of recipients, but only a few dozen or hundred complete eligibility-and-preference types. Goods might be physical assistance packages, course seats, or certification slots. Agents of the same type genuinely have the same valuation, eligibility, and other relevant parameters. The orientation constraint says that a package is assigned only to an eligible recipient type. This is a direct population-scale version of the paper’s question, not a change from allocation to lotteries.
I would expect Mass-EF1-Orientation\(_\infty\) to be Class A at least for bounded valuation range or bounded numbers of relevant items. Theorem 1’s essential invariant is a finite potential over valuation levels, not the identities of individual agents. In a high-multiplicity instance, one should be able to quotient the envy-cycle procedure by type and bundle-frequency classes. The paper’s Corollary 1, also proved here, strengthens this case: with at most \(\ell\) relevant items per agent, the discrete algorithm runs in \(O(mn^3 2^\ell)\). The continuous questions are whether the dependence on \(n\) can be replaced by dependence on \(\tau\), and whether exact policies can be found in time polynomial in \(m,\tau,\ell\), and the encoding length.
This mirror covers the paper’s central positive result. It also generates nontrivial follow-up questions: can a continuous EF1 policy be rounded while preserving EF1, or only approximate EF1? Is there always a policy with support polynomial in \(m+\tau\)? Does the pseudopolynomial dependence on valuation range disappear under high multiplicity, or is it a genuine bit-complexity barrier?
A second, more structured mirror is anchored in Corollary 3, proved here: with laminar agent lists, an EF1 orientation can be computed in \(O(m^2n)\). Define the type-level eligibility list of item \(a\) by
\[ E_a=\{t\in\Theta:a\in A_t\}. \]
Require the \(E_a\) to be laminar: for any two items, their eligible type sets are disjoint or one contains the other. The continuous problem, Laminar Mass-EF1-Orientation\(_\infty\), is exactly Mass-EF1-Orientation\(_\infty\) under this restriction.
This has a particularly credible regime: a large workforce or student population organized by nested certification levels. General-purpose goods are available to every cohort, while specialized goods are available only to progressively smaller trained groups. Since the laminar structure is preserved when type blocks are expanded into many cloned agents, this is not merely an analogy to Corollary 3. The paper’s item-ordering argument should aggregate naturally over those blocks. I would expect this version to be Class A, probably with a type-compressed algorithm polynomial in \(m\), \(\tau\), and the valuation encoding.
I would not use Theorems 3 or 4 as primary anchors. Their hardness is driven mainly by carefully chosen item weights and, in Theorem 4, even a constant number of agents; that is weak evidence for a population-continuous mirror. Theorem 5 is more promising, but its graph adjacency structure is not captured by a population distribution alone, so it needs a substantially richer networked continuation.
The weakest point is that EF1 is a support-wise, disjunctive condition rather than a linear constraint. Consequently, the bundle-frequency table is not immediately an LP of the kind used in the bribery programme, and the paper’s pseudopolynomial algorithm does not by itself yield a polynomial algorithm in \(\tau\). Moreover, a nondegenerate continuum requires a plausible high-multiplicity supply regime; with a fixed finite set of one-copy goods and an ever-growing population, most agents simply receive nothing. That limits the claim: this is not a universal continuous mirror for all fair-division instances. It is, however, a sensible and faithful mirror for large repeated allocations with many agents, few complete types, and indivisible goods supplied at population scale.
The strongest objection is not that the proposed \(z_{t,B}\) model is incoherent. It is coherent. The objection is that it becomes nontrivial only after changing the paper’s problem in two substantial ways: scaling the item supply with the population, and replacing arbitrary valuations on named goods by valuations on repeatable item classes.
With the paper’s literal finite item set \(A\), a continuum population is degenerate. At most \(|A|\) agents receive nonempty bundles, so every nonempty bundle has population mass zero. The positive-mass allocation therefore consists almost entirely of empty bundles, and EF1 becomes vacuous on the atomless population. The exceptional named recipients carrying the goods disappear from the mass description.
The proposed repair—\(N\rho_a\) copies of each item class—is sensible for course seats or standardized aid packages, but it is not a high-multiplicity encoding of the paper’s arbitrary instance. The paper gives a valuation \(V_i\) on subsets of a finite set of named goods. It does not provide a canonical way to lift \(V_i\) to multisets of cloned goods. Additivity, symmetry between copies, bounded bundle sizes, and per-capita supply are additional modelling assumptions. They may define a good new problem, but they are not consequences of Theorem 1.
The second difficulty is more fundamental. EF1 is not determined by the mass assigned to a type or by average utilities. It is a support-wise condition:
\[ z_{t,B}>0,\ z_{u,B'}>0 \quad\Longrightarrow\quad \exists a\in B'\; V_t(B)\ge V_t(B'\setminus\{a\}). \]
Thus the continuous object must retain the entire distribution of integral bundles. If one merges all agents of type \(t\) into a single average bundle, one has fractionalized the outcome and changed EF1. If one preserves the whole-bundle semantics, there may be exponentially many configuration cells \(B\) per type. The problem is then not a mass LP of the sort central to the continuization programme: after the compatible bundle supports have been selected, mass balancing is easy, but selecting a globally EF1-compatible support is the hard combinatorial problem.
That defeats the claimed transfer of Theorem 1. Its algorithm maintains an envy graph on named agents and a potential vector
\[ \bigl(V_1(\pi_1),\ldots,V_n(\pi_n)\bigr). \]
Agents of one valuation type can occupy different bundles, and hence have different utilities and different envy edges. Merging them destroys exactly the state information used by the proof. Splitting them back into bundle-state cells restores fidelity, but then the number of states is no longer controlled by the number \(\tau\) of ex ante types. The theorem gives no compact support bound, separation oracle, or type-level implementation.
Corollary 1 is even less transferable than the proponent suggests. Its parameter \(\ell\) is the number of relevant physical items per agent. Once item supply is replicated, a type may be relevant to \(N\) copies, so the relevant-item count is \(N\), not a fixed \(\ell\). Calling an entire item class one “relevant item” changes the definition. Keeping \(\ell\) fixed instead means keeping only finitely many goods, returning to the empty-bundle degeneracy. The continuous question can still be posed with class-level relevance, but it is then a new bounded-configuration model rather than Corollary 1’s stated regime.
The same problem affects Corollary 3. Laminarity of the type-level eligibility sets \(E_a\) survives cloning, but the proof’s key operation is still an item-by-item ordering followed by individual cycle elimination. With \(N\rho_a\) copies, the literal algorithm runs on the expanded instance. Compressing identical copies requires solving the support-selection problem above. Laminar eligibility controls which agents may receive an item; it does not control arbitrary monotone valuations or the number of mutually compatible bundle configurations. Therefore laminarity alone does not yield the proposed polynomial dependence on \(m\) and \(\tau\).
The proponent is right about one important point: this is not refuted merely by saying “the answer might be the same,” and a replicated course-allocation or benefits-allocation model could be a legitimate high-multiplicity fair-division project. Rational bundle frequencies do pass the clone test. But that strongest rescue is an extension with repeatable commodities, symmetric valuation lifts, scaled resources, and a new support-selection problem. The paper’s named theorems do not establish that this problem has a useful continuous algorithmic structure.
So the negative case is strong against a direct mirror of Theorem 1, Corollary 1, or Corollary 3. It is not an airtight universal impossibility claim: if ChoCo accepts a carefully specified replicated-goods extension as worthwhile in its own right, the proponent has found a credible candidate.
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.