| paper | d4-conf-ecai-2016-0278 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-complete}\), even with \(\tau=1\), \(q=1\), \(W=1\), and positive dyadic rational utilities equal to weights. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 1
statement extracted from the paper’s text layer
Given items \(P\), positive weights \(w_j\), capacity \(W\), a finite support \(T\) of types with rational masses \(\mu_t \ge 0\) summing to \(1\), and each type’s rational additive utilities \(u_j^t\) and approval threshold \(\delta_t\), does there exist \(X \subseteq P\) with \(\sum_{j \in X} w_j \le W\) such that \(\sum_{t \in T} \mu_t \mathbf{1}\{\sum_{j \in X} u_j^t \ge \delta_t\} \ge q\), for a given rational target share \(q\)?
The society is a distribution \(\mu\) over complete utility-and-threshold types; each feasible decision remains an integral item set \(X \subseteq P\). The objective is the mass of types whose approval threshold is met, and the decision question asks whether some feasible \(X\) reaches target share \(q\).
Covers Proposition 1’s full-information approval winner determination problem; leaves the possible-winner search procedures and the incremental elicitation, query, and regret results unaddressed.
The strongest mirror is a high-multiplicity version of the paper’s full-information approval knapsack problem.
My anchor is Proposition 1, proved in the paper: AMKP is NP-complete. Its input is a finite item set \(P\), positive integer capacity \(W\), item weights \(w_j\), a finite agent set \(N\), an integer \(K\), and each agent’s additive utilities \(u_j^i\) and approval threshold \(\delta_i\). It asks whether some subset \(X\subseteq P\) has total weight at most \(W\) and is approved by at least \(K\) agents—that is, whether \(\sum_{j\in X}u_j^i\ge\delta_i\) for at least \(K\) agents. The authors prove this by reducing from knapsack using one agent.
Call the continuous mirror Continuous Approval Knapsack. An instance has the same items, weights, and capacity, plus a finite set \(T\) of types. Each type \(t\) has an additive utility vector \(u^t\), an approval threshold \(\delta_t\), and rational mass \(\mu_t\ge 0\), with \(\sum_{t\in T}\mu_t=1\). Utilities, thresholds, and masses are binary-encoded rationals. For a feasible subset \(X\), its approval share is
\[
A_\mu(X)=\sum_{t\in T}\mu_t\mathbf{1}\left\{\sum_{j\in X}u_j^t\ge\delta_t\right\}.
\]
The optimization problem is to find a feasible \(X\) maximizing \(A_\mu(X)\). Equivalently, given a target share \(q\), the decision problem asks whether some feasible \(X\) has \(A_\mu(X)\ge q\). A type is the complete utility-and-threshold profile relevant to approval; its mass is the fraction of the population with that profile. The selected bundle remains integral. It is the population, whose support has size \(\tau=|T|\), that is continuous.
A plausible regime is a large cooperative or municipality choosing a portfolio of projects under a shared budget. Suppose members are assessed through a finite library of project-value profiles and approval cutoffs. Millions of members might then fall into a few dozen or hundred exact profiles, so \(n\) is very large while \(\tau\ll n\). Asking what fraction approves a portfolio is natural in that setting, and this model preserves the paper’s additive utilities, personal thresholds, common feasible knapsacks, and approval rule. It also avoids comparing utility scales across people: as in the paper, each person’s utility is used only to determine whether that person approves.
The hardness transfers directly. Given a discrete AMKP instance with \(n\) agents, assign each agent mass \(1/n\), merge agents with identical profiles, and set \(q=K/n\). The continuous instance answers yes exactly when the original does. In fact, the paper’s one-agent reduction already gives hardness with \(\tau=1\), mass \(1\), and \(q=1\). Under the rational encoding above, the decision version is therefore NP-complete: a subset is a polynomial-size certificate, and its approval share can be computed from the finite support. This is Class B hardness. Its source is the combinatorics of choosing items, not the number of agents, so continuizing the population does not remove this hard core.
The mirror covers Proposition 1’s winner-determination problem, not the paper’s incremental elicitation procedures or their uncertainty-set search. It gives the authors’ problem the high-multiplicity interpretation they already invite: the count of approving agents becomes the share of the society approving, while the underlying decision remains the same.
The follow-up questions are whether parameterizing by \(\tau\) yields useful exact algorithms, and whether one can approximate the maximum approval share with guarantees depending on \(p,\tau\), and the input bit length.
My weakest point is the exact-profile regime. If members’ utility vectors and cutoffs are highly idiosyncratic, then \(\tau\) may approach \(n\), and the high-multiplicity representation offers little compression. The case rests on settings with standardized or recurring profiles. I think those are plausible for large, repeated project-selection processes, but they are a condition of this mirror, not a universal property of approval voting.
The strongest skeptical case is that this mirror may offer little of the continuous-optimization machinery ChoCo hopes to bring into view. The knapsack decision stays integral, \(X\in\{0,1\}^p\); continuity enters through the weighted approval score \(A_\mu(X)\). Proposition 1’s hardness reduction already uses one agent, so at \(\tau=1\) the population axis adds no variation to the decision problem. With more types, the objective becomes a rationally weighted sum of threshold tests. That suggests a thin mirror whose computational difficulty still sits in choosing the items. But that is a concern about likely research yield, not a valid objection under the programme’s rules: an unhelpful complexity answer would still be an answer. Proposition 1 is a named computational result and therefore gives the mirror a legitimate anchor. [The paper’s AMKP definition and Proposition 1](https://comsoc-community.org/assets/proceedings/comsoc-2016/BenabbouPernyCOMSOC2016.pdf)
The best attack on the proposed population regime is that exact utility-and-threshold profiles may be rare: the paper says agents’ utility functions are generally constructed independently. If so, \(\tau\) could be close to the number of people. But this does not defeat the mirror. A large group using a finite library of project-value profiles and approval cutoffs is coherent, and grouping identical complete profiles is exactly the high-multiplicity interpretation. The paper’s warning about incomparable utility scales does not rule it out, since each person’s utility is used only with that person’s threshold. The authors’ particular examples need not supply the scenario; the municipality portfolio setting does.
Nor does converting counts to masses make the mirror a collision. The relation \(\mu_t=n_t/n\) is the high-multiplicity bridge the programme explicitly wants to study. It may make this anchor less novel than others, but it does not make the question ill-posed or already continuously solved. The incremental elicitation results also admit a natural type-level question: how many approval queries are needed when each query to a type represents a positive mass of identical agents?
So I cannot honestly defeat this anchor. The negative case can question its likely payoff, but the proposed mirror survives the stronger tests: a plausible repeated-profile regime, a computational theorem to mirror, and a population that is genuinely represented by masses.
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.