| paper | d4-conf-ecai-2024-0308 |
| 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→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\) for every fixed \(k\ge2\) and every fixed nonempty refinement \(\gamma\subseteq TC\), already with \(\tau=1\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Fix \(k\ge2\) and a tournament solution \(\gamma\subseteq TC\). Given a finite item set \(E\), a support of \(\tau\) types with positive binary-rational masses \(\mu_t\) summing to one, and common-scale rational coefficients \(\omega^t_S\) for \(S\in[E]^k\), with \(\Psi^t=0\), define \(u_t(A)=\sum_{S\subseteq A}\omega^t_S\) and \(\Phi_\mu(A,B)=\sum_t\mu_t(u_t(A)-u_t(B))\). Return one alternative in \(\gamma(2^E,\Phi_\mu)\), with input size measured in \(|E|,\tau\)\) and the coefficient and mass bit length. For \(\gamma=TC\), this is to return a set maximizing \(\sum_t\mu_tu_t(A)\).
A continuous society is a distribution \(\mu\) over complete SSB preference types on the same item set \(E\). Each type carries its calibrated coefficient vector \(\omega^t\); the aggregate tournament has coefficients \(\bar\omega_S=\sum_t\mu_t\omega^t_S\), and the task is to compute a winner under fixed \(\gamma\).
The mirror adds interpersonal cardinal calibration and utilitarian aggregation, commitments the paper does not itself endorse; the shared-elicitation platform scenario makes them plausible but does not derive them from the paper.
fatal: False
The mirror covers Theorem 3's hardness for Top-Cycle-refining solutions with bounded-degree set interactions and Theorem 4's tractable Borda computation for singleton parameters. It leaves the learning procedure, experiments, and other tournament-solution results without a population mirror.
I would lead with Theorem 3, because it gives a genuine hardness boundary for the winner problem. The population mirror is natural in a setting such as a large platform or university choosing a bundle of features or courses: millions of users may fall into a much smaller number \(\tau\) of recurring preference groups. A type is the group’s complete SSB model over the same item set \(E\); its mass \(\mu_t\) is its fraction of users. This requires a common scale for preference intensities, which is plausible when they come from the same elicitation process.
There is a useful exact bridge to the paper’s model. If type \(t\) has parameters \((\omega^t,\Psi^t)\), define the society’s comparison intensity by
\[
\Phi_\mu(A,B)=\sum_{t=1}^{\tau}\mu_t\,\phi_t(A,B).
\]
Because the SSB expression is linear in its parameters, \(\Phi_\mu\) is itself an SSB model, with parameters \(\bar\omega=\sum_t\mu_t\omega^t\) and \(\bar\Psi=\sum_t\mu_t\Psi^t\). Thus the mirror keeps the paper’s underlying question—compute winners of an SSB-induced weighted tournament—while making the population the continuous object.
Theorem 3 is proved in the paper, using a reduction based on a maximum-set-function hardness result of Fishburn and LaValle. It says that for every fixed \(k\ge 2\), when the alternatives are the complete set \(2^E\), the parameter set is \([E]^k\), and \(\gamma\subseteq TC\), SSB-ONE-\(\gamma\) has no polynomial-time algorithm unless \(\mathrm{P}=\mathrm{NP}\). Here \([E]^k\) consists of the nonempty subsets of \(E\) of size at most \(k\), and \(TC\) is the Top Cycle.
The continuous question I would hand to a prover is Population SSB Winner. The input is a finite item set \(E\), a fixed \(k\ge2\), a fixed tournament solution \(\gamma\subseteq TC\), and a support of \(\tau\) types with positive binary-rational masses \(\mu_t\) summing to one. Each type has rational coefficients \(\omega^t_S\) for \(S\in[E]^k\), and uses the SSB subcase with \(\Psi^t=0\):
\[
u_t(A)=\sum_{\substack{S\in[E]^k\\S\subseteq A}}\omega^t_S,\qquad
\Phi_\mu(A,B)=\sum_t\mu_t\bigl(u_t(A)-u_t(B)\bigr).
\]
The task is to return one alternative in \(\gamma(2^E,\Phi_\mu)\). For the lead instance \(\gamma=TC\), this means returning a subset maximizing \(u_\mu(A)=\sum_t\mu_tu_t(A)\). Its input size is measured in \(|E|\), \(\tau\), and the binary bit length \(L\).
I expect hardness transfers (Class B). Setting \(\tau=1\) recovers the paper’s hard instances, so hardness holds even when the population has only one type; the reduction’s combinatorics lie in selecting subsets of \(E\), not in population multiplicity. This makes the question a real mirror, although not a claim that continuous mass makes the problem easier. It also raises useful boundary questions: does bounded interaction structure, such as bounded treewidth among the pair terms, restore tractability? Does allowing intransitive \(\Psi\) alter the boundary for particular \(\gamma\)?
A second, complementary anchor is Theorem 4, proved in the paper. It says that SSB-ALL-BORDA can be solved in \(O^*(n^2)\) time in both the complete case and the partition case when \(\theta=[E]^1\). It gives a compact representation of the full Borda set. In the complete case, the set is described by
\[
C(i)=2\omega_i+\sum_{j\in E}\Psi_{ij},\qquad
\operatorname{BordaSet}(T)=\{A:C_{>0}\subseteq A\subseteq C_{\ge0}\}.
\]
In the partition case, where each alternative selects one item from each block \(X_1,\dots,X_p\),
\[
C(i)=\Bigl(\sum_{t=1}^p|X_t|\Bigr)\omega_i+
\sum_{j\in E}\Bigl(\sum_{t:\,j\notin X_t}|X_t|\Bigr)\Psi_{ij},
\]
and the Borda set consists of the alternatives choosing a \(C\)-maximizer in every block.
Its population mirror is Population SSB Borda Set. The input is \(E\), either the complete alternatives or a partition family, and \(\tau\) types of positive rational masses. Each type has singleton SSB coefficients \(\omega_i^t\) and skew-symmetric \(\Psi^t_{ij}\). Define \(\bar\omega_i=\sum_t\mu_t\omega_i^t\) and \(\bar\Psi_{ij}=\sum_t\mu_t\Psi^t_{ij}\). The task is to return a compact representation of all maximizers of
\[
\operatorname{Borda}_\mu(A)=\sum_{B\in\mathcal A}\Phi_\mu(A,B).
\]
Applying Theorem 4 to the averaged parameters gives the representation in time polynomial in \(n,\tau,L\) (with \(O^*(n^2)\) coefficient work after aggregation). I expect this mirror to be tractable (Class A). It asks whether the population’s Borda winners can be represented, not for an exponentially long listing of them. Natural follow-up questions are whether the compact description survives higher-order synergies and whether similar population algorithms exist for other tournament solutions.
Together, these anchors cover part of the paper’s winner-computation results: hardness for Top-Cycle-refining solutions with interactions of degree at least two, and tractable Borda computation with singleton parameters. They do not mirror the learning procedure, its experiments, or the paper’s results for every tournament solution.
The weakest point is that the paper presents an SSB model of preference intensities, not explicitly a population profile; aggregating intensities across people requires a shared cardinal scale. The hardness anchor also uses \(\Psi=0\), so by itself it says little about intransitive preferences. I think the mirror remains credible because the paper’s own object is a weighted tournament of intensities, aggregation preserves the SSB form exactly, and Theorem 4 supplies a separate anchor that permits nonzero, skew-symmetric \(\Psi\).
The strongest objection is that both anchors start from a model of one decision-maker’s pairwise preference intensities. Turning that into a society requires an aggregation rule the paper does not supply. The proposed rule, \(\Phi_\mu(A,B)=\sum_t\mu_t\phi_t(A,B)\), treats intensity scales as comparable across people. But the same ordinal preferences can be represented after multiplying one person’s coefficients by any positive constant, and that can change the aggregate winner. The mirror therefore needs a shared calibration convention—say, intensities elicited on a common probability scale—or it is not determined by the types’ preferences alone.
That matters especially for Theorem 3. In the proponent’s instance, \(\Psi=0\), so each type has a transitive utility \(u_t\), and Top Cycle returns the alternatives maximizing \(u_\mu(A)=\sum_t\mu_tu_t(A)\). This is a coherent population problem if a common cardinal scale and utilitarian aggregation are intended, but the hardness result is then about maximizing an aggregate set function, not about intransitive social preferences. Replacing intensity averaging with majority comparisons would avoid interpersonal cardinal comparison, but it would change the object to \(\sum_t\mu_t\operatorname{sgn}(\phi_t(A,B))\); Theorem 3 would no longer establish the result for that problem. This is a real modeling gap, though not a decisive objection: calibrated preferences and utilitarian aggregation are plausible in some bundle-selection settings.
Theorem 4 has the same dependency and is harder to dismiss. With calibrated types, averaging \(\omega^t\) and \(\Psi^t\) gives a valid aggregate SSB model, and the theorem’s compact Borda-set formula applies. That makes the population computation immediate after aggregation, but immediacy is not a reason the mirror is uninteresting under this programme: it is a tractable continuous result. The more substantive concern is whether averaging users’ intensities and then applying Borda across every feasible bundle is a norm the authors would endorse for a group choice. A platform choosing among bundles could adopt it, but it is an extra social-choice commitment, not a consequence of the individual model.
So the negative case is weak on the burden the prompt sets. It can show that neither theorem yields a population question without an explicit, defensible aggregation convention. It cannot show that no such convention or scenario is worthwhile. If users’ preferences are calibrated on a common scale, both mirrors are well-posed; in particular, Theorem 3 gives a strong computational question and Theorem 4 a clean tractable one. The best case against is a warning about the added modeling choice, not a convincing universal case against a continuous mirror.
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.