d4-journals-jair-2026-0068 (d4-journals-jair-2026-0068)

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\).

Fix an integer \(d\ge2\). Input consists of a rational \(\alpha\in(0,1]\), a finite connected undirected simple graph \(G=(V,E)\) with no induced \(K_{1,d+1}\), and rational supplies \(q_v\ge0\); write \(m=|V|\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass \(\mu_t\) a binary rational, with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. Each type has nonnegative binary-rational additive values \(w_t(v)\), satisfying \(S_t:=\sum_vq_vw_t(v)>0\) and \(w_t(v)\le\alpha S_t\) for every vertex. Let \(L\) be the total input bit length.
A bundle is \(b\in\mathbb Z_{\ge0}^{V}\) whose positive support induces a connected subgraph; the zero bundle is also allowed. Coordinates count copies of vertex goods, and its value to type \(t\) is \(\sum_vb_vw_t(v)\).
For a factor \(c\ge0\), a mass assignment consists of finitely many nonnegative rational entries \(x_{t,b}\), satisfying \(\sum_bx_{t,b}=\mu_t\), \(\sum_{t,b}x_{t,b}b_v\le q_v\), and \(\sum_vb_vw_t(v)\ge cS_t\) whenever \(x_{t,b}>0\). Unused supply is permitted.
Define \(\bar\beta_d(\alpha)=(1-\alpha)/(d-1)\) when \(d\ge3\) or when \(d=2\) and \(\alpha\ge1/2\); otherwise define \(\bar\beta_2(\alpha)=1/2\).

Does every admissible instance admit a mass assignment with factor \(\bar\beta_d(\alpha)\), constructible in time polynomial in \(m,\tau,L\) for fixed \(d\)?
For each fixed \(d,\alpha\), is \(\bar\beta_d(\alpha)\) the largest factor feasible for every admissible instance?

Discrete: with finitely many agents receiving disjoint connected vertex sets and each vertex valued at most \(\alpha\) times the agent’s proportional share, sharp agent-count-dependent guarantees are polynomial-time constructible; uniformly over agent counts, \(\bar\beta_d(\alpha)\) is sharp. [Lonc, 2026](https://doi.org/10.1613/jair.1.17263).
Continuous: no result settling this exact mass-assignment formulation was located in the searches.

Result

The first question has an affirmative answer. The proposed factor is never sharp in this mass-assignment model.

In fact, the largest universally feasible factor is
\[ C(\alpha):=\frac{k}{k+1},\qquad k:=\left\lfloor\frac1\alpha\right\rfloor. \]
It is independent of \(d\), and an assignment achieving it can be constructed in polynomial time using at most \(m\tau\) entries.

Repeated copies are essential here: a bundle supported on one vertex can contain several copies of that good.

Explicit construction and feasibility

Fix an admissible instance. For each type \(t\) and vertex \(v\) with \(w_t(v)>0\), define
\[ a_{t,v}:=\frac{w_t(v)}{S_t}, \qquad n_{t,v}:=\left\lfloor\frac1{a_{t,v}}\right\rfloor. \]
Let \(e_v\) denote the integer vector with coordinate \(1\) at \(v\) and \(0\) elsewhere. Assign mass
\[ x_{t,n_{t,v}e_v}:=\mu_tq_va_{t,v}. \]
Omit entries whose mass is zero.

Because \(0<a_{t,v}\le\alpha\le1\), the integer \(n_{t,v}\) is positive. Thus every bundle used has singleton support and is connected.

Type masses. For every type \(t\),
\[ \sum_{v:w_t(v)>0}x_{t,n_{t,v}e_v} = \frac{\mu_t}{S_t}\sum_vq_vw_t(v) = \mu_t. \]

Supply constraints. The definition of the floor gives \(a_{t,v}n_{t,v}\le1\). Consequently, the total consumption of vertex \(v\) is
\[ \sum_{t:w_t(v)>0}x_{t,n_{t,v}e_v}n_{t,v} = q_v\sum_{t:w_t(v)>0}\mu_ta_{t,v}n_{t,v} \le q_v\sum_t\mu_t = q_v. \]

Value guarantee. Fix a positive-mass entry, and abbreviate \(a=a_{t,v}\) and \(j=n_{t,v}\). Since \(a\le\alpha\),
\[ j=\left\lfloor\frac1a\right\rfloor \ge \left\lfloor\frac1\alpha\right\rfloor =k. \]
Also, \(1/a<j+1\), so \(a>1/(j+1)\). Therefore
\[ \frac{w_t(je_v)}{S_t} = ja > \frac{j}{j+1} \ge \frac{k}{k+1} = C(\alpha). \]
The last inequality follows from \(j\ge k\), by cross-multiplication.

Thus the displayed assignment satisfies every requirement with factor \(C(\alpha)\). Indeed, every bundle used has value strictly greater than this factor. The construction uses no graph property beyond the connectivity of singleton supports.

Polynomial-time construction

Compute each \(S_t\), and then compute the rational numbers \(a_{t,v}\), integers \(n_{t,v}\), and masses \(x_{t,n_{t,v}e_v}\) by exact arithmetic.

There are at most \(m\tau\) entries. Rational sums, products, quotients, and integer floors here all have bit lengths polynomial in \(L\): their numerators and denominators arise from polynomially many operations on the input rationals. The integers \(n_{t,v}\) are recorded in binary, so large copy counts do not require expanding bundles into individual copies.

Consequently, both the running time and the output length are polynomial in \(m,\tau,L\).

Matching upper bound

Let \(c>C(\alpha)\). We construct an admissible instance having no assignment with factor \(c\), even with two vertices, positive supplies, and one type.

By the definition of \(k\),
\[ \frac1{k+1}<\alpha. \]
Moreover, \(c>k/(k+1)\) implies \(c/k>1/(k+1)\). Hence there exists a rational \(a\) satisfying
\[ \frac1{k+1} < a < \min\left\{\alpha,\frac ck\right\}. \]

Take \(G\) to be a single edge with endpoints \(u,v\). This graph is connected and contains no induced \(K_{1,d+1}\) for any \(d\ge2\). Use one type of mass \(1\), with
\[ w(u)=w(v)=1, \qquad q_u=q_v=\frac1{2a}. \]
Its total supplied value is \(S=1/a>0\). The atom bound holds because \(a<\alpha\), giving \(1\le\alpha S\).

Every bundle receiving positive mass in a factor-\(c\) assignment must satisfy
\[ b_u+b_v\ge cS=\frac ca>k. \]
Since \(b_u+b_v\) is an integer, it must be at least \(k+1\). The assigned masses sum to \(1\), so total consumption must satisfy
\[ \sum_bx_b(b_u+b_v)\ge k+1. \]
But the supply constraints require
\[ \sum_bx_b(b_u+b_v) \le q_u+q_v =\frac1a <k+1, \]
a contradiction.

Thus every factor strictly greater than \(C(\alpha)\) fails on an admissible instance. Together with the construction, this proves exact sharpness.

Comparison with the proposed factor

For every allowed \(d,\alpha\), the proposed factor is strictly smaller than \(C(\alpha)\):

• If \(d\ge3\), then \(\bar\beta_d(\alpha)\le(1-\alpha)/2<1/2\le C(\alpha)\).
• If \(d=2\) and \(\alpha>1/2\), then \(\bar\beta_2(\alpha)=1-\alpha<1/2=C(\alpha)\).
• If \(d=2\) and \(\alpha\le1/2\), then \(\bar\beta_2(\alpha)=1/2\), whereas \(k\ge2\) gives \(C(\alpha)\ge2/3\).

The constructed assignment therefore establishes the requested polynomial-time guarantee, while the exact universal optimum is \(C(\alpha)\).

⟨structured verdict parsed — rendered above⟩

The output correctly resolves both questions: the proposed factor is polynomial-time constructible, and it is never sharp. The claimed universal optimum \(C(\alpha)=k/(k+1)\), where \(k=\lfloor1/\alpha\rfloor\), is established. No major or minor issues were found.

• Definitions and admissibility of the construction. Since \(S_t>0\), every normalization \(a_{t,v}=w_t(v)/S_t\) is well-defined. The construction only uses vertices with positive value, so \(0<a_{t,v}\le\alpha\le1\). Consequently, \(n_{t,v}=\lfloor1/a_{t,v}\rfloor\) is a positive integer. Each resulting bundle has singleton support, which induces a connected subgraph. Different vertices give distinct bundles for a fixed type, so the entry definition has no collisions.

• Type masses. The displayed identity is exact: summing the assigned masses gives \(\mu_t S_t/S_t=\mu_t\). Vertices with zero value contribute zero to this identity, and entries with zero mass can be omitted. All retained masses are nonnegative rationals. The assumption \(S_t>0\) ensures that each type has at least one positive-mass entry.

• Supply constraints. The floor inequality gives \(a_{t,v}n_{t,v}\le1\). Multiplying by \(\mu_tq_v\) and summing over types yields consumption at most \(q_v\), using \(\sum_t\mu_t=1\). This also covers zero supplies: every entry using such a vertex has zero mass and is omitted. There is no hidden requirement to exhaust supplies.

• Value guarantee. Both floor inequalities are used correctly. From \(a\le\alpha\), one obtains \(j=\lfloor1/a\rfloor\ge k\). From the definition of \(j\), one obtains \(1/a<j+1\), hence \(ja>j/(j+1)\). The function \(j/(j+1)\) increases for positive integers, so every retained bundle has normalized value strictly greater than \(C(\alpha)\). This implies the required weak inequality. Reciprocal boundary cases and \(\alpha=1\) are covered.

• Polynomial complexity. The bound of \(m\tau\) entries is correct. The arithmetic claim also holds for the specific operations used: each \(S_t\) is a sum of \(m\) products of input rationals, and each subsequent entry requires only a bounded number of rational operations and one integer floor. Their bit lengths remain polynomial in the input length. Binary encoding of bundle coordinates permits large copy counts without expanding copies. Even a dense vector representation has polynomial output length.

• Matching upper bound. For every \(c>C(\alpha)\), both \(\alpha\) and \(c/k\) exceed \(1/(k+1)\), so the stated open interval contains a rational \(a\). The resulting graph, masses, values, and supplies satisfy all input requirements. In particular, \(S=1/a\) and \(1\le\alpha S\). Every positive-mass bundle must contain at least \(k+1\) copies in total, because its integer copy count exceeds \(k\). Mass normalization then forces total consumption at least \(k+1\), whereas the supplies permit only \(1/a<k+1\). This is a valid contradiction for every assignment allowed by the task, including assignments with unused supply.

• Comparison and scope. All three comparisons with \(\bar\beta_d(\alpha)\) are correct. At \(d=2,\alpha=1/2\), the task’s first branch also equals \(1/2\), so the third comparison covers that boundary correctly. The construction establishes feasibility at \(C(\alpha)\), while the counterexamples exclude every larger factor. Thus the conclusion concerns a largest universally feasible factor, not merely a supremum. Graph independence is justified by the singleton construction and the admissible single-edge counterexamples.

No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩