| paper | d4-conf-ecai-2024-0193 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: The problem is in \(\mathrm{P}\): every valid instance is a yes-instance, including when \(\epsilon=0\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 14
statement extracted from the paper’s text layer
Given candidates \(C\), committee size \(k\), ballot size \(l\), and disjoint approval parties \(P_i\) with rational masses \(\mu_i\) summing to \(1\), let \(q_i=\lfloor k\mu_i\rfloor\) and assume \(l\le q_i\le |P_i|\). Each party allocates its mass among ballots \(B\in\binom{C}{l}\), with \(x_{i,B}\ge0\) and \(\sum_B x_{i,B}=\mu_i\); candidate \(c\) receives vote mass \(\sum_i\sum_{B\ni c}x_{i,B}\). The winning committees are the size-\(k\) sets with maximum total vote mass, and party \(i\)'s utility is its minimum number of candidates in any winning committee. Does the profile that chooses \(X_i\subseteq P_i\) with \(|X_i|=q_i\) and distributes type \(i\)'s mass uniformly over the \(l\)-subsets of \(X_i\) form an ε-Nash equilibrium against arbitrary unilateral mass reallocations, where \(\epsilon=k-\sum_i q_i\)?
The society has approval types \(P_i\) carrying masses \(\mu_i\); each party remains a strategic player and allocates its mass over integral \(l\)-candidate ballots. Outcomes remain discrete size-\(k\) committees, scored by vote mass, and party utility is the worst-case number of its candidates elected across tied winners.
The premise requires \(l\le q_i\) for every party; with the paper's motivating \(l=\lceil k/2+1\rceil\), this rules out a multi-party case, so that workplace scenario needs a smaller ballot limit.
fatal: False
The mirror covers only Theorem 14's lower-quota ε-stability guarantee; it leaves the other game-theoretic results and the paper's diversity, proportionality, and experimental analyses aside.
The paper has no named result classifying a problem as NP-hard, polynomial-time solvable, FPT, or similar. Its closest useful computational anchor is Theorem 14, proved in this paper: in an LV game where each party \(P_i\) has \(l \le \lfloor k n_i/|N|\rfloor \le |P_i|\), if every party uses a lower-quota strategy—spreading its votes as evenly as possible over that many of its own candidates—the profile is an \(\varepsilon\)-Nash equilibrium, with
\[
\varepsilon = k-\sum_i\left\lfloor\frac{k n_i}{|N|}\right\rfloor.
\]
Here the parties’ utility is the worst number of their candidates elected across tied winning committees. This is an equilibrium guarantee, not a complexity classification; I would not present it as an NP-hardness or tractability result.
The strongest positive mirror I see is Continuous Lower-Quota LV Stability, covering that result in Section 7. A natural regime is a large workplace or sector election with many employees but relatively few approval types: for example, employees organized around departments or office locations, where people of a type approve the same candidates. A type is an approval party \(P_i\); its mass \(\mu_i\) is its share of the electorate, with \(\sum_i\mu_i=1\). The regime has many voters and comparatively few types. This is a plausible setting for the paper’s strategic-party model, though it is more structured than the particular company scenario in the introduction.
An instance consists of candidates \(C\), disjoint approval parties \(P_1,\ldots,P_g\), committee size \(k\), ballot size \(l\), and binary-rational masses \(\mu_i\), satisfying \(l\le q_i\le |P_i|\), where \(q_i=\lfloor k\mu_i\rfloor\). Each party chooses an allocation \(x_{i,B}\ge 0\) of its mass among ballots \(B\in\binom{C}{l}\), with \(\sum_B x_{i,B}=\mu_i\). Candidate \(c\)’s vote mass is \(\sum_i\sum_{B\ni c}x_{i,B}\); the winning committees are all size-\(k\) sets with maximum total vote mass. As in the paper, party \(i\)’s utility is the minimum number of its candidates in any winning committee.
The problem is: construct a lower-quota mass allocation and establish its stability. Choose \(X_i\subseteq P_i\) of size \(q_i\), and have type \(i\)’s mass vote uniformly over the \(l\)-subsets of \(X_i\). The requested solution is this allocation together with the guarantee that no party can improve its worst-case number of elected candidates by more than
\[
\varepsilon=k-\sum_i q_i.
\]
This is a direct mass version of the paper’s lower-quota strategy: the finite game records the number of voters using each ballot, while the continuous game records the fraction of each type doing so.
The mirror should have the same \(\varepsilon\)-equilibrium conclusion. Under the construction, each candidate in \(X_i\) receives mass \(\mu_i l/q_i\ge l/k\), and \(\sum_i q_i\le k\), so all lower-quota candidates fit in every winning committee. A deviating party has total ballot incidence mass \(\mu_i l\); it cannot give \(q_i+1\) of its candidates vote mass at least \(l/k\), since \(q_i+1>k\mu_i\). The other parties’ lower-quota candidates retain at least that threshold, leaving the deviating party at most the \(\varepsilon\) unfilled seats beyond its \(q_i\) candidates. This points to Class A for this bounded stability question: the guarantee follows from a direct mass argument. It does not settle exact equilibrium computation or best responses in arbitrary LV games.
The soft spot is that Theorem 14 is a strategic-game result, not a hardness or complexity theorem about winner robustness or control. The committee remains discrete, and the bound is in seats: \(\varepsilon\) is determined by the quota slack, so it does not automatically shrink as the electorate grows. Still, the mirror retains the paper’s underlying question about how parties allocate votes to obtain representation. Replacing ballot counts by masses is especially credible here because the paper’s game already groups voters by which ballot they cast. My case is for this Section 7 result alone, not for continuizing the paper’s diversity and proportionality analyses wholesale.
The strongest case against is a scope objection. The paper has no named result about the complexity of a computational problem. Theorem 14 is a game-theoretic stability guarantee: under lower-quota assumptions, a specified strategy profile is an \(\varepsilon\)-Nash equilibrium. It gives no running time, hardness result, or algorithmic landscape for LV. The proposed mirror therefore does not continue a computational result of the kind ChoCo is set up to chart.
The proponent’s setting is nonetheless coherent. A workplace could have many employees in a small number of approval groups, and each group’s mass could be distributed over ballots. Treating candidates and committees as discrete while making voter mass continuous is a sensible co-modification. The objections that party membership is too coarse, or that committees remain discrete, do not defeat it.
But the best version of this mirror still asks for an equilibrium guarantee the paper already constructs explicitly: set \(q_i=\lfloor k\mu_i\rfloor\), spread type \(i\)’s mass over its lower-quota candidates, and report the resulting quota-slack bound. That is a valid continuous restatement. It does not pose the pricing, optimization, or complexity question that motivates the programme. One could invent adjacent questions about computing exact equilibria or best responses, but those would be new computational problems, not mirrors of Theorem 14’s result.
There is also a limitation in the proposed workplace connection: the theorem requires \(q_i\ge l\) for every party, so \(g l\le k\). With the paper’s motivated ballot size \(l=\lceil k/2+1\rceil\), this permits at most one party under those assumptions. Choosing a smaller \(l\) restores multi-party cases, so this weakens the particular application rather than ruling out the mirror generally.
So the honest negative case is narrow: this is not a strong ChoCo mirror because its anchor is outside the programme’s computational target, and its continuous version appears to be a direct fractional restatement rather than a new algorithmic question. The universal claim is weak, though. If ChoCo includes computational game theory and treats constructive equilibrium guarantees as in scope, the mass-game mirror survives; I see no fundamental modelling obstruction that rules it out.
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.