Making Group Decisions & Forming Coalitions fileEinleitung Grundlagen Mehrheitswahl Weitere Wahlverfahren Making Group Decisions Falko Klaaˇen 22. Juni 2010 Falko Klaaˇen Making

Making Group Decisions & Forming Coalitions

Falko KlaaßenKevin Schon

22. Juni 2010

Ubersicht

1. Making Group Decisions (Falko)

2. Forming Coalitions (Kevin)

3. Klausurfragen und Diskussion

EinleitungGrundlagen

MehrheitswahlWeitere Wahlverfahren

Making Group Decisions

Falko Klaaßen

22. Juni 2010

Falko Klaaßen Making Group Decisions



Inhalt

1 Einleitung

2 Grundlagen

3 MehrheitswahlMehrheitswahlDurchfuhrung und ManipulationMehrheitsgraph

4 Weitere WahlverfahrenDie Borda-WahlSlater Ranking




Motivation

Das Treffen von Entscheidungen in einer Gruppe bedarf andererRegeln und Uberlegungen, als wenn man fur sich alleine eineEntscheidung fallen muss.

Wie kann man in einer Gruppe Entscheidungen treffen?

Welche Verfahren, Moglichkeiten, Regeln?

Eigenschaften von Wahlverfahren

Strategien, Beeinflussbarkeit, Manipulationen




Grundlegendes

Endliche Menge von Agenten: Ag = 1, . . . , n|Ag | ungerade ⇒ verhindert Unentschieden

Menge verschiedener Kandidaten bzw. Ergebnisse:Ω = ω1, ω2, . . .




Grundlegendes

Wahler haben i. A. unterschiedliche Interessen

⇒ Rangordnung der Kandidaten/ErgebnisseBsp. Agent i bevorzugt ω2 vor ω1 vor ω3 ⇒ (ω2, ω1, ω3)

Praferenz Agenten 1 bis n: $1, . . . , $n

ω i ω′ bedeutet Agent i bevorzugt ω vor ω′ in $i




Grundlegendes

Wohlfahrtsfunktion

f :∏

(Ω)× · · · ×∏

(Ω)︸︷︷︸n−mal

→∏

(Ω)




Grundlegendes

Kollektive Entscheidungsfunktion

f :∏

(Ω)× · · · ×∏

(Ω)︸︷︷︸n−mal

→ Ω




MehrheitswahlDurchfuhrung und ManipulationMehrheitsgraph

Motivation

Wahlverfahren und Durchfuhrung beeinflussen Ergebnis der Wahl:

Wie funktioniert die Mehrheitswahl?

Welche Vor- und Nachteile hat sie?

Wie beeinflusst die Durchfuhrung das Ergebnis?





Die Mehrheitswahl

Algorithmus der Mehrheitswahl:

1 Jeder Wahler gibt Praferenzliste ab

2 Zahle Erstplatzierte

3 Gewinner: Der am haufigsten Erster





Die Mehrheitswahl

Vor- und Nachteile

Vorteile:

Einfach zu implementieren

Leicht verstandlich

Nachteile:

Viele Informationen ungenutzt

Anomalien bei mehr als zwei Parteien

Beeinflussbarkeit





Beispiel einer Anomalie

Drei Parteien, 100000 Wahler:

Liberal, 43000 Wahler

Mitte, 12000 Wahler

Konservativ, 45000 Wahler

⇒ Konservativ gewinnt.Betrachten wir einmal die Praferenzlisten.






Praferenzliste der Wahler:

Liberal: ωL ωM ωK , 43000 Wahler

Mitte: ωM ωL ωK , 12000 Wahler

Konservativ: ωK ωM ωL, 45000 Wahler

Frage: Was fallt auf?






Praferenzliste der Wahler:




Frage: Was fallt auf?

55% der Wahler lehnen die Konservativen ab!





Das Condorcet-Paradoxon


Es gibt Situationen in denen die Mehrheit unzufrieden sein wird,unabhangig vom Gewinner der Wahl.

Wie konnte so ein Fall aussehen?






Ω = ω1, ω2, ω3 mogliche ErgebnisseAg = 1, 2, 3 Wahler mit Praferenzen:

1 ω1 1 ω2 1 ω3

2 ω3 2 ω1 2 ω2

3 ω2 3 ω3 3 ω1

Egal wer gewinnt, 23 der Wahler sind unzufrieden.





Durchfuhrung und Manipulation

Fragen:

Welchen Einfluss hat der Aufbau des Wahlverfahrens?

Was passiert, wenn man statt einer einzigen Wahl eine Reihevon Wahlen durchfuhrt?

Kann man den Ausgang einer Wahl manipulieren, indem mandie Reihenfolge andert?





Sequentielle Mehrheitswahl


Gewinner tritt gegen nachsten Kandidaten an

Gesamtsieger ist Gewinner der letzten Wahl






Ein Beispiel:

Reihenfolge: ω2, ω3, ω4, ω1





Bedeutung der Reihenfolge

Frage: Welche Bedeutung hat die Reihenfolge?





Bedeutung der Reihenfolge

Frage: Welche Bedeutung hat die Reihenfolge?

Je weiter vorne, umso mehr Wahlen zu bestreiten.

⇒ Reihenfolge kann Ergebnis andern

Frage: Wie legt man die Reihenfolge fest?

Zufallig? ⇒ Gluck oder Pech beeinflussen Wahlausgang

Bestimmt durch Wahlkommitee? ⇒ Manipulation moglich

Ordne Gegner nach GefahrlichkeitGefahrlichste Gegner zuerstEigene Kandidat zuletzt





Der Mehrheitsgraph

Es reicht zu wissen, wer wen besiegt. ⇒ Mehrheitsgraph

Der Mehrheitsgraph

Gerichteter Graph mit Kandidaten in Knoten

Kante zeigt vom Sieger zum Besiegten

Graph komplett ⇒ ωi , ωj Ergebnisse, dann besiegt ωi ωj oderumgekehrt.

Asymmetrie: Besiegt ωi ωj , dann kann ωj niemals ωi besiegen.

Irreflexibilitat: Ergebnis besiegt sich niemals selber.





Ein Beispiel

99 Wahler

3 Kandidaten: ω1, ω2, ω3

33 Wahler bevorzugen: ω1 i ω2 i ω3







Ein Beispiel

Der Mehrheitsgraph sieht dann so aus:

Was fallt auf?





Ein Beispiel

Der Mehrheitsgraph sieht dann so aus:

Was fallt auf?

Der Graph enthalt einen Zyklus.⇒ Wir konnen bestimmen wer gewinnen soll!





Ein Beispiel

ω1 siegt bei: ω3, ω2, ω1

Frage: Bei welcher Reihenfolge gewinnt ω2 bzw. ω3?





Noch ein Beispiel

Ein weiterer Mehrheitsgraph:

Frage: Bei welcher Reihenfolge gewinnt ω4?





Noch ein Beispiel

Ein weiterer Mehrheitsgraph:

Frage: Bei welcher Reihenfolge gewinnt ω4?Bei ω1, ω3, ω2, ω4 oder ω3, ω1, ω2, ω4.




Die Borda-WahlSlater Ranking

Die Borda-Wahl

Bei Mehrheitswahl nur Erstplatzierte beachtet ⇒ viel Informationvernachlassigt.

Die Borda-Wahl

k Kandidaten, |Ω| = kJedem Kandidat wird Wert zugeordnet:

1 Betrachte jede Praferenzliste

2 Wenn ωi Erster, erhohe Wert von ωi um k − 1

3 Zweite erhalt k − 2

4 usw. Letzter bekommt 0 Punkte

5 Reihenfolge hangt von erhaltenen Punkten ab





Die Borda-Wahl

Nochmal das Beispiel von der Anomalie:




Wie sahe das Ergebnis bei der Borda-Wahl aus?





Die Borda-Wahl

Nochmal das Beispiel von der Anomalie:




Wie sahe das Ergebnis bei der Borda-Wahl aus?

1 Mitte: 112000 Punkte

2 Liberal: 98000 Punkte

3 Konservativ: 90000 Punkte





Slater Ranking

Ziel: Minimierung der Diskrepanz zwischen Mehrheitsgraph undder kollektiver Entscheidung durch:

Eliminieren von Zyklen.

Erzeugen einer stimmigen Rangfolge.

Bestimmen der Abweichung vom Ideal.





Slater Ranking

Slater Ranking

1 Betrachte alle moglichen Reihenfolgen.

2 Bestimme Abweichung zwischen Reihenfolge undMehrheitsgraph.

3 Kosten = Anzahl der Kanten, die umgedreht werden mussen.

4 Wahle Reihenfolge mit geringsten Kosten.





Slater Ranking

Reihenfolge: ω1 ∗ ω3 ∗ ω2 ∗ ω4

Reihenfolge stimmt mit Mehrheitsgraph uberein ⇒ Kosten: 0.





Slater Ranking

Reihenfolge: ω1 ∗ ω2 ∗ ω4 ∗ ω3

Graph hat Zyklus ⇒ Jede Reihenfolge weicht vom Graph ab.

Kante ω4 → ω1 umdrehen ⇒ Kosten: 1.

Kante ω3 → ω4 umdrehen ⇒ Kosten: 2.





Mindmap


Forming CoalitionsGrundzuge und Anwendung kooperativer Spieltheorie

Kevin Schon

22. Juni 2010

Erinnert ihr euch an folgende Situation?

IIC D

IIIII

Wodurch konnte das Dilemma aufgelost werden?

bindende Vereinbarungen undkeine direkte Gewinnauszahlung an das Individuum!

Erinnert ihr euch an folgende Situation?

IIC D

IIIII

Wodurch konnte das Dilemma aufgelost werden?

bindende Vereinbarungen undkeine direkte Gewinnauszahlung an das Individuum!

Forming Coalitions

Paradigmen und Begriffe

Kooperationszyklus

Koalitionsbildung

Gewinnaufteilung

Spielvarianten

Ubersicht


Kooperationszyklus

Koalitionsbildung

Gewinnaufteilung

Spielvarianten


Voraussetzung fur kooperative Spiele

Moglichkeit bindender Vereinbarungenuber Handlungen und die Gewinnaufteilung

zwischen weiterhin rational handelnden Akteuren (Agenten), dieihren eigenen Gewinn maximieren wollen.


KoalitionGruppe aus Agenten

Große KoalitionGruppe aller Agenten

Einzelkoalitionein Agent


kooperatives Spielbesteht aus Agenten und einer Spielfunktion

Spielfunktionordnet jeder moglichen Koalition einen Gewinn zu

Ubersicht


Kooperationszyklus

Koalitionsbildung

Gewinnaufteilung

Spielvarianten

Kooperationszyklus

Agenten(= Ressourcen + Fähigkeiten + Ziele)

Koalitionen(= Gruppen aus Agenten)

Teams(= Koali<onen + Pläne)

Koalitionsbildung

Teambildung

Gewinn

Handlungen Gewinn-verteilung

Ubersicht


Kooperationszyklus

Koalitionsbildung

Gewinnaufteilung

Spielvarianten

Koalitionsbildung

Versucht, rational zu denken! :-)

Warum wurdet ihr in einer Gruppe statt alleine arbeiten?

$

$ $ $ $

Weil ihr fur euch einen Gewinn gegenuber der Arbeit alleineerwartet!

Koalitionsbildung

Immer noch rational denken! :-)

Mit welcher Gruppe wurdet ihr arbeiten?

$ $ $ $?$ $$ $

$ $

$ $

$ $

Mit der Gruppe, die am meisten Gewinn verspricht!

Koalitionsbildung

Alle Agenten handeln jedoch genauso!

Fur eine bestimmte Koalition mussen alle Mitglieder keinenVorteil davon haben, in einer anderen Koalition zu sein!

Koalitionsbildung

Stabilitatnotwendige, aber nicht unbedingt hinreichende Bedingung fur dieBildung einer bestimmten Koalition

Gewinnaufteilungmuss sowohl moglich, als auch effizient sein(vollstandige Gewinnallokation)

KernMenge aller Gewinnaufteilungen auf die Mitglieder,die von keinem der Mitglieder abgelehnt werden

kleines Zahlenbeispiel

Agent Lila und Agent Blau konnen alleine jeweils 4 verdienen.Die Koalition aus beiden kann 10 verdienen.

0|10

1|9

2|83|7

10|0 9|1

8|2

7|3

4|6

5|5

6|4

Möglichkeiten der Gewinnaufteilung

0|10

1|9

2|8

3|7

10|0

9|1

8|2

7|3

4|6

5|5

6|4

Agent Lilaallein besser gestellt

0|10

1|9

2|8

3|7

10|0

9|1

8|2

7|3

4|6

5|5

6|4

0|10

1|9

2|8

3|7

10|0

9|1

8|2

7|3

4|6

5|5

6|4


Agent Blauallein besser gestellt

0|10

1|9

2|8

3|7

10|0

9|1

8|2

7|3

4|6

5|5

6|4



beide in Koalitionmindestens gleichoder besser gestellt als allein

$ $$ $


0|10

1|9

2|8

3|7

10|0

9|1

8|2

7|3

4|6

5|5

6|4


beide in Koalitionmindestens gleichoder besser gestellt als allein

$ $$ $DER KERN

Koalitionsbildung

Fur eine bestimmte Koalition mussen alle Mitglieder keinen Vorteildavon haben, in einer anderen Koalition zu sein!

wird zu

Eine Koalition ist stabil, wenn der Kern nicht leer ist.

Ubersicht


Kooperationszyklus

Koalitionsbildung

Gewinnaufteilung

Spielvarianten

Gewinnaufteilung

Anforderungen an eine gerechte Gewinnaufteilung

Symmetriegleiche Beitrage fuhren zu gleicher Gewinnbeteiligung

Dummy-Spielererzeugt ein Spieler keinen Synergieeffekt, wird er nur um denBetrag beteiligt, den er alleine verdienen konnte

Additivitatder Gewinn aus mehreren Spielen wird durch Addition kumuliert,es gibt keinen Vorteil durch mehrfaches Spielen

Shapley-Wert

ordnet jedem Agenten eine Gewinnbeteiligung zu, die diegenannten Anforderungen erfullt

entspricht dem Durchschnitt des marginalen Beitrags zurKoalition, berechnet uber alle moglichen Beitrittsreihenfolgen indie Koalition

Warum Beitrittsreihenfolgen? Je nach Stelle des Beitrittsunterscheidet sich die Veranderung des Koalitionsgewinns durchden Beitritt!

Shapley-Wert

Formel

shi = 1|Ag |!

∑o∈

∏(Ag)

µi(Ci(o))

Ag : Menge aus Agenten z.B. 1, 2∏(Ag): Menge aller Sortierungen z.B. (1, 2), (2, 1)

µi : marginaler Beitrag des Agenten i

Ci (o): Anhand Sortierung o vor Agent i beigetretene Agenten

Shapley-Wert

kleines Zahlenbeispiel

v : Gewinn

v(1) = 5; v(2) = 5; v(1, 2) = 20

µ1(∅) = 5; µ1(2) = 15; µ2(∅) = 5; µ2(1) = 15

sh1 = sh2 = (5 + 15)/2 = 10

Ubersicht


Kooperationszyklus

Koalitionsbildung

Gewinnaufteilung

Spielvarianten

Qualitative Koalitionsspiele

Agenten haben Mengen von Zielen

Koalitionen haben Mengen von Optionen

Ein Agent ist zufrieden mit einer Menge von Zielen, wenn mind.eines seiner Ziele erreicht wird

Eine Menge von Zielen ist machbar fur eine Koalition, wenn sieTeil ihrer Optionen ist

Eine Koalition ist erfolgreich, wenn sie alle ihre Mitgliederzufrieden stellt

Coalition Structure Formation

statt Gewinnmaximierung durch einzelne Agenten, Maximierungder sozialen Wohlfahrt, des Gesamtnutzens

System bestimmt zu bildende Koalition, also jene mit großtemGesamtnutzen

Klausurfragen

Wie lautet der Algorithmus der Borda-Wahl?

Warum ist die Reihenfolge bei der sequentiellen Mehrheitswahl vonBedeutung?

Wann spricht man von einer stabilen Koalition? Verwende dasKonzept des Kern zur Erlauterung!

Welche Große wird durch den Shapley-Wert bestimmt und nachwelchem grundsatzlichen Ansatz?

Diskussion

Haltet ihr die Borda-Wahl fur gerechter als eine einfacheMehrheitswahl?

Sind Verteilungsfragen wirklich”intuitiv“ zu beantworten? Wer

konnte hier, vor allem in einem offenen System, Entscheidungentreffen?

Danke fur die Aufmerksamkeit!

Documents

Making Group Decisions & Forming Coalitions fileEinleitung Grundlagen Mehrheitswahl Weitere Wahlverfahren Making Group Decisions Falko Klaaˇen 22. Juni 2010 Falko Klaaˇen Making