Chapter 11 Voting: Basic Notions

In this chapter, we consider the question of designing mechanisms for voting (i.e., electing a candidate). In the context of social networks, this is useful, for example, for electing a leader/representative for a set of users. In subsequent chapters, we will additionally apply many of the ideas developed in the context of voting to various types of matching markets and web search.

To phrase the task of voting as a mechanism design problem, we first need to define the mechanism design context.

11.1 Social-choice Contexts

Consider a mechanism design context $(n, Ω, T, v)$ where:

the outcome space $Ω$ is a set of candidates from which we wish to elect a single winner;
for each player $i$ , the type space $T_{i}$ for $i$ is a set of preferences over the candidates $Ω$ ; formally, a preference ordering $μ \in T_{i}$ is a ranking (i.e., an ordering) $μ = (x_{1}, \dots, x_{| X |})$ of the elements in $Ω$ ; to simplify notation, we let $x >_{μ} x^{'}$ denote that $x$ is higher ranked than $x^{'}$ according to $μ$ (and define $<_{μ}$ analogously);
for every player $i$ , $μ \in T_{i}$ , $v_{i} (μ, x) \geq v_{i} (μ, x^{'})$ if $x >_{μ} x^{'}$ .

We refer to such a context as a social-choice context; if it always holds that $v_{i} (μ, x) > v_{i} (μ, x^{'})$ (i.e., we have strict inequality) when $x$ is higher ranked than $x^{'}$ according to $t$ , we refer to the context as a social-choice context with strict preferences. Furthermore, if for each player $i$ , $T_{i}$ is the full set of preferences over the candidates $Ω$ (i.e., all orderings are possible), we refer to the context as a complete social-choice context.

For concreteness, consider a simple (complete) social-choice context with two players (voters) (i.e., $n = 2$ ), two candidates, $Ω = {A, B}$ , voter 1’s preferences are $(A, B)$ (i.e., he prefers $A$ to $B$ ), whereas voter 2’s preferences are $(B, A)$ , and for both players $i \in [2]$ , $v_{i} (t, x) = 10$ if $x$ is the highest ranked outcome according to $t$ and 0 otherwise.

As we saw in chapter 10, we can use the VCG mechanism to DST-implement social value maximization for any context, and thus, in particular for any social-choice context—such a mechanism ensures the selection of the candidate that maximizes social value assuming players act rationally (we revisit the VCG mechanism in the context of voting in Section 12.4).

But, recall that the VCG mechanism requires using payments. Typically, when considering voting rules (e.g., presidential elections), it is desirable to have a scheme without any payments (as the use of payments may, for example, unfairly prioritize the votes of people with more money to spend).¹ Consequently, we here explore mechanisms for selecting “desirable outcomes” without payments.

11.2 Voting Rules and Strategy-proofness

We refer to a mechanism $𝒱$ without payments (i.e., one that will always outputs prices $\vec{p} = \vec{0}$ ) as a payment-free mechanism. A voting rule $𝒱$ is simply a payment-free mechanism for a social-choice context.

To simplify notation, when discussing payment-free mechanism $𝒱$ , we simply ignore the payment part of the output of $𝒱$ and simply write $𝒱 (\vec{μ}) = x$ to mean that $𝒱$ selected the outcome $x$ .

We will be interested in voting rules that incentivize players to truthfully report their preferences over candidates:

Definition 11.1. We say that a voting rule $𝒱$ is strategy-proof if $𝒱$ is DST.

That is, if $𝒱$ is strategy-proof there does not exist some “situation” (formally, a profile of preferences for all the players) such that some rational player will want to vote “strategically,” lying about their preferences to influence the outcome—hence the name “strategy-proofness.”

11.3 Condorcet Voting

As we shall see later on, even in very simple social-choice contexts, we cannot hope to reproduce the success of the VCG mechanism without using payments: there are no voting rules that DST-implement social value maximization (see Theorem 12.1). But even in situations where we can, it is not clear that this is actually a reasonable desideratum in the context of voting: any social value maximizing mechanism must put a bigger weight on voters who are more strongly affected by the outcome of the election—for instance, if the utility function represents financial gains, the vote of a billionaire (who risks to lose a lot if, for instance, the tax code is changed) needs to count significantly more than the voters with more modest income/assets.

A natural desideratum—which is referred to as the Condorcet criterion—would instead be to elect a candidate that a majority of the voters prefer to all others:

Definition 11.2. Given a set of voter preferences $μ_{1}, \dots, μ_{n}$ over a set of candidates $Ω = {x_{1}, \dots, x_{m}}$ , we say that a candidate $x \in Ω$ is a Condorcet winner if for every other $x^{'} \in Ω$ at least $n / 2$ voters prefer $x$ to $x^{'}$ (according to the preferences $\vec{μ}$ ).

When there are only two choices, the most obvious voting rule works:

Theorem 11.1. For every social-choice context $Γ$ over two candidates, there exists a voting rule $𝒱$ that is strategy-proof for $Γ$ ; furthermore, $𝒱$ will always output a Condorcet winner.

Proof. Let $𝒱$ be the majority voting rule: simply pick the candidate that the majority of voters rank first, and break ties in some arbitrary way (e.g., lexicographically).² By definition, the candidate $x$ elected by $𝒱$ is preferred to the other candidate by at least $n / 2$ of the voters, and is thus a Condorcet winner.

Furthermore, no matter how other voters vote, a voter $i$ can never improve their utility by not reporting their favorite candidate; the only time when voter $i$ ’s vote would matter is in the event that there is a draw between the two candidates (or when $i$ ’s vote would produce a draw instead of a loss for their candidate), and in these cases, $i$ would never prefer voting for the other candidate to their own.

■

So, we have an excellent algorithm for $n$ voters and two candidates. However, there are often more than two candidates. The obvious extension would be a generalized version of the majority voting rule, called the plurality voting rule, where we consider only voters’ top choices and select whichever candidate receives the most “top-choice votes” (this is, for instance, how American elections typically work at the state level), and as before, we break ties in some arbitrary but fixed way. If we have two candidates, then the plurality voting rule is equivalent to the majority voting rule.

11.4 The Problem with Nonbinary Elections

So, with more than two candidates, does plurality output a Condorcet winner? Is it strategy-proof? Perhaps surprisingly, neither of these are true. As we first observe, with three or more candidates, no voting rule can always elect a Condorcet winner!

Theorem 11.2. Consider some complete social-choice context $Γ = (n, Ω, T, v)$ with strict preferences where $n$ is a multiple of 3 and $| Ω | \geq 3$ . There is no voting rule $𝒱$ for $Γ$ that always outputs a Condorcet winner.

Proof. Consider a complete social-choice context with $3$ voters and 3 candidates $A, B, C$ and consider a situation where voters’ preferences are described as follows:

$A > B > C$
$B > C > A$
$C > A > B$

So $2 / 3$ of the voters prefer $A$ to $B$ , $2 / 3$ of the voters prefer $B$ to $C$ , and $2 / 3$ of the voters prefer $C$ to $A$ . That is, for every candidate $x$ , there exists some candidate $x^{'}$ such that a majority of the voters (more precisely, $2 / 3$ of the voters) prefer $x^{'}$ to $x$ . Thus, there does not exist a Condorcet winner (i.e., a candidate $x$ that is preferred to every other candidate by half the voters), so no mechanism $𝒱$ can output one. The same proof obviously works even if the number of voters $n$ is a multiple of 3 or if we add (dummy) candidates.

■

We turn to considering strategy-proofness:

Claim 11.1. The plurality voting rule is not strategy-proof for any complete social-choice context $Γ = (n, Ω, T, v)$ with strict preferences where $n \geq 3$ is an odd integer³ and $| Ω | \geq 3$ .

Proof. Consider a social-choice context with $n = 2 k + 1$ voters and 3 candidates $A, B, C$ ; if the candidate space is larger, we simply ignore the other candidates. Consider a situation where voters’ preferences are described as follows:

$k$ voters prefer $A > B > C$ ;
$k$ voters prefer $B > A > C$ ;
and the final voter prefers $C > B > A$ .

If everyone votes truthfully, either $A$ or $B$ will be selected depending on how tie-break is implemented. Let’s first assume that $A$ is selected. If so, the “final voter” who prefers $C$ should clearly “lie” and cast, for instance, $B > A > C$ as his vote—this ensures that $B$ wins, which is a better outcome for him (according to his real preferences). If instead ties are broken so that $B$ wins, the player who prefers $C$ would instead prefer to lie if his preferences had been $C > A > B$ .

■

Note that plurality only consider players’ top choices; we may also consider an even more generalized version of majority voting called a scoring-based voting rule: such a voting rule is specified by “scores/weights” $w_{j}$ for each rank position $j$ such that $w_{1} \geq w_{2} \geq \dots$ ; the final score of a candidate is defined to be the sum of the “weights” it receives from the voters, and the candidate with the highest score is declared the winner. For instance, if $w_{1} = 10$ , $w_{2} = 5$ , and $w_{j} = 0$ where $j > 2$ , a candidate’s score is $10$ times the number of voters that rank him first, plus $5$ times the number of voters that place him second. Note that plurality is a special case of a scoring-based voting rule where $w_{1} = 1$ and $w_{j} = 0$ if $j > 1$ .

Can some scoring-based voting rule be strategy-proof? The answer again is no. In fact, the Gibbard-Satterthwaite theorem shows that if we restrict to voting rules that are onto (i.e., all candidates can win), then the only strategy-proof voting rule over three or more candidates is dictatorship! We will explore this result in the next chapter.

Notes

The area of social-choice theory was initiated in the papers by Condorcet [dC94] and Arrow [Arr50]. Condorcet also introduced the desideratum, which today is called the “Condorcet criterion,” and presented the impossibility result for Condorcet voting.

¹As a side remark, it can be argued that systems like the American election system do not fully satisfy this no-payment condition, as donations to parties or candidates may be viewed as a way to use money to influence the voters’ preferences and as a consequence also the outcome of the election; in our treatment, we ignore these effects—our formal model assumes that the type $t_{i}$ of a player $i$ , which determines $i$ ’s preferences among candidates, is fixed and cannot be influenced by others.

²Note that if exactly $n / 2$ voters prefer each candidate, then both are Condorcet winners.

³The restriction on $n$ is there only to simplify the proof; the claim is true assuming just that $n \geq 2$ . We shall later see a much more powerful result (Theorem 12.1), which implies this claim as a special case, thus we here content ourselves with the weaker statement.