| paper | Efficient Nearly-Fair Division with Capacity Constraints |
| authors | — |
| venue | AAMAS 2023 |
| 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.14
statement extracted from the paper’s text layer
Given finitely many complete two-agent team types \(q\) with rational masses \(\rho_q\), rational item-type supplies \(\nu_o\), category capacities, and additive utilities \(u_{q,i}(o)\), choose masses \(z_{q,P}\) over whole pair configurations \(P=(B_1,B_2)\) such that \(\sum_P z_{q,P}=\rho_q\) and \(\sum_{q,P}z_{q,P}(n_o(B_1)+n_o(B_2))=\nu_o\) for every item type \(o\). Require every used configuration to be \(\mathrm{EF[1,1]}\), or EF1 on same-sign instances, and output positive weights \(\lambda_{q,i}\) certifying that \(z\) maximizes total weighted utility over all feasible configuration-mass assignments, or report that no such assignment exists.
A high-multiplicity population of complete two-agent team types, with \(z_{q,P}\) assigning population mass to indivisible pair bundles, exact global item supplies coupling teams, and positive \(\lambda_{q,i}\) certifying weighted Pareto optimality.
The proponent does not establish that a globally weighted-optimal configuration assignment can coexist with local EF1 or \(\mathrm{EF[1,1]}\), nor that its configuration-pricing oracle follows from the paper’s one-team ratio scan.
fatal: False
The mirror covers the two-agent guarantee of Theorem 4.14—capacity feasibility, Pareto optimality, and \(\mathrm{EF[1,1]}\) or EF1—and uses Theorem 4.15 only as runtime motivation; it leaves the \(n\ge3\) case, heterogeneous capacities, and matroid extensions untouched.
The strongest positive case is an extension of the paper’s two-agent result to a high-multiplicity population of repeated two-person teams. It is not a claim that the paper already studies a continuum; it is a concrete continuous problem that keeps its categories, capacities, additive mixed valuations, Pareto criterion, and EF1/\(\mathrm{EF[1,1]}\) semantics.
My lead anchor is Theorem 4.14, proved in this paper. It states that Algorithm 1 returns, for two agents, a feasible allocation that is \(w\)-maximal and therefore Pareto-optimal, satisfies all capacity constraints, and is \(\mathrm{EF[1,1]}\); in same-sign instances it is also EF1. Theorem 4.15, also proved here, supplies the \(O(m^4)\) running time, but I regard it as supporting evidence for the same anchor rather than a separate result.
A natural regime is a large standardized student-project or household population. There are \(N\) repeated two-person teams, with one agent of role type \(1\) and one of role type \(2\) in every team. All role-1 agents have the same additive valuation function, all role-2 agents have another, and the category capacities are common. Thus the agent population has \(2N\) members but only two complete agent types, with \(\mu_1=\mu_2=\frac12\). The project supplies consist of \(N\nu_o\) copies of each item type \(o\), where \(\nu_o\) is rational and item types share both category and valuations. This is a credible high-multiplicity regime: standardized programming, interface, and algorithmic tasks are repeated across many projects, while the number of distinct preference/capacity types remains small.
The continuous problem I would put forward is \(\mathsf{Team\text{-}CapFair\text{-}PO}_\infty\). Its input consists of two agent types \(1,2\), rational item-type supplies \(\nu_o\), a category map \(o\mapsto j(o)\), integer capacities \(s_j\), and additive utilities \(u_i(o)\in\mathbb Q\). After dummy-item padding, every team member receives exactly \(s_j\) items from category \(j\), so \(\sum_{o:j(o)=j}\nu_o=2s_j\) per unit mass of teams.
A bundle \(B\) is a whole indivisible multiset of item types satisfying those category capacities. A pair configuration is \(P=(B_1,B_2)\). Let \(z_P\ge0\) be the mass of teams using configuration \(P\). The allocation variables must satisfy \(\sum_Pz_P=1\) and, for every item type \(o\), \(\sum_Pz_P(n_o(B_1)+n_o(B_2))=\nu_o\), where \(n_o(B)\) is the number of copies of \(o\) in \(B\).
Every configuration with \(z_P>0\) must satisfy the paper’s fairness predicate: EF1 on the same-sign domain, or \(\mathrm{EF[1,1]}\) in the general mixed domain. Pareto optimality is imposed through a positive weight certificate: the output must include \(\lambda_1,\lambda_2>0\) such that \(z\) maximizes \( \sum_P z_P(\lambda_1u_1(B_1)+\lambda_2u_2(B_2)) \) over all feasible configuration-mass vectors with the same item supplies. The question is to find such \(z\) and \(\lambda\), or certify that none exists.
This preserves indivisibility. A rational solution can be cleared to \(N\) repeated teams, with \(Nz_P\) teams receiving the entire bundles \(B_1,B_2\); no individual item is split. Conversely, any finite repeated-team allocation maps to such a configuration mass vector. The continuous object is the population distribution over two agent types and whole-bundle configurations, not a cake-cutting allocation.
I expect this problem to be Class A. The weighted-maximality part is a configuration LP, and its pricing problem has the same structure as the paper’s matching calculation: additive utilities, category-wise capacities, and exchanges between two roles. Theorem 4.14’s ratio scan and its dependence on only two agents suggest that fair configurations may admit polynomial separation or a compact frontier description. The paper’s result therefore gives more than a superficial analogy: it identifies the exact two-role structural mechanism that a continuous algorithm would need to lift.
The scope should remain narrow. This mirrors the two-agent branch of Theorem 4.14, especially its same-sign EF1 guarantee. It does not claim a mirror for the paper’s proposed \(3+\)-agent extension, heterogeneous capacities, or general matroid constraints. The natural follow-up questions are whether fair-configuration pricing is polynomial, how to round a continuous solution while retaining EF1 for finite \(N\), and whether the result survives unequal role masses, more than two agent types, or heterogeneous capacities.
The weakest point is that this is an author-recognizable extension, not a literal limit of the paper’s single two-agent instance. If one replaces whole bundles by item-flow variables \(x_{i,o}\), the model becomes easier but risks erasing the indivisibility that makes EF1 meaningful. Keeping whole bundles avoids that objection, but introduces exponentially many configurations, and Theorem 4.14 by itself does not prove that the resulting pricing problem is polynomial. That is a real unresolved obligation. Even so, it is a legitimate high-multiplicity mirror of the paper’s central problem, with a precise Class-A research target rather than a merely fractional restatement.
The proponent’s only serious anchor is Theorem 4.14, with Theorem 4.15 supplying its \(O(m^4)\) runtime. The strongest objection is that the proposed mirror continuizes the wrong object.
In \(\mathsf{Team\text{-}CapFair\text{-}PO}_\infty\), the population distribution is fixed at \(\mu=(1/2,1/2)\). The substantive variables are \(z_P\), a distribution over pair configurations \(P=(B_1,B_2)\), and the item-type supplies \(\nu_o\). But \(P\) is an allocation outcome, not an agent type. Thus the continuous object doing the work is a mixture over indivisible allocations. Clearing rational \(z_P\) to \(N\) repeated teams does not change this: any lottery over finite allocations can be represented by repeated copies. Keeping bundles whole prevents item divisibility, but it does not turn outcome-space continuity into population continuity. The programme explicitly excludes that kind of mirror.
The natural direct replication is weaker still. If every team receives its own copy of the finite instance, Theorem 4.14 is simply run independently on each team; the population coordinate is inert. If teams share a global item pool, then the problem becomes a new configuration-and-pairing problem. Theorem 4.14 does not provide its pricing oracle, its decomposition theorem, or its fairness guarantee. The ratio scan in Algorithm 1 handles exchanges inside one two-agent allocation; it does not coordinate a distribution of many pair allocations subject to exact global supplies.
The obvious repair is to consider \(2N\) agents with repeated valuation types and a shared item pool, allowing \(\mu\) to vary. That is a sensible high-multiplicity fair-division problem, but it no longer mirrors the theorem that was cited. The paper’s crucial Lemmas 4.5 and 4.12 are explicitly restricted to two agents, and the authors identify even the three-agent case as open. A population of repeated agents therefore asks for a new many-agent theorem rather than continuizing the proved result.
One can preserve the original \(\mathrm{EF1}\) or \(\mathrm{EF[1,1]}\) semantics only by retaining a joint distribution over agents, their bundles, and their pairings. Aggregate type masses do not determine whether an individual envies another up to one item. If instead one compares type-average utilities, the result is no longer the paper’s fairness notion; the local indivisible-item exception has been replaced by an aggregate criterion. The positive proposal consequently faces a trilemma: a fixed and vacuous population distribution, an outcome-distribution model, or a genuinely new fairness problem.
There is also an unresolved Pareto issue. If the weight certificate optimizes only over fair configuration distributions, it certifies Pareto optimality only within that restricted set. If it optimizes over all configuration distributions, Theorem 4.14 gives no reason that a global weighted optimum can be decomposed into individually fair configurations under arbitrary supplies. That may be an interesting problem, but it is not a consequence of the cited theorem.
This is not an airtight universal negative. A shared-pool model with many copies of a small set of valuation types is a credible high-multiplicity regime, and it could be worth studying in its own right. But the submitted case does not establish a continuous population mirror of Theorem 4.14: its nontrivial continuity lies in allocations, while its population distribution is fixed. So I would reject this particular anchor, while admitting that a broader new many-agent extension could survive the objection.
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.