| paper | Fair and Efficient Balanced Allocation for Indivisible Goods |
| authors | Yasushi Kawase, Ryoga Mahara |
| venue | AAAI 2026 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions, even when \(\tau=s=2\); therefore \(\mathrm{NP}\)-hard under polynomial-time Turing reductions. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Corollary 1
statement extracted from the paper’s text layer
Given a finite good catalogue \(G\), \(k\in\mathbb{N}\), rational per-capita supplies \(\rho\in\mathbb{Q}_+^G\) with \(\sum_{g\in G}\rho_g=k\), valuation types \(v_t\in\mathbb{Q}_+^G\), rational masses \(\mu\in\mathbb{Q}_+^\tau\) with \(\sum_t\mu_t=1\), and an explicit finite-support candidate allocation \(y_{t,B}\) over integral bundles \(B\in\mathbb{Z}_+^G\) satisfying \(\sum_g B_g=k\), \(\sum_B y_{t,B}=\mu_t\), and \(\sum_{t,B}y_{t,B}B_g=\rho_g\), decide whether there is no nontrivial mass-preserving reassignment \(z_{t,B,B'}\) such that \(\sum_{B'}z_{t,B,B'}=y_{t,B}\), \(\sum_{t,B,B'}z_{t,B,B'}B'_g=\rho_g\), \(z_{t,B,B'}=0\) whenever \(v_t(B')<v_t(B)\), and \(\sum_{t,B,B':\,v_t(B')>v_t(B)}z_{t,B,B'}>0\).
A high-multiplicity balanced allocation with nonatomic mass \(\mu_t\) over valuation types, per-capita supplies \(\rho_g\) of indivisible good units, and integral \(k\)-unit bundles; the decision variables are mass couplings \(z_{t,B,B'}\), and the objective is to detect a weak Pareto improvement with positive strict-improvement mass.
The continuous model introduces repeated good classes and per-capita supplies, while mass splitting moves the combinatorics into configuration feasibility; the resulting representation and complexity, including any surviving \(\mathrm{coNP}\)-hardness, are not settled.
fatal: False
The mirror covers Corollary 1's \(\mathrm{PO}\) verification, Theorem 1's \(\mathrm{EF1}\)-\(\mathrm{fPO}\) verification, and the two-type construction in Theorem 4. It leaves Theorem 3's personalized-bivalued construction, most structural lemmas, and the paper's fractional-lottery observations without separate mirrors.
There is a credible positive case, with the paper’s balanced indivisible-goods problem as the object being continuized. The most convincing mirror is not a divisible-goods market: individuals still receive integral bundles, while only the population of otherwise identical agents is represented by mass.
Take a finite catalogue \(G\) of indivisible good units or good classes, and let every agent receive exactly \(k\) units. A type \(t\) is a complete additive valuation vector \(v_t=(v_{tg})_{g\in G}\), including every feature relevant to the allocation. A society is a rational distribution \(\mu\) over finitely many such types. Because a unit-mass population needs a unit-mass supply of goods, the instance also specifies per-capita supplies \(\rho_g\), with \(\sum_g\rho_g=k\). This scaling is not an outcome-space relaxation: an individual still receives an integral \(k\)-unit bundle.
An allocation is a finite-support distribution \(y_{t,B}\), where \(y_{t,B}\) is the mass of type-\(t\) agents receiving integral bundle \(B\). It satisfies \(\sum_B y_{t,B}=\mu_t\) and \(\sum_{t,B}y_{t,B}B_g=\rho_g\). Rational masses can be cleared to obtain a finite population with repeated valuation types and repeated good units. A plausible regime is a large team draft or asset-allocation system with hundreds of thousands of recipients, a small number of recurring valuation templates, and supplies replenished per capita.
My lead mirror is Continuous Balanced Pareto Verification. Its anchor is Corollary 1, proved in this paper using the cited coNP-completeness result of de2009complexity. The corollary states that deciding whether a given balanced allocation is PO is coNP-complete. Here PO means that no other balanced integral allocation Pareto-dominates the given allocation.
The continuous question is:
Given \((G,k,(v_t),\mu,\rho)\) and a candidate allocation \(y\), is \(y\) population-PO? That is, does there exist no mass-preserving reassignment in which every individual keeps or increases utility and a positive mass strictly increases utility?
To retain the individual comparison implicit in Pareto dominance, the alternative is represented by a coupling \(z_{t,B,B'}\). It sends the mass currently assigned to \(B\) into new integral bundles \(B'\), preserves all good supplies, and is allowed only when \(v_t(B')\ge v_t(B)\). At least one used transition must be strict for some positive mass to constitute a Pareto improvement. Thus the problem does not compare merely type-average utilities; it preserves the old bundle of each agent cohort and asks whether that cohort can be improved.
This is recognisably the paper’s PO problem: same additive valuations, same balanced cardinality constraint, same indivisible bundles, and the same Pareto comparison. The only change is that repeated agents are represented by mass. I would expect this mirror to be continuum-specifically hard, or at least to expose a genuine new boundary. Population splitting removes the automatic transfer of the paper’s coNP-hardness: a mass of identical agents can be divided among several new integral bundles. But the remaining problem still has to select integral bundles satisfying type-specific utility thresholds and global supply constraints. Its natural configuration-LP pricing problem resembles a cardinality-constrained knapsack problem. The combinatorics now live in indivisible bundles and good types rather than in the number of named agents.
This generates worthwhile follow-up questions: does coNP-hardness survive when \(\tau\) is fixed? Is the problem polynomial for fixed \(k\) or bounded valuation levels? Does a configuration LP with column generation solve it for certain valuation classes? Can one distinguish a tractable fPO version from a hard PO version? Those are exactly the kinds of questions for which continuization is useful.
A second, cleaner algorithmic mirror is Continuous Balanced EF1–fPO Verification, anchored by Theorem 1, proved in this paper. The theorem says that, given a balanced allocation, one can decide in polynomial time whether it is both EF1 and fPO. EF1 is the paper’s pairwise “remove one good” condition, while fPO forbids Pareto domination by any balanced fractional allocation.
For the continuous problem, the candidate is again \(y\). It is EF1 if, for every two positive-mass bundles \(B\) of type \(t\) and \(B'\) of type \(t'\), some good in \(B'\) can be removed so that \(v_t(B)\ge v_t(B'\setminus\{g\})\). This is the support-wise version of the paper’s pairwise condition, not an average-utility substitute.
It is fPO if no fractional reassignment \(x_{t,B}\) can give every member of the cohort currently receiving \(B\) weakly greater utility, strictly improving some positive mass, while respecting the per-capita supplies and the requirement of \(k\) units per agent. Once the candidate allocation has explicit finite support, this is a linear program with variables indexed by \((t,B)\) and \(g\). EF1 is checked by enumerating support pairs; fPO is checked by the LP. I therefore expect this mirror to be Class A.
The strongest constructive anchor is Theorem 4, also proved here. It states that when there are at most two valuation types, a balanced allocation that is simultaneously EF1 and fPO always exists, and one can be found in polynomial time.
Its continuous counterpart is Continuous Two-Type Balanced EF1–fPO Construction:
Given two valuation types \(u_1,u_2\), rational masses \(\mu_1,\mu_2\), per-capita supplies \(\rho\), and integral bundles of cardinality \(k\), output a finite-support allocation \(y\) satisfying the support-wise EF1 and population-fPO conditions above.
This is a particularly plausible high-multiplicity regime: two large recurring populations may represent two departments, customer segments, or preference templates. The finite theorem already gives existence after clearing rational denominators: replicate each type and each good unit according to the denominators, apply Theorem 4, and aggregate equal type–bundle pairs. What remains genuinely computational is a denominator-independent compressed algorithm whose output has polynomial support. The paper’s matching, dual-price, and weight-sweep machinery gives a credible route to such an algorithm, so I would expect Class A, though the compression and support-wise EF1 proof should be supplied rather than assumed.
The mirror deliberately covers only the paper’s balanced indivisible-goods results: Corollary 1, Theorem 1, and Theorem 4. It does not continuize the paper’s fractional allocation benchmark instead of the population, nor does it rely on Fisher markets, lotteries, or divisible goods.
The weakest point is the treatment of Pareto comparisons after aggregation. If one silently replaces individual dominance by type-average dominance, the problem becomes easier but is no longer the paper’s PO question. The coupling formulation avoids that defect, but it also means that hardness transfer is not automatic and the compact representation of integral bundle distributions remains open. That is a genuine technical vulnerability, not a reason to reject the mirror: it is precisely the population-continuization question the paper makes available.
The strongest negative case is that the paper has no independent population axis to continuize. Its two finite atom sets are tied by \(m=nk\): increasing the number of agents forces the number of indivisible goods to increase as well. If the goods remain named and heterogeneous, an agent type is a valuation vector over an ever-growing inventory, so there is no stable finite type space and no genuine continuum of agents facing a fixed indivisible supply. If goods are instead repeated into classes with per-capita supplies, one has introduced a second high-multiplicity assumption and changed the problem into an anonymous inventory-allocation model. That may be a worthwhile new problem, but it is no longer an uncomplicated mirror of this paper.
Corollary 1 is the weakest anchor. The paper’s PO predicate concerns a particular finite allocation of named goods to named agents. The proposed population version must retain the current bundle of each cohort, so its real types are \((t,B)\), not merely valuation types \(t\). An improving allocation then becomes a configuration problem over all integral bundles \(B'\), with constraints \(v_t(B')\ge v_t(B)\). If one instead compares only type-average utilities, the resulting question is easier but is not the paper’s PO problem.
With explicit support, this is a legitimate configuration-feasibility problem; with an implicit allocation, its input and output representations are unspecified and the bundle catalogue may be exponential. The coNP-completeness statement therefore does not yield a clean population analogue: its combinatorics have moved from named agents to bundle configurations. That could motivate a new study, but it is not evidence that this paper itself supplies a worthwhile continuous mirror.
Theorem 1 is even less compelling as an anchor. For an explicitly represented allocation \(y\), support-wise EF1 is checked by enumerating pairs of positive-mass bundles, while fPO is checked by essentially the same LP as in the paper, with rows indexed by support cohorts \((t,B)\). This is a routine lifting of the finite verification procedure, not a population-driven computational phenomenon. If \(y\) is given compactly, support-wise EF1 becomes representation-sensitive: adding an arbitrarily small positive mass to a new bundle creates new pairwise EF1 obligations, whereas the obligation disappears at mass zero. Averages do not fix this without changing the fairness notion. Thus the best versions are either a trivial finite-support reformulation or a new support/separation problem whose connection to Theorem 1 is tenuous.
Theorem 4 is the strongest proposed anchor, but its continuous extension is not automatic. The proof relies on \(n_1\) and \(n_2\) integer agent counts, \(k\) individual slots per agent, round-robin ordering, and perturbations such as \(\epsilon=1/(nk(k+1))\). Clearing denominators in \(\mu\) and \(\rho\) gives a finite instance, but the denominator can be exponentially large in the encoded input. Aggregating the resulting allocation does not itself provide a denominator-independent algorithm or a polynomial-size support representation.
The natural repair is a price-ordered configuration or quantile construction. Yet EF1 is support-wise rather than linear: a tiny positive mass assigned to one additional bundle creates a new fairness comparison, and ordinary LP limits do not preserve this condition automatically. One would need a new theorem controlling support size and EF1 under population splitting. If such a theorem exists, it could indeed be worthwhile; Theorem 4 does not establish it.
So the negative case is ultimately weaker than the requested universal conclusion. The repeated-good scenario is plausible, the cohort coupling preserves individual Pareto comparisons, and the two-type theorem is a genuine candidate for a high-multiplicity algorithmic result. I would reject the mirrors as insufficiently specified and not yet justified by the paper, but I could not honestly claim that no worthwhile continuous mirror exists in any scenario.
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.