| paper | d4-conf-wine-2023-0024 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→NP-hard discrete result → its continuous mirror
Answer: Deciding \(S^*(q,c)\le K\) is \(\mathrm{NP}\)-complete, already for \(\tau=1\) and \(K=0\). Polynomial-time exact optimal-assignment computation would imply \(\mathrm P=\mathrm{NP}\). The sharp worst-case value is \(1/4\), and it is attained. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 3.3
statement extracted from the paper’s text layer
Given rational per-capita chore supplies \(q_e\ge0\) and costs \(c_e\in[0,1]\), let \(b=\sum_e q_ec_e\). Choose a finite-support distribution \(y_z\ge0\) over integral bundles \(z\in\mathbb Z_{\ge0}^m\), with \(\sum_z y_z=1\) and \(\sum_z y_zz_e=q_e\) for every chore type \(e\), minimizing \(\sum_z y_z[c\cdot z-b]_+\). Determine the worst-case optimum and whether an optimal mass assignment can be computed in time polynomial in \(m\) and the binary input length \(L\).
A one-type population with rational mass \(1\), per-capita chore supply \(q_e\), and common costs \(c_e\in[0,1]\). Each mass cohort receives an integral bundle \(z\in\mathbb Z_{\ge0}^m\); the distribution over bundles must have expected supply \(q_e\), and its objective is average subsidy \(\sum_z y_z[c\cdot z-b]_+\), where \(b=\sum_e q_ec_e\).
The finite algorithm may require work polynomial in the expanded population size, which can be exponential in the binary encoding of \(q\); the proponent acknowledges that compressed-input runtime is unresolved.
fatal: False
The mirror covers the identical-cost proportionality-with-subsidies guarantee of Theorem 3.3 and proposes an extension to finitely many cost types using Theorem 4.6's rounding idea. It leaves the weighted bounds, envy-freeness results, and the paper's goods and PROP1 results outside the stated one-type question.
The paper has no named hardness result. Its best anchors are constructive guarantees, so the positive case is that a population mirror asks how those guarantees behave when identical agents are represented by their mass.
A plausible regime is a large workforce receiving recurring chores: many workers, but relatively few distinct cost profiles, and many copies of each standardized task. A type is a complete vector of costs \(c_t(e)\), with each chore copy costing at most one. Let \(\mu_t\) be the fraction of the workforce with type \(t\), and \(q_e\) the number of copies of chore \(e\) per worker on average. Both are binary rationals. This makes the type’s proportional benchmark \(b_t=\sum_e q_e c_t(e)\), the per capita version of its total chore cost divided by the number of agents.
Here is the lead mirror, Continuous Homogeneous PROPS. Set \(\tau=1\), so everyone has the same cost vector \(c\). Find a finite-support mass assignment \(y_z\), where \(z\in\mathbb Z_{\ge 0}^m\) is an integral bundle of chores and \(y_z\) is the fraction of workers receiving it, satisfying
\[
\sum_z y_z=1,\qquad \sum_z y_z z_e=q_e\quad\text{for each }e.
\]
Minimize
\[
\sum_z y_z\,[c(z)-b]_+,\qquad
c(z)=\sum_e c(e)z_e,\quad b=\sum_e q_e c(e).
\]
A solution is the mass assigned to each integral bundle; workers’ subsidies are \([c(z)-b]_+\). Thus the bundle each person receives remains integral. The continuous object is the population split among bundles.
The strongest anchor is Theorem 3.3, proved in this paper: for identical cost functions, a PROPS allocation exists with total subsidy at most \(n/4\) when \(n\) is even, and at most \((n^2-1)/(4n)\) when \(n\) is odd. The continuous question is whether every rational one-type instance has a mass assignment with average subsidy at most \(1/4\), and what its worst-case optimum is. The quarter is tight in the mirror: take one chore category with unit cost and supply \(q=1/2\). Half the population must receive a copy and needs subsidy \(1/2\); the rest receive none, for average subsidy \(1/4\). I expect this homogeneous problem to be Class A: the paper’s load-balancing structure looks amenable to batching identical agents. Theorem 3.3 is proved here, and its finite odd-\(n\) bound converges to the same continuous threshold.
The broader mirror, Continuous-Type PROPS, uses the same optimization problem with \(\tau\) cost types and constraints
\[
\sum_z y_{t,z}=\mu_t,\qquad
\sum_{t,z}y_{t,z}z_e=q_e,\qquad
b_t=\sum_e q_e c_t(e).
\]
Its objective is \(\sum_{t,z}y_{t,z}[c_t(z)-b_t]_+\). The output is a finite-support bundle assignment and the corresponding subsidy for each type-and-bundle cohort. This is the underlying allocation problem, rather than a fractional allocation of chores to individuals.
Its anchor is Theorem 4.6, also proved here: given the fractional allocation \(X^0\) with \(n-1\) fractional items returned by Algorithm 2, there is a rounding scheme producing an integral PROPS allocation with total subsidy at most \(n/4\). This is a constructive component of the paper’s general-cost result; its stated premise is that particular fractional allocation, so it is not by itself a theorem about every continuous-type instance. For the mirror question, I would expect Class A, provisionally: type masses and chore supplies give a natural mass-assignment optimization problem, and the paper’s moving-knife-plus-rounding method may be batchable by type. A configuration LP is a plausible route, but its bundle-pricing problem needs analysis; knapsack-like pricing could instead expose continuum-specific hardness. Theorem 4.6 is proved here, not cited from prior work.
For rational \(\mu_t\) and \(q_e\), scaling by a common denominator gives a finite instance with repeated agents and chore copies; aggregating its solution back gives a mass assignment. That supports the mirror’s feasibility and subsidy guarantee. It does not establish runtime polynomial in \(m,\tau,L\): the denominator can be exponential in its binary encoding. This is the weakest point in the case, and the central further question for the general mirror is whether its type-compressed version admits a polynomial-time algorithm in those parameters. Other questions include the exact optimum rather than the \(1/4\) guarantee, and whether the paper’s PROP1 property also survives in the mass model.
The mirror covers proportional allocation of chores with subsidies, first for identical costs and then as a proposed generalization to finitely many cost types. Its appeal is that a large recurring workforce with a small number of complete cost profiles is a plausible high-multiplicity regime, while every worker still receives an indivisible bundle. The main risk is computational compression: the discrete guarantee scales to rational populations, but an efficient algorithm in the compressed input size remains to be shown.
The strongest objection is that the mirror becomes interesting only after changing the resource regime. Keep the paper’s finite set of chores and let the population grow, and the per-person supply \(q_e\) tends to zero; the average subsidy can then collapse. Keeping \(q_e\) positive instead means scaling the chore supply with the population. That gives a coherent model for recurring standardized tasks, but it is a model of repeated operations, not the paper’s one-time allocation of a finite estate.
That distinction weakens the case against Theorem 3.3, but does not defeat it. In the recurring-task setting, workers with one common cost vector are a plausible population type, and each worker can still receive an integral bundle. The continuous question is well formed. Its computational challenge is whether the mass over integral bundles can be optimized in time polynomial in the encoded supplies and costs. The paper’s algorithm runs on explicitly listed agents and chores; when rational supplies are expanded into copies, that input can be exponentially larger than its binary encoding. So the theorem gives no compressed algorithm. But that leaves a real high-multiplicity question; it is not a reason to dismiss the mirror.
Theorem 4.6 is a weaker anchor: it is a rounding guarantee conditional on the particular fractional allocation produced by Algorithm 2. Its proof uses a finite chain of agents and at most \(n-1\) fractional items. That analysis does not itself provide a type-compressed algorithm. The better mirror is the paper’s full general-cost result, represented by the proposer’s type-level configuration model. There the main unresolved issue is still substantial: finding or pricing integral bundles under type-specific costs. A continuum formulation may not simplify that computation. Yet hardness there would be a meaningful boundary result under the programme’s own criteria, so this objection also falls short.
I cannot make a convincing universal case that no scenario yields a worthwhile mirror. The proposed recurring workforce is plausible, the population is genuinely the continuous object, and bundles remain integral. The honest negative case is that Theorem 3.3 has a much less direct connection to the paper’s finite-inventory setting than the phrase “continuous mirror” suggests, while Theorem 4.6 alone does not establish tractability for the compressed model. But neither point defeats the strongest homogeneous mirror; claiming otherwise would manufacture an objection.
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.