Maximallotterien

Maximale Lotterien sind eine probabilistische Wahlregel , die mit Ranglistenstimmzetteln arbeitet und ein Losverfahren unter den Kandidaten auswählt, das die Mehrheit der Wähler im Durchschnitt allen anderen Kandidaten vorzieht. Formaler ausgedrückt: Die Regel hat die Eigenschaft, dass im Durchschnitt über eine Reihe wiederholter direkter Duelle mindestens die Hälfte aller Wähler das Ergebnis einer maximalen Lotterie dem Ergebnis einer anderen Wahlregel vorziehen wird . ^{[ 1 ]}

Maximale Lotterien erfüllen eine Vielzahl wünschenswerter Eigenschaften: Sie wählen den Condorcet-Gewinner mit Wahrscheinlichkeit 1, sofern dieser existiert ^{[ 1 ]} , und wählen niemals Kandidaten außerhalb der Smith-Menge ^{[ 1 ]} . Darüber hinaus erfüllen sie die Prinzipien der Verstärkung ^{[ 2 ]} , der Partizipation ^{[ 3 ]} und der Unabhängigkeit von Klonen ^{[ 2 ]} . Die probabilistische Wahlregel, die ausschließlich maximale Lotterien liefert, ist die einzige Regel, die Verstärkung, Condorcet-Konsistenz und Unabhängigkeit von Klonen erfüllt ^{[ 2 ]} . Die soziale Wohlfahrtsfunktion , die maximale Lotterien an die Spitze setzt, wurde eindeutig mithilfe von Arrows Unabhängigkeit von irrelevanten Alternativen und Pareto-Effizienz charakterisiert ^{[ 4 ]} .

Maximale Lotterien erfüllen nicht die Standardvorstellung von Strategieresistenz, da Allan Gibbard gezeigt hat, dass nur zufällige Diktaturen Strategieresistenz und ex-post-Effizienz gewährleisten können. ^{[ 5 ]} Maximale Lotterien sind zudem nicht-monoton in den Wahrscheinlichkeiten, d. h., die Wahrscheinlichkeit einer Alternative kann sinken, wenn ein Wähler diese Alternative höher einstuft. ^{[ 1 ]} Sie erfüllen jedoch relative Monotonie, d. h., die Wahrscheinlichkeit von A relativ zu der von B sinkt nicht, wenn A gegenüber B verbessert wird . ^{[ 6 ]}${\displaystyle x}$${\displaystyle y}$${\displaystyle x}$${\displaystyle y}$

Die Unterstützung maximaler Lotterien, die als essentielles Set oder dieDas überparteiliche Set wurde detailliert untersucht. ^{[ 7 ] [ 8 ] [ 9 ] [ 10 ]}

Maximallotterien wurden erstmals 1965 von dem französischen Mathematiker und Sozialwissenschaftler Germain Kreweras vorgeschlagen ^{[ 11 ]} und von Peter Fishburn popularisiert . ^{[ 1 ] Seitdem wurden sie mehrfach von Ökonomen [ 8 ]} , Mathematikern ^{[ 1 ] [ 12 ]} , Politikwissenschaftlern, Philosophen ^{[ 13 ]} und Informatikern ^{[ 14 ]} wiederentdeckt .

In Biologie, Physik, Chemie und maschinellem Lernen wurden verschiedene natürliche Dynamiken beobachtet, die zu maximalen Lotterien konvergieren. ^{[ 15 ] [ 16 ] [ 17 ]}

Die Eingangsdaten für dieses Abstimmungssystem bestehen aus den ordinalen Präferenzen der Akteure bezüglich der Ergebnisse (nicht aus Lotterien bezüglich Alternativen). Es lässt sich jedoch eine Relation auf der Menge der Lotterien folgendermaßen konstruieren: Wenn und Lotterien bezüglich Alternativen sind, dann ist der Erwartungswert des Siegesvorsprungs eines mit Verteilung ausgewählten Ergebnisses in einer direkten Abstimmung gegen ein mit Verteilung ausgewähltes Ergebnis positiv. Anders ausgedrückt: Es ist wahrscheinlicher, dass ein zufällig ausgewählter Wähler die aus gezogene Alternative der aus gezogenen Alternative vorzieht als umgekehrt. ^{[ 4 ]} Diese Relation ist zwar nicht notwendigerweise transitiv, besitzt aber stets mindestens ein maximales Element. ${\displaystyle p}$${\displaystyle q}$${\displaystyle p\succ q}$${\displaystyle p}$${\displaystyle q}$${\displaystyle p\succ q}$${\displaystyle p}$${\displaystyle q}$

Es ist möglich, dass aufgrund von Stimmengleichständen mehrere solcher maximaler Lotterien existieren. Die maximale Lotterie ist jedoch immer dann eindeutig, wenn die Anzahl der Wähler ungerade ist. ^{[ 18 ]} Aus demselben Grund ist die bipartisanische Menge eindeutig definiert, indem man den Träger der eindeutigen maximalen Lotterie nimmt, die ein Turnierspiel löst. ^{[ 8 ]}

Maximale Lotterien entsprechen gemischten Maximin-Strategien (oder Nash-Gleichgewichten ) des symmetrischen Nullsummenspiels, das durch die paarweisen Mehrheitsmargen gegeben ist. Daher lassen sie sich auf natürliche Weise im Kontext des Wahlwettbewerbs zwischen zwei politischen Parteien interpretieren ^{[ 19 ]} und können in Polynomialzeit mittels linearer Programmierung berechnet werden.

Angenommen, es gibt fünf Wähler, die folgende Präferenzen bezüglich dreier Alternativen haben:

• 2 Wähler:${\displaystyle a\succ b\succ c}$
• 2 Wähler:${\displaystyle b\succ c\succ a}$
• 1 Wähler:${\displaystyle c\succ a\succ b}$

Die paarweisen Präferenzen der Wähler können in der folgenden schiefsymmetrischen Matrix dargestellt werden , wobei der Eintrag für Zeile und Spalte die Anzahl der Wähler angibt, die Option bevorzugen, abzüglich der Anzahl der Wähler, die Option bevorzugen . ${\displaystyle x}$${\displaystyle y}$${\displaystyle x}$${\displaystyle y}$${\displaystyle y}$${\displaystyle x}$

${\displaystyle {\begin{matrix}{\begin{matrix}&&a\quad &b\quad &c\quad \\\end{matrix}}\\{\begin{matrix}a\\b\\c\\\end{matrix}}{\begin{pmatrix}0&1&-1\\-1&0&3\\1&-3&0\\\end{pmatrix}}\end{matrix}}}$

Diese Matrix kann als Nullsummenspiel interpretiert werden und besitzt ein eindeutiges Nash-Gleichgewicht (oder eine Minimax-Strategie ) , wobei , , . Definitionsgemäß ist dies auch die eindeutige maximale Lotterie des obigen Präferenzprofils. Das Beispiel wurde bewusst so gewählt, dass es keinen Condorcet-Gewinner gibt . Viele Präferenzprofile weisen einen Condorcet-Gewinner auf; in diesem Fall ordnet die eindeutige maximale Lotterie dem Condorcet-Gewinner die Wahrscheinlichkeit 1 zu. Wenn der letzte Wähler im obigen Beispiel die Alternativen und in seiner Präferenzrelation tauscht, wird zum Condorcet-Gewinner und mit Wahrscheinlichkeit 1 ausgewählt. ${\displaystyle p}$${\displaystyle p(a)=3/5}$${\displaystyle p(b)=1/5}$${\displaystyle p(c)=1/5}$${\displaystyle a}$${\displaystyle c}$${\displaystyle a}$

• voting.ml (Website zur Berechnung der maximalen Lotterieergebnisse)