| paper | d4-conf-ecai-2020-0271 |
| 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→P discrete result → its continuous mirror
Answer: The score \(S(p)\) is exactly computable in time polynomial in \(m,\tau,L\), and its threshold problem belongs to \(\mathrm P\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given candidates \(C\), a target \(p\), and a finite support \(\mathcal A\) of approval types with binary rational masses \(\mu_A\) summing to \(1\), compute the maximum retained mass \(\sum_{A\in\mathcal A}x_A\), subject to \(0\le x_A\le\mu_A\) and, for every \(a\ne p\), \(\sum_{A:p\in A,\ a\notin A}x_A\ge\sum_{A:a\in A,\ p\notin A}x_A\).
A society is a distribution \(\mu\) over approval-set types \(A\subseteq C\). Choose retained mass \(x_A\) for each type, bounded by \(\mu_A\), to maximize total retained mass while ensuring that \(p\) weakly defeats every rival by pairwise majority.
The mirror covers Theorem 2's dichotomous Young score result and also gives continuous score comparisons related to Theorem 4; the paper's other rules and preference domains are not covered.
The strongest mirror is dichotomous Young score. Consider a large approval election with a fixed slate of \(m\) candidates, where many people cast the same approval ballot. A type is an approval set \(A\subseteq C\); its mass \(\mu_A\) is the fraction of the electorate using that ballot. For example, an election might have millions of voters but only hundreds of observed ballot types. That is a plausible many-agent regime: sharing a type means sharing exactly the preference information Young’s rule uses.
Lead — Continuous Approval Young Score. Given candidates \(C\), a target \(p\), and a finite support \(\mathcal A\) of approval sets with positive binary rational masses \(\mu_A\) summing to \(1\), choose how much mass \(x_A\) of each type to retain. The objective is to maximize retained population while making \(p\) a weak Condorcet winner. For each \(a\ne p\), let \(P_a=\{A:p\in A,\ a\notin A\}\) and \(Q_a=\{A:a\in A,\ p\notin A\}\). The problem is to compute
\(\mathrm{YScore}_{\infty}(\mu,p)=\max\left\{\sum_{A\in\mathcal A}x_A:\ 0\le x_A\le\mu_A,\ \sum_{A\in P_a}x_A\ge\sum_{A\in Q_a}x_A\ \text{for every }a\ne p\right\}.\)
Its decision version asks whether this optimum is at least a given rational \(q\); a solution to the optimization version is an optimal vector \(x\). The constraints say exactly that, among the retained mass, \(p\) is preferred to each rival by at least as much mass as prefers that rival to \(p\). Candidates and approval types remain finite; the population and retained subpopulation are the continuous objects.
The main anchor is Theorem 2, proved in this paper: for dichotomous preferences, YoungWinner is in \(\mathrm P\), while YoungScore is NP-complete. The paper proves the hard score result by reduction from Independent-Set; the winner result follows from its Theorem 1. The continuous score problem above is a direct mass version of Young’s definition, and its LP has \(\tau\) variables, \(m-1\) pairwise constraints, and rational input. It is solvable exactly in time polynomial in \(m,\tau,L\), so I expect this mirror to be Class A, tractable. The continuous YoungWinner problem is also in \(\mathrm P\): compute each candidate’s score with an LP and compare.
There is a concrete reason to expect the Independent-Set hardness to dissolve. In the paper’s reduction, graph vertices become voter types and graph edges become candidates. For a triangle, the discrete Young score of \(p\) is \(\alpha(G)+1=2\), out of four voters. In the continuous version, retain mass \(1/4\) of the \(p\)-only type and mass \(1/8\) of each vertex type. Every edge candidate then receives exactly \(1/4\) mass preferring it to \(p\), so \(p\) remains a weak Condorcet winner; the retained mass is \(5/8\), above the discrete score fraction \(1/2\). More generally, the gadget’s constraints become \(x_u+x_v\le x_p\) for every edge, the fractional vertex-packing LP. This is a real relaxation: the integral independent-set choice becomes a tractable fractional optimization.
A second worthwhile anchor is Theorem 4, proved here by reduction from the cited \(\Theta_2^p\)-complete Min-Card-Independent-Set-Compare problem: YoungRanking for dichotomous preferences is \(\Theta_2^p\)-complete. Its continuous mirror, Continuous Approval Young Ranking, takes \((C,\mathcal A,\mu,p,r)\) and asks whether \(\mathrm{YScore}_{\infty}(\mu,p)\ge \mathrm{YScore}_{\infty}(\mu,r)\). The solution is yes or no, obtained by computing and comparing the two exact LP optima. I also expect this to be Class A.
These mirrors cover the dichotomous Young score and ranking results, with the winner result covered as a comparison among continuous scores. Natural follow-up questions are how large the integrality gap can be as a function of \(m\) and \(\tau\), which support structures make the LP integral, and whether the LP value gives useful additive guarantees for the discrete score.
My weakest point is that the discrete score retains or deletes whole voters, while the mirror can retain a fraction of a ballot type. That is the key co-modification needed to make population mass continuous, and it is natural for large homogeneous blocs, but it changes the exact finite-election quantity. Also, the hardness construction itself gives one voter per graph vertex and can have \(\tau\) near the electorate size; it does not establish the high-multiplicity regime. The case rests on the separate, plausible regime of large approval electorates with many repeated ballot types, and on the direct LP relaxation of the authors’ score definition.
I can’t make a credible case that both of these mirrors fail. The strongest objection is that Young’s score counts whole voters, while the proposed LP lets you retain fractions of each ballot type. That changes the finite election problem. But it is exactly the population co-modification the programme permits: in a large bloc of interchangeable voters, retaining a fraction of the bloc is meaningful, and an approval set fully describes the information Young uses. The graph reduction’s one voter per vertex does not rule out a separate regime with many voters sharing each approval ballot.
For Theorem 2, the mirror is well posed. Let \(x_A\) be the retained mass of approval type \(A\). The constraints
\[
\sum_{A:\,p\in A,\ a\notin A}x_A
\;\ge\;
\sum_{A:\,a\in A,\ p\notin A}x_A
\qquad (a\ne p)
\]
say precisely that \(p\) is a weak Condorcet winner among the retained mass. Maximizing \(\sum_A x_A\), subject to \(0\le x_A\le\mu_A\), is a rational LP with polynomially many variables and constraints in the explicit input size. Its tractability would be a meaningful continuous counterpart to the paper’s NP-complete score problem. The winner result also has a clear mirror: with dichotomous preferences, weak Condorcet winners have full Young score, and the winner question remains easy.
Theorem 4 survives the same scrutiny. Comparing the two candidates’ optimal retained masses is a natural continuous version of comparing Young scores. Solving two LPs answers it. The fact that this may erase the discrete \(\Theta_2^p\)-hardness is not a reason to reject the question; it is the kind of change the programme is meant to chart.
So the best negative case is only a caution about interpretation: fractional retention is not the exact finite operation of deleting voters. It does not defeat either mirror under the programme’s stated high-multiplicity standard. I see no sound objection here based on absent computational results, identity dependence, degeneration, or existing continuous treatment. The honest negative assessment is weak: these anchors look like worthwhile mirrors, especially Theorem 2.
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.