| paper | d4-conf-ijcai-2022-0912 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
parameterized→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete and \(\mathrm{W}[1]\)-hard parameterized by \(k\), even for dyadic masses; in XP in the encoded input length, but not FPT unless \(\mathrm{FPT}=\mathrm{W}[1]\). · discrete side: parameterized · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given a finite line \([m]\), parties with candidate sets \(C_i\), and a finitely supported binary-rational distribution \(\mu\) over voter locations, does there exist a nomination profile \(s\) in which every party’s expected payoff is at least its payoff from any unilateral change of nominee? All candidate costs are zero, and the parameter is the maximum overlap of the parties’ candidate intervals.
Voter locations are types carrying mass \(\mu_x\). Parties choose nominees from their original finite candidate sets; mass is divided equally among nearest distinct nominee locations and then among parties nominating at the same location. The question is existence of a pure Nash equilibrium.
Covers Theorem 5’s zero-cost \(W[1]\)-hardness by overlap and its ETH lower bound; it does not cover the paper’s results for nonzero or uniform costs, or its algorithmic parameter bounds.
The strongest mirror I believe is the zero-cost equilibrium problem. Call it Rational-Mass Hotelling–Downs Equilibrium Existence. Keep the paper’s line \([m]\), parties, and candidate sets \(C_i\). Replace the voter counts by a distribution \(\mu\) on locations: each positive mass \(\mu_x\in\mathbb{Q}_{>0}\) is the fraction of the electorate at \(x\), and the masses sum to \(1\). The type is a voter’s location, which fully determines how that voter contributes to party payoffs. A party still nominates one candidate from \(C_i\); all candidate costs are zero.
For a nominee profile \(s\), let \(D(x,s)\) be the set of distinct nominated locations nearest to \(x\), and let \(k_a(s)\) be the number of parties nominating at \(a\). Party \(i\)’s payoff is
\[
U_i(s)=\sum_{\substack{x:\ s_i\in D(x,s)}}\frac{\mu_x}{|D(x,s)|\,k_{s_i}(s)}.
\]
Thus ties between locations are divided equally, as are voters at a location among parties nominating there. The question is whether there is a profile \(s\) such that \(U_i(s)\ge U_i(a,s_{-i})\) for every party \(i\) and every alternative \(a\in C_i\). A solution is such a nomination profile. The parameter is the paper’s overlap: the maximum number of parties whose candidate intervals contain any one location.
The anchor is Theorem 5, proved in this paper: HD-NE is \(W[1]\)-hard parameterized by overlap even when every candidate cost is zero; moreover, assuming ETH, there is no \((n+m)^{o(\mathrm{ov})/\log(\mathrm{ov})}\)-time algorithm. The paper proves this through a reduction from Partitioned Subgraph Isomorphism, using the cited hardness results for that source problem. I would expect the same hardness for Rational-Mass HD-NE, with hardness transferring from the discrete problem.
The transfer is exact. Given the paper’s voter counts \(v_x\), set \(N=\sum_x v_x\) and \(\mu_x=v_x/N\). With costs zero, every party’s payoff is scaled by the same positive factor \(1/N\), so the best responses, equilibria, candidate choices, and overlap are unchanged. The reduction therefore remains valid with binary rational masses; its normalized values have polynomial encoding length. Conversely, any finite rational mass vector can be scaled by a common denominator into integer counts. This is a strong reason to expect the authors to recognize the mirror: it asks their equilibrium-existence question for a distributional electorate, with exactly the same strategic choices and tie rules.
A plausible regime is a large electorate spread across a modest set of locations or ideological positions, with many voters at each represented location. Their shared location makes them identical for the payoff calculation; population size can grow while the support stays small. This continuizes the population while retaining the paper’s finite line and nominee options. My claim covers Theorem 5’s zero-cost, overlap-parameterized hardness result, not every result in the paper. The expected classification is hardness transfers: the reduction’s combinatorics lie in the parties’ nominee choices and candidate arrangement, not in indivisible voter counts.
The soft spot is that the paper already aggregates voters by location, so this mirror is mathematically close to its input model. For rational masses, the zero-cost decision problem is essentially a normalized encoding of integer voter counts. That makes the mirror unusually credible, but it also means this anchor does not show that continuization dissolves hardness or creates a new algorithmic landscape. Natural follow-up questions are whether the paper’s algorithmic parameter bounds carry over with explicit binary-rational arithmetic, and whether support size or additional geometric restrictions yield stronger results for rational-mass electorates.
My strongest case against Theorem 5 is that its proposed rational-mass mirror adds no new computational instances. For any rational society \(\mu\), choose a common denominator \(N\) and set \(v_x=N\mu_x\). With zero costs, every payoff in the mass model is the paper’s payoff divided by \(N\). Best responses, equilibria, overlap, and the reduction are unchanged. The reverse map is \( \mu_x=v_x/\sum_y v_y \), and the common denominator has polynomial bit length. So the paper’s theorem already gives the mirror’s complexity classification by a change of units.
Even a continuous distribution of voter locations offers little escape while candidate positions stay finite. Refine the line at every possible midpoint between candidate positions. Each nominee profile assigns each resulting cell to the same nearest nominee, so a rational density can be compressed to its masses on those cells. A continuum of candidate choices would add a different continuous object: the strategy space, rather than the population.
That makes the mirror look unusually redundant. Still, this is a weak objection under ChoCo’s rules. The paper’s input is integer voter counts, while the mirror defines society as rational mass; the exact correspondence is the bridge between them. The programme treats such bridges as a deliverable, and it explicitly accepts “the same answer” as a worthwhile result when the models are genuinely distinct. The large-electorate scenario is also natural. I therefore cannot honestly defeat this anchor: the redundancy case raises a concern about incremental value, but it does not establish that the mirror is out of scope or not worth asking.
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.