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\).