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, and refined by Herve Moulin and several later authors.
Setting 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, 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.
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.
… excerpt ends here. Continue reading the full article.
