| paper | d4-conf-aaai-2017-0836 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable, in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 14
statement extracted from the paper’s text layer
Given supported complete agent types \(t\) with binary-rational masses \(\mu_t\), each carrying a fixed inventory of item types \(a\) with sizes \(s_{ta}\) and values \(v_{ta}\), and partitioned into two owner classes \(G_1,G_2\), choose selected masses \(x_{ta}\in[0,\mu_t]\). With \(\mu(G_i)=\sum_{t\in G_i}\mu_t>0\), maximize \(\sum_{t,a}v_{ta}x_{ta}\), subject to \(\sum_{t,a}s_{ta}x_{ta}\le b\) and \(\frac{\sum_{t\in G_1,a}v_{ta}x_{ta}}{\mu(G_1)}=\frac{\sum_{t\in G_2,a}v_{ta}x_{ta}}{\mu(G_2)}\), where \(b\) is per-capita capacity and \(x_{ta}\) is the mass of type-\(t\) agents receiving item \(a\).
A distribution \(\mu\) over complete owner types, each with a repeated inventory; \(x_{ta}\) records the mass receiving item \(a\). Maximize welfare under aggregate per-capita capacity and equality of the two owner classes’ average utilities. Each agent’s item decisions remain integral; only type-level averages are fractional.
Theorem 14 puts the arbitrary knapsack instance inside one owner’s inventory, whereas the repaired mirror scales owner types and allows selected item mass to be fractional; this limits what the mirror says about the original hardness, but does not invalidate the continuous question.
fatal: False
The mirror covers the equal-utility optimization problem in Theorem 14. It leaves the paper’s mechanism guarantees, strategic-equilibrium results, and other bounds and specialized models aside.
The strongest mirror is the optimization problem in Appendix Theorem 14, proved in this paper. The theorem says that solving PROGRAM is NP-hard. PROGRAM takes two agents’ item sets and asks for a feasible lottery over knapsack subsets that maximizes expected total value, subject to the two agents receiving equal expected utility. The paper proves hardness here by reducing ordinary knapsack: its constructed PROGRAM has optimum \(2k\) exactly when the original knapsack instance has a solution worth at least \(k\). This is a result about the optimization the mechanism must perform, not merely about an encoding.
I would call the mirror Continuous Equal-Utility Knapsack. Consider two hospital departments with many scan requests. A type is a request class, fully specified by its department, scan duration \(s_{i,t}\), and health value \(v_{i,t}\). The instance lists the \(\tau\) supported types and their rational masses \(\mu_{i,t}\), with total mass normalized to \(1\). Each request remains indivisible, but the population of requests within a type is nonatomic; capacity \(b\) is scaled per unit of population. Choose allocated masses \(x_{i,t}\) satisfying
\[
0\le x_{i,t}\le \mu_{i,t},\qquad
\sum_{i,t}s_{i,t}x_{i,t}\le b,\qquad
\sum_t v_{1,t}x_{1,t}=\sum_t v_{2,t}x_{2,t}.
\]
The objective is to maximize \(\sum_{i,t}v_{i,t}x_{i,t}\). A solution is the vector of allocated masses. This is a linear program with \(O(\tau)\) variables and constraints, so it is solvable in time polynomial in \(\tau\) and the input bit length.
The regime is a large imaging service with many cases but relatively few recurring combinations of department, scan duration, and value. Departments remain the strategic owners, as in the paper; the masses represent their populations of requests. The authors should recognize this as a direct continuous version of PROGRAM: the knapsack capacity, ownership, welfare objective, and equal-utility constraint all remain. What changes is that a continuum of requests lets the mechanism select a fraction of a type’s mass. I expect the discrete NP-hardness in Theorem 14 to dissolve here: the hard subset choice has become a tractable mass-allocation LP. This covers the PROGRAM computation used by EQUAL-UTILITY, not the paper’s full analysis of strategyproofness or its other models. Further questions include whether the LP yields additive approximations for finite high-multiplicity instances, and whether a mechanism using that approximation can retain the paper’s truthfulness guarantee.
The weak point is that this continuizes the population of requests in departments’ inventories, while the paper’s strategic agents are departments themselves. A strict reading of ChoCo’s population gate might not accept that as continuizing the strategic-agent population. The case rests on the paper’s own application, where departments manage large populations of patient requests, and on Theorem 14 being specifically about the allocation of those requests. If the mirror must scale the number of independently strategic departments, this is not that mirror.
The proposed mirror does not continuize the strategic population. Its variables allocate mass of request classes, while the two departments remain the strategic agents whose expected utilities are equated. That makes it a continuous inventory or allocation problem, not a continuous society of complete agent types. Calling each request a patient does not fix this: patients do not own and report the department’s full item set as the agents in the paper do.
The strongest repair is to take many copies of each complete agent type, scale capacity with the population, and equalize the types’ average utilities. That is a coherent high-multiplicity version. But it changes what Theorem 14 encodes: its arbitrary knapsack instance sits inside one agent’s inventory, and repeating that inventory across a nonatomic population lets the aggregate choose fractions of each item class. The resulting LP may be useful, but the reduction’s hardness has been relaxed through repeated inventories, not through a large population of the original two strategic owners.
That objection is not decisive under ChoCo’s rules. A large population of repeated agent types is an admissible regime, and the resulting change from integral bundles to fractional type averages is explicitly allowed. Theorem 14 is a named computational result, and a tractable continuous counterpart would be a meaningful finding even if its answer is straightforward. So the request-class formulation is a scope mismatch, but I cannot honestly rule out the repaired high-multiplicity mirror. The negative case is weak at this anchor; claiming no worthwhile mirror in any scenario would overreach.
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.