| paper | Computing the Proportional Veto Core |
| authors | Egor Ianovski, Aleksei Y. Kondratev |
| venue | AAAI 2021 |
| filed under | voting · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(m,\tau,L\), including exclusion witnesses. · discrete side: polynomial · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given candidates \(C\), ranking types \(T\), and rational masses \(\mu_t\) summing to \(1\), compute exactly the candidates \(c\) such that for every \(B\subseteq C\setminus\{c\}\), \(\sum_{t:B\subseteq A_t(c)}\mu_t\leq (|C|-|B|)/|C|\), together with witnesses \(B\) for excluded candidates.
A high-multiplicity proportional veto election: ranking types carry masses \(\mu_t\), blocking sets are supported by compatible type mass, and weighted biclique or minimum-weight vertex-cover flow computes the exact core.
The mirror covers Theorem 2 and leaves the paper's core-size results, axiomatic propositions, voting-rule properties, and manipulation results unaddressed.
The strongest positive case is a continuous-population version of the paper’s core-computation result.
The anchor is Theorem 2, proved in this paper: “The veto core can be computed in polynomial time.” Its content is exact, not approximate. Given any finite profile of \(n\) voters over \(m\) candidates, one can determine, for every candidate \(c\), whether some coalition \(T\) and blocking set \(B\) satisfy the paper’s two conditions: every voter in \(T\) ranks every member of \(B\) above \(c\), and \(m-|B|\leq \lceil m|T|/n\rceil-1\). The theorem reduces this to a biclique problem and then to maximum flow, yielding a polynomial-time algorithm; the paper gives running time \(O(m\max(n^3,m^3))\). The theorem is proved here, using Moulin’s cited lemma and the cited polynomial biclique result.
The natural mirror is Continuous Proportional Veto-Core Computation.
An instance consists of a finite candidate set \(C\), \(m=|C|\), a finite set of complete ranking types \(T\), and a rational distribution \(\mu\) over \(T\). A type \(t\) is a complete ranking, and \(\mu_t\) is the fraction of the population holding it. For a candidate \(c\), write \(A_t(c)=\{b\in C:b\succ_t c\}\).
For \(B\subseteq C\setminus\{c\}\), define the compatible coalition mass by \(M_\mu(B,c)=\sum_{t:B\subseteq A_t(c)}\mu_t\). The continuous problem asks for the exact set
\[ \Core_\infty(\mu)= \left\{ c\in C: M_\mu(B,c)\leq \frac{m-|B|}{m} \text{ for every }B\subseteq C\setminus\{c\} \right\}. \]
Equivalently, for each \(c\), maximize
\[ \operatorname{BlockScore}_\mu(c) = \max_{B\subseteq C\setminus\{c\}} \left( M_\mu(B,c)+\frac{|B|}{m} \right). \]
Candidate \(c\) is outside the continuous core exactly when this value exceeds \(1\). A solution is the complete core, together with a witnessing set \(B\) for every excluded candidate.
This is genuinely the paper’s question in continuous form. The finite condition is equivalent to strict inequality \(m-|B|<m|T|/n\). Thus, if \(\mu_t=n_t/n\), then \(M_\mu(B,c)> (m-|B|)/m\) precisely when the corresponding finite coalition blocks \(c\). The ceiling is not being discarded arbitrarily: it disappears because the discrete condition is already equivalent to this strict mass inequality. The continuous model therefore agrees exactly with every rational finite profile and extends it to arbitrary population proportions.
The computational structure also survives. For a fixed \(c\), construct a weighted bipartite graph with type vertices on the left, candidate vertices \(C\setminus\{c\}\) on the right, and an edge \(t b\) exactly when \(b\succ_t c\). Give type \(t\) weight \(\mu_t\) and candidate \(b\) weight \(1/m\). A biclique \(S\times B\) has weight \(\sum_{t\in S}\mu_t+|B|/m\). The maximum such weight is exactly \(\operatorname{BlockScore}_\mu(c)\). Passing to the bipartite complement turns this into a maximum-weight independent-set problem, equivalently a minimum-weight vertex-cover problem, solvable by weighted flow. Repeating for every \(c\) gives an algorithm polynomial in \(m\), the number \(\tau\) of supported ranking types, and the encoding length of \(\mu\).
The regime is plausible rather than artificial: a national or citywide election may contain millions of voters but only a comparatively small number of distinct reported rankings. Since the veto core is anonymous and depends only on coalitions’ common rankings, voters sharing a ranking really are interchangeable for this problem. The type is therefore a complete description of everything the paper uses, and mass is the honest quantity: a coalition is a measurable fraction of the electorate, not a list of named people. This is precisely a high-multiplicity version of the paper’s voting problem, not a change to the candidate space or to the outcome space.
I would classify this mirror as Class A. The weighted-flow formulation is continuous optimization machinery applied to the same underlying veto-core question. It does not claim that a discrete hardness result dissolves—the paper supplies no named hardness anchor, and Theorem 2 already places the finite problem in P. Its contribution is instead an exact compressed algorithm whose running time depends on the number of types rather than on the potentially enormous population size.
The weakest point is that this is a modest positive case. It shows that the paper’s anonymous coalition problem has a clean and computationally meaningful continuum, but not a dramatic complexity separation. A sceptic could call it a capacitated restatement of the paper’s flow proof. The answer is that the restatement is exact on rational profiles, extends naturally to fractional populations, and exposes a genuine high-multiplicity input regime; nevertheless, it should not be sold as a hardness-dissolution result.
It also leaves natural follow-up questions: whether the continuous core admits efficient anonymous single-winner selection under additional constraints; how rational finite elections round to nearby continuous instances near the strict blocking threshold; and what manipulation means when the manipulator is a positive-mass bloc rather than an individual of zero mass. Those questions are not needed to establish this mirror, but they mark its boundary.
I cannot honestly defeat this anchor. Theorem 2 is a named computational result about an anonymous, type-based population problem, and its high-multiplicity version is both natural and computationally distinct.
For a candidate \(c\) and blocking set \(B\), the finite condition is exactly
\[ m-|B|<m\frac{|T|}{n}. \]
After replacing voter counts by masses, this becomes
\[ M_\mu(B,c)>\frac{m-|B|}{m}. \]
Thus the proposed continuous core is not an arbitrary relaxation: it is the exact extension of the paper’s blocking condition from voter counts to population proportions. Rankings are complete types, and the veto core depends only on how much mass shares each relevant ranking property. Individual identity is irrelevant to the paper’s objective.
The strongest possible objection is that this is merely Theorem 2 with weighted counts. But that does not defeat it under the programme’s standard. A rational distribution \(\mu\) may have a binary denominator exponentially larger than its encoding length; expanding it into individual voters is then not a polynomial-time operation. The weighted biclique/flow algorithm gives a genuinely compressed high-multiplicity algorithm, polynomial in \(m\), the supported type count \(\tau\), and the encoding length of \(\mu\). That is precisely the computational value of continuization.
Nor can one object that the type space is artificial. A citywide or national election with many voters sharing a relatively small collection of reported rankings is exactly the kind of high-multiplicity regime the programme endorses. Existing high-multiplicity formulations would strengthen this case, not undermine it.
The mirror is modest: it does not dissolve a hardness barrier, and much of the flow structure is inherited from the discrete proof. But the instructions explicitly rule out treating a dull answer as a failed mirror. The paper does not already formulate the population as a distribution, and no identity-sensitive or vanishing-limit obstruction exists. The single anchor therefore survives, so the universal negative claim is not supportable.
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.