Veto voting

Special case: one outcome per voter

Mueller introduced the first veto voting method, in the context of deciding how many public goods to produce. His method consists of two steps. In step 1, each voter makes a proposal. Together with the status quo, the number of possible outcomes is n+1. In step 2, the voters are ordered randomly, and each voter in turn eliminates one outccome. Finally, a single outcome remains, and this outcome is implemented. Mueller shows that, given the voters' incentives, the winning proposal tends to contain an equal sharing of the potential gains.

Mueller's method cannot be used in general voting settings, as usually the number of candidates is not exactly n+1. Another disadvantage of it is that the outcome might depend on the ordering of voters, that is, it is not an anonymous procedure.

General case: anonymous veto functions and the veto core

Moulin extended the idea of veto voting by giving veto powers to coalitions, rather than just individuals. Formally, a veto function is a function that assigns, to each subset of voters, a number in {0,1,...,m-1} (where m is the number of candidates), called its veto power, which represents the number of candidates this coalition is allowed to veto. An anonymous veto function is a veto function that satisfies Anonymity, that is, does not distinguish apriori between voters. Thus, the veto power of a coalition depends only on the coalition size. An anonymous veto function is required to be a superadditive set function.

Given a veto function v, an outcome x is blocked by a coalition T of voters if there exists a subset B of outcomes such that (i) all members of T prefer every outcome in B to x; (ii) the veto power v(T) is at least m-|B|, that is, the coalition T can force an outcome of B by vetoing all other outcomes. An outcome x is called stable if it is not blocked by any coalition. The veto core of v is the set of stable outcomes.

The special case of one outcome per voter corresponds to giving every coalition a veto power equal to its size, v(T) = |T|.

Majority-based veto functions

Consider the following veto function (defined for odd n, for convenience):

• Each coalition of size more than n/2 has the maximum voting power: v(T)=m-1;
• Each coalition of size less than n/2 has no voting power: v(T)=0.

Given this function, an outcome x is blocked if and only if there is a strict majority of voters who prefer another outcome over x. In other words, an outcome is stable if and only if it is a Condorcet winner. The core of this function might be empty, as some profiles do not have a Condorcet winner - this is known as the Condorcet paradox.

Nakamura suggested a variant of the majority principle, by which a coalition has full (m-1) veto power if it contains more than some fraction f of the voters, where f can be different than 1/2. He proved that, if and only if f > 1-1/m, where m is the number of candidates, there will always be at least one stable outcome. The problem is that, usually, there will be many stable outcomes. For example, if there are m=10 outcomes, then only a coalition of over 90% of the voters can veto a candidate, which is very rare. Often, the veto core will contain all m candidates.

Proportional veto function

Moulin suggested the proportional veto principle as an alternative to both variants of the majority principle. This principle allocates to each coalition, a veto power proportional to its size. More precisely, a coalition T with t voters has veto power ${\displaystyle \lceil \frac{mt}{n}\rceil -1}$, which is always between m*t/n-1 and m*t/n, where m is the number of candidates and n the number of voters.

An equivalent expression for this veto function can be given by the Bezout coefficients. Let r, c be two integers such that: r*n = c*m - gcd(m,n). Then the above veto function is equal to ${\displaystyle \lfloor \frac{r\cdot t}{c}\rfloor }$.

The proportional veto core is the veto core of the proportional veto function. The proportional veto core is always nonempty. The proof is constructive and uses a sequential veto procedure, which is described below.

Moreover, the proportional veto function gives the largest veto power possible for guaranteeing a stable outcome; every other veto function that guarantees a stable outcome, must give at most the same voting power to all coalitions, and less voting power to some coalitions, which means that the veto core might be larger. Thus, the proportional veto function attains the smallest non-empty veto-core of any anonymous veto function. We illustrate the proof for the special case that m=n. In this case, the veto power function is simply v(t)=t-1. Suppose we give one coalition a larger veto power, e.g. a coalition of size k gets veto power k. We construct a profile with 'circular' preferences: agent 1 prefers candidates 1>2>...>m, agent 2 prefers candidates 2>3>...>m>1, etc. To show that the core is non-empty, we show that each outcome is vetoed by some coalition. Here all outcomes are symmetric, so it is sufficient to prove for outcome m. Indeed, the coalition made of agents 1,...,k has veto power k, and they all prefer candidates k,...,m-1 to m, so they can veto the k candidates m,1,...,k-1.

Examples

Example 1. Suppose there are m=5 outcomes and n=5 voters with the following preferences:

• 1: A > B > C > D > E
• 2: E > A > B > C > D
• 3: D > E > A > B > C
• 4: C > D > E > A > B
• 5: A > B > C > D > E

The proportional veto power function is v(T) = |T|-1. The coalition {1,5} has veto power 1, so they can veto E. The coalition {1,2,5} has veto power 2, so they can veto {D,E}. The coalition {1,2,3,5} has veto power 3, so they can veto {C,D,E}. The coalition {1,2,3,4,5} has veto power 4, so they can veto {B,C,D,E}. Hence, the only stable outcome is A; the proportional veto core is the singleton {A}.

Example 2. Suppose there are m=6 outcomes and n=5 voters with the following preferences:

• 1: A > B > C > D > E > F
• 2: A > C > D > E > B > F
• 3: A > D > E > B > C > F
• 4: F > E > D > C > B > A
• 5: F > E > D > C > B > A

The proportional veto power function is v(T) = |T|. The coalition {4,5} has veto power 2, so they can veto {A,B}. The majority coalition {1,2,3} agree on A, but do not agree on the following four candidates, so the only candidate they can veto is F. Hence, the outcomes {C,D,E} are all stable; the proportional veto core is not a singleton.

Computing the proportional veto core

Sequential veto implmenetation

Moulin suggested the following voting by veto tokens procedure, for identifying one stable outcome:

• Each candidate is replicated c times, so there are c*m clones overall.
• Each agent is given r "veto tokens".
• The agents are ordered in some order; each agent in turn can use one token to veto one clone.

Thus, every coalition with t voters can veto at most r*t clones, which is equivalent to floor(r*t/c) candidates. Overall, r*n clones out of c*m clones are vetoed, so gcd(m,n) clones remain. In particular, at least one clone remains, and this clone is always in the proportional veto core.

The problem with this algorithm, similarly to the one-outcome-per-voter special case, is that the outcome depends on the ordering of the voters, and thus it is not unique.

Computing the entire core

Ianovski and Kondratev present a polynomial-time algorithm for computing all outcomes in the proportional veto core. Their algorithm is based on blocking graphs. The blocking graph for an outcome x is a bipartite graph with r*n vertices on one side (r vertices per voter) and c*(m-1) vertices on the other side (c vertices for each outcome other than x), and an edge from a voter-clone v to an outcome clone y iff the voter prefers y to x. They proved that an outcome x is blocked iff its blocking graph contains a biclique with t*m vertices. The existence of such a biclique can be decided in polynomial time by an algorithm of Gary and Johnson. Using this algorithm, the proportional veto core can be computed in time O(m * max(n³, m³)).

They also prove that, with the impartial culture assumption, when the number of voters approaches infinity, with probability 1, the proportional veto core consists of the candidates which are ranked last by fewer than n/m voters; the expected size of the core is about m/2.

They then suggest a neutral and anonyomus algorithm for selecting a candidate from the core, called veto by consumption. It is similar to the Simultaneous eating algorithm: at each round, each voter "eats" his least-preferred remaining candidate. A candidate who is totally eaten, is removed. The last eaten candidates are the winners. The winners are always in the proportional voting core. Although the rule still does not guarantee a unique winner, empirical tests on impartial culture profiles show that the number of winners tends to one as the number of voters tends to infinity. Moreover, veto-by-consumption is immune to manipulation by adding "spoiler" candidates (candidates that everyone hates), as these candidates will all be consumed before the real candidates.

They also show that the proportional veto core can be manipulated in polynomial time by a pessimist (a voter who ranks sets of outcomes by their worst element, as in the Duggan–Schwartz theorem). They conjecture that a manipulation by an optimist (a voter who ranks sets of outcomes by their best element) is not possible.

Veto functions of existing rules

Instead of deciding in advance on a veto-power function and then designing a rule to implement it, one can go the other way around: given an existing voting rule, compute the veto-power of each coalition. Formally, given a social choice rule R, the veto power of a coalition T is the largest integer k such that, for each subset B containing at most k outcomes, the members of T can vote in such a way that no member of B is elected.

Examples

1. The veto function of every Condorcet-consistent voting rule is the dichotomous function: v(T)=m-1 if |T|>n/2; v(T)=0 if |T|<n/2.

2. The Borda count voting rule (with any neutral tie-breaking rule) induces the following voting power:

• For every coalition with size t < n/2, the voting power is 0;
• For every coalition with size t in [n/2, 2n/3), the voting power is between ${\displaystyle \lceil 2\left(\frac{2t-n}{t+1}\right)\cdot (m-1)\rceil }$ and ${\displaystyle \lfloor 2\left(\frac{2t-n}{t}\right)\cdot (m-1)\rfloor +1}$ (the exact number depends on tie-breaking).
• For every coalition with size t ≥ 2n/3, the voting power is m-1 (that is, full voting power).

The veto core of this function might be empty, as there might be a cycle of outcomes, each of which is preferred over the next outcome in the cycle by 2n/3 voters.

3. The veto function of Borda-egalitarian rules (rules that pick an outcome that maximizes the smallest Borda score, with a neutral tie-breaking rule) is highly dependent on the tie-breaking use.

Approval ballots

Halpern, Procaccia and Suksompong extended the notion of proportional veto core from ranked ballots to approval ballots. The idea is to give more power to voters that are more "flexible", that is, approve a larger fraction of the voters.

Formally, for any s in (0,1), an s-flexible voter is a voter who approves at least s*m candidates. An (r,s)-flexible coalition is a coalition of at least r*m voters, each of whom is s-flexible.

For a single-winner voting rule, an (r,s)-guarantee is a guarantee that, for any (r,s)-flexible coalition T, at least one voter in T approves the winner. For a rule R, the FVR(R,s) is the smallest r for which the rule has an (r,s)-guarantee. The following guarantees are proved for single-winner rules:

• For (utilitarian) approval voting rule, FVR(R,s) = 1/(1+s) for all s.
• For power-weighted approval voting rule, where the weight of each voter with flexibiilty f is f^p for some power p>0, FVR(R,s) = ${\displaystyle \frac{1}{1+\frac{(s(1+p){)}^{1+p}}{p^p}}}$.
• For threshold approval voting rule, which counts only the votes of s₀-flexible voters for some fixed threshold s₀, FVR(R,s₀) = 1-s₀, but the guarantees to other values of s might be much worse.
• The harmonic-weighted approval voting rule, where the weight of each voter with flexibility f is 1/(1-f), FVR(R,s) = 1-s for every s, and this is the best possible guarantee for every s. Hence, the harmonic-weighted approval voting rule is optimal with respect to the FVR guarantee. The rule guarantees to each group of (1-s)*n voters who are all s-flexible, that at least one voter of the group approves the winner.

For a multi-winner voting rule, an (r,s,t)-guarantee is a guarantee that, in any (r,s)-flexible coalition, at least one member approves at least t winners. The following are proved for multi-winner rules:

• There is a lower bound for FVR(r,s,t,m), but it is much more complex than the lower bound of 1-s for single-winner voting.
• For any fixed k and t, there exists a rule that yields the optimal guarantee simultaneously for all s and m. Similarly to the single-winner case, the rule works by assigning a weight to each voter, and selecting a candidate with the highest total weight. But here the weight changes dynamically as more candidates are selected.
• On the other hand, if k, m and s are fixed, no rule is simultaneously optimal for all t.
• The FVR guarantee is not compatible with justified representation guarantees: for every k>1, there exists some s such that no rule for selecting a committee of size k is both FVR-optimal for (s,1) and satisfies JR.