| paper | Welfare Loss in Connected Resource Allocation |
| authors | Xiaohui Bei, Alexander Lam, Xinhang Lu, Warut Suksompong |
| venue | IJCAI 2024 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper’s numbered results, including Theorem 3.13, are welfare-ratio bounds; the only NP-hardness statement is unnumbered, and Algorithm 3 assumes OPT\text{-}egal(I)\u0000. The proposed path census is a plausible high-multiplicity extension of the authors’ office-allocation setting, so continuity is not the fatal issue. ChoCo’s named-result requirement nevertheless fails, making the grade red.
fails bit a — no named computational result to mirror
Theorem 3.13 is a welfare-ratio statement, while Algorithm 3 presupposes OPT\text{-}egal(I)\u0000; hence no numbered result asserts a computational complexity or algorithmic guarantee.
fatal: True
The candidate mirrors only the path egalitarian price result in Theorem 3.13 and its moving-knife construction; it leaves the other egalitarian graph classes, all utilitarian price results, and the paper’s unnumbered NP-hardness observation alone.
The strict answer is that this paper has no qualifying named computational-complexity anchor. Its numbered results are welfare-ratio theorems, not theorems stating membership in \(P\), NP-hardness, W[1]-hardness, or FPT. The sentence after Lemma 3.2 saying that optimal egalitarian allocation is “known to be NP-hard” is unnumbered. Thus a fully literal ChoCo verdict would record “no named computational result.” The strongest positive case is nevertheless built around the paper’s most constructive named result.
My lead anchor is Theorem 3.13, proved in this paper. For a path \(P_m\), it establishes
\[
\mathrm{Egal\text{-}PoC}(P_m,n)=
\begin{cases}
m-n+1,&n\le m<2n-1,\\
n,&m\ge 2n-1,
\end{cases}
\]
and its proof gives Algorithm 3, a discretized moving-knife procedure. This is not itself a polynomial-time theorem—the procedure is supplied with \(\mathrm{OPT\text{-}egal}(I)\), and Lemma 3.2 invokes an optimal egalitarian allocation—so I would present it as a constructive welfare anchor, not mislabel it as a \(P\)-result.
The natural mirror is \(\textsc{Mass-Path-Egal}_{\infty}\). Consider a path of item sites \(1,\ldots,m\), a finite set \(T\) of complete utility types, and a society distribution \(\mu\in\Delta(T)\). Type \(t\) specifies the full additive utility vector \(u_t(1),\ldots,u_t(m)\). Let \(M\) be the total population mass, so type \(t\) has mass \(M\mu_t\). Item supplies \(b_j\) scale with the population; they remain indivisible copies, not divisible goods.
A connected bundle is an interval \(I=[a,b]\). The decision variable is a bundle census \(x_{t,I}\ge0\): the mass of type-\(t\) agents receiving the entire interval \(I\). It must satisfy
\[
\sum_I x_{t,I}=M\mu_t
\]
for every type \(t\), and
\[
\sum_{t,I:j\in I}x_{t,I}=b_j
\]
for every site \(j\). The egalitarian value of a census is the largest \(z\) such that
\[
x_{t,I}>0\quad\Longrightarrow\quad
u_t(I):=\sum_{j\in I}u_t(j)\ge z.
\]
The problem is to output a feasible rational census maximizing \(z\). Its price-of-connectivity version also computes the unrestricted benchmark by allowing arbitrary subsets \(S\subseteq[m]\), and asks for the ratio between the unrestricted and interval-restricted optima.
This is a genuine high-multiplicity scenario: many research groups, hospital teams, or departments receive connected offices along a corridor, while only a small catalogue of standardized space-preference profiles exists. The regime is \(M\to\infty\), \(m=\Theta(M)\), and fixed or slowly growing \(\tau=|T|\), so \(M/\tau\) is large. This is exactly the kind of office allocation scenario the authors themselves give, with the population represented by fractions of groups rather than named individuals.
The census does not fractionalize an individual bundle. If all data are rational, clearing denominators turns \(x\) into an ordinary finite allocation of cloned agents and indivisible item copies: every clone receives one whole interval, and every item copy is used once. Thus the model has rational-clone fidelity to the paper. The continuous object is the population/type census, not a divisible office or a fractional utility.
For the connected side on a path, I expect Class A. For a fixed threshold \(z\), only the \(O(m^2)\) intervals whose utility for type \(t\) is at least \(z\) need be considered, yielding a rational LP with \(O(\tau m^2)\) variables. This is the same structural phenomenon behind the paper’s moving-knife argument, expressed as a high-multiplicity configuration formulation. The exact continuous analogue of the paper’s \(n\)-factor should not simply be obtained by replacing \(n\) with \(\tau\); determining the correct mass-sensitive price is a further theorem.
The mirror covers only the path-based egalitarian result, not the paper’s utilitarian results or its general graph bounds. Its main unresolved questions are whether the continuous price depends only on \(\tau\), on the mass vector \(\mu\), or on both; whether the unrestricted benchmark remains tractable in compressed encoding; and whether connected-bundle pricing on trees or general graphs produces a genuine Class C boundary.
The weakest point is the necessary joint scaling of population and item supply. With a fixed finite set of indivisible goods and an atomless growing population, egalitarian welfare quickly degenerates because most agents receive nothing. Scaling supplies with the population is therefore essential, but it makes this an extension of the paper’s model rather than a literal population-only limit. If ChoCo disallows that extension, then the honest conclusion is simply that this paper has no qualifying continuous mirror anchored in a named complexity result.
The strongest case against starts with the paper’s status under ChoCo’s rules: it has no qualifying named computational-complexity anchor. Theorem 3.13 is a welfare-ratio theorem, not a theorem about the complexity of a decision or optimization problem. Algorithm 3 is not an algorithm in the required sense: it is given \(\mathrm{OPT\text{-}egal}(I)\), while the paper explicitly notes that obtaining an optimal egalitarian allocation is NP-hard. Thus the proponent’s anchor is constructive mathematics, but not a named computational result.
The literal population limit also degenerates. The paper has \(m\) one-copy goods and partitions them among \(n\) agents. With \(m\) fixed and population mass tending to infinity, almost all agents receive nothing; egalitarian welfare becomes zero. If empty bundles are permitted, the price ratio falls into the paper’s \(0/0\) convention. A nontrivial limit therefore requires scaling the resource side as well.
That is exactly what the proposed \(b_j\)-copy model does, but it changes the problem. Vertices are no longer individual goods in a graph allocation; they are capacitated sites, with many co-located copies and a new definition of connected support. This is a legitimate connected fair-division problem, but it is not a high-multiplicity version obtained by replacing the agent population with a distribution. It is a jointly scaled resource-and-population model, and Theorem 3.13 provides no computational result about it.
Trying to preserve the original one-copy model does not solve the problem. One can let \(m\) grow with the population, but then a complete utility type is a vector of length \(m\). To retain the paper’s arbitrary utility profiles, the number of distinct types can grow essentially one-for-one with the agents; \(\tau\) then ceases to be a compressed multiplicity parameter. If one instead fixes a small catalogue of repeated utility vectors, one has restricted the supremum over utility profiles that defines the paper’s price of connectivity. The resulting question may be sensible, but it is a new restricted model, not a mirror of the named theorem.
There is also a structural mismatch in what \(n\) means. In the paper, every individually distinct agent needs one connected bundle, and the theorem’s guarantee is expressed in terms of that number \(n\). In the proposed census, many interchangeable agents of one type can be represented by many interval assignments. The type masses govern capacity, but they do not preserve the individual-agent structure behind the theorem. Introducing a mass-weighted or quantile version of egalitarian welfare could repair that, but it would be a new welfare objective.
The proposed path LP may well be worth studying independently: interval configurations are polynomially enumerable, and the unrestricted benchmark can likely be written as a transportation LP. But that is not evidence that this paper contains a worthwhile ChoCo mirror. It is an invented capacitated extension whose tractability follows from the path structure, while the paper contributes neither a named complexity theorem nor a high-multiplicity formulation motivating it.
So I would reject this paper as a ChoCo anchor. The negative case is not an impossibility proof: a standardized-office interpretation could support an interesting new continuous allocation problem. Its weakness is precisely that such a project would be an extension inspired by the paper, not a continuous computational mirror of one of its named results.
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.