In social choice theory, veto voting is a method of voting by which individual voters, or coalitions of voters, can veto a certain number of outcomes that they dislike. The veto power of a coalition is the number of candidates it can veto. The veto core is the set of outcomes that are not vetoed. The idea was introduced by Dennis C. Mueller in 1978,^[1] and refined by Herve Moulin^[2][3] and several later authors.^{[4][5][6][7][8]}

Suppose a group of voters has to choose one out of several possible outcomes (also called: candidates). Each voter has a total order over the candidates. Two considerations in selecting the winning outcome is respecting the will of the majority, and protecting the minorities. These considerations might be contradictory.

For example,^[9] suppose 100 voters have to choose one out of three outcomes. 60 voters prefere A to B to C; 40 voters prefer B to C to A. The majority principle would select A, who is supported by a strict majority of voters (this outcome is also the Condorcet winner). But the minority principle says that A should not be elected, as he is opposed by 40% of the voters, whereas B is a reasonable compromise for all voters. The minority principle makes sense in settings such as selecting a time for a meeting: it is better to select a time that is reasonable (if not perfect) for all voters, than to select a time that is optimal for 60% and impossible for 40%.

Veto voting is a voting method that implements the minority principle by letting individuals and groups of voters a predefined amount of veto power, by which they can eliminate outcomes that they strongly oppose.

Mueller^[1] 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.

Moulin^[2] 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|.

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^[10] 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.

Moulin^[2] 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}\{\backslash displaystyle\; \backslash left\backslash lceil\; \{\backslash frac\; \{mt\}\{n\}\}\backslash right\backslash 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 }\{\backslash displaystyle\; \backslash left\backslash lfloor\; \{\backslash frac\; \{r\backslash cdot\; t\}\{c\}\}\backslash right\backslash 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.^[2]: Thm.1 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.

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,^[3] 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.

Halpern, Procaccia and Suksompong^[11] 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:^{[11]: Sec.2}

• 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}}}\{\backslash displaystyle\; \{\backslash frac\; \{1\}\{1+\{\backslash 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:^{[11]: Sec.3}

• 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.

• Sequential elimination method