https://sites.google.com/view/optdemocracy24

class held by Ariel Procaccia

## Voting rules

there is a rather subtle rule called constant function. Where what ever the voters cas their beliefs, the result is predefined.

### Plurality

why is it bad?

### Ballot Types

#### Ranking

most common

#### Approvals

#### Score/stars

will not be covered

### Borda Count

### Single Transferable Vote

STV is not monotonic. In cases any voter push an alternative to a higher position, this does not gaurantee that this will help that alternative.

### Condorcet Paradox

- impartial culture model

cyclical preferences

even though individual preferences is acyclic, the social choice can be cyclic.

property -> **Condorcet consistence**

#### dividuals and condorcet paradox

if we let dividuals, we can say it is can happen inside one person.

#### Llull’s rule

Each alternative receives one point for each head-to-head comparison it wins. : Condorset consistent

#### Dodgson Rule

Dodgson score of an alternative x is the minimum swaps to make x a condorcet winner. NP-hard

## Axiomatic Approach

### Voting model

Voters: \(N = {1, \dots, n} (n > 1)\)

Alternatives: \(|A| = m\)

Ranking: \(i \in N, \sigma_i \in \mathcal{L}\) over the alternatives; \(x \succ_{\sigma_i } y\) means voter i prefers x to y.

Preference Profile: \(\sigma \in \mathcal{L}^n\) a collection of voters rankings.

Social choice function: \(f: \mathcal{L}^n \leftarrow A\)

Social welfare function: \(f: \mathcal{L}^n \leftarrow \mathcal{L}\)

when \(n=2\) SCF is SWF, and plurarity is the only sensible method.

### Axioms satisfied by Majority

**Anonymity** if you swap the voters, this will not change the outcome.
**Neutrality** if you swap the alternatives, the final output should also follow that swap.
**Monotonic** if you push the position of an alterative, that should not hurt that alternatives overall position.

### May’s theorem

if \(m=2\) and \(n\%2==1\), then \(f:\mathcal{L} \leftarrow A\) is anonymous, neutral, and monotonic only if it is majority rule. if the there are 2 options (\(m=2\)) and odd number of voters (\(n mod 2 = 0\)), and the SCF satisfies Anoymity and Neutrality and Monotonicty, Majority is the only way.

proof:

make an contradicting case like the example profile(\(\sigma\)) below:

a | b | c | d | e |

x | y | x | x | y |

\(m=2\) and \(n=5\), results in \(y\) winning.

\[f(\sigma) = y\]

use neuturality swap all options (\(\sigma^{\prime}\)) and also the results

a b c d e y x y y x \[f(\sigma^{\prime}) = x\] or (\(\neg y\))

use monotonicty

so we push \(x\) for (5/2 - 2) \(n/2-t\) where \(t\) is the number of votes directed to \(x\) or \(\neg y\). This profile will be \(\sigma^{\prime\prime}\), and because of monotonicty, pushing up \(x\) will not hurt the fact that this social choice function will chose \(x\)

\[f(\sigma^{\prime\prime}) = x\] or (\(\neg y\))

a b c d e x x y y x we pushed \(a\)’s \(y\) to \(x\).

use anonymity to swap voters.

a b c d e x y x x y this profile is the same as the first one. (\(\sigma^{\prime\prime\prime} = \sigma\)), but anonymity says it should not change the outcome.

\[f(\sigma^{\prime\prime\prime}) = x\] or (\(\neg y\))

\[f(\sigma) = y\]

hence this contradicts.

similar in when the number of voters are even. May’s Theorm says that if there is only two options, majority is the case.

### Arrow’s Axioms

given \(m > 2\)

#### Unanimity

if all voters rank \(x \succeq y\) the SCF should also render \(x \succeq y\).

#### Independence of irrelevant altenatives

if you isolate into two options, the sum of the preference should be the same as the final result.

Borda count relies on the fact of other voters….intensity of votes do count.

#### Nondictatorship

no single voter can flip the result.

#### Proof

assuming Unanimty and IIA, but will contradict with Nondictatorship.

- (Step 1) Setting

let \(b \in A\) where \(A\) is a set of options. so, some option \(b\). and we have \(i \in N\) which is the set of voters. every voter puts \(b\) in the top or the bottom.

Then the setting is that \(f(b)\) should be top or bottom, but not in the middle.

1 2 3 4 5 6 a c b b a a c a c a c c b b a c b b - suppose not that b is not at the bottom or the top of \(f(\sigma)\)

This \(b\) is in top or bottom of each \(\sigma_i\), but there is a condition that satesfies the following:

\[ a \succ_{f(\sigma)} b \succ_{f(\sigma)} c \]

1 2 3 4 5 6 a c b b a b c a c a c a b b a c b c - IIA and Unanimity contradicting

swap \(c\) enough that it will change the ordering relative to \(a\), so that this new \(\sigma^{\prime}\) will have \(c \succ a\) but, not to the extent that it is \(b \succ c\). By axiom IIA, this will show that

1 2 3 4 5 6 *c c b b *c b *a a c *c *a *c b b a *a b *a \(a \succ_{f(\sigma^{\prime})} b\) and \(b \succ_{f(\sigma^{\prime})} c\) holds, but it contradicts to Unanimity where \(c \succ_{f(\sigma^{\prime})} a\)

- suppose not that b is not at the bottom or the top of \(f(\sigma)\)
- (Step 2) suppose there exists an profile \(\sigma^{i*}\) that voter \(i^*\) can move a bottom \(b\) to the top.

To denote this, define profiles \(\sigma^0, \sigma^1, ..., \sigma^n\) and \(\sigma^i\) means that \(i\) pushed \(b\) to the top (from the bottom) which all the voters before her did so, meaning \(\sigma^{i-1}\). From Unanimity, \(f(\sigma_0)\) will have \(b\) in the bottom, and \(f(\sigma_n)\) will have \(b\) in the top. From our Setting, somewhere in the middle, we will have a profile that \(f(\sigma^{i*})\) that will bring \(b\) to the top from the bottom.

\(i*\) is powerfull (or the unfortunate) that he flips changes the whole situation.

- (Step 3) \(i*\) is a dictator on any pair that doesn’t involve \(b\).

This means that if \(i*\) picks, \(a \succ c\) the social order will follow it (and vice versa).

We modify \(\sigma^{i*}\) to \(\pi\), which has the following constraints:

- where voter \(i*\) prefers: \(a \succ_{\pi_{i*}} b \succ_{\pi_{i*}} c\)
- let the other voters rank \({a,c}\) arbitrarily, but keeping their \(b\) intact.

By IIA, \(\pi\) holds these two conditions:

The social order of \({a, b}\) in isolation is the same between \(\sigma^{i-1}\) and \(\pi\). \(=a \succ b\)

\(b\)’s relation to \(a\) except \(i*\) is the same and \(i*\) has \(b\) remained in the bottom in \(\sigma^{i-1}\).

The social order of \({b, c}\) is the same between \(\sigma^i\) and \(\pi\). \(=b \succ c\)

\(b\)’s relation to \(a\) except \(i*\) is the same and \(i*\) has now put \(b\) in the top at \(\sigma^i\).

The two IIA conditions above through transivity implies that \(a \succ_{f(\pi)} c\). And because in \(\pi\) we let everyone except \(i*\) rerank any two pairs except ones that contain \(b\), we can say that again from IIA, if \(a \succ_{f(\pi)} c\), then the sum of isolated \({a,c}\) outcomes should

**all**align. Yet in step2, or the way we construct, \(\pi\), we let every voter except \(b\) to arbitrarily rank \({a, c}\), so the only information required is that \(i*\) needs to \(a \succ c\), which \(i*\) dictates narrowly the outcome that doesn’t incorporate \(b\). \(={a, c}\)so \(i*\) is a dictor of all social orders except for \(b\).

- (Step 4) i* is a dictator

- we can do the same operation to determine \(i**\) where, he/she is the dictator on any pair except for \(c\). \(={a,b}\).
- but we know int the previous profile \(\pi\), that when \(i*\) moved \(b\) from the bottom to the top, it changed the orderingin of \({a,b}\).

This only is sound if \(i*\) and \(i**\) is the same voter, because the \(i**\) should be the only one that changes \({a,b}\) where \(i*\) also changed the social ordering of that pair.

## Strategic Manupilation

### Example: Borda count

by lying about a ranking, you can manupilate the result.

### Strategy Proofness

\[ \forall \sigma \in \mathcal{L}^n, \\ \forall i \in N, \\ \forall \sigma_i' \in \mathcal{L}, \\ f(\sigma) \succeq_{\sigma_i} f(\sigma_i', \sigma_{-i}) \]

\(\sigma_{-i}\) means a profile without \(i\)’s preference.

in english: for all preference, for all voter, for all of the the individual preference, \(f\) is more prefereable to \(\sigma\) than to change it in any way.

### Gibbard Satterthwaite Theorem

- SCF \(f\) is Strategy Proof and on to A (any alternative can be selected)
^{1}\(iff\) \(f\) is dictorial. - if it is onto and not dictorial, \(f\) is \(\not SP\).

very sad :( . One very restricted way to avoid. ^{2}

#### Proof (for special case of G-S)

**Lemma**

**Strong monotonicity**, between \(\sigma\) and \(\sigma'\), \(a\) is pushed upwards, but the other alternative can be re-ordered in any way. This should still help \(a\). The normal monotonisty did not have the later condition that it does not touch the other alternatives.if \(f\) is SP, with profile \(\sigma\), if \(f(\sigma) = a\), then \(f(\sigma') = a\) (also \(a\) is preferred.) for all profiles \(\sigma'\) such that \(\forall x \in A, i\in N: [a \succ_{\sigma_i} x \Rightarrow a \succ_{\sigma'_i} x]\)

**Unanimity**, but in the context of SCF. \([\forall i \in N, a \succ_\sigma_i b] \Rightarrow f(\sigma) \neq b\)

**Assumuptions** (to make the proof simpler, loose generality)

- \(m \geq n\) (we have more alternatives than voters)
**neutrality**, \(f(\pi(\sigma)) = \pi(\f(\sigma)) for all \pi:A \rightarrow A\): If we preform permutations to a profile, the result will act accrodingly. (permutations: swap or rename \(a\) to \(b\))

**Special case**

- \(n = 4, A = {a,b,c,d,e}\)
- \(\sigma\) is this. except \(e\), we have a cyclical preference throug 1 - 4.

1 | 2 | 3 | 4 |

a | b | c | d |

b | c | d | a |

c | d | a | b |

d | a | b | c |

e | e | e | e |

we know from **unanimity** \(e\) is not the winner.

- suppose that \(f(\sigma) = a\)

- mess things up with
**strong monotonicity**

we have \(\sigma^1\) that lies under the strong monotonicty lemma.

1 2 3 4 a b c d b c d a c d a b d a b c e e e e what happend?

- \(a\) was pushed upwards for 2 - 4
- and 2 - 4’s other preferece was shifted to be the same \({d, a, b, c, e}\)

\(\Rightarrow\) looks like \(d\) is winning? but

**strong monotonicity**says:\[ f(\sigma^1) = a \]

- drop \(a\) to the bottom for one voter

change \(2\)’s preference to \(d \succ b \succ c \succ e \succ a\).

## Footnotes:

^{1}

There exists (at least one) a preference \(\sigma_x\) that selects every alternative. Very weak property.

^{2}

Assume that everyelse has a uniformly random preference, and you being the manupilator. This looks like it is close to dictatorship. The G-S is robust in various Probalistic distributions.