Metoda Kemeny – Young - Kemeny–Young method

Část Seriál o politice
Volební systémy
Pluralita / majorita Množství První příspěvek Jeden nepřenosný hlas Omezené hlasování Plurality-at-large (blokové hlasování) Obecný lístek Vícekolové hlasování Dvoukolové Vyčerpávající hlasování Hodnocené / preferenční systémy Okamžitý odtok (alternativní hlasování) Podmíněné hlasování Coombsova metoda Condorcetovy metody (Copeland, Dodgson, Kemeny – Young, Minimax, Nanson, hodnocené páry, Schulze, Alternativní Smith ) Poziční hlasování (Borda počítat, Nauru / Dowdallova metoda, Soutěž Eurovision Song Contest ) Bucklin hlasování Oklahoma primární volební systém Preferenční blokové hlasování Kardinální / odstupňované systémy Hodnocení hlasování Hlasování o schválení (sjednocený primární ) Kombinované hlasování o schválení Hlasování o schválení spokojenosti Většinový úsudek Hlasování STAR
Poměrné zastoupení Seznam stran (otevřené seznamy, uzavřené seznamy, místní seznamy ) Nejvyšší průměry (D'Hondt, Sainte-Laguë, Huntington – Hill ) Největší zbytek (Zajíc, Vadnout, Imperiali, Hagenbach-Bischoff ) Proporcionální formy okamžité odtokové hlasování Jeden převoditelný hlas (Gregory, Wrighte ) Proporcionální formy Condorcetovy metody CPO-STV Schulze STV Proporcionální formy schvalovací hlasování Proporcionální hlasování o schválení Postupné poměrné hlasování o schválení Biproporcionální rozdělení Hlasování spravedlivou většinou
Smíšené systémy Smíšený člen proporcionální Další členský systém Paralelní hlasování (smíšený-majoritní) Scorporo Majoritní bonus Alternativní hlasování Plus Dvoučlenný proporcionální Venkovské a městské proporcionální
Další systémy a související teorie Kumulativní hlasování Binomické hlasování Hlasování proxy Delegované hlasování Náhodný výběr (třídění, náhodné hlasování ) Srovnání volebních systémů Teorie sociální volby Arrowova věta Gibbard – Satterthwaiteova věta Teorie veřejné volby
Portál politiky

The Metoda Kemeny – Young je volební systém který používá preferenční hlasovací lístky a párové srovnání počítá k určení nejpopulárnějších voleb ve volbách. Je to Condorcetova metoda protože pokud existuje vítěz Condorcet, bude vždy považován za nejoblíbenější volbu.

Tato metoda přiřadí skóre pro každou možnou sekvenci, kde každá sekvence zvažuje, která volba by mohla být nejoblíbenější, která volba by mohla být druhá nejoblíbenější, která volba by mohla být třetí nejoblíbenější, a tak dále, na kterou by volba mohla být oblíbený. Sekvence, která má nejvyšší skóre, je výherní sekvence a první volba ve výherní sekvenci je nejoblíbenější volbou. (Jak je vysvětleno níže, vazby se mohou vyskytovat na jakékoli hodnotící úrovni.)

Metoda Kemeny – Young je také známá jako Kemenyho pravidlo, Hodnocení popularity VoteFair, maximální pravděpodobnost metodaa střední vztah.

Popis

Metoda Kemeny – Young používá preferenční hlasovací lístky podle kterého voliči řadí výběr podle svého preferenčního pořadí. Volič může hodnotit více než jednu volbu na stejné úrovni preferencí^{[Citace je zapotřebí ]}. Nehodnocené volby jsou obvykle interpretovány jako nejméně preferované.

Dalším způsobem, jak zobrazit pořadí, je, že je to ten, který minimalizuje součet Vzdálenosti Kendall tau (třídění bublin vzdálenost) na seznamy voličů.

Kemeny – Youngovy výpočty se obvykle provádějí ve dvou krocích. Prvním krokem je vytvoření matice nebo tabulky, která počítá párové preference voličů. Druhým krokem je otestovat vše možné žebříčku, vypočítat skóre pro každé takové hodnocení a porovnat skóre. Každé skóre v hodnocení se rovná součtu počtů párů, které se vztahují k danému hodnocení.

Hodnocení, které má největší skóre, je identifikováno jako celkové hodnocení. (Pokud má více než jedno hodnocení stejné nejvyšší skóre, jsou všechna tato možná hodnocení svázaná a celkové hodnocení obvykle zahrnuje jednu nebo více remíz.)

Abychom předvedli, jak je jednotlivé pořadí preferencí převedeno na tabulku shod, stojí za zvážení následující příklad. Předpokládejme, že jeden volič má na výběr mezi čtyřmi kandidáty (tj. Elliot, Meredith, Roland a Selden) a má následující pořadí preferencí:

Tyto preference lze vyjádřit ve srovnávací tabulce. Sčítací tabulka, která uspořádá všechny párové sčítání do tří sloupců, je užitečná pro počítání (sčítání) předvoleb hlasování a výpočet skóre pořadí. Středový sloupec sleduje, když volič označuje více než jednu volbu na stejné úrovni preferencí. Výše uvedené pořadí preferencí lze vyjádřit jako následující srovnávací tabulku:^{[Citace je zapotřebí ]}

Nyní předpokládejme, že o těchto čtyřech kandidátech hlasovalo více voličů. Po spočítání všech hlasovacích lístků lze ke shrnutí všech předvoleb všech voličů použít stejný typ srovnávací tabulky. Zde je příklad případu, který má 100 voličů:

Součet počtů v každém řádku se musí rovnat celkovému počtu hlasů.

Po dokončení srovnávací tabulky se postupně prozkoumá každé možné pořadí voleb a jeho skóre se vypočítá přidáním příslušného počtu z každého řádku srovnávací tabulky. Například možné pořadí:

1. Elliot
2. Roland
3. Meredith
4. Selden

uspokojuje preference Elliot> Roland, Elliot> Meredith, Elliot> Selden, Roland> Meredith, Roland> Selden a Meredith> Selden. Příslušná skóre převzatá z tabulky jsou

• Elliot> Roland: 30
• Elliot> Meredith: 60
• Elliot> Selden: 60
• Roland> Meredith: 70
• Roland> Selden: 60
• Meredith> Selden: 40

což dává celkové skóre v hodnocení 30 + 60 + 60 + 70 + 60 + 40 = 320.

Výpočet celkového hodnocení

Po vypočítání skóre pro každé možné hodnocení lze identifikovat hodnocení, které má největší skóre, a stane se celkovým hodnocením. V tomto případě je celkové hodnocení:

1. Roland
2. Elliot
3. Selden
4. Meredith

s bodovým hodnocením 370.

Pokud existují cykly nebo remízy, více než jedno možné hodnocení může mít stejné nejvyšší skóre. Cykly jsou vyřešeny vytvořením jediného celkového hodnocení, kde jsou některé z možností shodné.^{[je zapotřebí objasnění ]}

Souhrnná matice

Po výpočtu celkového pořadí lze počty párových srovnání uspořádat do souhrnné matice, jak je znázorněno níže, ve které se volby zobrazují ve výherním pořadí od nejoblíbenějšího (nahoře a vlevo) po nejméně populární (dole a vpravo). Toto rozložení matice nezahrnuje párové počty stejné preference, které se objevují v tabulce shod:^[1]

V této souhrnné matici se největší bodovací skóre rovná součtu počtů v pravé horní trojúhelníkové polovině matice (zde je uvedeno tučně se zeleným pozadím). Žádné jiné možné hodnocení nemůže mít souhrnnou matici, která poskytuje vyšší součet čísel v pravé horní trojúhelníkové polovině. (Pokud ano, pak by to bylo celkové hodnocení.)

V této souhrnné matici je součet čísel v levé dolní trojúhelníkové polovině matice (zde zobrazený s červeným pozadím) minimum. Akademické práce od Johna Kemenyho a Peytona Younga^[2][3] odkazují na zjištění této minimální částky, která se nazývá skóre Kemeny, a která je založena na tom, kolik voličů je proti (spíše než podporuje) každé párové pořadí:

Příklad

Představ si to Tennessee má volby podle umístění hlavní město. Populace Tennessee je soustředěna kolem jeho čtyř hlavních měst, která jsou rozmístěna po celém státě. V tomto příkladu předpokládejme, že celý voliči žije v těchto čtyřech městech a že každý chce žít co nejblíže k hlavnímu městu.

Kandidáti na kapitál jsou:

• Memphis, největší město státu se 42% voličů, ale nachází se daleko od ostatních měst
• Nashville, s 26% voličů, blízko centra státu
• Knoxville, se 17% voličů
• Chattanooga, s 15% voličů

Preference voličů by byly rozděleny takto:

Tato matice shrnuje odpovídající párové srovnání počty:

Metoda Kemeny – Young uspořádá počty párových srovnání v následující tabulce shod:

Bodové hodnocení možného umístění Memphisu jako prvního, Nashvillu druhého, Chattanoogy třetího a Knoxvillského čtvrtého se rovná (číslo bez jednotek) 345, což je součet následujících anotovaných čísel.

42% (hlasujících) dává přednost Memphisu před Nashvillem

42% dává přednost Memphisu před Chattanoogou

42% dává přednost Memphisu před Knoxville

68% dává přednost Nashvillu před Chattanoogou

68% dává přednost Nashvillu před Knoxville

83% dává přednost Chattanoogě před Knoxville

V této tabulce jsou uvedena všechna hodnocení:

Největší skóre v hodnocení je 393 a toto skóre je spojeno s následujícím možným hodnocením, takže toto hodnocení je také celkovým hodnocením:

Pokud je zapotřebí jediný vítěz, vybere se první volba, Nashville. (V tomto příkladu je Nashville Condorcet vítěz.)

Níže uvedená souhrnná matice uspořádá počty párů v pořadí od nejpopulárnějších (nahoře a vlevo) po nejméně populární (dole a vpravo):

V tomto uspořádání se největší bodovací skóre (393) rovná součtu počtů tučně, které jsou v pravé horní, trojúhelníkové polovině matice (se zeleným pozadím).

Vlastnosti

Ve všech případech, které nevedou k přesné shodě, identifikuje metoda Kemeny – Young nejoblíbenější volbu, druhou nejoblíbenější volbu atd.

K remíze může dojít na jakékoli úrovni preferencí. Kromě případů, kdy kruhové nejasnosti Jsou-li zapojeni, metoda Kemeny – Young vytvoří remízu na úrovni preferencí pouze tehdy, když se počet voličů s jednou preferencí přesně shoduje s počtem voličů s opačnými preferencemi.

Splněná kritéria pro všechny metody Condorcet

Všechny metody Condorcet, včetně metody Kemeny – Young, splňují tato kritéria:

Neukládání

Existují preference voličů, které mohou přinést všechny možné výsledky celkového pořadí preferencí, včetně vazeb na libovolné kombinaci úrovní preferencí.

Kritérium Condorcet

Pokud existuje volba, která vyhraje všechny párové soutěže, pak tato volba vyhraje.

Kritérium většiny

Pokud většina voličů striktně upřednostňuje volbu X před každou jinou volbou, pak je volba X označena jako nejoblíbenější.

Nediktatura

Jediný volič nemůže ve všech případech kontrolovat výsledek.

Další splněná kritéria

Metoda Kemeny – Young také splňuje tato kritéria:

Neomezená doména

Určuje celkové pořadí preferencí pro všechny volby. Metoda to dělá pro všechny možné sady preferencí voličů a vždy produkuje stejný výsledek pro stejnou sadu preferencí voličů.

Paretova účinnost

Jakákoli párová preference vyjádřená každým voličem vede k tomu, že preferovaná volba bude hodnocena výše než méně preferovaná volba.

Monotónnost

Pokud voliči zvýší úroveň preferencí volby, výsledek hodnocení se buď nezmění, nebo se zvýší propagovaná volba v celkové popularitě.

Smithovo kritérium

Nejoblíbenější volbou je člen Smithova sada, což je nejmenší neprázdná množina možností, takže každý člen sady je párově upřednostňován před každou volbou, která není v Smithově sadě.

Nezávislost alternativ ovládaných Smithem

Pokud volba X není v Smithova sada, přidání nebo odebrání volby X nemění výsledek, ve kterém je volba Y označena jako nejoblíbenější.

Posílení

Pokud jsou všechny hlasovací lístky rozděleny do samostatných závodů a celkové pořadí pro jednotlivé závody je stejné, pak ke stejnému pořadí dojde, když jsou všechny hlasovací lístky zkombinovány.^[4]

Reverzní symetrie

Pokud jsou preference na každém hlasovacím lístku obráceny, pak nejoblíbenější volba nesmí zůstat tou nejoblíbenější volbou.

Selhala kritéria pro všechny metody Condorcet

Stejně jako všechny metody Condorcet, metoda Kemeny – Young selže tato kritéria (což znamená, že popsaná kritéria neplatí pro metodu Kemeny – Young):

Nezávislost irelevantních alternativ

Přidání nebo odebrání možnosti X nemění výsledek, ve kterém je volba Y označena jako nejoblíbenější.

Nezranitelnost pohřbívání

Volič nemůže vytlačit výběr z nejpopulárnějších tím, že mu dá neúspěšně nízké hodnocení.

Nezranitelnost vůči kompromisu

Volič nemůže způsobit, že se volba stane nejpopulárnější tím, že dá tomuto výběru upřímně vysoké hodnocení.

Účast

Přidání hlasovacích lístků, které hodnotí výběr X oproti výběru Y, nikdy nezpůsobí, že by se volba Y místo volby X stala nejpopulárnější.

Později neškodit

Hodnocení další volby (která byla jinak nehodnocená) nemůže vytlačit výběr z toho, že bude označen jako nejoblíbenější.

Konzistence

Pokud jsou všechny hlasovací lístky rozděleny do samostatných ras a volba X je označena jako nejoblíbenější v každém takovém závodě, je volba X nejpopulárnější, když jsou všechny hlasovací lístky spojeny.

Další nevyhovující kritéria

Metoda Kemeny – Young také selže tato kritéria (což znamená, že popsaná kritéria neplatí pro metodu Kemeny – Young):

Nezávislost klonů

Nabídka většího počtu podobných možností nezmění místo jediné takové volby pravděpodobnost, že jedna z těchto možností bude označena jako nejoblíbenější.

Nezranitelnost při prosazování

Volič nemůže způsobit, že se volba X stane nejpopulárnější tím, že dá výběru Y neuvěřitelně vysoké hodnocení.

Schwartz

Výběr označený jako nejpopulárnější je členem Schwartzovy sady.

Polynomiální běh^[5]

Je známo, že algoritmus určuje vítěze pomocí této metody za běhu, který je polynomický v počtu možností.

Metody výpočtu a výpočetní složitost

Algoritmus pro výpočet Kemenyho-Youngova žebříčku v čase polynomu v počtu kandidátů není znám a je nepravděpodobné, že by existoval, protože problém je NP-tvrdé^[5] i když jsou jen 4 voliči.^[6][7]

Bylo ohlášeno^[8] že metody výpočtu založené na celočíselné programování někdy umožňoval výpočet úplného pořadí pro hlasy až 40 kandidátů během několika sekund. Některé náhodně generované volby Kemenyho s 40 kandidáty, které byly generovány náhodně, však nebyly v užitečném časovém limitu v roce 2006 na počítači Pentium 3 GHz řešitelné.^[8]

Všimněte si, že složitost výpočtu se lineárně mění podle počtu voličů, takže času potřebnému ke zpracování dané sady hlasů dominuje počet kandidáti^[9] spíše než počet hlasů, což omezuje význam tohoto omezení na volby, kde jsou voliči schopni efektivně zvažovat podstatně více než běžné sedm položek pracovní paměti.

Existuje a schéma polynomiálního času za výpočet hodnocení Kemeny-Young,^[10] a existuje také parametrizovaný algoritmus subexponenciálního času s dobou běhu O^*(2^Ó(√OPT)) pro výpočet takového hodnocení.^[11]

Dějiny

Metodu Kemeny – Young vyvinul John Kemeny v roce 1959.^[2]

V roce 1978 Peyton Young a ukázal Arthur Levenglick^[3] že tato metoda byla jedinečná neutrální metoda uspokojující posílení a verze kritéria Condorcet. V jiných dokumentech^{[12][13][14][15]}Young přijal epistemický přístup k agregaci preferencí: předpokládal, že existuje objektivně „správné“, ale neznámé pořadí preferencí před alternativami, a voliči dostávají hlučné signály tohoto skutečného pořadí preferencí (srov. Condorcetova věta o porotě.) Pomocí jednoduchého pravděpodobnostního modelu pro tyto hlučné signály Young ukázal, že metoda Kemeny – Young byla odhad maximální pravděpodobnosti skutečného pořadí preferencí. Young to dále tvrdí Condorcet sám si byl vědom Kemenyho-Youngova pravidla a jeho interpretace maximální pravděpodobnosti, ale nebyl schopen jasně vyjádřit své myšlenky.

V novinách Johna Kemenyho a Peytona Younga používají skóre Kemenyho počty toho, kolik voličů oponuje, místo aby podpořili, každý párové preference,^[2][3] ale nejmenší takové skóre označuje stejné celkové hodnocení.

Od roku 1991 tuto metodu propaguje Richard Fobes pod názvem „VoteFair popularity ranking“.^[16]

Srovnávací tabulka

Následující tabulka porovnává metodu Kemeny-Young s jinými přednostní metody voleb pro jednoho vítěze:

Poznámky

externí odkazy

• VoteFair.org - Web, který počítá výsledky Kemeny – Young. Pro srovnání také vypočítá vítěze podle plurality, Condorcetu, Bordova počtu a dalších hlasovacích metod.
• VoteFair_Ranking.cpp - Program C ++, dostupný na GitHub pod licencí MIT, který počítá výsledky hodnocení VoteFair, které zahrnují výpočty Condorcet-Kemeny.
• Condorcet Class PHP knihovna podpora více metod Condorcet, včetně metody Kemeny – Young.
• Program C ++ pro agregaci preferencí Kemeny-Young - Program příkazového řádku pro rychlý výpočet výsledků Kemeny-Young, jako zdrojový kód a kompilované binární soubory pro Windows a Linux. Otevřený zdroj, kromě použití Numerické recepty.
• Program C pro agregaci preferencí Kemeny-Young - Implementuje Davenportův algoritmus bez dalších závislostí na knihovně. Open source, licence LGPL. Rubínová vazba na knihovnu je také otevřený zdroj s licencí LPGL.
• Kemeny-Young Optimal Aggregation Rank v Pythonu - Výukový program, který používá jednoduchou formulaci jako celočíselný program a je přizpůsobitelný pro jiné jazyky s vazbami na lpsolve.