\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