| paper | The Complexity of Extending Fair Allocations of Indivisible Goods |
| authors | Argyrios Deligkas, Eduard Eiben, Robert Ganian, Tiger-Lily Goldsmith, Stavros D. Ioannidis |
| 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 5
statement extracted from the paper’s text layer
Given finite complete agent types \(H\) with rational masses \(\mu_h\), additive valuations over item types \(U\), integral fixed endowments \(e_h\), rational per-capita supplies \(\sigma_u\) of open item copies, and a given set \(R\) of at most \(p\) recipient cohorts, decide whether there are integral bundle vectors \(b_h\) uniform within each cohort, with \(b_h = 0\) outside \(R\), such that the aggregate supply constraints \(\sum_h \mu_h b_{h,u} = \sigma_u\) hold for every item type \(u\) and \(v_h(e_h+b_h) \ge v_h(e_{h'}+b_{h'})\) for every pair of population types \(h,h'\).
A supply-scaled, high-multiplicity workplace or public-service REFAE model with complete valuation/endowment cohorts, integer per-cohort bundle variables, and linear inventory and envy constraints.
The claimed p|U|-variable FPT formulation relies on every cohort receiving one common bundle and on interpreting p as recipient cohorts, whereas the source permits identical agents to receive different bundles and counts individual recipients.
fatal: False
The mirror covers the restricted-recipient, item-type-sensitive results of Theorems 5 and 3, but not the few-open-items results of Theorems 1, 2, and 4 or the EF1/EFX propositions.
There is a credible mirror, but it is strongest for the paper’s restricted-recipient results and for a genuinely high-multiplicity workplace or public-service regime. My lead anchor is Theorem 5, proved in this paper; Theorem 3, also proved here, supplies the hardness boundary.
The mirror I would propose is Mass-REFAE\(_\infty\), a clone-stable high-multiplicity version of REFAE.
An instance has a finite set \(H\) of complete agent types. A type \(h\) includes:
The fixed bundle belongs in the type description. The paper identifies agent types only through valuations, but under ChoCo’s definition two agents are the same type only if their current endowments and every other relevant parameter also coincide.
There is a rational per-capita stock \(\sigma_u\) of open copies of each item type \(u\). This does not fractionalize goods: for a common denominator \(D\), \(D\mu_h\) and \(D\sigma_u\) are integers, so the instance represents exactly \(D\mu_h\) agents and \(D\sigma_u\) indivisible item copies.
A set \(R\subseteq H\) of at most \(p\) recipient cohorts is given. The decision variable is an integral bundle vector \(b_h\in\mathbb Z_{\ge 0}^{U}\) for every \(h\in R\), with \(b_h=0\) otherwise. Every member of cohort \(h\) receives the same bundle \(b_h\). The stock constraints are
\[ \sum_{h\in R}\mu_h b_{h,u}=\sigma_u \]
for every item type \(u\). The resulting allocation is accepted exactly when
\[ v_h(e_h+b_h)\ge v_h(e_{h'}+b_{h'}) \]
for every pair of population types \(h,h'\). The output is either such a bundle vector or NO. Thus the objective is precisely the source problem’s objective: decide whether the partial allocation has an envy-free extension.
This is a natural regime rather than an artificial compression. Imagine a large company, hospital system, or public agency with millions of employees represented by a small number of standardized role-and-endowment cohorts. A few role cohorts are eligible to receive a newly released batch of tasks or goods. The number of agents is enormous, while the number of complete types, item types, and recipient cohorts is modest. It is also close to the paper’s own motivating example of distributing new tasks to recently hired employees.
This problem should be tractable in the parameterized sense of Theorem 5. For a fixed recipient set, there are only \(p|U|\) integer variables \(b_{h,u}\). Both inventory and envy-freeness are linear constraints in these variables. After clearing the rational masses, the problem becomes a fixed-dimensional integer program. Lenstra-style machinery therefore suggests an algorithm fixed-parameter tractable in \(p+|U|\), polynomial in the number of agent types and the encoding length. This is the same structural phenomenon exploited by the paper’s Theorem 5: item types convert the allocation decision into a bounded number of integer variables.
The free-recipient analogue, Mass-FEFAE\(_\infty\), would additionally choose at most \(p\) recipient cohorts. Enumerating candidate cohorts gives an XP algorithm, paralleling the FEFAE half of Theorem 5. Whether that can be improved to FPT is a natural continuous question rather than a cosmetic reformulation.
The second anchor is Theorem 3, which states that both REFAE and FEFAE are strongly NP-hard even when \(p\le2\). Its hardness transfers directly to the mass model. Given any finite instance with \(n\) agents, make each agent its own type of mass \(1/n\), retain its valuation and fixed bundle, and set the per-capita supply of each open item to \(1/n\). Clearing denominators recovers exactly the original finite allocation problem. Hence Mass-REFAE\(_\infty\) remains NP-hard with only two recipient cohorts when the item catalogue and type system are unrestricted. This is Class B hardness: it is inherited from the discrete problem, not caused by the continuum.
The two anchors therefore give a useful classification rather than a blanket claim. The bounded-\((p,|U|)\), clone-stable regime is a plausible Class A problem; the unrestricted two-recipient regime is Class B. The paper’s type-sensitive complexity results become a genuine continuous research programme: determine which additional type parameters make the full mass problem tractable, and which forms of combinatorial hardness survive denominator clearing.
The main questions generated by this mirror are whether FPT survives when a homogeneous cohort may split among several different integral bundles, whether the free-recipient version can improve from XP to FPT, and what happens for continuous EF1 and EFX extension. One could also study additive approximation when the masses or item supplies are rounded, and social-network variants where envy is checked only along a finite interaction graph.
The weakest point is the clone-stability convention. In the original problem, two valuation-identical agents may have different preallocated bundles and may receive different extensions. In the mirror I have made the complete type include the current bundle and used uniform bundles within a cohort. That is defensible for standardized employee or customer classes, but it does narrow the full allocation space. A referee could reasonably demand the more general bundle-census version. Also, proportional item supply is needed for new goods to affect positive population mass; with only finitely many open items in an atomless population, their recipients have zero mass and the limit becomes degenerate. I would therefore present this as a serious continuous mirror for the high-multiplicity, supply-balanced extension regime, not as a claim that every theorem in the paper admits a clean population limit.
The strongest negative case is that the proposed Mass-REFAE\(_\infty\) does not actually continuize Theorem 5; it changes two features that carry the theorem’s content.
In Theorem 5, \(p\) counts individual agents who may receive the open items. In a population of \(D\) clones, keeping \(p\) fixed means that the recipients have mass at most \(p/D\), which vanishes. With finitely many open indivisible items, the limiting population distribution does not record who receives them, although envy-freeness still depends on those individuals. The continuum has therefore lost the extension problem’s relevant information. Scaling the item supply proportionally avoids this degeneration, but then positive-mass recipient cohorts replace the paper’s \(p\) individual recipients. That is a new recipient-cohort problem, not the high-multiplicity version of REFAE.
The fixed-dimensional ILP also depends on the extra requirement that every member of a type cohort receive the same bundle. High multiplicity does not imply this. It only makes agents identical in their preferences, endowments, and other input parameters; the allocation may still assign different bundles to identical agents. Adding the fixed bundle \(e_h\) to the type correctly handles different preallocations, but it does not justify uniform future allocations.
The natural repair is a bundle-census model: a type may split across several integral bundles, with variables recording how much mass receives each bundle. That restores the source problem’s allocation semantics, but the variables are now configurations \(B\), potentially exponentially many in the item catalogue and supply. The \(p|U|\)-variable Lenstra argument disappears, and neither FPT nor even a canonical compact formulation follows from Theorem 5. If one retains uniform bundles, the tractability is a consequence of a newly imposed batch-assignment policy.
Theorem 3 is weaker evidence than claimed. The construction with mass \(1/n\) per type and supply \(1/n\) per open item merely encodes the original finite instance, with every source agent made its own type. It demonstrates weighted restatement, not a population regime with multiplicity. Repeating the agents requires repeating every open item and again forcing clone-identical recipient bundles. That may yield a valid hardness result for the remodeled batch problem, but it does not establish that the paper’s two-recipient extension problem has a meaningful continuous population limit.
The same fault affects the proposed EF1/EFX directions. With fixed supply, the relevant recipients become null exceptions. With scaled supply, fairness must be defined over the entire support of integral bundles, producing another configuration problem rather than a straightforward mass inequality.
This is nevertheless not an airtight negative case. If ChoCo accepts a supply-scaled, cohort-uniform workplace model as an author-recognizable extension, then Theorem 5 is a genuine Class A candidate and Theorem 3 a legitimate Class B boundary. Under that broad standard, the universal claim that no worthwhile mirror exists cannot honestly be maintained. The negative case succeeds only under the stricter requirement that a mirror preserve individual-recipient semantics and permit the source allocation space.
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.