# Chapter 23. Voting

[TOC]

## 23.1 Voting for Group Decision Making
**Voting** encompasses a broad class of methods for reaching a group decision:
1. to choose a single “winner”
2. to produce a ranked list

It is often used in situations where:
1. divergence in voters' subjective evaluations
- _e.g. film critics_
2. a lack of information
- _e.g. jury who verdicts in criminal trials_

### On-line applications of voting
- **Meta-search engines**
- combining rankings from different Web search engines into a single aggregate ranking
- **Recommendation systems**
- combining the preferences of other users to produce a ranked list of recommendations

## 23.2 Individual Preferences
**Notation**
- If individual $i$ prefers alternative $X$ to alternative $Y$ , then we write $X\succ_iY$
- The symbol $\succ_i$ represents **individual $i$’s preference relation** over the alternatives

**Properties**
We require that **individual preferences** $\succ_i$ satisfy two properties:
1. **Completeness**
- For each pair of distinct alternatives $X$ and $Y$, either $X\succ_iY$, or $Y\succ_iX$, but not both.
2. **Transitivity**
- If $X\succ_iY$ and $Y\succ_iZ$, then $X\succ_iZ$

### Preference Relation and Ranked List
- Definition of ranked list:
- A list produced by each individual that ranks all the alternatives from best to worst
- Another definition of $\succ_i$ :
- If alternative $X$ comes before alternative $Y$ in $i$’s **ranked list**, then $X\succ_iY$
- Observation:
- If a preference relation arises from a ranked list of the alternatives, then it must be complete and transitive, and **_vice versa_**.
- The forward direction is trivial, but to see why the backward direction is true, let's consider the following method
:::info
**Construct a ranked list from a complete and transitive preference relation**
Pseudo code:

    construct_ranked_list(set_of_alternatives):
        ranked_list = empty list
        while(set_of_alternatives is not empty):
            pick X such that X defeats all other alternatives in set_of_alternatives
            ranked_list.append(X)
            set_of_alternatives.remove(X)
        return ranked_list

- Using the above way, each alternative is preferred to all the alternatives that come after it, and so $\succ_i$ arises from this ranked list
:::

## 23.3 Voting Systems: Majority Rule
A **voting system** is any method that takes a collection of individual rankings and produces a group ranking

### Majority rule
Assume that the number of voters is **odd**
- Case of 2 alternatives:
- We take the alternative that is **preferred by a majority of the voters** and rank it first, placing the other alternative second.
- Case of more than 2 alternatives:
- **Step 1:** apply majority rule to each pair of alternatives to create **group preferences**
:::success
**Group preference**
For each pair of alternatives $X$ and $Y$, if the number of individuals for whom $X\succ_iY$ is larger than the number of individuals for whom $Y\succ_iX$, then we say that the group preference $\succ$ satisfies $X\succ Y$
:::
- **Step 2:** turn these group preferences into a group ranking
- One could first select a **group favorite**, remove it from the available alternatives, and then apply the procedure repeatedly to what’s left
- To select a **group favorite**, a general method is holding a **elimination tournament** for all the alternatives
|Example 1|Example 2|
|---|---|
|||

### Pathologies
:::info
**Condorcet Paradox**
_The group preferences may not be transitive, even when each individual’s preferences are transitive._

Let's consider the following example:
- Suppose that we have three individuals named $1$, $2$, and $3$, and three alternatives named $X$, $Y$, and $Z$.
- Individual $1$’s ranking is: $X\succ_1Y\succ_1Z$
- Individual $2$’s ranking is: $Y\succ_2Z\succ_2X$
- Individual $3$’s ranking is: $Z\succ_3X\succ_3Y$
- Using majority-rule to define group preferences, we would have $X\succ Y$, $Y\succ Z$, and $Z\succ X$, which violates transitivity!
:::
By the Condorcet Paradox, we can uncover a pathology in our "elimination tournament" system
- The overall winner is determined entirely by how the votes between pairs are sequenced
- The group favorite is thus determined by the individual who controls the **agenda**

## 23.4 Voting Systems: Positional Voting
### Positional voting
- Each alternative receives a certain **weight** based on its **positions** in all the individual rankings, and the alternatives are then ordered according to their total weight
- A simple example is the **_Borda count_**
:::info
**Borda count**
Assume there are $k$ alternatives, then individual $i$ confers:
- a weight of $k-1$ on her first-ranked alternative
- a weight of $k-2$ on her second-ranked alternative
- ...
- a weight of $1$ on her second-to-last alternative
- a weight of $0$ on her last alternative

|$i$'s ranking|1|2|...|k-1|k|
|---|---|---|---|---|---|
|Assigned weight|k-1|k-2|...|1|0|

The total weight of each alternative is simply the sum of the weights it receives from each of the individuals.

**Example:**
Suppose that we have two individuals $1$ and $2$, and four alternatives $A$, $B$, $C$, and $D$.
- Individual $1$’s ranking is: $A\succ_1B\succ_1C\succ_1D$
- Individual $2$’s ranking is: $B\succ_2C\succ_2A\succ_2D$

Then, total weight of
- $A$ is $3+1=4$
- $B$ is $2+3=5$
- $C$ is $1+2=3$
- $D$ is $0+0=0$

So the group ranking is $B\succ A\succ C\succ D$
:::
- **Key feature of Borda Count**
- It always produces a complete, transitive ranking for a set of alternatives, if ignoring ties

### Pathologies
Consider the following scenario:
- Suppose there are 5 film critics discussing 2 movies $A$ and $B$
- Critics $1$, $2$, and $3$ favor $A$, while critics $4$ and $5$ favor $B$
- No matter Borda count or majority rule is applied, $A$ is reported as the group favorite
- Now, another movie $C$ is introduced
- Critics $1$, $2$, and $3$ report $A\succ_iB\succ_iC$
- Critics $4$ and $5$ report $B\succ_iC\succ_iA$
- The total weights of
- $A$ is $2\cdot3+0\cdot2 = 6$
- $B$ is $1\cdot3+2\cdot2 = 7$
- $C$ is $0\cdot3+1\cdot2 = 2$
- The group favorite becomes $B$

From the example, what we find is that the outcome in the Borda Count can depend on the presence of “irrelevant” alternatives (such as $C$ above).
:::danger
**Further pathologies — _strategic misreporting of preferences_**
Consider the movie example again:
- If critics $4$ and $5$ report $B\succ_iA\succ_iC$, then the group favorite is still $A$.
- However, by reporting $B\succ_iC\succ_iA$, critics $4$ and $5$ make their favorite $B$ become the group favorite successfully
---
Similar pathologies can be seen from U.S. Presidential elections
:::

## 23.5 Arrow’s Impossibility Theorem
> _Is there any voting system that avoids all of the pathologies we’ve seen thus far?_

- First we need to specify what it means for a voting system to be **free of pathologies**
:::info
A reasonable voting system should satisfy two properties:
1. **Unanimity**
- If there is any pair of alternatives $X$ and $Y$ for which $X\succ_iY$ in the rankings of every individual $i$, then the group ranking should also have $X\succ Y$
2. **Independence of Irrelevant Alternatives (IIA)**
- The group ranking of $X$ and $Y$ should depend only on voter preferences between $X$ and $Y$, not on how they evaluate any other alternative $Z$
:::
- Neither the positional voting nor the majority voting satisfies both properties
- However, voting systems based on **dictatorship** can be shown to satisfy the two properties
:::success
**Dictatorship**
We pick one of the individuals $i$ to be the **dictator**, then we simply declare the group ranking to be equal to the ranking provided by that dictator
1. **Unanimity**
- If everyone prefers $X$ to $Y$, then the dictator does, and hence the group ranking does
2. **IIA**
- The group ranking of $X$ and $Y$ depends only how the dictator ranks $X$ and $Y$, and does not depend on how any other alternative $Z$ is ranked
:::
:::info
**Arrow’s Impossibility Theorem**
_If there are at least three alternatives, then there is no voting system that satisfies **unanimity**, **IIA**, and **non-dictatorship**._
:::

## 23.6 Single-Peaked Preferences and the Median Voter Theorem
### Single-peaked preferences
- Assume that the $k$ alternatives are ordered by their **numerical quantities** (e.g. amounts of budget) and named $X_1, X_2, \dots, X_k$
- We say that a voter $i$ has **single-peaked preferences** if there is no alternative $X_s$ such that $X_{s−1}\succ_iX_s$ and $X_{s+1}\succ_iX_s$.
- In other words, each voter $i$ has a top-ranked option $X_t$:
$$
X_t \succ_i X_{t+1} \succ_i X_{t+2} \succ_i \cdots
$$
and
$$
X_t \succ_i X_{t-1} \succ_i X_{t-2} \succ_i \cdots
$$

Recall that when using **majority rule** to produce a group preference, we may suffer from the **Condorcet Paradox**. But with single-peaked preferences, our original plan works perfectly.
:::info
**Claim**
If all individual rankings are single-peaked, then majority rule applied to all pairs of alternatives produces a group preference relation $\succ$ that is complete and transitive.
:::

### The Median Individual Favorite
Here we introduce another method for finding a group favorite
- **Step 1:** Consider the top-ranked alternative for each voter, and sort this set of individual favorites from left to right, along our linear order
- **Step 2:** Pick the individual favorite that forms the **median** of this list. It is a natural idea to consider it as a **potential group favorite**
- For example, if the individual favorites were $X_1, X_1, X_2, X_2, X_3, X_4, X_5$, then the median individual favorite $X_2$ would be a potential group favorite
:::info
**The Median Voter Theorem**
_With single-peaked rankings, the median individual favorite defeats every other alternative in a pairwise majority vote_

---
To see why this is true, let $X_m$ be the median individual favorite, and let $X_t$ be any other alternative
- Suppose $X_t$ lies to the right of $X_m$, that is, $t>m$
(The case $t<m$ has a symmetric argument)
- Assume the number of voters $k$ is odd, so everyone in the first $(k+1)/2$ positions prefers $X_m$ to $X_t$
**Example:** for $k=5$, first $3$ voters prefer $X_m$ to $X_t$
|voter 1: $X_m\succ_1X_t$|voter 2: $X_m\succ_2X_t$|voter 3: $X_m\succ_3X_t$|
|---|---|---|
||||
- The first $(k+1)/2$ is the majority, so $X_m$ defeats $X_t$ in a pairwise majority vote
:::
:::success
**Conclusion**
With the median voter theorem, the way we pick the group favorite assures the completeness and transitivity of the group preference, so the above claim makes sense.
:::

## 23.7 Voting as a Form of Information Aggregation
In some cases, there is a true best ranking of the alternatives, and the purpose of the voting system is to discover it by gathering information from the individuals
- e.g. jury deliberations

### Simultaneous and sincere voting
- There are two alternatives $X$ and $Y$; one of these two is genuinely the best choice, but voters possess different, uncertain information
- Suppose that there is a **prior probability** of $X$ being the best choice, and that this is known to all voters
- For simplicity, let the prior probability to be $\frac{1}{2}$, i.e., $Pr[X\text{ is best}] = Pr[Y\text{ is best}] = \frac{1}{2}$
- Each voter receives an independent, private **signal** about which of $X$ or $Y$ is better
- Let $q>\frac{1}{2}$
- $Pr[X\text{-signal is observed }|\ X\text{ is best}] = q$
- $Pr[Y\text{-signal is observed }|\ X\text{ is best}] = 1-q$
- $Pr[Y\text{-signal is observed }|\ Y\text{ is best}] = q$
- $Pr[X\text{-signal is observed }|\ Y\text{ is best}] = 1-q$
- When a voter observes a signal favoring $X$, she first evaluates the **posterior probability**, $Pr[X\text{ is best }|\ X\text{-signal is observed}]$, then she decides to vote for $X$ if $Pr[X\text{ is best }|\ X\text{-signal is observed}] > \frac{1}{2}$; otherwise, vote for $Y$
- By **Bayes' Rule**, we have
$$
Pr[X\text{ is best }|\ X\text{-signal is observed}] = \frac{Pr[X\text{ is best}]\cdot Pr[X\text{-signal is observed }|\ X\text{ is best}]}{Pr[X\text{-signal is observed}]}
$$
where
$$
\begin{aligned}
Pr[X\text{-signal is observed}] = & Pr[X\text{ is best}]\cdot Pr[X\text{-signal is observed }|\ X\text{ is best}] + \\
& Pr[Y\text{ is best}]\cdot Pr[X\text{-signal is observed }|\ Y\text{ is best}] \\
= & \frac{1}{2}\cdot q + \frac{1}{2}\cdot (1-q) = \frac{1}{2}
\end{aligned}
$$
so
$$
Pr[X\text{ is best }|\ X\text{-signal is observed}] = \frac{\frac{1}{2}\cdot q}{\frac{1}{2}} = q
$$

- **Conclusion:** Since $q>\frac{1}{2}$, the voter will favor the alternative that is reinforced by the signal she receives

## 23.8 Insincere Voting for Information Aggregation
### An experiment that encourages insincere voting
- An urn with 10 marbles is placed in a room
- 50% chance that it contains 10 white marbles (described as **"pure"**)
- 50% chance that it contains 9 green and 1 white (described as **"mixed"**)
- A group of three people is asked to collectively guess which kind of urn it is. Rules are the following:
1. Each person is allowed to draw one marble and look at it without showing it to the other two, and then replace it back
2. The three people cast simultaneous votes, without communicating
3. If a majority of the votes are for the correct type of urn, then all three people win a monetary prize; otherwise, all three people get nothing

:::info
**Analysis**
Suppose you are one of the three people
- If you draw a **white** marble, then by Bayes' Rule, the urn is more likely to be **"pure"**
- If you draw a **green** marble, then you know for certain that the urn is **"mixed"**

Now consider a possible situation:
- The other two vote sincerely, but one vote for pure and one vote for mixed, so your vote will affect the outcome

In the above situation, even if you drew a white marble, you should vote for **mixed** to maximize the chance of winning, because one of your partner drew a green marble
:::

- **Conclusion:** If you know your two partners will be voting sincerely, you can best help the group by **always voting “mixed”**

## 23.9 Jury Decisions and the Unanimity Rule

### Vote the Signal

- $k$ junors
- conviction/acquittal
- convicted only when all junors choose conviction
- choose conviction only when the defendant is *very

$$
\mbox{Pr}[\textit{defendant is guilty}\mid\textit{all available information}]>z>\frac{1}{2}
$$

- private signal
- G-signal
- I-signal
- assume the signal is credible

$$
\mbox{Pr}[G\mid\textit{guilty}]=\mbox{Pr}[I\mid\textit{innocent}]=q>\frac{1}{2}
$$

$$
\mbox{Pr}[guilty]=\mbox{Pr}[innocent]=\frac{1}{2}
$$

- assume everyone believes in their signal
- for one get signal $I$, one's vote is *critical* if he is the only one choose acquittal and all others choose conviction

$$
\begin{split}
&\mbox{Pr}[\textit{the only }I]\\
=&\mbox{Pr}[\textit{guilty}]\mbox{Pr}[\textit{the only }I\mid\textit{guilty}]+\mbox{Pr}[innocent]\mbox{Pr}[\textit{the only }I\mid\textit{innocent}]\\
=&\frac{1}{2}q^{k-1}(1-q)+\frac{1}{2}(1-q)^{k-1}
\end{split}
$$

Thus

$$
\mbox{Pr}[guilty\mid \textit{the only }I]=\frac{\mbox{Pr}[guilty\,\wedge\,the\ only\,I]}{\mbox{Pr}[the\ only\ I]}=\frac{\frac{1}{2}q^{k-1}(1-q)}{\frac{1}{2}q^{k-1}(1-q)+\frac{1}{2}(1-q)^{k-1}q}=\frac{q^{k-2}}{q^{k-2}+(1-q)^{k-2}}
$$

which converges to $1$ as $k\to\infty$ since $q>\frac{1}{2}$. And thus there exists a large enough $k$ such that

$$
\mbox{Pr}[guilty\wedge acquitted\wedge this\,I\,matters\mid I]=\mbox{Pr}[guilty\mid \textit{the only }I]>z
$$

so vote the signal is not an equilibrium.

### Some Facts
- vote acquittal regardless of the signal is an equilibrium
- there is a unique equilibrium that
- all junors use the same strategy
- the strategy depends on the signal
- implies the Condorcet Jury Theorem
- *f-majority rule*
- convicted if fraction of $f$ of junors choose conviction

## 23.10 Sequential Voting and the Relation to Information Cascades
- voters choose sequentially
- choose $X$ if

$$
\mbox{Pr}[X\mid\textit{all available information}]>\frac{1}{2}
$$

- totally the same as Section 16.5
- increase the number of voters does not stop the cascade

## 23.11 Advanced Material: A Proof of Arrow’s Impossibility Theorem

:::success
**Definition.**
Let $1,2,\ldots,k$ be voters, $A$ be finite set of alternatives.
- a *ranking* $\succ$ is a total order on $A$
- a *profile* is a collection of each ranking of voters $\{\succ_i\mid 1\leq i\leq k\}$.
- a *vote system* is a function $F$ from profile to ranking.
- the output of vote system is called *group ranking*
:::

:::success
**Definition.**
Let
- $1,2,\ldots,k$ be voters
- $A$ be the set of alternatives
- $\mathcal{P}$ be the set of all profiles
- $F$ be a vote system
- for $p\in\mathcal{P}$
- $\succ_i^p$ be the ranking of $i$ in profile $p$
- given $F$, $\succ^p$ be the group ranking of $F$ on $p$

then we define

- $F$ satisfies *unanimity* if for all $p\in\mathcal{P}$, $X,Y\in A$, $$(\forall\,i, X\succ_i^p Y)\Rightarrow X\succ^p Y$$
- $F$ satisfies *independence of irrelevant alternatives(IIA)* if for all $p,q\in\mathcal{P}$, $X,Y\in A$ $$(\forall\,i,X\succ_i^pY\Leftrightarrow X\succ_i^qY)\Rightarrow(X\succ^pY\Leftrightarrow X\succ^qY)$$
- $F$ satisfies *dictatorship* if there exists $j$ such that $$\forall\,p\in\mathcal{P},\succ_j^p\,=\,\succ^p$$
- $F$ satisfies *non-dictatorship* if $F$ is not dictatorship
:::

:::info
**Lemma.**
Let $F$ satisfy unanimity and IIA, and for $p\in\mathcal P$ with $X$ be the first or the last in all $\succ_i^p$, then $X$ is either first or the last in $\succ^p$

**Proof.**
Assume $X$ is neither the first nor the last, then $\exists\,Y,Z\in A$ such that $$Y\succ^pX\succ^pZ$$
then for all $i$ that $Y\succ_i^pZ$ in $p$, swap $Y$ and $Z$ to get profile $q$, then

- by IIA, $Y\succ^qX$ and $X\succ^qZ$
- by unanimity, $Z\succ^qY$

which gets contradiction.
:::

:::info
**Theorem.**
If $|A|\geq 3$, then there is no $F$ satisfying all
- Unanimity
- IIA
- non-dictatorship

**Proof.**
Let $p_0\in\mathcal{P}$ be arbitrary profile satisfying that $X\in A$ is the last in all $\succ_i^{p_0}$, we construct $p_1,p_2,\ldots,p_k$ where $p_i$ is $p_0$ but $X$ is moved to the first for rankings of $1,2,\ldots,i$. Then

- by unanimity, $X$ is the last in $\succ^{p_0}$
- by unanimity, $X$ is the first in $\succ^{p_k}$
- by lemma, $X$ is either the first or the last in $\succ^{p_i}$, $i=1,2,\ldots,k-1$

thus there is a minimum $j$ such that $X$ is the first in $\succ^{p_j}$. Now fix $q\in\mathcal P$, for any $Y\succ_j^q Z\in A$, and $Y\neq X\neq Z$. Now let $r$ be $q$ but moving $X$ to the first for rankings of $1,2,\ldots,j-1$, moving $X$ to the last for rankings of $j+1,j+2,\ldots,k$, and moving $Y$ to the first, $X$ to the second for ranking of $j$, then

- $r$ and $p_j$ are the same when restricted to $X$ and $Z$, by IIA, $X\succ^rZ$
- $r$ and $p_{j-1}$ are the same when restricted to $Y$ and $X$, by IIA, $Y\succ^rX$
- by transitivity, $Y\succ^rZ$
- $r$ and $q$ are the same when restricted to $Y$ and $Z$, by IIA, $Y\succ^qZ$

We say $j$ is a dictator not involving $X$. Now pick $Y$ with the same process, we will have another $l$ to be a dictator not involving $Y$., then

- since $Z\succ^{p_{j-1}}X$, we have $Z\succ_l^{p_{j-1}}X$
- since $X\succ^{p_j}Z$, we have $X\succ_l^{p_j}Z$

Thus $l=j$, and hence $j$ is a dictator.
:::