| paper | d4-conf-ecai-2023-0086 |
| 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}\)-complete when \(k\) is part of the input; polynomial-time solvable for every fixed \(k\). · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given a finite item set \(C\), a support \(T\) of strict rankings with positive rational masses \(\mu_t\) summing to \(1\), and an integer \(k\), is there a subset \(S\subseteq C\) with \(|S|\le k\) such that for every \(t\in T\), \(\sum_{c\in S}(m-\operatorname{pos}_t(c))\ge\sum_{c\in C\setminus S}(m-\operatorname{pos}_t(c))\)?
Borda-SAS over a high-multiplicity society: types are strict rankings of the items, \(\mu_t\) is each type’s population fraction, and the decision variable is an indivisible subset \(S\subseteq C\) of size at most \(k\). Every positive-mass type must weakly prefer \(S\) to its complement under Borda utilities.
The mirrors cover Theorem 4’s Borda-SAS NP-completeness and polynomial-kernel lower bound in \(m\), and Theorem 2’s approval hardness and linear-time boundary cases. They leave the paper’s other utility models and parameterized results unmirrored.
The best mirror here is an exact high-multiplicity version of SAS. Picture a large organization choosing a small bundle of items for a shared destination—equipment for an event, say—where every participant must weakly prefer the chosen bundle to what remains. Participants with identical complete preferences form a type; \(\mu_t\) is that type’s fraction of the population. In a large organization, \(N\) can be very large while the number \(\tau\) of distinct preference types stays moderate. That is a plausible regime for approval profiles and for recurring preference cohorts with shared rankings. The chosen items remain indivisible: it is the population, not the outcome, that is continuous.
The lead is Borda-SAS\(_\infty\), mirroring Theorem 4, which the paper proves here. Theorem 4 says that BORDA-SAS is NP-complete and, unless \(\mathrm{NP}\subseteq\mathrm{coNP/poly}\), has no polynomial-size problem kernel in the number \(m\) of items.
An instance of Borda-SAS\(_\infty\) consists of a finite item set \(C\), a support \(T\) of \(\tau\) strict rankings of \(C\), positive rational masses \(\mu_t\) summing to \(1\), and an integer \(k\). If \(\mathrm{pos}_t(c)\in\{1,\ldots,m\}\) is the position of item \(c\) in type \(t\)’s ranking, set \(b_t(c)=m-\mathrm{pos}_t(c)\). The question is whether there is a subset \(S\subseteq C\), \(|S|\le k\), such that for every \(t\in T\),
\[
\sum_{c\in S} b_t(c)\ \ge\ \sum_{c\in C\setminus S} b_t(c).
\]
A solution is the subset \(S\); the associated optimization problem minimizes \(|S|\).
This is a direct population mirror of the paper’s problem: every type represents agents with exactly the same ranking, and every positive-mass type must be satisfied. Any discrete instance gives such a society by assigning each ranking its fraction of the agents; conversely, one representative agent per support type preserves the answer. Thus the expected classification is Class B: the NP-completeness transfers, and the kernel lower bound in \(m\) transfers under this support representation. The reduction’s combinatorics sit in the items and preference constraints, not in having many individually named agents.
A second anchor is Approval-SAS\(_\infty\), mirroring Theorem 2, also proved in this paper, with some technical details deferred to the full version. Theorem 2 says that APPROVAL-SAS is NP-hard when every agent approves exactly \(d\) items for \(d\in\{2,\ldots,m-2\}\); it is linear-time solvable when every agent approves one item or when every agent approves all but one item.
Here the instance is \(C\), a support \(T\) of approval sets \(B_t\subseteq C\), positive rational masses \(\mu_t\) summing to \(1\), and \(k\). The question is whether there is \(S\subseteq C\), \(|S|\le k\), satisfying
\[
|S\cap B_t|\ \ge\ |B_t\setminus S|
\qquad\text{for every }t\in T.
\]
Again, the solution is \(S\), and the optimization version minimizes its size. The theorem’s hardness regimes transfer to this mirror, while its two easy boundary cases remain linear-time solvable. The paper’s cited high-multiplicity fair-allocation work [13] is useful context for the plausibility of repeated-agent regimes in resource allocation; it is supporting precedent, not a collision with this question.
The scope is deliberately narrow: these mirrors cover the Borda and approval SAS results, including Theorem 4’s kernel lower bound and Theorem 2’s hardness and boundary cases. A useful further question is whether Borda-SAS\(_\infty\) is FPT in \(\tau\). The paper leaves FPT parameterized by the number of agents open for Borda; after identical preferences are grouped, that parameter is precisely the support size.
The weak point is that \(\mu_t\) does not affect feasibility or the optimum: a tiny positive-mass type constrains \(S\) just as much as a type holding most of the population. For these anchors, the continuous model is therefore exactly support-sensitive SAS, not a new LP or a route to tractability through population averaging. I still think it is a legitimate mirror: the type distribution is the natural representation of a high-multiplicity society, and the paper’s universal-agreement condition itself makes support the relevant information. That leaves a clear, if modest, continuous question—and a clean example where the expected answer is that continuization does not dissolve the hardness.
The paper does have computational results to mirror, and there are plausible repeated-type settings for SAS: a large group choosing a shared bundle could contain many people with the same approval set. I can’t make a convincing case that such a population is inherently implausible.
The strongest objection is that neither proposed mirror uses the population masses. For Borda, define
\[
g_t(S)=\sum_{c\in S} b_t(c)-\sum_{c\notin S} b_t(c).
\]
The continuous feasibility condition is \(g_t(S)\ge 0\) for every \(t\) with \(\mu_t>0\). Approval-SAS has the same form, with \(g_t(S)=|S\cap B_t|-|B_t\setminus S|\). Thus any two distributions with the same support give exactly the same feasible sets and optimum, whatever their masses. A type with arbitrarily small positive mass constrains the solution just as much as the majority type; when its mass reaches zero, its constraint disappears. That discontinuity makes the distribution a poor account of population proportions for this unanimous property.
This applies to both anchors. Theorem 4’s Borda constraints reduce to one representative ranking per type, and the paper’s Reduction Rule 1 already deletes agents with duplicate preferences. After that reduction, the number of agents is the support size \(\tau\); the proposed FPT question in \(\tau\) is the paper’s open FPT question in the number of agents, expressed in distribution notation. Theorem 2’s approval hardness and easy boundary cases likewise depend on which approval sets occur, not how much mass they carry. The resulting problems may be worth studying, but their continuous formulation adds no population-weighted computational question.
A stronger mirror would make the mass count: for example, minimize \(|S|\) subject to at least a \(q\)-fraction of the population preferring \(S\) to its complement. That is a genuine distribution-sensitive problem. The paper itself points toward maximizing the number of agents who agree, so this extension is plausible and potentially worth investigating. It changes the unanimous SAS condition, though, and does not preserve either named theorem’s problem.
So the negative case is strongest against these two exact anchors: their “continuization” retains only the support. I can’t honestly extend that case to the claim that no worthwhile mirror exists in any scenario. The mass-based partial-agreement variant is a credible counterexample to that universal claim, even though it is a new problem rather than a continuous version of Theorem 2 or Theorem 4.
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.