| paper | Finding Fair Allocations under Budget Constraints |
| authors | — |
| venue | AAAI 2023 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Given rational masses \(\lambda_r\) of recipient types \(r\) with budgets \(B_r\), and rational supplies \(\eta_q\) of indivisible item types \(q\) with sizes \(s_q\) and values \(v_q\), find rational masses \(y_{r,b}\) over integral bundles \(b \in \mathbb{Z}_{\ge 0}^Q\) satisfying \(s \cdot b \le B_r\), \(\sum_b y_{r,b} = \lambda_r\), and \(\sum_{r,b} y_{r,b} b_q \le \eta_q\). Treat unused supply as charity and require that every occupied bundle \(b\) of every recipient type is EF2 against every occupied bundle and every fitting integral charity subbundle, using the paper's additive-value envy predicate; decide whether such an allocation exists or output one.
A high-multiplicity allocation model with continuous masses of recipient types and item supplies, but integral bundles per recipient; variables are bundle masses \(y_{r,b}\), the objective is EF2 feasibility, and unused item mass is charity.
The proponent has not shown that support-wise EF2 admits polynomial-size representations or separation in the type encoding; exponentially many integral bundle states may remain necessary.
fatal: False
The mirror covers the general EF2 algorithm of Theorem 1 and the equal-size and equal-value EF1 algorithms of Theorems 9 and 10; it leaves Theorem 8, the structural lemmas, the tightness example, and the full-version agent-specific-size extension unaddressed.
The strongest positive case is a high-multiplicity allocation mirror, not a model in which goods become divisible. The population becomes continuous; each individual still receives an integral bundle of indivisible goods.
Take a finite set \(R\) of recipient types and a finite set \(Q\) of good types. A recipient type \(r\) has budget \(B_r\), and mass \(\lambda_r\); a good type \(q\) has size \(s_q\), value \(v_q\), and supply intensity \(\eta_q\). The natural regime is a large relief programme, school-supply distribution, or museum network: millions of recipient units fall into a few budget classes, while the inventory consists of many copies of a small catalogue of item types. Thus the number of agents and goods is enormous, but \(|R|+|Q|\) is small.
Formally, a bundle is an integral vector \(b\in\mathbb Z_{\ge0}^{Q}\), with size \(s\cdot b\le B_r\). The continuous allocation variable is
\[ y_{r,b}\ge 0, \]
the mass of type-\(r\) recipients receiving bundle \(b\). It satisfies
\[ \sum_b y_{r,b}=\lambda_r,\qquad \sum_{r,b}y_{r,b}b_q\le \eta_q. \]
The residual supply is charity. A positive \(y_{r,b}\) means that a positive-mass class of agents receives the same discrete bundle; no individual receives a fraction of a good. Equivalently, the instance represents all sufficiently large integer replications of the type catalogue.
The EF2 condition is imposed pointwise on the support: for every occupied bundle \(b\) of type \(r\), every other occupied bundle \(b'\), and every integral subbundle \(f\le b'\) of size at most \(B_r\), removing two goods from \(f\) must leave value at most \(v\cdot b\). The same must hold for every fitting finite subbundle of the charity. EF1 is defined analogously with one removed good. The objective is feasibility: find any such \(y\), exactly as in the paper. This preserves indivisibility, additive values, individual budgets, charity, and the paper’s exact envy predicate; it does not replace them with expected-value or average-envy constraints.
My lead anchor is Theorem 1, proved in this paper: “Algorithm 1 (DensestGreedy) computes an EF2 allocation in polynomial time” for arbitrary budget-constrained instances. Its continuous counterpart is:
Continuum-EF2-Budget Allocation. Given rational \((\lambda_r)_{r\in R}\), item-type data \((s_q,v_q,\eta_q)_{q\in Q}\), and budgets \(B_r\), output a rational bundle-mass allocation \(y\) satisfying the supply constraints and the support-wise EF2 conditions above.
I would expect this to be Class A. The reason is not merely that the finite theorem is polynomial. The proof’s substantive ingredients—density ordering, the envy-count function, the prefix lemmas, and the fact that the greedy process compares only value and budget states—are precisely the sort of structure that can survive aggregation. A continuous implementation would process masses of identical goods and masses of agents in the same current bundle state rather than iterating over every named agent and item. The technical question is whether this batching can be done in time polynomial in \(|R|+|Q|\) and the encoding length, rather than merely simulating a large finite instance.
This is a genuine computational question: the possible bundles are exponentially numerous, and the continuous formulation has a natural column-generation interpretation. The positive conjecture is that the density-greedy structure gives a compact separation or event-based implementation. Further questions include whether exact EF2 remains stable under zero-versus-positive charity mass, whether the algorithm is fixed-parameter tractable in the number of item and budget types, and whether one can optimize charity or social welfare while retaining EF2.
A second, independently defensible anchor is Theorem 9, also proved here: when all goods have the same size, Algorithm 1 computes an EF1 allocation in polynomial time. Its mirror is Continuum-Unit-Size-EF1: use the same type-mass allocation problem, impose \(s_q=s\) for every item type, and ask for a support-wise EF1 allocation. Each recipient then has an integral cardinality capacity \(\lfloor B_r/s\rfloor\), while values may still vary by item type. This is a particularly plausible high-multiplicity regime—many copies of standard-sized but differently valuable items allocated among many recipients with a few capacity classes. I would again expect Class A, with a compressed value-ordering or flow-like implementation. The question generated by this anchor is whether the continuous model permits exact EF1 with minimum charity, rather than merely finding some EF1 allocation.
A third anchor is Theorem 10, proved here: when all goods have the same value, Algorithm 1 computes an EF1 allocation in polynomial time. The corresponding Continuum-Equal-Value-EF1 problem keeps arbitrary item sizes but sets \(v_q=v\) for all \(q\). The decision variable and EF1 predicate are unchanged. This models, for example, a large population receiving standardized-value aid items whose physical sizes differ and must fit recipient-specific storage budgets. The theorem’s density order becomes an order by increasing size, so a batched continuous algorithm appears especially plausible. I would classify this as Class A as well. Natural follow-up questions concern agent-specific sizes, which the paper says are handled in the full version, and whether the continuous model admits stronger guarantees than EF1 under this restriction.
These mirrors cover the paper’s own positive results: general EF2 computation (Theorem 1), EF1 for equal-sized goods (Theorem 9), and EF1 for equal-valued goods (Theorem 10). All three anchors are proved in the paper, not merely cited. I am deliberately not using the paper’s remarks about NP-hard knapsack as anchors: those are background observations and not numbered computational results established here.
The weakest point is that the paper’s polynomial runtime is measured in the explicit numbers \(m\) and \(n\). A continuous mirror must compress repeated goods and repeated recipient states; “run DensestGreedy on a huge replicated instance” would only be pseudo-polynomial in the multiplicities. Also, EF1/EF2 involve removing individual goods, so the exact limiting interpretation of a positive charity mass must be specified carefully. Those are real proof obligations. They do not undermine the mirror itself: the model remains a faithful high-multiplicity version of the authors’ allocation problem, and the unresolved issue is exactly the kind of new complexity question the continuization programme is meant to expose.
The strongest negative case is that the proponent has shown a plausible high-multiplicity reformulation, but not yet a genuinely continuous computational problem with the structure they claim. That case is ultimately weak, however.
For Theorem 1, the proposed variables \(y_{r,b}\) do preserve indivisible goods, but the EF2 constraint is not linear or even closed under limits. A bundle constraint applies whenever \(y_{r,b}>0\), however small that mass is. Thus an arbitrarily small positive subgroup imposes the same obligations as a macroscopic one. Replacing this with an almost-everywhere or average-envy condition would give a better-behaved continuum model, but it would no longer mirror the paper’s EF2 theorem.
Retaining support-wise EF2 creates a different problem: a configuration problem over integral bundles with a discontinuous support predicate. The supply constraints admit column generation, but the fairness constraints do not form the sort of LP separation problem that motivates ChoCo. Clearing denominators also shows that every rational instance is exactly a finite replicated instance. The proposed computation is therefore primarily a compression question—whether DensestGreedy’s output can be represented without enumerating copies or bundle states—not a new continuous fairness theorem.
That is a legitimate question, but it is weaker than the proponent suggests. The paper’s polynomial algorithm is measured in the explicit numbers of agents and goods; nothing in its proof supplies a polynomial bound in the number of recipient and item types or guarantees a compact bundle-support representation.
Theorem 9 is harder to reject. With finitely many item-value types and budget classes, equal-sized goods give a natural large-population regime: recipients have integral capacity slots and goods remain indivisible. The resulting problem is essentially high-multiplicity allocation of unit items. Its continuous version may be useful, but the population distribution contributes little beyond counts of interchangeable bins; the combinatorial content lies in the catalogue of goods and possible bundles. If one asks only for EF1 feasibility, the paper already guarantees existence for every finite replication. “Minimum charity” would create a more interesting optimization problem, but that is a new result rather than a mirror of Theorem 9.
Theorem 10 has the same limitation. Equal values reduce EF1 largely to a cardinality condition, while sizes determine which subsets fit. A large aid-distribution scenario with repeated package types is perfectly plausible, and bounded per-recipient budgets prevent the deleted good from becoming measure-zero. So neither identity-dependence nor continuum degeneration defeats this mirror. At most, one can say that the continuous population is serving as a bookkeeping device for many identical recipients.
The usual decisive objections are unavailable here. The paper has explicit numbered polynomial-time results; agents can naturally be grouped by budget and other parameters; goods can naturally occur as repeated catalogue types; and the objective does not track named individuals. High-multiplicity work, if found, would support rather than undermine the model.
So the honest negative verdict is not that no worthwhile mirror exists. It is that the proponent has established admissibility, not tractability: the support semantics, output representation, and compression problem remain unresolved, and their claimed column-generation route is not yet justified. I cannot honestly defeat all three anchors under the programme’s rules. The negative case should therefore be recorded as weak; the paper merits a continuous-mirror investigation, though not yet the proponent’s Class A prediction.
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.