summaryrefslogtreecommitdiff
path: root/macros/generic/infpic/voting1.cs
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
committerNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
commite0c6872cf40896c7be36b11dcc744620f10adf1d (patch)
tree60335e10d2f4354b0674ec22d7b53f0f8abee672 /macros/generic/infpic/voting1.cs
Initial commit
Diffstat (limited to 'macros/generic/infpic/voting1.cs')
-rw-r--r--macros/generic/infpic/voting1.cs269
1 files changed, 269 insertions, 0 deletions
diff --git a/macros/generic/infpic/voting1.cs b/macros/generic/infpic/voting1.cs
new file mode 100644
index 0000000000..0c615e7691
--- /dev/null
+++ b/macros/generic/infpic/voting1.cs
@@ -0,0 +1,269 @@
+\input my.tex
+\input incpic
+\font\sipky=sipky
+
+\fontcharplace{\sipky}{`\A}{
+ \fontmark rc 0 1 {\strut a}
+ \fontmark rc 0 0 {\strut b}
+ \fontmark rc 1 0 {\strut c}
+ \fontmark rc 2 0 {\strut d}
+ }
+
+\podtitul 1: Hlasov n¡ a la Condorcet: Postupn‚ vˆt¨inov‚ porovn v n¡
+
+ V˜bˆr z dvojice, kde mus¡ b˜t vybr n jeden ze dvou
+ kandid t–, je univers lnˆ vy©e¨en vˆt¨inovou volbou. Celkov˜
+ pocit n m napov¡d , ‘e jedinˆ takov˜ v˜bˆr je spravedliv˜,
+ a teorie potvrzuje, ‘e nelze postupovat jinak, pokud chceme
+{ \item {(i)} spravedlnost: ‘ dn  p©edem ur‡en  diskriminace voli‡– ani
+ kandid t–, a
+ \item {(ii)} odolnost proti pou‘it¡ strategi¡: ka‘d˜
+ voli‡ m  motiv volit svobodnˆ -- ‘ dn˜ osamˆl˜ voli‡ (bez
+ £‡asti v nˆjak‚ koalici) nem–‘e £spˆ¨nˆ ovliv¤ovat pr–bˆh
+a v˜sledek voleb.}
+ Tato charakteristika je zn ma jako May–v
+ teor‚m (May [1952]).
+
+ Pokud je t©eba vybrat z v¡ce ne‘ dvou kandid t–, je obvykle
+ situace ponˆkud slo‘itˆj¨¡. Vˆt¨inov‚ porovn v n¡ m–‘e
+ poslou‘it k vytvo©en¡ bin rn¡ relace, tzv. vˆt¨inov‚ relace,
+ kter  vyjad©uje kolektivn¡ preference mezi p ry kandid t–.
+ Bohu‘el, v t‚to relaci se mohou objevit cykly, tato
+ skute‡nost je naz˜v na "Condorcet–v paradox". P©edpokl dejme
+ t©i voli‡e $\{1,2,3\} = N$, kte©¡ maj¡ n sleduj¡c¡ preference:
+
+\vskip 1cm
+\centerline {\hbox {
+\vbox{
+\offinterlineskip
+\halign
+{\strut \ # \quad & \vrule \quad # \quad & # \quad & # \ \cr
+ voli‡ & 1 & 2 & 3 \cr
+ \noalign {\hrule}
+ vrchol & a & c & b \cr
+ & b & a & c \cr
+ dno & c & b & a \cr
+ }} }}
+\vskip 1 cm
+
+ Pokud se vytvo©¡ cykly, nemus¡ ve vˆt¨inov‚m porovn v n¡
+ dvojic existovat Condorcet–v v¡tˆz: ka‘d˜ kandid t je pora‘en
+ nejm‚nˆ jedn¡m jin˜m kandid tem ve vˆt¨inov‚m porovn v n¡.
+ Takto m–‘eme nazvat Condorcetov˜m v¡tˆzem kandid ta $a$, kter˜
+ p©i porovn v n¡ s kter˜mkoliv jin˜m kandid tem $x$ z¡sk 
+ nejm‚nˆ stejnˆ hlas– jako jeho protivn¡k.
+
+ €etnost v˜skytu paradoxu je p©ekvapivˆ vysok .
+ P©edpokl dejme, ‘e voli‡i maj¡ uspo© dan‚ preference a ‘e
+ v˜skyt jednotliv˜ch uspo© d n¡ kandid t– je rovnomˆrnˆ
+ a nez visle rozlo‘en, pak pravdˆpodobnost, ‘e ‘ dn˜ kandid t
+ nen¡ Condorcetov˜m v¡tˆzem m–‘e b˜t spo‡tena nebo
+ p©inejmen¨¡m odhadnuta.
+
+ Pokud ‘ dn˜ Condorcet–v v¡tˆz neexistuje, hled  se
+ zpravidla takov˜ kandid t, kter˜ by jej nahradil (a m  pro to
+ rozumn‚ d–vody). Jako p©¡kld lze uv‚st zn m˜ postup u‘¡van˜
+ v Kongresu USA p©i hlasov n¡ mezi n vrhem z kona a jeho
+ p©¡davky (zn m˜ jako tzv. n vrhov  {\sl (amendment)} procedura, viz
+ Riker [1982], str. 70, pro podrobnosti).
+
+ Hlasov n¡ postupn˜m vylu‡ov n¡m {\sl (succesive elimination)}:
+
+\vskip 1cm
+\inspicture
+\vskip 1cm
+
+ Neprve se vˆt¨inou rozhodne mezi $a$ a $b$, potom se v¡tˆz
+ porovn v  s $c$, atd. V p©¡padˆ nerozhodnutelnosti hlasov n¡
+ (rem¡za) kandid t zdola prohr v .
+
+ V n vrhov‚ procedu©e $a$ znamen  p©¡davek k pozmˆ¤ovac¡mu
+ n vrhu, $b$ p©¡davek k p©¡davku, $c$ je pozmˆ¤ovac¡ n vrh
+ a $d$ platn˜ z kon. Samoz©ejmˆ po©ad¡ v˜bˆru m  sv–j v˜znam:
+ kandid ti nejsou pova‘ov ni za rovnocenn‚ (©¡k me, ‘e
+ hlasovac¡ pravidlo nen¡ neutr ln¡).
+
+\vfill\eject
+
+\def\*{$^*$}
+\def\mez{\hskip 2ex$\vdots$}
+\centerline{ \hbox {
+\vbox{\offinterlineskip
+\halign
+{ \quad # \ & \vrule height 2em depth 1em \qquad # \quad & # \quad
+ & # \quad & # \quad & # & \ # \ & # \quad \cr
+\hskip4em \rlap {\raise 1ex \hbox {po‡et}} \leavevmode \lower 1ex
+ \hbox {voli‡–} & \ 3 & \ 5 & \ 7 & \ 9 & \ 11 && limit \cr
+\noalign {\vskip -1.5em}
+\rlap {\raise 1ex \hbox {po‡et}} \leavevmode \lower 1ex
+ \hbox {kandid t–} &\cr
+\noalign {\hrule}
+\hskip3em 3 & .056 & .069 & .075 & .078 & .080 &.....& .088 \cr
+\hskip3em 4 & .111 & .139 & .150 & .156 & .160 &.....& .176 \cr
+\hskip3em 5 & .160 & .200 & .215 & .230 & .251 &.....& .251 \cr
+\hskip3em 6 & .202 & .255\* & .258\* & .284\* & .294\* &.....& .315 \cr
+\hskip3em 7 & .239\* & .299\* & .305\* & .342\* & .343\* &.....& .369 \cr
+\noalign {\vskip -1em}
+ &\mez &\mez &\mez &\mez &\mez &&\mez \cr
+\noalign {\vskip -1em}
+\hskip2.5em limit & \ 1 & \ 1 & \ 1 & \ 1 & \ 1 &.....& \ 1 \cr
+}}}}
+\vskip .5cm
+\centerline {—daje zna‡en‚ \* jsou odhadnut‚}
+\vskip 3mm
+\centerline { Tabulka 1: Pravdˆpodobnost neexistence Condorcetova v¡tˆze}
+\centerline { Zdroj: Fishburn [1973], str. 95.}
+
+ Tato metoda v‘dy spl¤uje Condorcet–v axiom: jestli‘e a je
+ Condorcet–v v¡tˆz, vyhraje (nehledˆ na pravdˆpodobnost
+ rem¡z). Ve skute‡nosti je to d–sledek vˆt¨inov‚ho porovn v n¡
+ v daleko ¨ir¨¡m smyslu:
+
+
+ Smithova podm¡nka: jestli‘e se mno‘ina A kandid t– rozdˆl¡
+ na dvˆ disjuktn¡ podmno‘iny $B_1,\, B_2$ a ka‘d˜ kandid t $b_1$ z $B_1$
+ poraz¡ (bez rem¡z) ka‘d‚ho $b_2$ z $B_2$, potom v¡tˆz mus¡ b˜t
+ z mno‘iny $B_1$.
+
+ V¨echny hlasovac¡ metody odvozen‚ z bin rn¡ho stromu
+ (v¨echny p©edv dˆn‚ v t‚to ‡ sti jsou tohoto typu) vyhovuj¡
+ Smithovˆ podm¡nce. Bohu‘el nˆkter‚ z nich poru¨uj¡
+ d–le‘itˆj¨¡ p‘adavky kolektivn¡ho v˜bˆru, p©edev¨¡m
+ jednomyslnost neboli Paretovo krit‚rium:
+
+
+ Paretovo krit‚rium: jestli‘e ka‘d˜ voli‡ d v  p©ednost
+ kandid tu $a$ p©ed $b$, kandid t $b$ nem–‘e b˜t vybr n.
+
+ Hlasov n¡ postupn˜m vylu‡ov n¡m m–‘e vybrat Paretova
+ hor¨¡ho kandid ta.
+
+ P©edpokl dejme preference voli‡– n sledovnˆ
+
+\vskip 1cm
+\centerline {\hbox {
+\vbox{
+\offinterlineskip
+\halign
+{\strut \ # \quad & \vrule \quad # \quad & # \quad & # \ \cr
+ voli‡ & 1 & 2 & 3 \cr
+ \noalign {\hrule}
+ vrchol & b & a & c \cr
+ & a & d & b \cr
+ & d & c & a \cr
+ dno & c & b & d \cr
+ }} }}
+\vskip 1 cm
+
+ potom postupn˜ v˜bˆr v po©ad¡ $abcd$ postupuje
+
+\vskip 1cm
+\fontcharplace{\sipky}{`\A}{
+ \fontmark cc 0 1 {\strut a}
+ \fontmark rc 0 0 {\strut b}
+ \fontmark rc 1 0 {\strut c}
+ \fontmark rc 2 0 {\strut d}
+ \fontmark cd 1 1 {\strut b}
+ \fontmark cd 2 1 {\strut c}
+ \fontmark lc 3 1 {\strut d}
+ }
+\inspicture
+\vskip 1cm
+
+ A‡koliv $a$ je Paret–v lep¨¡ kandid t {\sl (Pareto superior)}, ‡ili
+ je jednomyslnˆ preferov n oproti $d$.
+
+ V hlasov n¡ postupn˜m v˜bˆrem m  kandid t, kter˜ vstupuje
+ posledn¡ (jmenovitˆ $d$), o‡ividnou v˜hodu: m–‘e vyhr t
+ pora‘en¡m jenom jednoho (dob©e vybran‚ho) oponenta (toto
+ znamen , ‘e nez le‘¡ na preferenc¡m v–‡i ostatn¡m
+ kandid t–m).
+
+ K zachov n¡ spravedlnosti je mo‘n‚ sestavit dvˆ symetrick‚
+ hlasov n¡ postupn˜m v˜bˆrem n sledovnˆ:
+
+\bye
+
+ a____________________________________
+ / / / \
+ / / / \
+ b/ c/ d/ \
+ /
+ /
+ d____________________________________/
+ / / /
+ / / /
+ c/ b/ a/
+
+ Tabulka 2: Paraleln¡ v˜bˆrov  metoda
+
+ Nyn¡ bˆ‘¡ dvˆ paraleln¡ v˜bˆrov‚ procedury. Dva finalist‚
+ kone‡nˆ soutˆ‘¡ o v¡tˆzstv¡.
+
+ Je dobr‚ cvi‡en¡ ovˆ©it si, ‘e p©i tomto postupu v¡tˆz
+ nem–‘e b˜t Paret–v hor¨¡ kandid t {\sl (Pareto inferior)}. Pro
+ jednoduchost p©edpokl dejme, ‘e v¨echny dvojice je vˆt¨inov‚
+ porovn v n¡ jednozna‡n‚ (pro ka‘dou dvojici $x,\, y$ existuje
+ jednozna‡n  vˆt¨ina preferuj¡c¡ $x$ p©ed $y$ nebo naopak $y$ p©ed
+ $x$). Jestli‘e je zde Condorcet–v v¡tˆz, mus¡ z©ejmˆ vyhr t.
+ Pokud toto neplat¡, zv¡tˆz¡ Copeland–v v¡tˆz, kandid t, kter˜
+ vyhraje pr vˆ dvakr t (a prohraje jednou) v soutˆ‘¡ch dvojic.
+ Mohou se zde vyskytnout nejv˜¨e dva Copelandovi v¡tˆzov‚.
+ Ovˆ©te si, ‘e ‘ dn˜ z nich nem–‘e b˜t Paret–v hor¨¡ kandid t.
+ Pak si v¨imnˆte, ‘e pokud v¡tˆz paraleln¡ho v˜bˆru --- ©eknˆme
+ $x$ --- nen¡ Copeland–v v¡tˆz, pak mus¡ porazit alespo¤ jednoho
+ Copelandova v¡tˆze a to zaru‡uje, ‘e $x$ nen¡ Paret–v hor¨¡
+ kandid t.
+
+ Ale bˆda, paraleln¡ v˜bˆr m  jinou perverzn¡ vlastnost,
+ kter  jej znev˜hod¤uje oproti n sleduj¡c¡m metod m:
+
+ Algoritmus slo‘it‚ho jedn n¡
+{\sl (The Sophisticated Agenda Algorithm)}
+
+ Mˆjme kandid ty $a_1,...,a_n$. Definujme indukc¡
+\def\a {\alpha}
+\hskip 1 cm $\a _{i+1}=a_{i+1}$ pokud $a_{i+1}$ poraz¡
+ $\a _1,\a _2,...,\a _i$
+
+ $\a _1=a_1,
+
+ \hskip 1cm $ a_ {i+1}=\a _i$ pokud nejm‚nˆ jeden $\a _j$, $1<j<i$,
+ rem¡zuje s $a_{i+1}$, nebo jej poraz¡.
+
+ V˜sledek algoritmu je kandid t $\a _n$.
+
+ Nyn¡ m me zaru‡eno:
+\item {a.} algoritmus slo‘it‚ho jedn n¡ vybere stejn‚ho kandid ta,
+ jako v¡cestup¤ov  v˜bˆrov  procedura;
+\item {b.} tento kandid t poraz¡, aŸ p©¡mo ‡i nep©¡mo, ka‘d‚ho
+ jin‚ho kandid ta;
+\item {c.} proto nem–‘e b˜t ani Paret–v hor¨¡ kandid t; a
+\item {d.} tato v˜bˆrov  metoda je monotonn¡.
+
+ Toto jsou v˜sledky z kladn¡ho v˜znamu, a‡koli se v literatu©e
+ o hlasov n¡ objevily teprve ned vno (Miller [1980]; Shepsle
+ a Weingast [1982]; Moulin [1983], ‡ st 5; Banks [1984]).
+
+ Copelandovo hlasovac¡ pravidlo je jin‚ pravidlo zalo‘en‚
+ na vˆt¨inov‚m porovn v n¡ dvojic, kter‚ vyhovuje uveden˜m
+ podm¡nk m b,c,d.
+
+ Copelandovo pravidlo: Copeland [1951].
+
+ Porovnejme ka‘d‚ho kandid ta s ka‘d˜m jin˜m kandid tem
+ a vyberme toho kandid ta, kter˜ vyhr l nej‡astˆji; p©i
+ stejn‚m po‡tu v¡tˆzstv¡ u v¡ce kandid t– vyberme jednoho
+ podle p©edem ur‡en‚ho libovoln‚ho po© dku.
+
+ Navzdory sv‚ jednoduchosti, tato metoda vy‘aduje v¡ce
+ porovn v n¡ dvojic, ne‘ algoritmus slo‘it‚ho jedn n¡: pokud
+ m me $p$ kandid t–, v¨ech $p(p-1)/2$ souboj– mus¡ b˜t rozhodnuto;
+ oproti algoritmu slo‘it‚ho jedn n¡, kde je pot©eba nejv˜¨e
+$p(p-1)/2$ takov˜ch porovn n¡. Pokud m me 13~kandid t– nebo
+ v¡ce, je mo‘n‚ nal‚zt takov˜ soubor preferenc¡, kde dvˆ
+ metody (Copelandova a slo‘it‚ho jedn n¡) vyberou radik lnˆ
+ odli¨n‚ v¡tˆze (Moulin [1984]). Tak‚ lze dok zat, ‘e
+ Copelandovo pravidlo se ned  odvodit z bin rn¡ho stromu,
+ jakkoliv rozs hl‚ho (Moulin [1984]).
+ \ No newline at end of file