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:

1. 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).
2. A egyes párok sorba rendezése a győzelmek erőssége (többletszavazatok száma) szerint.
3. 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:

Első példa

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

Második példa, ugyanazzal a leadott szavazattal

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

1. Tideman (1987. szeptember 1.). „Independence of clones as a criterion for voting rules” (angol nyelven). Social Choice and Welfare 4 (3), 185–206. o. DOI:10.1007/BF00433944. ISSN 1432-217X. 
2. Schulze (2003. október 1.). „A New Monotonic and Clone-Independent Single-Winner Election Method”. Voting matters (www.votingmatters.org.uk) 17, Kiadó: McDougall Trust. [2020. július 11-i dátummal az eredetiből archiválva]. (Hozzáférés: 2021. február 2.) 
3. Munger (2022. január 20.). „The best Condorcet-compatible election method: Ranked Pairs”. Constitutional Political Economy. DOI:10.1007/s10602-022-09382-w. 

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