| paper | Epistemic EFX Allocations Exist for Monotone Valuations |
| authors | Hannaneh Akrami, Nidhi Rathi |
| 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.8
statement extracted from the paper’s text layer
Given rational masses of valuation types, rational capacities of finitely many indivisible item kinds, and value-oracle access to each type valuation, output an aggregate allocation x over whole bundles B⊆G satisfying type and capacity marginals, together with an EEFX certificate for every supported (type,B): a mass partition of the remaining item supply into whole comparison bundles C satisfying v(B)≥v(C\{g}) for every g∈C.
High-multiplicity multi-unit fair division: complete valuation types carry population mass; x assigns mass to whole bundles; item-kind capacities scale with population; the objective is exact EEFX search and, with oracles, query complexity.
The paper does not determine a canonical scaling of item capacities or prove that the proposed mass certificate is the limit of finite EEFX certificates; different clone-symmetric item models could yield different problems.
fatal: False
The mirror covers the Section 4 EEFX search and value-query lower bounds for identical submodular valuations; Theorem 3.5 supplies structural motivation but no complexity guarantee, and the mirror does not cover the paper's other fair-division results.
The strongest positive case is a high-multiplicity course-assignment mirror, not cake-cutting. Imagine a large university with many students, but only a modest number of complete preference types: degree programme, year, prerequisites, and course preferences. Course seats remain indivisible. The population is represented by rational masses \(\mu_t\), while seat capacities scale with enrolment. This is exactly the sort of regime in which “17.4% of students have this valuation type” is more meaningful than naming every student.
Formally, let \(T\) be a finite set of complete valuation types, \(\mu_t\) their masses, \(G\) a finite catalogue of indivisible item kinds, and \(q_g\) the mass-scaled supply of each item. A bundle is a whole subset \(B\subseteq G\), and \(v_t(B)\) is the value of that bundle to type \(t\). An allocation is a mass assignment \(x_{t,B}\ge 0\) satisfying
\[ \sum_B x_{t,B}=\mu_t,\qquad \sum_{t,B:g\in B}x_{t,B}=q_g. \]
Thus \(x_{t,B}\) says how much of type \(t\) receives the complete bundle \(B\); it does not give an individual a fractional course. At any rational denominator, the assignment can be blown up to a finite market of students and whole seat copies.
For a type \(t\) receiving \(B\), an epistemic certificate is a mass partition \(z^{t,B}\) of the remaining item supply into comparison bundles \(C\), every one satisfying
\[ v_t(B)\ge v_t(C\setminus\{g\}) \quad\text{for every }g\in C. \]
A continuous EEFX allocation is an \(x\) together with such a certificate for every \((t,B)\) with \(x_{t,B}>0\). In the nonatomic limit, the distinguished agent consumes zero population mass; a finite-resolution version subtracts one agent and her bundle explicitly. This is the direct population analogue of the paper’s definition of EEFX, while retaining whole bundles and the paper’s “shuffle the other bundles” interpretation.
My lead anchor is Theorem 4.8: “the problem of computing an EEFX allocation … for any number \(n\ge2\) of agents with identical submodular valuations is PLS-hard.” This theorem is proved in the paper, using Lemma 4.6 and the cited Theorem 4.2 of Goldberg, Høgh, and Hollender.
The corresponding problem is:
Continuous-ID-EEFX. Given a rational population mass \(P\), a rational type distribution \(\mu\) concentrated on one submodular valuation \(v\), rational item supplies \(q\), and value-oracle access to \(v\), output a feasible mass allocation \(x\) and an EEFX certificate for every bundle appearing in its support.
The question is not whether a fractional utility vector exists. It is whether a large population of indistinguishable agents can be assigned whole indivisible bundles, in aggregate, so that every represented agent has the paper’s epistemic-EFX certificate.
I would forecast the fully nonatomic version as Class C: hard for reasons specific to the continuum formulation, or at least genuinely open. The source PLS-hardness does not automatically transfer, because allowing a type mass to split over several bundles may destroy the discrete local-search structure. But the continuum does not make the problem convex: the condition “every bundle in the support has a certificate” is a disjunction over exponentially many bundle patterns, and the certificate itself is a partition-feasibility problem. A finite-resolution version that preserves the paper’s heavy-item extraction gadget may instead be Class B, with hardness transferring. Establishing precisely where that transition occurs would be a worthwhile result rather than a defect.
The second anchor is Theorem 4.7, proved here: with \(|M|=2k+n-1\), computing EEFX for \(n\) identical submodular agents requires
\[ \Omega\!\left(\frac1k\binom{2k+1}{k}\right) \]
value queries. The paper derives this from the cited Theorem 4.1 of Plaut and Roughgarden through Lemma 4.6.
Its continuous counterpart is:
Continuous-Oracle-EEFX. Given rational type masses and item supplies, with each valuation supplied only through a value oracle, output an exact continuous EEFX allocation and certificates, minimizing the number of oracle queries.
Here I would expect the lower bound to survive as a Class-B boundary result, or at least remain population-independent hardness. The difficulty in Theorem 4.7 is hidden combinatorial information about the valuation of bundles, not the identities of the agents. The hard instances already use identical valuations, so compressing millions of students to one valuation type should not by itself reveal the required EEFX certificate. The precise open question is whether mass splitting lets the continuous algorithm evade the hidden valuation; if it does, that would identify exactly what the continuization has changed.
Theorem 3.5, proved in the paper, supplies useful supporting evidence even though I would not use it as a computational anchor: EEFX allocations exist for arbitrary monotone valuations, and the recursive algorithm ALG returns one. Its EEFX-graph and Hall-violator proof suggest a natural continuous follow-up using finite-type flow or measure-matching methods. One could ask whether, for explicitly represented bundle families or additive valuations, the continuous existence/search problem becomes an LP or a column-generation problem. That would mirror the paper’s structural theorem without pretending that its general-oracle algorithm is polynomial-time.
The mirror is therefore narrow but credible. It covers the paper’s Section 4 search and query results, and it uses the exact EEFX predicate, identical/submodular valuation regime, and course-assignment motivation. It does not claim that every fair-division theorem has a useful population limit, and it does not rely on fractional goods, lotteries, or divisible outcomes.
The weakest point is the interaction between nonatomic population mass and indivisible items. EEFX removes one item from a comparison bundle, while a literal continuum makes one agent’s own bundle negligible in aggregate. Consequently, the limiting certificate is not uniquely forced by the finite definition, and Theorem 4.8’s PLS-hardness cannot simply be declared to transfer. That is a real vulnerability. The positive case survives because the underlying regime—many students, few complete valuation types, many whole seat copies—is economically and mathematically natural, and because the resulting problem retains the paper’s central computational object: finding an assignment whose bundles admit epistemic-EFX certificates.
The positive case fails to establish a population limit for any of its three anchors. The difficulty is not that the proposed limit might become easy; that would itself be an interesting result. The difficulty is that EEFX is sensitive to the ratio between agents and indivisible items, and the paper contains no asymptotic regime for that ratio.
If the paper’s finite item set is held fixed while the population grows, EEFX degenerates. Once there are at least as many agents as items, assign every item as a singleton bundle and leave the remaining agents empty. Removing the sole item from any nonempty comparison bundle leaves the empty set, worth zero to every normalized monotone valuation. This allocation is EFX, hence EEFX, for arbitrary valuations. The hard object has disappeared because the “up to any item” relaxation becomes vacuous.
The proposed repair—scaling course capacities with the population—is coherent, but it is no longer a limit of the paper’s input model without substantial new choices. The paper gives a valuation \(v:2^M\to\mathbb R\) over a finite set of individually distinct goods. A course model needs a valuation over repeated item copies or course types, together with constraints such as “at most one seat of each course per student.” Clone-symmetric, additive-over-copies, capped, and label-sensitive extensions all produce different EEFX problems. The claim that rational masses can be blown up proves only that one newly defined finite multi-unit problem has finite realizations; it does not show that those realizations converge to the paper’s problem.
This breaks the first anchor, Theorem 4.8, particularly sharply. Its reduction uses exactly \(n-2\) heavy items and the pigeonhole principle to isolate two agents who receive no heavy item. If the hard goods and exceptional agents remain \(O(1)\) while the population grows, they have zero mass and disappear from the continuous allocation. If the heavy and hard goods are replicated so that they have positive mass, the pigeonhole extraction no longer has the same meaning and the valuation must be extended to a new multi-unit domain. For fixed \(n=2\) or \(n=3\), the theorem gives a discrete fair-division problem, not a continuum population. Thus the theorem’s phrase “for any number \(n\)” is not itself a population-limit theorem.
Theorem 4.7 has the same problem. Its query lower bound hides information in subsets of \(2k+1\) labelled goods. Keeping that hard block finite makes it invisible in a normalized mass limit; scaling it changes the oracle problem. One could certainly seek a new lower bound for multi-unit course valuations, but that would be a fresh result, not a continuous counterpart established by the paper. The fact that the original agents have identical valuations is evidence that the finite instance is compressible—not evidence that its item-level oracle hardness survives population continuization.
Theorem 3.5 does not repair this gap. Its proof is a finite Hall-matching argument: it removes a nonempty set of named agents together with whole bundles and recurses. A nonatomic population has no such positive-mass “next agent,” while a finite-resolution interpretation simply reinstates the original finite matching problem. A measure-valued matching theorem could be interesting, but it would be a new existence theorem, not a computational mirror of the paper’s algorithm; moreover, the theorem itself supplies no polynomial-time result.
The strongest version of the proponent’s proposal is therefore a legitimate new research direction: high-multiplicity EEFX for multi-unit course assignment with clone-symmetric valuation types. But that is precisely its weakness as a mirror. It changes the item model, the valuation oracle, the certificate from a finite partition to a mass distribution, and the scaling regime simultaneously. The paper’s three named results do not survive that translation, while the literal population limit either loses the hard information or becomes trivial.
I would not claim this proves that no such course-assignment problem could ever be worthwhile. That is the negative case’s real weakness: the repaired model is mathematically sensible. What can be defended is the narrower conclusion that the paper itself does not provide a robust continuous-population anchor; the proposed mirror must be invented as a new multi-unit fair-division programme rather than extracted from Theorems 3.5, 4.7, or 4.8.
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.