| paper | Tree Splitting Based Rounding Scheme for Weighted Proportional Allocations with Subsidy |
| authors | Xiao-Wei Wu, Shengwei Zhou |
| venue | WINE 2024 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→NP-hard discrete result → its continuous mirror
Answer: Under binary-rational cost encoding, the general problem is \(\mathrm{NP}\)-complete, already for \(\tau=1\) and \(K=0\). It is in \(\mathrm P\) when \(q\), \(B\), or both are fixed. The universal bound \(S^*\leq1/3\) is false, already for \(q=B=1\), where a feasible instance has \(S^*=3/8\). · discrete side: polynomial · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 5.3
statement extracted from the paper’s text layer
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.
Types carry \((a_t,c_{t1},\ldots,c_{tq})\) and mass \(\mu_t\); variables \(\theta_{t,b}\) distribute type mass among integral bundles \(b\), conserving type mass and chore supply. Each unit of mass pays \(\sigma_{t,b}=(\sum_jb_jc_{tj}-a_t\sum_j\lambda_jc_{tj})^+\), and the objective is \(S(\theta)=\sum_{t,b}\theta_{t,b}\sigma_{t,b}\).
The atom-path and expanded-atom-path certificate depends on named-agent/item order and is not determined by \((\mu,a,c,\lambda)\), so replacing it by \(\theta\) does not literally preserve the theorem's structural object.
fatal: False
It covers the weighted additive chore-allocation problem with WPROPS and the normalized subsidy-bound question represented by Theorem 5.3; it leaves the finite successor-tree proof, exact named-item instances, the stronger all-instance bound \(n/3-1/6\), and the goods appendix unmirrored.
The supplied paper contains no named hardness theorem, so the strongest positive anchor is its algorithmic result.
My lead anchor is Theorem 5.3, proved in this paper. In the paper’s weighted additive chore-allocation setting, it states:
Given the fractional allocation \(\bx\) returned by FBTA with fewer than \(n-1\) fractional items, there is a rounding scheme producing an integral WPROPS allocation with total subsidy at most \((n-1)/3\).
Here “fractional item” means an item shared by at least two agents. The theorem is proved using atom-path splitting, expanded atom-paths, and induction over the item-sharing tree. It covers the difficult “shattered item” branch of the paper’s main argument.
The continuous mirror I would put to the authors is High-Multiplicity Weighted Proportional Chore Allocation with Subsidy, \(\mathsf{HM\text{-}WPROPS}_\infty\).
There are finitely many worker types \(T\), with type mass \(\mu_t\), \(\sum_t\mu_t=1\). A type \(t\) completely specifies the worker’s relative obligation \(a_t>0\) and her additive cost \(c_{tj}\in[0,1]\) for each of \(q\) recurring chore classes \(j\). Normalize \(\sum_t\mu_ta_t=1\). Chore class \(j\) has per-capita supply \(\lambda_j\). This represents, for example, a large production network with many interchangeable workers in each job category and a recurring task mix per shift.
The finite approximation with population \(n\) has \(n\mu_t\) workers of type \(t\), \(n\lambda_j\) copies of chore \(j\), and gives every type-\(t\) worker weight \(a_t/n\). Her total cost for all chores is \(nC_t\), where \(C_t=\sum_j\lambda_jc_{tj}\), so her proportional share is exactly \(a_tC_t\), independent of \(n\). Thus this is not an analogy: it is the high-multiplicity form of the paper’s own WPROP definition.
A solution is a distribution over integral bundles. Let \(b=(b_1,\ldots,b_q)\in\mathbb Z_{\ge0}^q\) be a bundle containing \(b_j\) copies of chore \(j\), and let \(\theta_{t,b}\) be the mass of type-\(t\) workers receiving \(b\). The constraints are \(\sum_b\theta_{t,b}=\mu_t\) for every \(t\), and \(\sum_{t,b}\theta_{t,b}b_j=\lambda_j\) for every chore class \(j\). Each worker receiving \(b\) gets the subsidy \(\sigma_{t,b}=\bigl(\sum_jb_jc_{tj}-a_tC_t\bigr)^+\). The objective is to minimize the subsidy density
\[ S(\theta)=\sum_{t,b}\theta_{t,b}\sigma_{t,b}. \]
The continuous question is: given rational \(\mu\), \(a\), \(c\), \(\lambda\), and a threshold \(\beta\), compute the minimum \(S^*\), or decide whether \(S^*\le\beta\); in particular, does every such high-multiplicity instance admit a solution with \(S\le1/3\)?
This preserves indivisibility. No worker receives a fractional bundle: every unit of mass receives an integral bundle \(b\). Only the distribution of integral bundles is continuous. In a finite rational approximation, \(\theta\) can be implemented by assigning whole chore copies to whole workers, and \(S\) is exactly total subsidy divided by \(n\).
The connection to Theorem 5.3 is direct. Its finite guarantee becomes \((n-1)/(3n)\) after normalization by population, converging to \(1/3\). The theorem therefore supplies a concrete prediction for this mirror: the discrete tree-rounding bound should survive as a per-capita subsidy bound in the continuum. The paper’s result does not prove that limit statement, because its tree is built over named agents and its rounding is finite, but it is exactly the kind of finite-to-high-multiplicity bridge the programme is designed to investigate.
I expect this mirror to be Class A in the natural regime of finitely many chore classes and bounded per-worker workload. The variables \(\theta_{t,b}\) form a configuration LP. For fixed \(q\) and workload bound \(B\), there are finitely many configurations \(b\), so the problem is directly solvable in polynomial time by linear programming. If \(q\) or \(B\) is part of the input, column generation becomes relevant; its pricing problem resembles a knapsack problem. That creates a worthwhile computational boundary rather than making the mirror vacuous: fixed task taxonomy should be tractable, while variable task taxonomy may require parameterized algorithms or could become continuum-specifically hard.
The authors should recognize this as their problem. The agents remain weighted workers, the costs remain additive, the chores remain indivisible, WPROPS is unchanged, and the objective is still minimum total subsidy. The only change is that many workers are genuinely interchangeable and the task supply is expressed per capita. A type includes the entire cost profile and obligation parameter, so no idiosyncratic information has been discarded improperly.
The weakest point is that the paper’s tree structure does not survive literally in the limit. A critic can argue that the configuration LP replaces the paper’s delicate atom-path rounding by a more permissive distribution over bundles, and that the bounded-workload assumption narrows the original problem. That criticism is real. The response is that the proposed question does not impose fractional bundles or average-only fairness: it retains integral bundles and individual WPROPS for every unit of mass. Even if the \(1/3\) bound ultimately fails, this remains a legitimate high-multiplicity version of the paper’s underlying allocation problem, with a precise optimization objective and a genuine separation/pricing question.
Theorem 5.3 is a genuine algorithmic anchor, so the “no named computational result” objection is unavailable. The strongest negative case is that the theorem’s real object is not the population distribution but a particular finite rounding certificate.
Its atom-paths and expanded atom-paths arise from the order in which named agents consume named items under FBTA. In the proposed high-multiplicity model, the data \((\mu_t,\lambda_j)\) specify only masses and final bundle frequencies. They do not specify the item-to-worker incidence history or a canonical successor relation. After quotienting by type symmetry, the tree is therefore not an invariant of the instance. The same configuration distribution can arise from many incompatible finite trees.
One can try to repair this by asking for a continuum analogue of rounding a prescribed FBTA allocation. But then the model must retain a measure of allocation histories, copy identities, or successor incidences. That is no longer a society described by type masses alone; it is an additional measure-valued object introduced solely to preserve the proof’s bookkeeping. If instead one discards that history, the problem becomes the configuration LP over \(\theta_{t,b}\), which is a new high-multiplicity allocation problem rather than a continuous version of the paper’s tree-splitting theorem.
Moreover, under the proponent’s bounded-workload regime, the finite bound already passes to the limit mechanically. Apply the paper’s finite algorithm to rational \(n\)-fold copies, divide the subsidy by \(n\), and obtain a bound tending to \(1/3\). Thus the tree theorem supplies an asymptotic guarantee without yielding a new continuous structural theorem. The proposed LP may still ask for the optimum \(S^*\), but that question is no longer anchored specifically in Theorem 5.3; it has replaced the paper’s rounding problem by a general configuration-allocation problem whose pricing resembles knapsack.
This is not an invalid model. Workers with repeated cost profiles are a sensible high-multiplicity regime, subsidies remain individual, and integral bundles are preserved. Nor is existing high-multiplicity work an objection. The honest conclusion is therefore that the negative case is weak: it can show that the paper’s delicate tree structure does not survive as a canonical type-level object, but it cannot establish that the resulting configuration problem is not worthwhile. I would not vote against a continuous mirror on this anchor alone.
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.