| paper | Understanding EFX Allocations: Counting and Variants |
| authors | Tzeh Yuan Neoh, Nicholas Teh |
| 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 4.3
statement extracted from the paper’s text layer
Given finite item kinds \(G\), agent types \(T\), rational masses \(\mu_t\), entitlements \(w_t>0\), binary values \(a_{t,g}\in\{0,1\}\), and rational per-capita supplies \(\rho_g\), where a bundle is an indivisible-copy vector \(b\in\mathbb{Z}_{\ge0}^{G}\), find a rational sparse configuration \(x_{t,b}\ge0\) satisfying \(\sum_b x_{t,b}=\mu_t\) and \(\sum_{t,b}b_gx_{t,b}=\rho_g\). Require that every pair of supported type-bundle pairs satisfies WEFX after removing any one copy, and that the configuration is PO under identity-preserving measurable reallocations; determine whether such a configuration can be computed in time polynomial in \(|T|+|G|\) and the input bit length, independently of the common denominator.
A capacitated high-multiplicity fair-division model with type masses \(\mu_t\), binary additive values \(a_{t,g}\), entitlements \(w_t\), and indivisible-copy supplies \(\rho_g\). The decision variables are configuration masses \(x_{t,b}\) over integer bundles \(b\), and the objective is to compute one configuration satisfying exact support-wise WEFX and PO.
The support-wise WEFX constraints are support-sensitive and potentially nonconvex, and the paper does not establish that its matching or leximin proof lifts to capacitated item supplies with a sparse, bit-polynomial configuration.
fatal: False
The mirror covers Theorem 4.3's polynomial computation of WEFX and PO allocations; it leaves the EFX counting and allocation-count bounds, the nonexistence propositions, Theorem 4.8's approximation result, and the EFX+ results untreated.
The strongest positive case is narrower than “the whole paper continuizes.” My lead anchor is Theorem 4.3:
“Under binary additive valuations, for any number of agents, a WEFX and PO allocation exists and can be computed in polynomial-time.”
This is proved in the paper, not merely cited.
A natural high-multiplicity setting is a large course-allocation or food-bank market. There are \(N\) agents, but only finitely many complete types: a type records the agent’s binary additive valuation vector and entitlement \(w_t\). Thus two agents have the same desired item categories, the same entitlement, and no other allocation-relevant difference. If \(\mu_t\) is the fraction of the population of type \(t\), then \(|T|=\tau\ll N\). The goods are also in a repeated-item regime: \(g\in G\) is an item kind with \(\rho_g\) copies per unit population. For example, many course seats may be interchangeable for valuation purposes, while each individual seat remains indivisible.
My continuous problem is:
\[ \mathrm{WEFX\mbox{-}PO}_\infty^{\mathrm{bin}}. \]
An instance consists of a finite item-kind set \(G\), a finite type set \(T\), rational masses \(\mu_t\) with \(\sum_t\mu_t=1\), rational entitlements \(w_t>0\), binary values \(a_{t,g}\in\{0,1\}\), and rational per-capita supplies \(\rho_g\). An integral bundle is \(B\subseteq G\), with
\[ v_t(B)=\sum_{g\in B}a_{t,g}. \]
The decision variable is a configuration \(x_{t,B}\ge 0\), meaning the mass of type \(t\) receiving bundle \(B\). It must satisfy
\[ \sum_B x_{t,B}=\mu_t \]
for every \(t\), and
\[ \sum_{t,B:g\in B}x_{t,B}=\rho_g \]
for every item kind \(g\). Thus \(x\) is an aggregate assignment of agents to integral bundles; it does not give an individual a fractional good.
The configuration is WEFX if, whenever \(x_{t,B}>0\) and \(x_{s,D}>0\), then for every \(g\in D\),
\[ \frac{v_t(B)}{w_t} \ge \frac{v_t(D\setminus\{g\})}{w_s}. \]
It is PO if there is no other measurable allocation of the same item supplies that makes almost every individual weakly better off and makes a positive-mass set strictly better off. The problem is to output a rational, preferably sparse, configuration satisfying both WEFX and PO.
This is recognisably the authors’ problem: the valuation class, entitlement comparison, WEFX predicate, complete allocation requirement, and Pareto criterion are unchanged. Only the agent list is replaced by masses of exchangeable clones, and item supplies are scaled jointly so that the indivisibility does not disappear.
The high-multiplicity bridge is exact for rational data. Given a common denominator \(N\), create \(N\mu_t\) identical agent clones of type \(t\) and \(N\rho_g\) distinct copies of item kind \(g\). A rational configuration \(x\) becomes an ordinary finite allocation by assigning \(Nx_{t,B}\) clones to bundle \(B\). Conversely, every such finite allocation compresses to a configuration. Because WEFX is imposed support-wise on every pair of bundles that actually occurs, this is not an average-utility or lottery relaxation. Each finite clone still receives an indivisible bundle, and the finite WEFX inequalities are exactly the displayed inequalities above.
I expect this problem to be Class A. The paper’s matching-based construction and weighted-leximin argument should have capacitated versions in which individual agents are replaced by type masses. The desired complexity target is polynomial in \(|T|+|G|\) and the encoding length of the rational data, independent of the denominator \(N\). The main algorithmic task is to establish a sparse configuration representation and implement the relevant matching or leximin steps with capacities rather than explicitly expanding all clones.
This mirror covers only Theorem 4.3. I would not anchor on Theorem 3.3, despite its importance, because “count the number of EFX allocations” has no canonical atomless replacement: one would have to introduce entropy, configuration volume, or a finite-denominator counting scheme, each of which changes the paper’s computational question. Likewise, Theorem 4.8 and Propositions 4.6–4.7 concern \(n=2\), so they do not themselves provide a population-scalable anchor.
The further questions are substantial: does the capacitated algorithm really run polynomially in \(\tau\) rather than in the expanded clone population; can every rational solution be rounded to a finite allocation with a controlled WEFX loss; and do the nonexistence phenomena for binary submodular or restricted additive valuations survive in a genuinely many-type continuum?
The weakest point is that this is an extension of the paper’s instance regime, not a literal limit with a fixed collection of one-off goods. If the authors insist that only agents may be replicated while every good remains unique, complete allocation becomes ill-posed as the population grows. The positive case therefore depends on accepting repeated item copies and support-wise bundle allocations as the appropriate high-multiplicity form of their fair-division problem. That dependence is real, but the resulting model is still close to their definitions and passes the rational-clone test.
The strongest negative case targets Theorem 4.3, since the paper’s other results do not offer a scalable computational anchor. Theorem 3.3 counts allocations, while Theorem 4.8 fixes \(n=2\); the remaining propositions are existence or impossibility statements rather than complexity results.
If only the population is continuized, the model degenerates. With \(m\) fixed indivisible goods and \(n\to\infty\), at most \(m\) agents receive nonempty bundles. Almost the entire population receives nothing, so either WEFX is imposed on a vanishing set of exceptional recipients, or an “almost-everywhere” interpretation makes the constraints involving those recipients disappear. Neither is the paper’s finite-agent WEFX problem in a meaningful population limit.
The proponent’s repair—scaling item supplies as well and replacing goods by repeated item kinds—is much stronger. Its rational-clone correspondence is exact, provided bundles are represented by item multiplicity vectors rather than subsets. Thus it cannot be dismissed as fractional allocation. But it is no longer merely a continuous population version of the paper’s problem: it is a new capacitated fair-division problem in which both agents and resources have been replicated.
More importantly, exact WEFX does not aggregate smoothly. For a configuration \(x_{t,B}\), every pair of bundles in its support must satisfy the WEFX inequalities. Mixing two individually valid allocations can introduce cross-pairs that violate WEFX. Hence the aggregate feasible set is support-sensitive and generally nonconvex. If one replaces this by an average or expected WEFX condition, one obtains a different fairness notion; if one retains the support condition, \(x\) is essentially a compressed description of a large finite allocation, not an atomless fairness constraint amenable to the programme’s usual LP intuition. The claimed polynomial dependence on \(\tau\), item kinds, and binary-encoded capacities—and the existence of a succinct support—therefore do not follow from Theorem 4.3 or its matching proof.
The counting result supplies no better rescue. In an atomless population, the literal number of allocations is typically either uncountable or representation-dependent. Counting finite-denominator configurations gives a sequence of discrete problems; entropy, volume, or a partition function would be interesting new statistical-mechanical questions, but none is a canonical mirror of Theorem 3.3.
This is nevertheless not an airtight negative case. The course-seat or food-bank regime is genuinely plausible, and the rational-clone test establishes a sensible high-multiplicity object. The programme explicitly treats such high-multiplicity reformulations as legitimate. Consequently, the argument defeats the literal fixed-good limit and the proponent’s unproved claim that the algorithm automatically scales, but it does not defeat the better repeated-item mirror. The honest verdict is that the paper is a weak source for a broad continuization programme, yet Theorem 4.3 probably survives as one worthwhile high-multiplicity research question.
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.