Arrows Unmöglichkeitssatz

Arrows Unmöglichkeitssatz
Olga Heismann
Linus Mattauch
CdE-PfingstAkademie 2012
1
Einführung
Die Essenz der Arrowschen Unmöglichkeit ist das Condorcet-Paradoxon (1785):
Wenn drei Wähler ihre Präferenzen über drei Wahlmöglichkeiten angeben,
kann es vorkommen, dass eine Mehrheitswahl, bei der paarweise über Alternativen abgestimmt wird, ein zyklisches Ergebnis liefert, also keinen Sieger.
1.1
Hinführung: Die normative Grundlage der Sozialwahltheorie
• Definition: Sozialwahltheorie untersucht auf formale Weise die Möglichkeiten, individuelle Präferenzen oder Urteile zu gesellschaftlichen
Bewertungen oder Entscheidungen zu aggregieren. (Social choice theory wird bisweilen auch als „Theorie bzw. Logik kollektiver Entscheidungen“ übersetzt.)
• Sozialwahltheorie ist eine normative Theorie, baut daher auf Prinzipien
der Moralphilosophie auf.
• Sozialwahltheorie ist konsequentialistisch: Bewertet werden Zustände
der Welt, gesucht wird das beste Ergebnis. Unter den drei großen Strömungen gegenwärtiger Moralphilosophie steht Konsequentialismus im
Gegensatz zu Deontologie und Kontraktualismus.
1.2
Historischer Hintergrund
• Frühe Gedanken über demokratische Gruppenentscheidungen: JeanCharles de Borda (1733–1799) und Marie Jean Caritat Marquis de
Condorcet (1743-1794).
• Frühe Wohlfahrtstheorie: Utilitarismus nach Jeremy Bentham (1748–
1832)
• Wohlfahrtstheorie im 19. Jahrhundert: Ist Nutzen kardinal? Ist der
Nutzen verschiedener Menschen vergleichbar?
1
• Wohlfahrtstheorie in der ersten Hälfte des 20. Jahrhunderts (nach Abrahm Bergson und Paul Samuelson): Welche Entscheidungen Individuen treffen, offenbart ihre Präferenzen. Gesellschaftliche Wohlfahrt
kann allein durch die Aggregation von individuellen Präferenzordnungen bestimmt werden. Der Nutzen, den verschiedene Individuen von
einem Zustand haben, ist nicht vergleichbar.
• Sozialwahltheorie: Begründet durch Kenneth Arrow (*1921), der den
nach ihm benannten Unmöglichkeitssatz im Rahmen seiner Dissertation (Arrow, 1950, 1951) bewies.
2
Arrows Unmöglichkeitssatz
2.1
Heuristische Darstellung
Eine soziale Wohlfahrtsfunktion (SWF) bewertet Zustände der Welt nach
ihrem Nutzen bzw. nach den Präferenzen der Individuen.
Arrows Idee: Betrachte verschiedene normative Anforderungen an eine
ordinale SWF: eine SWF, die Präferenzen von Individuen so ordnet, dass eine
soziale Präferenzordnung entsteht. Ergebnis: Unter milden Anforderungen ist
eine Aggregation unmöglich.
Arrows Anforderungen an eine Wohfahrtsfunktion:
• (P) Pareto Prinzip: Wenn jedes Individuum Option A lieber als Option
B mag, dann ist A besser als B (nach Vilfredo Pareto).
• (U) Unabhängigkeit irrelevanter Alternativen: Ob A sozial besser ist
als B, soll nur von der individuellen Bewertung von A und B, und von
nichts anderem abhängen.
• (UB) Unbeschränkter Definitionsbereich: Jegliche individuelle Präferenzen müssen zulässig sein.
• (CR) Das Ergebnis der Bewertung durch die SWF muss „rational“ sein:
alle Optionen müssen vergleichbar sein und in eine Reihenfolge gebracht werden können.
• (D) Keine Diktatur: Die soziale Präferenzordnung darf nicht nur von
den Präferenzen eines einzigen Individuums abhängen.
Arrows Unmöglichkeitssatz: Es gibt keine ordinale SWF, die (P),
(U), (UB), (CR) und (D) erfüllt.
2
2.2
Interpretation
„Der einzige universal anwendbare Mechanismus, individuelle Präferenzen
über Zustände zu einer gesamtgesellschaftlichen Präferenz zu aggregieren,
ist, ein Individuum zum Diktator zu machen.“ (Hausman and McPherson,
2006, S. 220)
Was wird aggregiert und wozu? Welche Art von Aggregationsmechanismus angemessen scheint, hängt vom Input und vom Zweck der Aggregation ab!
Bewertung
Entscheidung
Präferenzen
präferenzbasierte
präferenzbegründete
Bewertung (1.)
Entscheidung (2.)
Urteile
urteilsbasierte
urteilsbegründete
Bewertung (3.)
Entscheidung (4.)
(Hausman and McPherson, 2006, Kap. 12)
1. Z. B.: Präferenzutilitarismus der Volkswirtschaftslehre
2. Unfaire Entscheidungsmethode
3. Unüberzeugende Urteilsfindung
4. Z. B.: Demokratische Entscheidungsfindung
Umgang mit der Unmöglichkeit
• Die Unmöglichkeit zeigt überhaupt erst auf, welche Möglichkeiten von
Präferenzaggregation denkbar sind. Ohne Unmöglichkeitsresultat gibt
es keinen Maßstab dafür, wie erfolgreich ein Aggregationsverfahren sein
kann. Daher: Zweck der Sozialwahltheorie ist es, die Möglichkeiten von
Aggregationen und ihre nötige Informationsgrundlage besser zu verstehen (Sen, 1999, Nobel Lecture).
• top-down und bottom-up Begründungen für die Wahl von Axiomen.
• Unterschiedliche Wege, die Unmöglichkeit zu umgehen, werden unterschiedlich überzeugend sein für präferenzbasierte Bewertung (Anwendung: Wohlfahrtsmessung) und urteilsbasierte Entscheidungsfindung
(Anwendung: Wahlverfahren).
3
2.3
Formalisierung
Definition 2.1 (Präferenzordnung). Sei X eine Menge von gesellschaftlichen Allokationen und die Präferenzrelation R ⊆ X × X eine Menge von
geordneten Paaren von gesellschaftlichen Allokationen aus X.
Wir schreiben für (x1 , x2 ) ∈ R auch x1 %R x2 und x2 -R x1 . Weiterhin
schreiben wir x1 ∼R x2 , falls (x1 , x2 ), (x2 , x1 ) ∈ R, sowie x1 R x2 und
x2 ≺R x1 , falls x1 %R x2 , aber nicht x1 %R x2 .
%R heißt eine rationale Präferenzrelation oder Präferenzordnung auf X,
falls gilt:
1. %R ist vollständig, d. h., für alle x1 , x2 ∈ X ist x1 %R x2 oder x2 %R x1 .
2. %R ist transitiv, d. h., für alle x1 , x2 , x3 ∈ X folgt aus x1 %R x2 und
x2 %R x3 , dass x2 %R x3 .
Definition 2.2 (Soziale Wohlfahrtsfunktion). Sei X eine Menge von gesellschaftlichen Allokationen, R die Menge aller Präferenzordnungen auf X und
{1, . . . , n} eine Menge von Individuen.
• Eine Bergson-Samuelson-Wohlfahrtsfunktion ist eine Abbildung
W : RN → R, W : (u1 (x), ..., un (x)) 7→ W (u1 (x), . . . , un (x)).
• Beispiel (Soziale Wohlfahrtsfunktion
des klassischen Utilitarismus):
Pn
W (u1 (x), . . . , un (x)) = i=1 ui (x)
• Eine Arrow-Wohlfahrtsfunktion ist eine Abbildung
W : Rn → R, (%1 , . . . %N ) 7→%W .
• Eine soziale Wohlfahrtsfunktion heißt kardinal, wenn ihr Ergebnis von
den Werten der Nutzenfunktionen abhängt, sonst heißt sie ordinal. Eine
Arrow-Wohlfahrtsfunktion ist immer ordinal.
• Im Folgenden meinen wir mit einer sozialen Wohlfahrtsfunktion immer
eine Arrow-Wohlfahrtsfunktion.
Definition 2.3 (Eigenschaften einer sozialen Wohlfahrtsfunktion). Die soziale Wohlfahrtsfunktion W
• ist unabhängig von irrelevanten Alternativen (U), falls für alle x1 , x2 ∈
X und
(%1 , . . . %n ), (%01 , . . . %0n ) ∈ Rn
mit
x1 i x2 ⇔ x1 0i x2 , x1 ∼i x2 ⇔ x1 ∼0i x2 ∀i ∈ {1, . . . n}
gilt, dass
(x1 , x2 ) ∈ W (%1 , . . . %n ) ⇔ (x1 , x2 ) ∈ W (%01 , . . . %0n ),
4
d. h. die Bewertung von zwei gesellschaftlichen Allokationen durch W
hängt nur von der Bewertung dieser Allokationen durch die Individuen
ab.
• erfüllt das schwache Pareto-Prinzip (P), falls x1 i x2 für alle i ∈
{1, . . . , N } auch x1 W x2 impliziert. Das bedeutet: W bewertet x1
strikt besser als x2 , falls dies jedes Individuum tut.
• ist eine Diktatur (D), falls ein Individuum i ∈ {1, . . . n} existiert, sodass für alle x1 , x2 ∈ X mit x1 i x2 gilt: x1 W x2 , d. h., es gibt ein
Individuum, sodass, wenn es eine gesellschaftliche Allokation gegenüber einer anderen präferiert, dies auch die soziale Wohlfahrtsfunktion
tut.
Bemerkung 2.4. Das starke Pareto-Prinzip besagt, dass x1 W x2 für x1 , x2 ∈
X, falls für mindestens ein Individuum i x1 i x2 und für kein Individuum
j x2 j x1 . Das bedeutet: W bewertet x1 strikt besser als x2 , falls dies
mindestens ein Individuum tut und alle anderen x1 mindestens genau so gut
finden wie x2 .
Theorem 2.5 (Arrows Unmöglichkeitssatz (Arrow, 1950)). Sei X = {x1 , . . . xm }
eine Menge von m ≥ 3 gesellschaftlichen Allokationen, R die Menge aller
Präferenzordnungen auf X und {1, . . . , n} eine Menge von Individuen. Jede
soziale Wohlfahrtsfunktion W : Rn → R, (%1 , . . . %N ) 7→%W , die unabhängig von irrelevanten Alternativen ist und das schwache Pareto-Prinzip
erfüllt, ist eine Diktatur.
Beweisidee. Der Satz wird dadurch gezeigt, dass jede zulässige soziale Wohlfahrtsfunktion als Diktatur identifiziert wird. Wir betrachten ein spezifisches Präferenzprofil, das ein Analogon zur Präferenzstruktur im CondorcetParadoxon (siehe oben) darstellt. Der Beweis erfolgt in vier Schritten: Zuerst
wird dieses Präferenzprofil eingeführt und darauf das Ergebnis der Wohlfahrtsfunktion bestimmt. Zweitens wird gezeigt, dass es ein Individuum gibt,
dessen Präferenzen dann auf diesem Profil die Wohlfahrtsfunktion bestimmen (lokaler Diktator ). Durch ein induktives Argument, die schrittweise
Überführung jeglicher Präferenzen in das spezifische Condorcet-Präferenzprofil,
können wir drittens zeigen, dass der lokale Diktator auch ein globaler Diktator ist. Dafür muss viertens gezeigt werden, dass der lokale Diktator auch
noch für um ein Element veränderte Präferenzen das Gesamtergebnis bestimmt.
Beweis (Geanakoplos, 2005). Sei W eine soziale Wohlfahrtsfunktion, die (U)
und (P) erfüllt. Wir zeigen im Folgenden, dass sie eine Diktatur sein muss.
Schritt 1: Für jedes j ∈ {1, . . . m} nennen wir die Präferenzordnung
C
%j ∈ R mit
C
C
C
C
xj C
j · · · j xm j x1 j · · · j xj−1
5
eine Condorcet-Präferenzordnung.
Falls es ein j ∈ {1, . . . m} gibt, sodass %i =%C
j für alle i ∈ {1, . . . , N }, so
C
muss nach (P) %W =%j sein.
Es gibt damit also n-Tupel von Condorcet-Präferenzordnungen der In0
0
dividuen, für die %W =%C
1 . Sei unter diesen n-Tupeln (%1 , . . . , %n ) eines,
C
das die Anzahl der Individuen mit Präferenzordnung %1 minimiert (Minimalitätsanforderung, benötigen wir weiter unten wieder). Es muss ein Individuum i∗ geben, sodass %0i∗ =%C
1 . Ansonsten erhalten wir einen Widerspruch
zu (P), weil jedes Individuum xm gegenüber x1 präferiert, die soziale Wohlfahrtsfunktion aber nicht.
Schritt 2: Wir definieren nun
W (%i∗ ) := W (%01 , . . . , %0i∗ −1 , %i∗ , %0i∗ +1 , . . . , %0n )
und zeigen, dass i∗ ein lokaler Diktator für (%01 , . . . , %0n ) ist. Das bedeutet:
Falls für zwei gesellschaftliche Allokationen xj , xk xj i∗ xk ist, dann gilt
auch xj W (%i∗ ) xk . Wenn also alle anderen Individuen bei ihren Präferenzordnungen bleiben und i∗ xj strikt gegenüber xk präferiert, so übernimmt
dies auch die Präferenzordnung, auf welche die soziale Wohlfahrtsfunktion
abbildet.
−C
x1
· · · −C
Sei nun %i∗ =%−C
1
1 , wobei dies für das Präferenzprofil xm 1
stehe. Um die lokale-Diktator-Eigenschaft zu zeigen, reicht es nach (U), dass
−C
gilt. Denn: Dies ist eine Präferenzordnung mit der man für
W (%−C
1 ) =%1
je zwei gesellschaftliche Allokationen genau die gegenteilige Bewertung zu
∗
%C
1 erhält, und mit (U) kann i für jedes Paar unabhängig bestimmen, wie
die soziale Wohlfahrtsfunktion darüber entscheidet.
Seien xj , xj+1 ∈ X. Da nach (U)
x1 W (%C
j+1 )
. . . W (%C
j+1 )
xj
und
xj+1 W (%C
j+1 )
. . . W (%C
j+1 )
xm
und die Änderung der Präferenzordnung von i∗ nach obiger Minimalitätsanforderung der Auswahl der Profile etwas ändern muss, ist xj+1 %W (%C ) xj .
j+1
%−C
und %C
j+1 bewerten beide xj+1 höher als xj und xm höher als x1 .
1
Folglich gilt, da xj+1 %W (%C ) xj , xj+1 %W (%−C ) xj . Da dies für beliebiges
j+1
1
j gilt, erhalten wir
xm %W (%−C ) · · · %W (%−C ) x1 .
1
1
Wäre xj+1 ∼W (%C ) xj , so folgt aus der Transitivität und |X| ≥ 3 x1 W (%C )
j+1
j+1
xm . Dies widerspricht aber xm %W (%−C ) x1 . Damit ist i∗ ist ein lokaler Dik1
tator für (%01 , . . . , %0n ).
6
Schritt 3: Wir zeigen nun Folgendes: Angenommen, i∗ ist lokaler Diktator
für (%1 , . . . , %n ), wobei es für jede der Präferenzordnungen %i maximal ein
Paar von gesellschaftlichen Allokationen x1 , x2 ∈ X gibt, sodass x1 ∼ x2 .
Sei %k00 eine Präferenzordnung und seien xh , xj ∈ X, sodass %k und %k00
für alle Paare von gesellschaftlichen Allokationen, die nicht (xh , xj ) sind,
übereinstimmen, und für dieses Paar sich nur dann unterscheiden dürfen,
wenn xh ∼k xj oder xh ∼k00 xj . Dann ist i∗ auch lokaler Diktator für
(%1 , . . . , %k−1 , %k00 , %k+1 , . . . , %n ).
Das hieße, dass i∗ für jedes n-Tupel von Präferenzordnungen ein lokaler Diktator ist, denn wir erhalten jedes beliebige n-Tupel aus (%01 , . . . , %0n ), indem
wir nacheinander jede der Präferenzordnungen verändern und diese Veränderungen mit Hilfe von Änderungen von strikten Präferenzen auf Indifferenz
und dann ggf. weiter auf strikte Präferenz in die Gegenrichtung durchführen.
Damit wäre W eine Diktatur.
Schritt 4: O. b. d. A. nehmen wir an, dass i∗ xh gegenüber xj präferiert.
Da sich %k und %k00 höchstens für (xh , xj ) unterscheiden, können sich nach
(U) W (%1 , . . . , %n ) und W (%1 , . . . , %k−1 , %k00 , %k+1 , . . . , %n ) auch höchstens für dieses Paar unterscheiden. Gilt xh i∗ xl i∗ xj für irgendein
xl ∈ X, so gilt dies, da i∗ lokaler Diktator ist, auch für W (%1 , . . . , %n ).
Nach (U) muss dies dann auch für W (%1 , . . . , %k−1 , %k00 , %k+1 , . . . , %n ) gelten. Wegen Transitivität kann i∗ also auch erzwingen, dass die soziale Wohlfahrtsfunktion für
(%1 , . . . , %k−1 , %k00 , %k+1 , . . . , %n )
xh gegenüber xj präferiert, und die Aussage ist damit bewiesen.
3
3.1
Weitere Resultate der Sozialwahltheorie
Eingipflige Präferenzen
(Mas-Colell et al., 1995, Kap.21)
3.2
Gibbard-Satterthwaite-Theorem
(Svensson, 1999)
3.3
Das Paradoxon des Pareto-Liberalen
(Sen, 1970a,b)
3.4
Arrows Originalbeweis
(Mas-Colell et al., 1995, Kap. 21)
7
4
Sozialwahltheorie und Wahlverfahren
4.1
Einige Wahlverfahren
Wahlverfahren, die eine vollständige Ordnung angeben:
• Borda-Wahl (verletzt (U))
• Rangfolgewahl, engl. „Instant Runoff Voting“ (verletzt (U))
Wahlverfahren, mit denen lediglich ein einzelner Sieger bestimmt wird:
• Mehrheitswahl
• Mehrheitswahl mit instant runoff zwischen den ersten beiden
• Condorcet-Sieger (gibt es nicht immer)
• Wahl durch Zustimmung, engl. „Approval Voting“ (nur bestimmte Präferenzordnungen erlaubt)
4.2
Schulze-Methode
• Entwickelt von Markus Schulze im Jahre 1997 (Schulze, 2003, das war
die erste Publikation).
• Es wird ein einzelner Sieger bestimmt.
• Idee: Bestimme paarweise den stärksten Weg im gerichteten Graphen
paarweiser Präferenzen.
• Die Schulze-Methode verletzt (U).
• x1 wird gegenüber x2 präferiert, wenn der stärkste Weg von x1 nach
x2 stärker ist als der von x2 nach x1 , diese Relation ist transitiv.
• Die Schulze-Methode wird derzeit nicht in öffentlichen Wahlen angewandt, jedoch in zahlreichen Organisationen (Wikimedia, Piratenparteien unterschiedlicher Länder, FSFE, Debian, KDE, . . . ).
8
5
Sozialwahltheorie und Wohlfahrtsmessung
Was ist soziale Wohlfahrt? Die nachfolgende Aufstellung folgt (Fleurbaey, 2009).
Sozialphilosophische Position
Wohlfahrtskonzept
Hedonistischer Welfarismus:
Alle negativen und positiven Affekte
(„Glücksgefühle“) der Bevölkerung
Die Lebenszufriedenheit der Bevölkerung (die im Leben erreichten „Erfolge“)
Die „Verwirklichungschancen“: Die
Menge aller Möglichkeiten, die ein
Individuum hat, Tätigkeiten auszuüben oder Umstände zu verändern,
und die Zustände in seinem Umfeld.
(„Capability Approach“ nach Amartya
Sen)
Die zur Verfügung stehenden Ressourcen (ein „buchhalterisch korrigiertes
BIP“, z. B. John Rawls)
„Kognitiver“ Welfarismus:
Liberalismus – Fähigkeitsansatz:
Liberalismus – Ressourcismus:
Diese Ansätze umgehen die Arrowsche Unmöglichkeit dadurch, dass sie
entweder die Ordinalität verletzen und eine kardinale Wohlfahrtsfunktion
annehmen (Welfarismus, Liberalismus) oder die Unabhängigkeit irrelevanter
Alternativen verletzen (Liberalismus).
Ein kleines konzeptuelles Modell menschlicher Wohlfahrt
Ausblick
Literatur
Arrow, K. J. (1950). A difficulty in the concept of social welfare. Journal of
Political Economy 58, 328–346.
Arrow, K. J. (1951). Social choice and individual values. New York: Wiley.
Fleurbaey, M. (2009). Beyond GDP: The quest for a measure of social welfare. Journal of Economic Literature 47(4), 1029–1075.
Geanakoplos, J. (2005). Three brief proofs of arrow’s impossibility theorem.
Economic Theory 26(1), 211–215.
9
Hausman, D. M. and M. S. McPherson (2006). Economic Analysis, Moral
Philosophy and Public Policy (2nd ed.). Cambridge: Cambridge University
Press.
Mas-Colell, A., M. D. Whinston, and J. R. Green (1995). Microeconomic
Theory. New York: Oxford University Press.
Schulze, M. (2003). A new monotonic and clone-independent single-winner
election method. Voting Matters (17), 9–19.
Sen, A. (1970a). Collective Choice and Social Welfare. Amsterdam: Elsevier.
Sen, A. (1970b). The impossibility of a paretian liberal. The Journal of
Political Economy 78(1), 152–157.
Sen, A. (1999). The possibility of social choice. American Economic Review 89(3), 349–378.
Svensson, L.-G. (1999). The proof of the gibbard-sattherthwaite theorem
revisited. Working Paper No. 1999:1, Department of Economics, Lund
University.
10