Metoda Dodgson Quick
Nápad Lewise Carrolla: zvolit možnost, se kterou by se na lístcích muselo pohnout nejméně, aby porazila všechny. Intuitivní, ale bez dokázaných záruk srovnatelných se Schulzeho metodou.
Kdy ji zvolit: pokud ji určují vaše stanovy nebo pokud je takový pohled na výsledek vašim voličům blízký.
- Původ
- Charles Dodgson (Lewis Carroll), 1876; aproximace: McCabe-Dansted, Pritchard a Slinko, 2008
- Nabízené varianty
- Dodgson Quick
- Výpočet
- Polynomiální, řádově n² pro n možností (přesná Dodgsonova metoda: NP-těžká)
Měřit vzdálenost od Condorcetova vítěze.
Dodgsonova metoda zvolí možnost, ze které by se nejmenším počtem prohození na lístcích stal Condorcetův vítěz. Tento přesný výpočet je NP-těžký (Bartholdi, Tovey a Trick, 1989).
Dodgson Quick ho jednoduše odhaduje: u každého prohraného souboje je potřeba převrátit nejméně polovinu rozdílu. Skóre sečte tyto poloviny rozdílů, zaokrouhlené nahoru, a vyhrává nejnižší.
Stejný cyklus, měřený v prohozeních.
- Camille , pak Adèle , pak Sophie Voliči: 40
- Adèle , pak Sophie , pak Camille Voliči: 35
- Sophie , pak Camille , pak Adèle Voliči: 25
- 1 Camille. Prohrává se Sophií o 20 hlasů: skóre 10.
- 2 Adèle. Prohrává s Camille o 30 hlasů: skóre 15.
- 3 Sophie. Prohrává s Adèle o 50 hlasů: skóre 25.
- Camille poráží ji Sophie o 20 hlasů 10
- Adèle poráží ji Camille o 30 hlasů 15
- Sophie poráží ji Adèle o 50 hlasů 25
Co metoda zaručuje ve srovnání s relativním většinovým systémem.
Dodgson Quick nepokrývá žádná publikovaná tabulka. Vyplněná jsou jen pole, která plynou z její konstrukce nebo z obecného výsledku.
| Kritérium | Dodgson Quick | Relativní většinový systém |
|---|---|---|
| Kritérium většiny Možnost, kterou více než polovina voličů dá na první místo, vyhraje. | Ano Poznámka 1 | Ano |
| Kritérium většinového poraženého Možnost, kterou více než polovina voličů dá na poslední místo, nikdy nevyhraje. | Nedoloženo | Ne |
| Kritérium vzájemné většiny Pokud většina dá určitou skupinu možností před všechny ostatní, vítěz pochází z této skupiny. | Nedoloženo | Ne |
| Condorcetův vítěz Možnost, která ve vzájemném souboji porazí každou jinou, je vždy zvolena. | Ano Poznámka 2 | Ne |
| Condorcetův poražený Možnost, kterou ve vzájemném souboji porazí každá jiná, není nikdy zvolena. | Nedoloženo | Ne |
| Smithovo kritérium Vítěz patří do nejmenší skupiny možností, které porazí všechny možnosti mimo ni. | Nedoloženo | Ne |
| Nezávislost na klonech Přidání možnosti, která je velmi podobná jiné, nezmění výsledek mezi ostatními. | Nedoloženo | Ne |
| Monotonie Když voliči vítěze posunou v pořadí výš, nemůže kvůli tomu prohrát. | Nedoloženo | Ano |
| Lokální nezávislost Odebrání možnosti, která ve výsledku skončila poslední (nebo první), nezmění pořadí ostatních. | Nedoloženo | Ne |
| Symetrie při obrácení Když se pořadí na všech hlasovacích lístcích obrátí, dosavadní vítěz už nevyhraje. | Nedoloženo | Ne |
| Kritérium účasti Upřímný hlas nemůže voliči nikdy uškodit víc, než kdyby se hlasování vůbec nezúčastnil. | Ne Poznámka 3 | Ano |
| Konzistence Pokud možnost vyhraje ve dvou oddělených skupinách, vyhraje i po jejich spojení. | Ne Poznámka 3 | Ano |
| Bez újmy pro první preferenci Zařazení další možnosti nikdy nemůže uškodit možnostem, které jsou už seřazené před ní. | Ne Poznámka 3 | Ano Poznámka 4 |
| Rozhodnutelnost S rostoucím počtem voličů se nerozhodný konečný výsledek stává nepravděpodobným. | Nedoloženo | Ano |
| Rychlý výpočet Výsledek se spočítá v polynomiálním čase, i když je možností hodně. | Ano | Ano |
- ✓ vždy splněno
- ✕ v některých hlasováních může být porušeno
- ? žádný publikovaný zdroj to nedokládá
- 1 Přímý důsledek Condorcetova kritéria: možnost, kterou většina dá na první místo, porazí ve vzájemném souboji všechny ostatní.
- 2 Zaručeno konstrukcí: CondorcetPHP dává Condorcetova vítěze vždy na první místo.
- 3 Toto kritérium nemůže splnit žádná metoda, která splňuje Condorcetovo kritérium. Je to obecně dokázaný výsledek.
- 4 Triviálně: relativní většinový systém se nikdy nedívá dál než na první preferenci.
Jak jsme metodu implementovali.
- Condorcetův vítěz na prvním místě. Pokud existuje, CondorcetPHP ho vždy dá na první místo.
- Vědomá aproximace. Přesnou Dodgsonovu metodu nenabízíme: její výpočet může být prakticky neproveditelný.
- Mez, o které je dobré vědět. Skóre bere v úvahu jen porážky. Možnost, kterou porazí všechny ostatní, se tak může umístit před možností, která prohraje jediný souboj.
K dalšímu čtení.
| Typ | Citace |
|---|---|
| Encyklopedie | Dodgson’s method Wikipedia |
| Dokumentace | Voting Methods CondorcetPHP · docs.condorcet.io |
| Článek | Approximability of Dodgson’s rule John C. McCabe-Dansted, Geoffrey Pritchard, Arkadii Slinko (2008) · Social Choice and Welfare 31(2) |
Další metody
- Schulzeho metoda Pro každou dvojici možností hledá nejsilnější cestu vítězství. Naše výchozí metoda.
- Metoda Ranked Pairs Souboje se uzamykají jeden po druhém, od nejjasnějšího po nejtěsnější, a ty, které by vytvořily cyklus, se přeskočí.
- Copelandova metoda Za každý vyhraný souboj bod, za každý prohraný bod méně. Snadno se počítá i ručně.
- Srovnání metod Vlastnosti jednotlivých metod kritérium po kritériu ve srovnání s relativním většinovým systémem.