Tree Splitting Based Rounding Scheme for Weighted Proportional Allocations with Subsidy (d4-conf-wine-2024-0024)

Given rational data consisting of worker types \(T\) with masses \(\mu_t\), obligations \(a_t>0\) satisfying \(\sum_t\mu_ta_t=1\), \(q\) chore classes with per-capita supplies \(\lambda_j\), costs \(c_{tj}\in[0,1]\), and bundle bound \(B\), let \(\mathcal{B}_B=\{b\in\mathbb{Z}_{\ge0}^q:\sum_{j=1}^q b_j\le B\}\). Compute or decide the optimum \(S^*\) over \(\theta_{t,b}\ge0\) satisfying \(\sum_{b\in\mathcal{B}_B}\theta_{t,b}=\mu_t\) and \(\sum_{t\in T,b\in\mathcal{B}_B}\theta_{t,b}b_j=\lambda_j\), where \(S^*=\min_\theta\sum_{t,b}\theta_{t,b}(\sum_jb_jc_{tj}-a_tC_t)^+\) and \(C_t=\sum_j\lambda_jc_{tj}\); determine in particular whether \(S^*\le 1/3\) for every feasible instance and how complexity changes when \(q\) or \(B\) varies.

A society is given by its support: the list \(T\) of the \(\tau\) types with positive masses \(\mu_t\), each encoded as a binary rational; \(\tau\) is the support size, not the number of possible types. Normalize \(\sum_t\mu_t=1\).
There are \(q\geq1\) chore classes, with rational per-capita supplies \(\lambda_j\geq0\), additive unit costs \(c_{tj}\in[0,1]\), and rational obligations \(a_t>0\) satisfying \(\sum_t\mu_ta_t=1\). The bundle bound \(B\in\mathbb Z_{\geq0}\) is encoded in binary.
Set \(\mathcal B_B=\{b\in\mathbb Z_{\geq0}^q:\sum_jb_j\leq B\}\) and \(C_t=\sum_j\lambda_jc_{tj}\). Each worker receives an integer bundle; a type's mass may be split among bundles, including the empty bundle.
An allocation consists of masses \(\theta_{t,b}\geq0\) satisfying \(\sum_{b\in\mathcal B_B}\theta_{t,b}=\mu_t\) and \(\sum_{t,b}\theta_{t,b}b_j=\lambda_j\) for every class \(j\). Instances are promised feasible.
The minimum subsidy for a type-\(t\) worker receiving \(b\) is \((\sum_jb_jc_{tj}-a_tC_t)^+\), where \(x^+=\max\{x,0\}\); define \(S^*=\min_\theta\sum_{t,b}\theta_{t,b}(\sum_jb_jc_{tj}-a_tC_t)^+\).
The decision input also contains a binary rational threshold \(K\geq0\). Let \(L\) be the total input bit length and \(m=q\) the number of listed chore classes; there is no finite total item count.

Is deciding \(S^*\leq K\) in \(\mathrm P\) or \(\mathrm{NP}\)-hard, and how does the classification change when \(q\), \(B\), or both are fixed? State running times in \(m\), \(\tau\), \(L\), and \(B\).
Does \(S^*\leq1/3\) hold for every feasible instance?

Discrete: for positive normalized weights and additive chore costs bounded by one, a connected fractional bid-and-take sharing tree containing an item shared by at least three agents admits polynomial-time rounding with total subsidy at most \((n-1)/3\), where \(n\) is the number of agents. [Verified source](https://arxiv.org/html/2404.07707v1).
No result settling this precise mass problem was located in the literature search.

1. Classification and running times

I use the standard bit-model interpretation that the explicitly listed costs \(c_{tj}\) are also binary rationals.

The general decision problem is \(\mathrm{NP}\)-complete, already for \(\tau=1\) and \(K=0\). Fixing either \(q=m\) or \(B\) makes it polynomial-time solvable. The proposed universal bound is false: a feasible instance with \(m=B=1\) has \(S^*=3/8\).

The following are valid running-time bounds; all hidden polynomial exponents are absolute constants.

| Parameters | Classification | Running-time upper bound |
|---|---|---|
| General | \(\mathrm{NP}\)-complete | \(\bigl(\tau\binom{B+m}{m}+\tau+m+L\bigr)^{O(1)}\) |
| Fixed \(m=q\) | \(\mathrm P\) | \(2^{O(m\log(m+1))}\operatorname{poly}(\tau,m,L,\log(B+1))\) |
| Fixed \(B\) | \(\mathrm P\) | \(\bigl(\tau(m+1)^B+\tau+m+L\bigr)^{O(1)}\) |
| Both fixed | \(\mathrm P\) | \(\operatorname{poly}(\tau,L)\) |

The fixed-\(m\) bound depends logarithmically on \(B\). In contrast, the fixed-\(B\) enumeration bound has a polynomial degree depending on \(B\).

2. The configuration LP and polynomial certificates

Define
\[ \]
\(h_t=a_tC_t\) and \(f_t(b)=(c_t\cdot b-h_t)^+\).

The allocation problem is the finite rational linear program
\[ \]
\(\displaystyle \min_{\theta\geq0}\sum_{t,b}f_t(b)\theta_{t,b},\)
subject to
\[ \]
\(\displaystyle \sum_b\theta_{t,b}=\mu_t\quad(t\in T),\qquad \sum_{t,b}b_j\theta_{t,b}=\lambda_j\quad(j=1,\ldots,m).\)

There are \(\tau\binom{B+m}{m}\) variables and \(\tau+m\) equality constraints. Every variable satisfies \(0\leq\theta_{t,b}\leq\mu_t\), so feasibility implies that the feasible set is nonempty and compact. Consequently, an optimum exists.

For completeness, feasibility is equivalent to \(\sum_j\lambda_j\leq B\). Necessity follows by summing the supply equalities. For sufficiency when \(B>0\), give every type the same bundle distribution: probability \(\lambda_j/B\) on \(Be_j\), and the remaining probability on the empty bundle. Multiplying these probabilities by \(\mu_t\) gives a feasible allocation. When \(B=0\), feasibility requires every supply to vanish.

Polynomial certificates

An optimal basic feasible solution has at most \(\tau+m\) positive variables. Each selected bundle is encoded using \(O(m\log(B+1))\) bits.

The equality matrix has integer entries bounded by \(\max\{1,B\}\). For a basic solution, select an invertible square submatrix of order \(r\leq\tau+m\). Hadamard’s inequality bounds its determinant by
\[ \]
\(\displaystyle r^{r/2}\max\{1,B\}^{r}.\)

Clearing the denominators of the relevant right-hand-side entries and applying Cramer’s rule therefore gives polynomial-length rational masses. The subsidy coefficients are also computable exactly with polynomial bit length from the input and the selected bundles.

Thus a yes-certificate lists at most \(\tau+m\) bundle–mass pairs. All allocation equalities and the subsidy inequality can be checked by exact rational arithmetic in polynomial time. This proves membership in \(\mathrm{NP}\).

Enumeration

Enumerating all bundles and solving the displayed LP gives the general running time in the table. Moreover,
\[ \]
\(\displaystyle |\mathcal B_B|=\binom{B+m}{m}\leq(m+1)^B.\)

To see the inequality, encode a bundle by a length-\(B\) sequence over the \(m\) classes plus an empty-slot symbol; every bundle has such an encoding. Hence fixed \(B\) gives polynomial time, and fixing both parameters gives \(\operatorname{poly}(\tau,L)\).

3. NP-hardness with one supported type

We reduce from Partition: given positive integers \(w_1,\ldots,w_r\) with even total \(W=\sum_iw_i\), decide whether some subset sums to \(W/2\). This restriction remains \(\mathrm{NP}\)-complete: doubling every integer converts an unrestricted Partition instance into an equivalent instance with even total.

Construction

Set
\[ \]
\(\displaystyle D=rW+1,\qquad M=D^r+W.\)

Use one type with \(\mu=a=1\), and \(2r\) classes indexed by \((i,s)\), where \(i=1,\ldots,r\) and \(s\in\{0,1\}\). Set
\[ \]
\(\displaystyle B=r,\qquad K=0,\qquad \lambda_{i,0}=\lambda_{i,1}=\frac12,\)
and
\[ \]
\(\displaystyle c_{i,0}=\frac{D^i}{M},\qquad c_{i,1}=\frac{D^i+w_i}{M}.\)

All costs lie in \([0,1]\), since \(D^i+w_i\leq D^r+W=M\). The normalization conditions hold. The total supply is \(r=B\), so the instance is feasible by Section 2.

Every constructed number has polynomial encoding length: in particular, \(\log M=O(r\log D)\).

The single type’s baseline is
\[ \]
\(\displaystyle C=\sum_{i,s}\lambda_{i,s}c_{i,s} =\frac{\sum_{i=1}^rD^i+W/2}{M}.\)

Zero subsidy forces every used bundle to have cost exactly \(C\)

For every feasible allocation,
\[ \]
\(\displaystyle \sum_b\theta_b(c\cdot b)=c\cdot\lambda=C,\qquad \sum_b\theta_b=1.\)

If its total subsidy is zero, every positive-mass bundle satisfies \(c\cdot b\leq C\). Their mean is \(C\), so every such bundle must actually satisfy \(c\cdot b=C\).

Since an optimum exists, \(S^*=0\) therefore implies the existence of a bundle satisfying
\[ \]
\[\displaystyle \sum_{i=1}^r(b_{i,0}+b_{i,1})D^i+ \sum_{i=1}^rw_ib_{i,1} = \sum_{i=1}^rD^i+\frac W2. \tag{1}\]

The digit encoding forces a partition

Because the bundle has at most \(r\) chores,
\[ \]
\(\displaystyle 0\leq\sum_iw_ib_{i,1}\leq rW<D,\qquad 0\leq b_{i,0}+b_{i,1}\leq r<D.\)

Also \(W/2<D\). Thus both sides of (1) are already valid base-\(D\) expansions, with no carries. Uniqueness of that expansion gives
\[ \]
\(\displaystyle b_{i,0}+b_{i,1}=1\quad\text{for every }i,\qquad \sum_iw_ib_{i,1}=\frac W2.\)

Consequently, the indices with \(b_{i,1}=1\) form a partition.

Conversely, suppose a partition exists. Construct a bundle choosing class \((i,1)\) for indices in the partition and class \((i,0)\) otherwise. Construct a second bundle making the complementary choices. Both have \(r\) chores and cost exactly \(C\). Giving each bundle mass \(1/2\) supplies every class in amount \(1/2\) and incurs zero subsidy.

We have proved
\[ \]
\(\displaystyle S^*\leq0\quad\Longleftrightarrow\quad \text{the Partition instance is a yes-instance}.\)

This is a polynomial reduction whose outputs always satisfy the feasibility promise. Together with Section 2, it proves the general \(\mathrm{NP}\)-completeness claim.

4. Polynomial time for fixed \(q=m\)

Enumeration alone would give a dependence polynomial in the numerical value of \(B\). To obtain dependence on its binary length, use the LP dual:
\[ \]
\(\displaystyle \max_{u,v}\left(\sum_t\mu_tu_t+\sum_j\lambda_jv_j\right),\)
subject to
\[ \]
\(\displaystyle u_t+v\cdot b\leq f_t(b) \quad(t\in T,\ b\in\mathcal B_B).\)

Here \(u\in\mathbb R^\tau\) and \(v\in\mathbb R^m\) are unrestricted. Ordinary finite-dimensional LP duality identifies its optimum with \(S^*\).

Exact separation using two integer programs per type

Given rational \(u,v\), define
\[ \]
\(\displaystyle \gamma_t(v)=\min_{b\in\mathcal B_B}\bigl(f_t(b)-v\cdot b\bigr).\)

The constraints for type \(t\) hold exactly when \(u_t\leq\gamma_t(v)\). Split the minimization into the two regions defining the positive part:
\[ \]
\(\displaystyle \gamma_t^-= \min\{-v\cdot b: b\in\mathbb Z_{\geq0}^m,\ \sum_jb_j\leq B,\ c_t\cdot b\leq h_t\},\)
and
\[ \]
\(\displaystyle \gamma_t^+= \min\{(c_t-v)\cdot b-h_t: b\in\mathbb Z_{\geq0}^m,\ \sum_jb_j\leq B,\ c_t\cdot b\geq h_t\}.\)

An empty region has value \(+\infty\). These regions cover all bundles, so
\[ \]
\(\displaystyle \gamma_t(v)=\min\{\gamma_t^-,\gamma_t^+\}.\)

Each problem has \(m\) integer variables, a linear objective, rational linear constraints, and a bounded feasible region contained in \([0,B]^m\). Clearing denominators preserves polynomial encoding length.

Deterministic fixed-dimension integer optimization solves these problems in \(2^{O(m\log(m+1))}\) times a polynomial in their encoding length. One applicable result is [Hildebrand–Köppe, Theorem 1.1](https://arxiv.org/html/1006.4661): linear objectives and constraints are quasiconvex polynomials, and the bounded region here has a bound of polynomial encoding length.

If \(u_t>\gamma_t(v)\), an optimizing bundle supplies a violated dual inequality. Otherwise, all inequalities for that type hold. Processing the \(\tau\) types therefore gives an exact separation oracle.

Why the oracle gives exact optimization

The dual has dimension \(\tau+m\). Each defining inequality has coefficients consisting of a type indicator, an integer bundle with coordinates at most \(B\), and the rational value \(f_t(b)\). Their encoding lengths are uniformly polynomial in \(\tau,m,L,\log(B+1)\).

These bounds make the dual a well-described rational polyhedron. The strong separation–optimization theorem therefore applies, including to an unbounded or lower-dimensional feasible set; see [Grötschel–Lovász–Schrijver, *Rational Polyhedra*](https://link.springer.com/chapter/10.1007/978-3-642-78240-4_7).

The dual is feasible because \(u=v=0\) satisfies every inequality. Its optimum is finite: for every bundle,
\[ \]
\(\displaystyle 0\leq f_t(b)\leq c_t\cdot b\leq B,\)
so every feasible primal allocation has subsidy at most \(B\).

Exact dual optimization consequently computes \(S^*\), and comparison with the rational threshold \(K\) is exact. Combining the oracle and optimization bounds gives
\[ \]
\(\displaystyle 2^{O(m\log(m+1))} \operatorname{poly}(\tau,m,L,\log(B+1)).\)

This proves polynomial-time solvability for every fixed number of listed classes.

5. The universal \(1/3\) bound is false

Consider the following instance:
\[ \]
\(\displaystyle q=B=1,\qquad \lambda_1=1,\qquad \mu_1=\mu_2=\frac12,\)
\[ \]
\(\displaystyle a_1=\frac14,\qquad a_2=\frac74,\qquad c_{11}=1,\qquad c_{21}=\frac12.\)

The obligations normalize correctly:
\[ \]
\(\displaystyle \frac12\cdot\frac14+\frac12\cdot\frac74=1.\)

Each bundle contains either zero or one chore. The supply equality requires an average of one chore per worker. Therefore every worker must receive one chore: any positive mass receiving the empty bundle would make the average strictly smaller than one.

The baselines are \(a_1C_1=1/4\) and \(a_2C_2=7/8\). Hence the forced allocation has
\[ \]
\(\displaystyle S^*= \frac12\left(1-\frac14\right)^+ +\frac12\left(\frac12-\frac78\right)^+ =\frac38>\frac13.\)

The failure can grow linearly with the bundle bound. For any integer \(B\geq1\), keeping these types and setting \(\lambda_1=B\) forces every worker to receive \(B\) chores and gives \(S^*=3B/8\).

The cited discrete rounding theorem concerns its specified fractional sharing-tree setting. It does not provide a rounding guarantee preserving this model’s bundle cap, which prevents transferring additional chores to the type with the larger obligation. See [Wu–Zhou, Theorem 5.3](https://arxiv.org/html/2404.07707v1).

⟨structured verdict parsed — rendered above⟩

Assessment: proved with minor gaps. The substantive conclusions are correct: the general decision problem is \(\mathrm{NP}\)-complete, fixing either \(q\) or \(B\) yields polynomial time, and the universal subsidy bound is false. I found no false mathematical step. The only issues concern the precise statements and input conventions of the algorithmic theorems invoked in Section 4.

• Input interpretation and scope

The prover explicitly assumes binary-rational encoding of the listed costs. This is the natural bit-model interpretation of the task, which otherwise leaves their encoding unspecified. It is an acceptable clarification, not a restriction that evades the intended question.

The argument consistently uses \(\tau\) as the number of supported types and \(m=q\) as the number of listed classes. It introduces no finite item-count assumption.

• Configuration LP and feasibility

The LP exactly represents the allocation constraints and subsidy objective. The variable count \(\tau\binom{B+m}{m}\) and equality count \(\tau+m\) are correct.

The bounds \(0\leq\theta_{t,b}\leq\mu_t\) establish compactness of the nonempty feasible set, so the minimum is attained. This attainment is subsequently used correctly in the hardness reduction.

The asserted feasibility characterization is correct. Necessity uses both the bundle cap and total population mass one. The proposed distribution on \(Be_j\) and the empty bundle proves sufficiency when \(B>0\), with nonnegative probabilities summing to one. The separate treatment of \(B=0\) is correct.

• Polynomial certificates and membership in \(\mathrm{NP}\)

An optimal basic feasible solution can have at most \(\tau+m\) positive variables. Possible redundancy among the equality constraints only decreases this bound.

Selected bundles have polynomial encoding length because each coordinate is at most the binary-encoded \(B\). The stated Hadamard determinant bound is valid for the integer basis matrix.

Clearing the relevant right-hand-side denominators and applying Cramer’s rule gives polynomial-length masses. The input contains all those right-hand-side rationals, so their combined denominator encoding remains polynomial in the input length.

Subsidy coefficients for selected bundles can likewise be computed exactly with polynomial bit length. Consequently, a certificate specifying the selected type–bundle variables and their masses permits polynomial-time verification of every allocation equality and the objective threshold. Membership in \(\mathrm{NP}\) is established.

• Enumeration and the fixed-\(B\) cases

The bundle count is correct. The sequence encoding proves \(\binom{B+m}{m}\leq(m+1)^B\); the encoding need not be unique for this counting argument.

Explicit rational LP optimization therefore supports the general enumeration bound and the fixed-\(B\) polynomial bound. The factors required to write the constraint matrix and its rational coefficients are absorbed by the displayed polynomial bounds.

The case \(B=0\) is covered: there is only the empty bundle, and feasibility forces all supplies to vanish. Fixing both parameters gives the claimed \(\operatorname{poly}(\tau,L)\) bound.

• Partition reduction

The source restriction to even total weight is legitimate: doubling the integers preserves the Partition answer and produces even total weight.

Every constructed instance satisfies the task’s requirements:

• There is one positive-mass type, with both normalizations satisfied.
• Every cost is rational and belongs to \([0,1]\).
• Total supply equals the bundle cap, ensuring feasibility.
• The encoding length of \(D^r+W\), and therefore of every constructed rational, is polynomial in the source input length.

The zero-subsidy implication is correct. All positive-mass bundles must have cost at most \(C\), while their average cost is exactly \(C\). Hence each such bundle has cost exactly \(C\). Attainment of the optimum justifies applying this argument when \(S^*=0\).

The digit argument is also correct. The residual weight term is strictly below \(D\), and each coefficient of \(D^i\) is strictly below \(D\). Thus neither side of equation (1) has carries. Uniqueness of the base-\(D\) expansion forces exactly one class from each pair and a selected weight sum of \(W/2\).

Conversely, the partition and its complement produce two bundles of cost \(C\), each with \(r\) chores. Their equal mixture supplies every class exactly as required and has zero subsidy.

Both directions of the reduction are established, and the outputs satisfy the feasibility promise. Together with membership in \(\mathrm{NP}\), this proves the general \(\mathrm{NP}\)-completeness claim, including the stated restrictions \(\tau=1\) and \(K=0\).

• Fixed-\(m\) separation oracle

The dual has the correct objective, inequalities, and unrestricted variables. Finite LP duality applies because the primal is feasible and has an attained finite optimum.

The two integer minimizations correctly describe the two branches of the positive-part objective. Their overlap at \(c_t\cdot b=h_t\) is harmless because the objectives agree there. Treating an empty region as having value \(+\infty\) is correct.

Both problems have \(m\) integer variables, linear rational objectives and constraints, and bounded feasible regions. Denominator clearing preserves polynomial encoding length. An optimizing bundle provides an actual violated dual inequality whenever one exists.

Minor issue 1 — precise integer-optimization theorem conventions. The cited Hildebrand–Köppe theorem is stated for sparsely encoded integer-coefficient quasiconvex polynomials with strict inequalities. Its bounded-case statement also specifies a degree parameter and a condition on the encoding length of the region bound. Section 4 does not explicitly reconcile all these conventions with its weak rational inequalities. The source itself discusses equivalence of strict and weak inequalities on integer inputs, and the linear specialization supports the claimed running time. This is a routine exposition gap, not an unverified substantive application. [Hildebrand–Köppe, Theorem 1.1 and preceding discussion](https://arxiv.org/html/1006.4661).

Minimum clarification: state the applicable theorem precisely and explicitly identify the inequality convention, degree parameter, coefficient-length parameter, and region-bound parameter after preprocessing.

• Exact optimization and its running time

The dual inequalities have uniformly polynomial encoding length: each contains a type indicator, bounded integer bundle coordinates, and a polynomial-length rational subsidy coefficient. The exponentially many inequalities do not invalidate this bound.

The oracle returns exact separating inequalities, rather than approximate objective information. The dual objective also has rational input coefficients.

Feasibility of the dual follows from \(f_t(b)\geq0\). The objective is bounded above by the primal optimum, and the stated estimate \(f_t(b)\leq B\), together with total allocation mass one, verifies finiteness.

The strong separation–optimization theorem does apply to well-described rational polyhedra without boundedness or full-dimensionality assumptions. Thus those geometric concerns do not create a gap here. The theorem’s oracle-polynomial guarantees also control query encoding lengths, supporting the claimed combined running time. [Grötschel–Nešetřil, Section 11](https://arxiv.org/html/2303.03148).

Minor issue 2 — theorem statement and citation precision. The prover names the separation–optimization theorem but supplies only a chapter-level citation and does not explicitly state its oracle-polynomial guarantee in the dimension, inequality-encoding bound, and objective encoding length. Under the requested strict standard, that statement should appear in the write-up.

Minimum clarification: identify the exact theorem and state its input-size and oracle-call guarantees, explicitly matching them to the bounds already given. No additional mathematical argument is needed.

Subject to these expositional clarifications, the fixed-\(m\) bound
\(2^{O(m\log(m+1))}\operatorname{poly}(\tau,m,L,\log(B+1))\)
is supported.

• Counterexample to the universal bound

Every parameter in the proposed example satisfies the input restrictions, including positive obligations and their weighted normalization.

With \(B=1\) and supply one, all population mass must receive the one-chore bundle. The two baselines are correctly calculated as \(1/4\) and \(7/8\). The forced subsidy is therefore \(3/8\), which exceeds \(1/3\).

The extension with supply \(\lambda_1=B\) also checks out: the cap and supply equality force every worker to receive \(B\) chores, yielding \(3B/8\).

The cited discrete result does not assert preservation of this model’s bundle cap. Its stated rounding guarantee therefore does not contradict the counterexample. [Wu–Zhou, Theorem 5.3](https://arxiv.org/html/2404.07707v1).

The requested classification, running times, and universal-bound question are all resolved in substance. Neither identified issue blocks the conclusions.

⟨structured verdict parsed — rendered above⟩