Rangsorolt párok
A rangsorolt párok (néha „RP”) vagy másképp a Tideman-módszer egy Nicolaus Tideman által 1987-ben kifejlesztett választási rendszer, amely a preferenciákat kifejező szavazatok alapján választ ki egyetlen győztest.[1][2] A rangsorolt párok eljárása használható a nyertesek rendezett listájának létrehozására is.
Ha van egy jelölt, akit előnyben részesítenek a többi jelölttel szemben a választók, akkor a rangsorolt páros eljárás garantálja, hogy ez a jelölt nyer. Emiatt a tulajdonság miatt a rangsorolt párok eljárása megfelel a Condorcet-kritériumnak (és így egy Condorcet-módszer).[3]
Eljárás
A rangsorolt párok eljárása a következőképpen működik:
- A szavazatok összeszámlálása a lehetséges jelöltpárokba való rendezéssel, a párok győzteseinek meghatározása (feltéve, hogy nincs döntetlen).
- A egyes párok sorba rendezése a győzelmek erőssége (többletszavazatok száma) szerint.
- A párok „zárolása”. Ez egy olyan gráf létrehozását jelenti, amelynek a csúcsait az egyes jelöltpárok képezik, és az élei az erősebb győzelmek irányából a gyengébb győzelmek irányába mutatnak. A gráfhoz a 2. pontban meghatározott sorrendben kell hozzáadni az éleket úgy, hogy az új csúcsok ne zárjanak be a korábbi csúcsokhoz mutató éleikkel ciklusokat (elkerülve így a kő-papír-olló helyzeteket). Az elkészült gráf forrása a győztes, illetve a győztesek sorrendje is kimutatható belőle az egyes csúcsokba és csúcsoktól elmutató élek aránya alapján.
Megjegyzés: a számlálás során a szavazatok számainak tényleges értéke és a szavazatok százalékos aránya egyaránt használható. Ugyanaz lesz az eredmény, mivel a szavazatok aránya számít.
Egy példa
A választók w, x, y, z jelöltekre szavazhatnak. Egy szavazólapra lehetséges példák ebben az esetben:
| Kérem, hogy a preferenciája sorrendjében ragassza be a rendelkezésére bocsátott jelöltmatricákat! (A legkedveltebb jelölt legyen a legelső, a legkevésbé kedvelt az utolsó). | |
|---|---|
| 1. | z |
| 2. | w |
| 3. | y |
| 4. | x |
| Kérem, hogy x-elje be a jelölteket a preferenciája sorrendjében (1-es a legkedveltebb jelölt, 2-es a második legkedveltebb jelölt, stb.) | ||||
|---|---|---|---|---|
| 1 | 2 | 3 | 4 | |
| w | × | |||
| x | × | |||
| y | × | |||
| z | × | |||
Miután minden szavazó leadta a szavazatát, az egyes sorrendeket össze kell számolni, aminek az eredménye a példánkban (a > relációs jeltől balra található fél előrébb van sorolva, mint a jobbra található):
| w > x > y > z | 7 szavazólap |
| w > y > x > z | 2 szavazólap |
| x > y > z > w | 4 szavazólap |
| x > z > w > y | 5 szavazólap |
| y > w > x > z | 1 szavazólap |
| y > z > w > x | 8 szavazólap |
A szavazatok páronkénti eloszlásai egy mátrixban (táblázatban) foglalhatóak össze. Ebben a táblázatban a soronként mennek a jelöltek, és az egyes oszlopok azt mutatják, hogy a sorban található jelölt az oszlopokban látható jelölteket hány esetben győzte le (negatív számmal jelölve, ha veszített). Pl. az első sor második oszlopa a következőképpen számolható:
| Rangsor | szavazatok száma | Győzött (+) vagy vesztett-e (-) w? | Pontszám |
| w > x > y > z | 7 szavazólap | w előrébb van x-nél, tehát pozitív előjel | +7 |
| w > y > x > z | 2 szavazólap | w előrébb van x-nél, tehát pozitív előjel | +2 |
| x > y > z > w | 4 szavazólap | w az x-hez képest hátrébb van sorolva, tehát negatív előjel | -4 |
| x > z > w > y | 5 szavazólap | w az x-hez képest hátrébb van sorolva, tehát negatív előjel | -5 |
| y > w > x > z | 1 szavazólap | w előrébb van x-nél, tehát pozitív előjel | +1 |
| y > z > w > x | 8 szavazólap | w előrébb van x-nél, tehát pozitív előjel | +8 |
A pontszámok összege: +7+2-4+5+1+8=9. Tehát a táblázat (w, x) cellája 9 lesz.
Ugyanígy végigszámolva a többi cellára a páronkénti szavazateloszlás:
| w | x | y | z | |
|---|---|---|---|---|
| w | 0 | 9 | 1 | –7 |
| x | –9 | 0 | 5 | 11 |
| y | –1 | –5 | 0 | 3 |
| z | 7 | –11 | –3 | 0 |
Ennek a táblázatnak a főátlója értelemszerűen 0-kból áll (magukkal szemben nem győznek és nem veszítenek a jelöltek). Emellett a táblázat ferdén szimmetrikus, mivel minden győzelem a másik oldalon egy ugyanakkora veszteség, tehát elegendő csak az egyik felét kiszámolni.
Sorba rendezés
A táblázat pozitív többségeit ezután csökkenő sorrendbe rendezzük:
| Sorszám | Győztes | Vesztes | Győzelem erőssége |
|---|---|---|---|
| 1. | x | z | 11 |
| 2. | w | x | 9 |
| 3. | z | w | 7 |
| 4. | x | y | 5 |
| 5. | y | z | 3 |
| 6. | w | y | 1 |
Zárás
A legerősebb győzelmet x-z páros mutatta fel, így x lesz a gráf első csúcsa, amiből az első él z-be mutat.
A 2.legerősebb győzelmet a w-x páros tudhatja magáénak anélkül, hogy ellentmondásba keveredne a korábbi győzelmekkel. A következő csúcs így w lesz, amiből x-be mutat egy él.
A 3. sorszámú győzelem z-t illetné meg a w-vel szemben, de ez ellentmond a korábbi két csúcsnak, amelyek alapján z-nél erősebb x és w szintén erősebb, mint x. A gráfon ez úgy mutatkozik, hogy x, w és z ebben a lépésben egy ciklust alkotna (hasonlóan egy kő-papír-olló helyzethez). ezért ezt az élet figyelmen kívül hagyjuk.
A 4. sorszámú győzelem alapján x-ből kell y-ba húzni a gráfon egy élet. Ez nem mond ellent a korábbi, erősebb győzelmeknek, nem zár be ciklust, tehát ez az él érvényes.
Az 5. győzelem szerint egy y-ból z-be mutató él következik, ami nem alkot újabb ciklust, így behúzható.
Végül egy w-ből y-ba irányuló él következik, ami szintén érvényes. A folyamatot a következő animáció illusztrálja:
Győztes
A zárolt párok gráfjának a forrása a nyertes, jelen esetben w. Az ezt követő helyezések úgy rangsorolhatóak, hogy az egyes résztvevőkből hány él mutat el (minél több, annál feljebb kerülnek a végeredményben), illetve hány él mutat rájuk (minél több, annál lejjebb kerülnek az eredményben):
A második helyezett x egy rámutató éllel, és kettő elmutató éllel. A harmadik helyezett y egy elmutató, illetve kettő rámutató éllel. Utolsó helyen z végzett, elmutató élek nélkül, két ráirányuló éllel.
Tulajdonságok
- Többségi kritérium
- Többségi vesztes kritérium
- Monotonitási kritérium
- Kölcsönös többségi kritérium
- Smith-kritérium (amely magában foglalja a Condorcet-kritériumot)
- Condorcet-vesztes kritérium
- klónok függetlenségének kritériuma
- A rangsorolt párok nem függetlenek az irreleváns alternatívától. A módszer azonban egy kevésbé szigorú tulajdonságot kielégít, amelyet Smith-dominated alternatives (ISDA) függetlenségnek neveznek.Ez szerint ha egy jelölt (X) nyer egy választást, és egy új alternatívát (Y) adunk hozzá, X nyeri a választást, ha Y nincs a Smith halmazban. Az ISDA szintén magában foglalja a Condorcet-kritériumot.
- Lokális függetlenség az irreleváns alternatíváktól.
- Fordításra szimmetrikus
- A döntetlen eredmény feloldható
Hivatkozások
Fordítás
Ez a szócikk részben vagy egészben a Ranked pairs című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
További információk
- Rob LeGrand rangsorolt szavazási módszereinek leírása
- Példa JS implementációra, Asaf Haddad
- Páros rangsor Ruby Gem, Bala Paranj
- A Tideman rangsorolt párjainak margin alapú PHP megvalósítása
- Cory Dickson Ranked Pairs Rust implementációja