| paper | d4-conf-ijcai-2018-0907 |
| 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: Polynomial-time solvable (\(\mathrm{P}\)). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given candidates \(C\), issue relations \(\mathrm{SUPPORTS}\) and \(\mathrm{OPPOSES}\), and partial-ballot types \(t\) with rational masses \(\mu_t\) summing to \(1\), let \(y_{t,c}\ge 0\) be mass of type \(t\) completed with \(c\) first, for \(c\in\operatorname{Max}(t)\), with \(\sum_{c\in\operatorname{Max}(t)}y_{t,c}=\mu_t\). Define \(W_y=\arg\max_{c\in C}\sum_t y_{t,c}\). Is it true for every feasible \(y\) that some issue \(i\) has a candidate \(c\in W_y\) with \(\mathrm{SUPPORTS}(c,i)\) and a candidate \(d\in W_y\) with \(\mathrm{OPPOSES}(d,i)\)?
A distribution over partial-ballot types with rational mass; each type’s mass may split among its possible top-ranked candidates. The resulting plurality winners are tested against the paper’s issue-conflict query.
The mirror covers the connected coNP-complete case of Theorem 3, specifically \(q_3\); it leaves the disconnected tractability case and the paper’s other results unaddressed.
The strongest mirror I see is the paper’s connected plurality-query hardness, instantiated by its issue-conflict query \(q_3\). Its scenario is a large poll in which many respondents share one of a modest number \(\tau\) of incomplete ballot patterns: they report the same pairwise comparisons, but leave other comparisons unspecified. Candidate issue positions remain in an ordinary database. A type \(t\) is one such ballot pattern, with rational population share \(\mu_t\); different members of the cohort may have different full rankings consistent with it.
My anchor is Theorem 3, proved in this paper. It classifies necessity for Boolean conjunctive queries with exactly two distinct plurality-winner atoms for the same election and with self-join-free ordinary atoms: if the winner variables are in different connected components of the query’s Gaifman graph, necessity is in P; if they are connected, necessity is coNP-complete. The paper explicitly applies the hard case to \(q_3\):
\[ q_3() \leftarrow \mathrm{WINNER}(\mathrm{plurality},e,c),\ \mathrm{SUPPORTS}(c,i),\ \mathrm{WINNER}(\mathrm{plurality},e,d),\ \mathrm{OPPOSES}(d,i). \]
This asks whether, in every completion, there are two plurality winners who take opposing recorded positions on the same issue. Theorem 3 is proved here; its hardness proof establishes a coNP-hard core query by reduction from the complement of Maximum Independent Set, then extends that hardness to connected queries in the stated class.
I would call the mirror Continuous Necessary Issue-Conflict. An instance gives candidates \(C\), one election, issue tables \(\mathrm{SUPPORTS}\) and \(\mathrm{OPPOSES}\), and a finite support of partial-order ballot types \(t\), each with rational mass \(\mu_t\), where \(\sum_t\mu_t=1\). For each candidate \(c\) that is maximal in type \(t\)’s partial order, choose \(y_{t,c}\ge 0\), the mass of that type completed with \(c\) at the top, subject to
\[ \sum_{c\in\max(t)} y_{t,c}=\mu_t. \]
The plurality score is \(S_y(c)=\sum_t y_{t,c}\), and \(W_y=\arg\max_{c\in C}S_y(c)\). The decision question is: for every feasible mass allocation \(y\), do there exist an issue \(i\), a supporter \(c\), and an opposer \(d\) of that issue such that \(c,d\in W_y\)? A yes-instance means the query is necessary in the continuous society; a no-instance has a feasible mass allocation whose winner set contains no such pair.
This is a faithful population relaxation of the paper’s query semantics: it retains partial rankings, completions, plurality winners, and the contextual query, while replacing individual voter counts with rational cohort masses. A discrete profile with counts \(n_t\) maps to \(\mu_t=n_t/n\); its completions give integral multiples of \(1/n\) in the \(y\)-variables. The continuous problem also admits fractional allocations between those grid points. Winners and issue positions remain discrete. The mirror covers this connected-query hardness result, not the paper’s full database framework or its possible-answer and non-plurality results.
My expectation is continuum-specific hardness, though with only moderate confidence. For any proposed winner set, feasibility can be expressed through the mass-allocation constraints and score comparisons. The hard part appears to be finding a realizable winner set that avoids every issue-conflict pair; the issue table can make that a combinatorial search even though the underlying mass allocation is linear. That is a reason to investigate hardness, not a proof of it.
The soft spot is substantial: Theorem 3’s discrete reduction chooses completions voter by voter, while the continuous mirror lets a cohort split its mass among several admissible top choices. The reduction therefore does not establish hardness transfer, and splitting might make the mirror easier. The authors could still recognize the question as theirs—the query and its universal completion semantics are preserved—but any complexity claim for the continuous version needs a new argument that handles fractional mass.
I can make one serious objection, but it does not defeat the mirror. Theorem 3 is an explicit computational result: for its stated class of fixed queries, connected winner atoms make necessity coNP-complete, and the paper names \(q_3\) as an instance. That gives the proponent a real anchor. [The paper](https://www.ijcai.org/proceedings/2018/0044.pdf)
The concern is that incomplete ballots describe uncertainty about named voters’ rankings, while the proposed mirror lets the mass of one partial-ballot type split among completions. That changes the set of possible worlds. But for \(q_3\), no voter identity appears in the query. In a large poll with repeated partial-ballot patterns, every such split describes a possible aggregate composition of latent full rankings. The question—whether an issue conflict occurs among the plurality winners in every composition consistent with the recorded ballots—is coherent and close to the paper’s necessity semantics. A survey with many respondents and a modest number of repeated response patterns is a plausible high-multiplicity regime.
A second concern is that \(q_3\) requires co-winners, which often arise only at exact score ties in a continuous population. That makes the query sensitive to special mass distributions. It does not make it vacuous: some ballot types can force tied top shares, and the query deliberately asks about the entire winner set. Its tie semantics carry over naturally.
So the honest negative case is weak. Theorem 3’s discrete reduction does not itself establish hardness after fractional splitting, and the proponent’s continuum-specific-hardness expectation is unproved. But that is a gap in the answer, not a reason the question lacks value. I cannot defend the claim that no worthwhile continuous mirror exists for this anchor.
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.