| paper | d4-conf-aaai-2014-0108 |
| 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{-complete}\), even with one candidate in party \(2\), positive masses for every candidate, and dyadic rational masses. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given two disjoint candidate sets \(C_1,C_2\) and binary-rational masses \(\mu_c\) over candidate-favorite voter types, with \(\sum_c \mu_c=1\), each party partitions its candidates into lists. A list \(\ell\) has mass \(\mu(\ell)=\sum_{c\in\ell}\mu_c\); using quota \(1/2\), it receives \(\min\{|\ell|,\lfloor 2\mu(\ell)\rfloor\}\) first-round seats, and remaining seats are allocated by the paper’s largest-remainder rule with ties split by lottery. Does there exist a pair of list partitions that is a pure Nash equilibrium and gives party 1 expected payoff \(2\)?
A rational distribution \(\mu\) over voter types indexed by their favored candidate; candidates remain indivisible and parties choose partitions into lists. List support is the sum of its types’ masses, seats are allocated by the normalized two-seat Hare and largest-remainder rule, and payoffs are expected seat counts.
The paper already represents voters by candidate-favorite counts, and every rational distribution in the mirror can be scaled to an even-count electorate, so the mirror may be a normalization of its existing histogram model.
fatal: False
The mirror covers Theorem 2’s two-party, one-constituency, two-seat decision problem under the paper’s single-favorite-candidate and additive-support assumptions. It leaves the other equilibrium-payoff questions, including Theorem 3 and the general membership result in Theorem 4, aside.
The strongest mirror is the paper’s two-seat list-formation game in a large constituency where many voters share a favorite candidate. A type \(t_c\) is a voter whose one candidate of interest is \(c\). The society is a rational distribution \(\mu\) over these types, with \(\sum_c\mu_c=1\); \(\mu_c\) is the fraction of voters supporting \(c\). For example, the constituency may have many thousands of voters but only a few dozen candidate-favorite groups, with each group containing many people.
Call the resulting problem Mass-SEATS(2,2). An instance gives two parties’ finite candidate sets \(C_1,C_2\) and binary-encoded rational masses \(\mu_c\). Each party’s strategy is still a partition of its candidates into lists. For a list \(\ell\), its vote mass is \(\mu(\ell)=\sum_{c\in\ell}\mu_c\). With two seats, the exact continuous Hare quota is \(1/2\): in the first round, \(\ell\) receives \(\min\{|\ell|,\lfloor 2\mu(\ell)\rfloor\}\) seats. Remaining seats go by the paper’s largest-remainder rule, using remainder \(\mu(\ell)-r(\ell)/2\) for a list that received \(r(\ell)\) first-round seats, and ties are resolved by lottery. Each party’s payoff is its expected number of seats. The question is whether there are partitions \((L_1,L_2)\) that form a pure Nash equilibrium and give party 1 both seats. A yes instance has such a pair of partitions as a witness.
The anchor is Theorem 2, proved in this paper: SEATS(2,2) is NP-complete. In the paper, SEATS\((S,N)\) asks whether an election game has a pure Nash equilibrium in which party 1 wins at least \(N\) seats; thus SEATS(2,2) asks whether party 1 can win both seats in equilibrium. The authors prove NP-hardness by reducing from PARTITION and establish membership in NP. PARTITION’s NP-completeness is cited; Theorem 2 itself is proved here.
I expect the mass version to be NP-hard, with hardness coming from candidate partitioning rather than voter multiplicity. The paper’s integer quota is \(\lfloor V/2\rfloor\), whereas a unit-mass electorate has exact quota \(1/2\), so I would not claim the theorem transfers verbatim. But its Partition gadget adapts to the exact quota. Given positive integers \(a_1,\ldots,a_n\) with \(A=\sum_i a_i>3\), give party 1 candidates with raw support masses \(2a_i\), and party 2 one candidate with mass \(A-1\); divide all masses by \(3A-1\). A partition of the \(a_i\) into two groups of sum \(A/2\) gives party 1 two lists of raw mass \(A\) each. They are below the quota \((3A-1)/2\), but each outweighs party 2’s mass \(A-1\), so party 1 wins both remaining seats. Conversely, if party 1 gets both seats, no party-1 list can cross the first-round quota: its remaining mass, and that of any other party-1 list, would be at most \((A+1)/2<A-1\). Without a first-round seat, two party-1 lists must each outweigh \(A-1\). Their raw masses are sums of the even weights \(2a_i\), and together they total \(2A\), so each must have mass \(A\). Those two lists give a partition of the original numbers. Since party 2 has only one possible partition, a party-1 strategy that wins both seats is a pure equilibrium. This is why I expect hardness to transfer: the reduction’s combinatorics remain in dividing candidate support among lists.
The mirror keeps the paper’s underlying question intact. Parties still partition whole, indivisible candidates, and seats remain discrete; the continuous object is the voter population whose favorite-candidate blocs determine list support. That is a natural reformulation of the paper’s additive vote-count assumption: the mass of a list is the sum of the masses of the voters who favor its candidates. It also gives a high-multiplicity regime—population size can greatly exceed the number \(\tau\) of candidate-favorite types, even as the candidate and type counts vary across instances.
My case covers only Theorem 2’s two-party, one-constituency, two-seat equilibrium-payoff decision under the paper’s single-favorite-candidate and additive-support assumptions. It does not claim to mirror every result in the paper. The main soft spot is the scenario’s narrowness: a large electorate with candidate-level favorite blocs is plausible, but not every election has that structure, and the paper’s two-seat setting is stylized. Still, the paper itself isolates exactly this support-based model, so the mirror retains its central strategic choice rather than simplifying it away. Natural next questions are the mass analogue of the paper’s SEATS(2,1) threshold and the complexity of the same equilibrium-payoff questions when the number of seats varies.
I would not attack the proposed PARTITION adaptation on its arithmetic; it appears sound. My case against the mirror is that the paper has already reduced the voter population to the relevant type histogram. Its input \(\pi(c)\) is the number of voters whose favored candidate is \(c\), and every payoff depends on voters only through those counts. Any type distinctions beyond the favored candidate would be irrelevant to this game.
The proposed continuous model is exactly representable within the paper’s existing input. Given rational masses \(\mu_c\), choose a common denominator \(D\) and set \(\pi(c)=2D\mu_c\). Then \(V=2D\) and the paper’s quota is \(Q=D\). For every list \(\ell\), its first-round seat count is \(\min\{|\ell|,\lfloor 2\mu(\ell)\rfloor\}\), and its discrete remainder is \(D\) times the continuous remainder. So the seat allocations, remainder rankings, tie lotteries, and best responses all agree. The conversion has polynomial bit length. The mirror is therefore the paper’s SEATS\((2,2)\) game on even-electorate instances, expressed in normalized units. The exact continuous quota selects an even-population representative; it does not introduce a population feature this game can observe.
The stronger scenario of a large electorate with candidate-favorite blocs does not change that: it gives a plausible story for the same histogram. Making fractional voters strategically consequential would require changing the paper’s actions or assumptions—for example, allowing parties to split candidates or target voter subgroups—which would no longer mirror Theorem 2.
There is a limit to this objection: Theorem 2’s hardness for all instances does not by itself establish hardness for the even-electorate subfamily. The proposed reduction may establish that refinement. But that would be a complexity result about an already aggregated input model, rather than a distinct continuous-population problem. If a mirror only needs a well-posed mass formulation, my negative case is weak: the mirror is valid, and the paper makes high multiplicity entirely natural.
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.