Teorie sociálního výběru
$$ \xdef\scal#1#2{\langle #1, #2 \rangle} \xdef\norm#1{\left\lVert #1 \right\rVert} \xdef\dist{\rho} \xdef\and{\&}\xdef\AND{\quad \and \quad}\xdef\brackets#1{\left\{ #1 \right\}} \xdef\parc#1#2{\frac {\partial #1}{\partial #2}} \xdef\mtr#1{\begin{pmatrix}#1\end{pmatrix}} \xdef\bm#1{\boldsymbol{#1}} \xdef\mcal#1{\mathcal{#1}} \xdef\vv#1{\mathbf{#1}}\xdef\vvp#1{\pmb{#1}} \xdef\ve{\varepsilon} \xdef\l{\lambda} \xdef\th{\vartheta} \xdef\a{\alpha} \xdef\vf{\varphi} \xdef\Tagged#1{(\text{#1})} \xdef\tagged*#1{\text{#1}} \xdef\tagEqHere#1#2{\href{#2\#eq-#1}{(\text{#1})}} \xdef\tagDeHere#1#2{\href{#2\#de-#1}{\text{#1}}} \xdef\tagEq#1{\href{\#eq-#1}{(\text{#1})}} \xdef\tagDe#1{\href{\#de-#1}{\text{#1}}} \xdef\T#1{\htmlId{eq-#1}{#1}} \xdef\D#1{\htmlId{de-#1}{\vv{#1}}} \xdef\conv#1{\mathrm{conv}\, #1} \xdef\cone#1{\mathrm{cone}\, #1} \xdef\aff#1{\mathrm{aff}\, #1} \xdef\lin#1{\mathrm{Lin}\, #1} \xdef\span#1{\mathrm{span}\, #1} \xdef\O{\mathcal O} \xdef\ri#1{\mathrm{ri}\, #1} \xdef\rd#1{\mathrm{r}\partial\, #1} \xdef\interior#1{\mathrm{int}\, #1} \xdef\proj{\Pi} \xdef\epi#1{\mathrm{epi}\, #1} \xdef\grad#1{\mathrm{grad}\, #1} \xdef\gradT#1{\mathrm{grad}^T #1} \xdef\gradx#1{\mathrm{grad}_x #1} \xdef\hess#1{\nabla^2\, #1} \xdef\hessx#1{\nabla^2_x #1} \xdef\jacobx#1{D_x #1} \xdef\jacob#1{D #1} \xdef\subdif#1{\partial #1} \xdef\co#1{\mathrm{co}\, #1} \xdef\iter#1{^{[#1]}} \xdef\str{^*} \xdef\spv{\mcal V} \xdef\civ{\mcal U} \xdef\other#1{\hat{#1}} \xdef\xx{\vv x} \xdef\yy{\vv y} $$
Teorie sociálního výběru - teorie her o volebních systémech
Příklad
Máme 15 zaměstnanců - ti si chtějí zvolit nového šéfa - a 3 kandidáty $$ A,B,C $$ Potom prefereční uspořádání jsou
- 7 zaměstnanců: $A > B > C$
- 7 zaměstnanců: $B > A > C$
- 1 zaměstnanec: $C > A > B$
Přehled bodů:
| # people | A | B | C |
|---|---|---|---|
| 7 | 2 | 1 | 0 |
| 7 | 1 | 2 | 0 |
| 1 | 1 | 0 | 2 |
Celkem má $A$ 22 bodů, $21$ bodů pro $B$ a $2$ pro C
Pokud by ale těch 7 zaměstnanců s 1. $B$ chtělo uškodit $A$, mohou si změnit preference na $$ B > C > A $$
To stejné mohou udělat i ti s 1. $A$. Potom prefereční uspořádání jsou
- 7 zaměstnanců: $A > C > B$
- 7 zaměstnanců: $B > C > A$
- 1 zaměstnanec: $C > A > B$
Přehled bodů:
| # people | A | B | C |
|---|---|---|---|
| 7 | 2 | 0 | 1 |
| 7 | 0 | 2 | 1 |
| 1 | 1 | 0 | 2 |
Celkem má $A$ 15 bodů, $14$ bodů pro $B$ a $16$ pro C
Označme
- $N$ voliče
- $i$-tici uspořádání $(<_i)_{i \in N}$ nazývanou preferenční uspořádání na množině $A$
- $A$ množinu variant
Preferenční schéma $$ p : N \to S_m, \quad |A| = m, $$ kde $S_m$ je permutace množiny $A$
Dále označme $P$ množinu všech preferenčních schémat (pro pevné $N,A$).
Náš cíl je najít pevné $d : P \to S_m$, kde $d$ nazýváme funkcí sociálního rozhodování $$ d((<_i)_{i \in N}) = < $$ a požadujeme
$$(\forall (<_i)_{i \in N} \in P) (\forall a,b \in A) (\forall i \in N) \quad a <_i b \implies a < b \tag{\T{FSR-1}}$$
$$(\forall (<_i)_{i \in N}, (\prec_i)_{i \in N} \in P)(\forall a,b \in A) \quad \set{i | a <_i b} = \set{i | a_i \prec_i b} \implies (a < b \iff a \prec b) \tag{\T{FSR-2}}$$
Definice $\D{Dikt}$
Dále $j \in N$ nazveme diktátorem, pokud $$ d((<_i)_{i \in N}) = <_j $$
Věta $\D{Arrow}$
Nechť $n \geq 2, n \geq 3$. Pak libovolná funkce soc. rozhodování má diktátora.
Příklad
-
$m = 2, n \geq 2$, např. většinové pravidlo
$$I \subseteq N (\forall i \in I) \quad a <_i b \ (\forall j \in N \setminus I) \quad b <_j a$$
Je-li $|I| > \frac n 2 \implies a < b$ (a opačně). Při $n$ sudém dáme na "čestného předsedu" -
$m = 2, n = 2$, možnosti
$$a <_1 b, a <_2 b \quad \implies a < b\ a <_1 b, b <_2 a\quad \implies a < b,\overbrace{b < a}^{\text{2. diktátor}}, \overbrace{a < b}^{\text{1. diktátor}}, b < a\ b <_1 a, a <_2 b\quad \implies a < b, \underbrace{a < b}_{\text{2. diktátor}}, \underbrace{b < a}_{\text{1. diktátor}}, b < a \ b <_1 a, b <_2 a \quad \implies b < a $$
Definice $\D{Filtr}$
Řekneme, že $\mcal F$ je filtr na množině $N$, pokud
- $\emptyset \notin \mcal F$
- $F, G \in \mcal F \implies F \cap G \in \mcal F$
- $F \in \mcal F, F \subseteq G \implies G \in \mcal F$
Dále definujme hlavní filtr $$ \uparrow_A = \set{F \subseteq N | a \in F} $$ a ultrafiltr - maximální filtr, tj. $$ \mcal F \subseteq \mcal G \subseteq P(N) \implies \mcal G = \mcal F $$
Lemma $\D{L1}$
Filtr $\mcal F$ na $N$ je ultrafiltr $\iff$ $$ \forall F \subseteq N \text{ je } F \in \mcal F \text{ nebo } N \setminus F \in \mcal F $$
Důkaz $\tagDe{L1}$
Pokud by $F \notin \mcal F$ a ani $N \setminus F \in \mcal F$, pak generujme $\mcal G = \mcal F \cup \uparrow_F$
Nyní je třeba ukázat, že $\emptyset \notin \mcal G$. Kdyby ano, pak by muselo platit $\emptyset = F \cap G$ pro $G \in \mcal F$, pak $G \subseteq N \setminus F$, což je spor s $N - F \notin \mcal G$.
Lemma $\D{L2}$
Pro libovolnou konečnou množinu $N$ je každý ultrafiltr hlavní.
Podmnožina $F\subseteq N$ přehrává $F'$, typicky $F' = N \setminus F$, ve dvojici $a,b \in A$, platí-li $$ a <_F b, a <_{F'} b \implies a < b, $$ kde pod $a <_F b$ myslíme $(\forall i \in F) \quad a <_i b$
Lemma $\D{L3}$
Pokud $F$ přehrává $F' = N \setminus F$ pro $d$ v $a,b$ a $x,y$ jsou libovolné $x,y \in A \implies$ $F$ přehrává $F'$ i v $x,y$
Tedy pokud umí vynutit $a < b$ pro nějakou dvojici, umí to pro všechny dvojice
Důkaz $\tagDe{L3}$
Uvažujme $c <_F a <_F b$ a také $b <_{F'} c <_{F'} a$ (preferenční schéma musí být připravené pro všechny situace).
Pak ale podle $\tagEq{FSR-1}$ musí být $c < a$, ale také $a < b$ podle předpokladů. Celkem máme, že $c < a < b$.
Nyní vezměme libovolná $<_F, <_{F'}$ splňující $c <_F b, b <_F c$, pak dostaneme $c < b$, protože výsledek $d$ nezávisí na $a$ podle $\tagEq{FSR-2}$. Jinak řečeno $F$ přehrává $F'$ i v $c,b$.
Duálně nahradíme $b$ nějakým $e$ a stejně se dostaneme k $x,y$