| paper | Approximating Fair Division on D-Claw-Free Graphs |
| authors | Zbigniew Lonc |
| venue | IJCAI 2023 |
| filed under | fairalloc · shares |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | no |
The paper has no numbered result asserting an algorithmic or computational-complexity property; the polynomial-time observation appears only in an unnumbered final remark. Moreover, the proposed \(x_{\theta,B}\) formulation lets mass share one copy of an indivisible good and therefore requires a new repeated-resource model. Thus bit (a) fails, regardless of whether that redesigned model might later be worthwhile.
fails bit a — no named computational result to mirror
The opponent's source-gate objection is unanswered: Theorem 1 is not a numbered computational result, and the proposed capacity constraints do not encode allocations of the paper's indivisible goods.
fatal: True
The proposed mirror targets Theorem 1's existence guarantee; Theorem 2, Theorem 2′, Lemma 2, and Proposition 1 are not computational anchors either.
Strictly speaking, this paper has no numbered computational-complexity result. Theorem 1, Theorem 2, Theorem 2′, Lemma 2, and Proposition 1 are existence or structural statements; none asserts membership in P, NP-hardness, FPT, or similar. The computational statements occur only in the unnumbered final remarks: the proof of Theorem 1 “can be easily turned into a polynomial time algorithm”, whereas the proof of Theorem 2 uses packing maximin share values that are NP-hard to compute. Thus, under the literal anchor rule, this is a no-named-complexity-result paper.
The strongest positive case nevertheless comes from the named and proved-here Theorem 1, whose constructive content is explicitly identified as polynomial-time in the final remarks.
My proposed mirror is Continuous Bounded-Proportional Connected Allocation. Let \(G\) be a connected \((d+1)\)-claw-free graph of goods, let \(\Theta\) be a finite set of utility types, and let \(\mu\) be a distribution over \(\Theta\). A type \(\theta\) is a complete additive utility vector \(u_\theta:V(G)\to\mathbb{Q}_{\ge 0}\); agents of that type are indistinguishable. Let \(\rho\) be the population scale, so the mass of type \(\theta\) is \(\rho\mu_\theta\). Define \(U_\theta=\sum_{v\in V(G)}u_\theta(v)\).
The \(\alpha\)-boundedness assumption is the direct continuous version of the paper’s assumption:
\[ u_\theta(v)\le \alpha\frac{U_\theta}{\rho} \qquad\text{for every }\theta\text{ and }v. \]
Let \(\mathcal{C}(G)\) be the connected nonempty vertex sets of \(G\). A solution is a nonnegative mass allocation \(x_{\theta,B}\), where \(x_{\theta,B}\) is the mass of type-\(\theta\) agents receiving the whole connected bundle \(B\). It must satisfy
\[ \sum_{B\in\mathcal{C}(G)}x_{\theta,B}=\rho\mu_\theta \]
for every type \(\theta\), and
\[ \sum_{\theta}\sum_{B\ni v}x_{\theta,B}\le 1 \]
for every good \(v\). The objective is to maximize
\[ \eta(x)= \min_{\theta,B:x_{\theta,B}>0} \frac{\rho\,u_\theta(B)}{U_\theta}, \qquad u_\theta(B)=\sum_{v\in B}u_\theta(v). \]
Equivalently, the decision version asks whether there is an allocation with \(\eta(x)\ge \beta(\alpha)\), where
\[ \beta(\alpha)= \begin{cases} \dfrac{1-\alpha}{d-1}, & d\ge 3\text{ or }(d=2,\alpha\ge \frac12),\[4pt] \frac12, & d=2\text{ and }\alpha<\frac12. \end{cases} \]
This is not a lottery over outcomes for one named agent. Each infinitesimal agent receives an entire connected bundle; \(x\) merely records how much population receives each bundle. At integral scale, \(x_{\theta,B}\) is the number of identical agents assigned \(B\), so this is precisely the high-multiplicity relaxation of the paper’s allocation problem.
The regime is plausible. Take many standardized regional service providers, research groups, or land-management teams, with only a small number of utility profiles, while the graph of routes, rooms, or plots grows proportionally. Then \(|\Theta|=\tau\) remains small while \(\rho\) and \(|V(G)|\) grow. In fact, the paper’s own sharpness construction for Theorem 1 already exhibits this regime: it uses \(n=k+1\) agents with exactly the same utility function while the graph grows with \(k\). Thus the proposed mirror is not imposed on an unrelated story; the paper itself studies a one-type, high-multiplicity family.
Theorem 1 is proved in this paper. It says that every such finite instance has a \(\beta(\alpha)\)-proportional allocation, and the final remarks state that its proof yields a polynomial-time construction. I would expect the continuous problem to be Class A. The block decomposition and bipolar-ordering argument is structural rather than dependent on the identities of individual agents. In the mass version, one should be able to remove a positive amount of one type at a time, or formulate the construction as a flow/configuration LP over connected bundles. The natural target is an exact algorithm polynomial in \(|V(G)|\), \(\tau\), and the encoding length, with complexity independent of the total multiplicity.
The main further questions are whether the mass allocation can be rounded to an integral allocation with only \(O(1/\rho)\) loss, whether the sharp \(\beta(\alpha)\) bound remains tight in the limit, and whether the connected-bundle configuration LP admits efficient separation on all \((d+1)\)-claw-free graphs.
The weakest point is that the normalized capacity constraints and real-valued \(x_{\theta,B}\) can be accused of fractionalizing goods. That objection would be valid if \(x\) meant that one named indivisible good could be split among agents. My intended interpretation is instead the high-multiplicity limit: at scale \(K\), there are \(K\) repeated copies of the goods and \(Kx_{\theta,B}\) agents receive whole bundles; the continuous variables record normalized counts. If the programme insists that the graph of goods remain fixed while only the population becomes continuous, then no nontrivial mirror exists here: finitely many indivisible goods cannot serve a genuinely nonatomic population. Under the programme’s high-multiplicity reading, however, Theorem 1 supplies a credible and unusually well-matched positive mirror.
The proponent’s anchor fails at the source gate. Theorem 1 is an existence theorem, not a numbered computational result. Its statement does not assert membership in \( \mathrm{P} \), hardness, approximation complexity, or even a formally specified algorithmic problem. The final remark that its proof “can be easily turned into a polynomial time algorithm” is an informal observation, not the named computational result required here. The proposed continuous optimization problem is therefore newly manufactured rather than a mirror of a computational theorem in the paper.
Even granting that generous reinterpretation, the proposed formulation is not a faithful high-multiplicity limit of the paper’s model. In the paper, each vertex is one indivisible good and can belong to at most one agent’s bundle. In the proposed constraints,
\[ \sum_{\theta,B\ni v}x_{\theta,B}\le 1, \]
a positive mass of agents can receive the same bundle \(B\) while consuming only one unit of each good. That is not what happens with one indivisible copy of \(v\). If \(x_{\theta,B}\) is interpreted as a normalized count, clearing denominators produces \(Kx_{\theta,B}\) agents, but it requires \(K\) copies of every good. The original instance has one copy. If instead the supply remains fixed, total feasible population mass is bounded by \(|V(G)|\), and the purported continuum simply becomes infeasible.
More seriously, the per-vertex inequalities are only a fractional configuration-packing relaxation. They are not the convex hull of allocations into disjoint connected bundles. On a triangle, suppose two-vertex connected bundles clear a target while singleton bundles do not. Assigning mass \(1/2\) to each of the three edges satisfies every vertex-capacity constraint and serves total mass \(3/2\). But one triangle contains only one pairwise disjoint edge bundle, so no integral allocation realizes this solution. With \(K\) disjoint copies, the proposed point serves \(3K/2\) agents although the copies serve at most \(K\). Denominator clearing therefore does not recover the finite allocation problem.
The best repair is to scale resources as well: introduce \(K\) copies of the graph, specify whether bundles must lie within one copy or may use a graph blow-up, and require the aggregate bundle census to decompose into per-copy allocations. That is a legitimate repeated-facility or multi-unit resource model, but it is a joint population-and-resource scaling, not continuization of the population alone. Different choices of copy topology produce different problems. If bundles are restricted to separate copies, the per-copy decomposition is missing from the proposed LP; if copies are freely linked, connectivity has been changed.
Nor does Theorem 1 establish the needed compressed algorithm for that repaired model. Its proof removes agents and bundles one at a time. Running such a construction after clearing a denominator may take time proportional to the multiplicity, and the paper gives no theorem showing that equal-type masses can be processed in batches in time polynomial in \( \log K \), the number of types, and the graph size. The proposed claim of a polynomial continuous algorithm is consequently speculation, not a consequence of the paper.
The sharpness construction does show many identical agents, but only while the graph and its supply grow with the number of agents. That is evidence that a repeated-agent regime can be invented, not evidence for a population-only mirror. With a fixed graph, the boundedness condition
\[ u_i(v)\le \alpha \frac{u_i(V)}{n} \]
eventually fails as \(n\) grows, and positive-fairness allocation becomes impossible for the elementary reason that there are too few indivisible goods. Allowing goods to be split among agents would avoid that failure, but would move the problem into outcome-space continuity, explicitly outside ChoCo’s scope.
A repeated-building or repeated-network extension might be worthwhile as a new fair-division model. It does not rescue this paper’s anchor: it changes the resource ontology, requires new decomposition constraints, and has no named computational result here to mirror. Under the programme’s stated screening rule, this paper should therefore receive a negative verdict. The claim that no imaginable extension could ever be interesting would be too strong; the defensible claim is that no qualifying continuous population mirror is supplied or supported by this paper.
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.