| paper | d4-journals-jair-2026-0068 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Answer: Yes, the proposed factor is polynomial-time constructible. No, it is never sharp. The largest universal factor is \(C(\alpha)=\lfloor1/\alpha\rfloor/(\lfloor1/\alpha\rfloor+1)\), independently of \(d\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 3.3
For fixed \(d\ge2\) and rational \(\alpha\in(0,1]\), given a connected \((d+1)\)-claw-free template graph \(G=(V,E)\), a finite rational type distribution \(\mu\) with \(\sum_t\mu_t=1\), rational per-capita supplies \(q_v\ge0\), and nonnegative additive values \(w_t(v)\), where \(S_t=\sum_v q_vw_t(v)>0\) and \(w_t(v)\le\alpha S_t\), construct a finite-support mass assignment \(x_{t,b}\) over integral connected bundles \(b\in\mathbb Z_{\ge0}^{V}\) such that \(\sum_bx_{t,b}=\mu_t\), \(\sum_{t,b}x_{t,b}b_v\le q_v\), and \(\sum_vb_vw_t(v)\ge\bar\beta_d(\alpha)S_t\) whenever \(x_{t,b}>0\). Determine whether this can be done in time polynomial in \(|V|\), \(\tau\), and the rational input bit length, and whether the factor is sharp, where \(\bar\beta_d(\alpha)=(1-\alpha)/(d-1)\) for \(d\ge3\) or \(d=2,\alpha\ge1/2\), and \(\bar\beta_d(\alpha)=1/2\) for \(d=2,\alpha<1/2\).
A finite template graph whose vertices are parcel classes, with \(q_v\) identical goods per capita and complete additive valuation vectors as types. The assignment distributes type mass over integral connected bundles; only the population is split across bundles, while each assigned unit of mass receives a whole bundle.
The land-consolidation interpretation depends on a replicated graph where copies within each parcel class form a clique and copies of adjacent classes are completely joined; the proponent acknowledges a narrow regime but gives no concrete land layout showing this adjacency pattern.
fatal: False
This question mirrors Theorem 3.3 and the limiting guarantee in Corollary 3.8. Theorem 4.1’ has a separate continuous pmms mirror; this question leaves that result and the paper’s other auxiliary results aside.
The strongest mirror is a large land-consolidation scheme: many landowners, parcels joined by an adjacency graph, and each owner receives a connected plot. A landowner’s type is their complete additive valuation vector over parcel classes. In a large scheme, the number \(N\) of owners can greatly exceed the number \(\tau\) of distinct valuation types. This is a regime of the instance, not a claim that every land-allocation problem has high multiplicity.
Here is a continuous model that keeps each person’s bundle integral. Take a finite connected \((d+1)\)-claw-free graph \(G\) of parcel classes, type masses \(\mu_t\) with \(\sum_t\mu_t=1\), and per-capita parcel supplies \(q_v\). Type \(t\) values one copy of class \(v\) at \(w_t(v)\). A bundle is an integer vector \(b\in\mathbb Z_{\ge0}^{V(G)}\) whose nonempty support is connected, and its value is \(u_t(b)=\sum_v b_vw_t(v)\). Let \(x_{t,b}\) be the mass of type \(t\) receiving that bundle. The constraints are
\[
\sum_b x_{t,b}=\mu_t,\qquad
\sum_{t,b}x_{t,b}b_v\le q_v\quad\text{for every }v.
\]
Thus the assignment is fractional only across mass: each individual in each assigned group still receives an integral bundle of goods.
This has a direct high-multiplicity interpretation. For suitable \(N\), instantiate \(N\mu_t\) owners and \(Nq_v\) copies of each parcel class. Make copies within a class a clique and copies of adjacent classes mutually adjacent. Connected bundles in this graph correspond to the integer vectors \(b\); this blow-up preserves the claw-free restriction. Identical owners share the same complete valuation vector. Per-capita supply scaling is a co-modification of the goods model, while the population is the object being continuized.
My lead anchor is Theorem 3.3, proved in this paper. For integers \(d\ge2,n\ge1\) and \(\alpha>0\) with \((n-1)\alpha\le n\), it defines
\[
\beta_n(\alpha)=
\begin{cases}
\dfrac{n-(n-1)\alpha}{(n-1)(d-1)+1},
& d\ge3\text{ or } \bigl(d=2\text{ and }\alpha\ge \dfrac{n}{2n-1}\bigr),\\[6pt]
\dfrac{n}{2n-1},
& d=2\text{ and }\alpha<\dfrac{n}{2n-1}.
\end{cases}
\]
For every connected \((d+1)\)-claw-free graph and every set of \(n\) agents whose value for each individual good is at most \(\alpha S_i/n\), there is a \(\beta_n(\alpha)\)-proportional allocation, computable in polynomial time. For every \(\beta'>\beta_n(\alpha)\), some such graph and agents admit no \(\beta'\)-proportional allocation. The theorem’s algorithm and tightness claims are both proved here.
The corresponding Continuum Connected Proportional Allocation problem is: given rational \(G,\mu,q,w\), with \(S_t=\sum_v q_vw_t(v)>0\) and \(w_t(v)\le\alpha S_t\), find a mass assignment \(x\) such that every bundle receiving positive mass satisfies \(u_t(b)\ge\lambda S_t\). For \(\alpha\in(0,1]\), the natural target is the large-population limit supplied by Corollary 3.8, also proved here:
\[
\bar\beta_d(\alpha)=
\begin{cases}
\dfrac{1-\alpha}{d-1},
& d\ge3\text{ or } \bigl(d=2\text{ and }\alpha\ge\tfrac12\bigr),\\[5pt]
\tfrac12,
& d=2\text{ and }\alpha<\tfrac12.
\end{cases}
\]
I expect a Class A result for fixed \(d\), with a sparse allocation computed in time polynomial in \(|V(G)|,\tau\), and the rational input bit length. Whether the finite-\(n\) tight examples remain tight when type mass can be split arbitrarily is a further question; the continuous problem should determine its own sharp boundary.
A second, broader anchor is Theorem 4.1′, proved in this paper. For every \((d+1)\)-claw-free graph and any \(n\) agents, there is an \(n/[d(n-1)+1]\)-pmms allocation, computable in polynomial time. Here the packing maximin share is defined by packing connected bundles and may leave goods unused. The guarantee tends to \(1/d\) as the population grows.
Its continuous mirror, Continuum Connected Packing-MMS Allocation, uses the same mass and supply model. Define \(M_t\) as the supremum \(z\) for which a unit mass of type \(t\) can be assigned connected integer bundles of value at least \(z\), using at most supply \(q_v\) of each class. Given a heterogeneous type population, the question is to compute \(x\) satisfying the mass and supply constraints above and \(u_t(b)\ge M_t/d\) whenever \(x_{t,b}>0\). I expect this target to be Class A, again with complexity measured in \(|V(G)|,\tau\), and bit length. The further question is the best universal continuous factor: does it exceed \(1/d\), particularly for \(d=2\), and how do the paper’s cycle upper bounds behave when mass is splittable?
These are recognizable continuations of the paper’s allocation questions: the same agents’ additive valuations, graph constraint, connected integral bundles, and fairness benchmarks remain. The model does not continuize the bundles. It groups owners with identical problem-relevant valuations and gives the growing goods stock a per-capita description.
The weak point is twofold. The repeated parcel-class construction must fit a real setting: large land schemes with many owners, a modest number of valuation profiles, and bounded-degree parcel adjacency are plausible, but not every land map has that structure. And the paper’s polynomial time bound for explicit finite instances does not itself imply polynomial time in the binary encoding of \(\mu\) and \(q\). The continuous configuration problem has many possible bundles, so its pricing or compression step needs proof. Those are genuine open computational tasks; they do not make the mirror a different allocation problem.
The paper has no numbered hardness theorem to anchor a hardness-transfer claim; these anchors are positive algorithmic results. My case covers its proportional and maximin allocation results, rather than claiming that every part of the paper needs a continuous counterpart.
The strongest case against both anchors is that a fixed type space for agents is easy to posit, but a fixed type space for goods is doing much more work than the paper’s applications support. The proposed model needs the stock to grow with the population: with a fixed graph of \(m\) goods, Theorem 3.3’s proportionality hypothesis itself forces \(m\ge n/\alpha\). Co-scaling supplies is allowed, but preserving connected bundles while doing so requires repeated copies of each good class to be interchangeable in the graph: copies within a class form a clique, and copies in adjacent classes are joined completely. That is a special network structure. In land or room allocation, adjacency usually depends on the individual locations; a realistic growing graph then tends to grow the number of distinct good classes too. The proposed mirror remains coherent, but its natural setting is a replicated network, not the broad class of spatial allocation problems motivating the paper.
For Theorem 3.3, the strongest mirror is the proposed mass assignment over integral connected bundles, with per-capita supplies and full valuation vectors as types. The objection is not that this is ill-defined. It is that the theorem’s polynomial algorithm is for an explicit instance, with goods and agents listed individually. Clearing denominators in rational masses and supplies can produce an expanded instance whose size is exponential in the compact input length. Nor does the paper supply a finite list of bundle configurations or an efficient pricing method for the resulting configuration problem. Thus the continuous question needs a new algorithmic result at precisely the point where the finite theorem stops supporting it. That makes it a plausible research problem, while weakening the claim that this theorem already points to a useful continuous algorithm.
For Theorem 4.1′, the proposed type-specific benchmark \(M_t\) is a reasonable way to express the maximin share per capita. But computing it and then meeting it for all types is a coupled configuration-allocation problem. The paper’s proof goes through Lemma 4.5, which removes individual agents and goods and applies proportional-allocation guarantees to the remaining finite instance. That argument offers no immediate compression when a type’s mass can be split across many bundles. A better mirror could seek a new configuration or convex optimization argument for that coupled problem; the paper gives no reason to expect one.
These points do not establish that either question is unworthy. In particular, the graph construction does preserve the formal claw-free and connectivity conditions, and large systems with repeated network modules and a small number of complete valuation profiles are conceivable. The computational gap in the compact encoding is also exactly where a useful result could live. So I cannot honestly defend the requested universal claim that no worthwhile mirror exists. The negative case is strongest as a warning that both anchors require a narrow replicated-network interpretation and a new high-multiplicity algorithm; it does not defeat the proponent’s model outright.
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.