| paper | d4-conf-ijcai-2011-0342 |
| 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 dyadic masses and threshold. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 8
statement extracted from the paper’s text layer
Given a candidate set \(A\), a support \(T\) of complete rankings over \(A\) with positive rational masses \(\mu_t\) summing to \(1\), an integer \(K\le |A|\), and a rational threshold \(q\ge 0\), does there exist a slate \(\Phi\subseteq A\) with \(|\Phi|=K\) such that \(\sum_{t\in T}\mu_t\max_{a\in\Phi}(|A|-\operatorname{pos}_t(a))\ge q\)?
Types are complete rankings over the discrete alternatives, each carrying mass \(\mu_t\). The decision variable is a \(K\)-alternative slate \(\Phi\); its objective is the population's average best Borda score, and the task is to meet a given threshold.
The mirror is anchored on Theorem 8; the same distributional objective also preserves Theorem 9's greedy \(1-1/e\) guarantee. It leaves the general cost-sensitive BSC model, SweetSpotGreedy, and the empirical results outside this mirror.
The strongest mirror is the paper’s Limited Choice problem. Imagine a large online market with a fixed catalog of \(m\) products and room to recommend \(K\) of them. A customer’s type is their complete ranking of the catalog; customers with the same ranking share one type. In a high-volume market, the number \(n\) of customers can greatly exceed the number \(\tau\) of observed ranking types. Each type’s mass is its fraction of the market. A type receives its most-preferred product on the slate, and the objective is to maximize the population’s total Borda score. This keeps the paper’s choice and utility model intact while making the population the continuous object.
The anchor is Theorem 8. It states that deciding whether there is a \(K\)-recommendation set \(\Phi\) whose Borda score \(S_\beta(\Phi,V)\) is at least \(t\) is NP-complete, for \(t\ge 0\). Lu and Boutilier assert this result in the paper; they say full proofs appear in their longer version [19]. They also distinguish it from the related proportional-representation hardness cited from [23], which does not by itself establish their theorem.
The corresponding continuous problem is:
\[ S_\mu(\Phi)=\sum_{t\in T}\mu_t\max_{a\in\Phi}\bigl(|A|-\operatorname{pos}_t(a)\bigr). \]
This is the continuous-population version of their Limited Choice/Borda problem, not a continuization of the product outcomes: the slate still consists of \(K\) discrete alternatives. To see the bridge, take any explicit finite profile \(V\) of \(n\) voters and let \(\mu_t\) be the fraction with ranking \(t\). Then \(S_\mu(\Phi)=S_\beta(\Phi,V)/n\), so the threshold becomes \(q=t/n\). Aggregating an explicit profile into its support and masses is polynomial, giving hardness transfer. Conversely, clearing denominators turns a rational society into a weighted finite profile, though expanding that into an explicit list of voters can be exponentially large when masses are given in binary.
I expect Class B: hardness transfers. The reduction’s combinatorics concern choosing a slate from the alternatives, not the number of individual voters. The exact score threshold can be checked in polynomial time from a slate and the rational masses, so the continuous decision problem is in NP as well. I would not claim Theorem 8 establishes hardness for a fixed number of alternatives or a small support; it does not say that.
The authors should recognize this mirror: their Limited Choice objective already sums each voter’s best score from the slate, and replacing that finite sum with a distributional average preserves the model’s segmentation and decision criterion. The weakest point is that this mirror does not show the continuum making the hard problem tractable; in this case it preserves the hardness. It is also a close high-multiplicity reformulation of their finite model. That limits the novelty of the result, but not the fit: the paper’s model is stated over a finite voter set, while the mirror asks the same computational question for a society specified directly by type proportions.
Natural follow-up questions include whether the continuous problem admits useful exact algorithms parameterized by \(K\) or \(\tau\), and which extensions of the paper’s model—such as nonuniform product costs—preserve the transferred hardness.
The strongest case against this mirror is about its marginal research value, not its fit. For a slate \(\Phi\), the paper’s finite Borda objective is already a sum of each voter’s best score. Replacing that sum with an expectation over ranking types gives
\[
F_\mu(\Phi)=\sum_{t\in T}\mu_t\max_{a\in\Phi}\bigl(m-\operatorname{pos}_t(a)\bigr).
\]
For a finite profile \(V\), setting \(\mu_t\) to each ranking’s frequency divided by \(n\) makes \(F_\mu(\Phi)=S_\beta(\Phi,V)/n\). The finite theorem and its approximation result therefore transfer with little new modeling work. One could argue that this is a thin lift of the paper’s existing analysis, rather than a mirror that reveals a new structural phenomenon.
But that argument does not defeat the anchor. Limited Choice has a named computational result, and a plausible high-volume recommendation market supplies a sensible regime: customers with the same complete ranking are indistinguishable for this objective, and the objective depends on their mass rather than their identities. The continuum remains nontrivial, and the fixed slate preserves the paper’s decision problem. Theorem 8’s hardness transfers to rational type masses; the fact that the answer is inherited is not a reason to reject the question under the programme’s criteria.
So I cannot honestly make the case that no worthwhile continuous mirror exists for this paper. The anti-case is weak precisely at its strongest anchor: it can question how much new work the mirror opens, but it cannot show that the mirror is ill-posed or out of scope.
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.