Ein Vortrag von: Rhena Möller und Svenja Heitländer Für ... · Dominante Strategien & Nash Equlibrium Nash Equilibrium Unter der Annahme, dass Agent I s1 spielt, bleibt Agent J

Multiagent Interactions

Ein Vortrag von:Rhena Möller und Svenja Heitländer

Für das SeminarMultiagentensysteme SS09

Inhalt

Einleitung Was ist Interaktion und wie funktioniert sie?

Utility & Preferences Multiagent Encounters Dominante Strategien & Nash Equlibrium Konkurrenz- & Nullsummen-Interaktionen

Anwendungen Prisoner's Dilemma Axelrod's Tournament Stag Hunt The Game of Chicken Abhängigkeiten in Multiagentensystemen

Einleitung

„There is no such thing as a single agent system!“

Einleitung

Agenten interagieren miteinander

Agenten agieren in einer Umwelt

Ein Agent kann nur Teile dieser Umwelt beeinflussen

Die Bereiche können sich auch überlagern

Typische Struktur eines Multiagentensystems

Utility & Preferences

Vereinfachung auf 2 Agenten

Jeder von ihnen hat eigene Präferenzen und Wünsche

Sie handeln eigennützig

Agent I Agent J

Utility & PreferencesMenge Ω = ω1, ω2,... von Zuständen/Ausgängen der Umwelt

Die Präferenzen der beiden Agenten werden durch eine Nutzwertfunktion beschrieben

ui : Ω → ℝ uj : Ω → ℝ

für Präferenz gilt: ω ci ω' für ui(ω) ≥ ui(ω′) für strenge Präferenz gilt: ω _i ω' für ui(ω) > ui(ω′)

für Präferenz gilt: ω ci ω' für ui(ω) ≥ ui(ω′) für strenge Präferenz gilt: ω _i ω' für ui(ω) > ui(ω′)

Utility & Preferences

Präferenzordnung

Reflexivität: für alle ωєΩ gilt: ω ci ω

Transitivität: wenn ω ci ω' und ω' ci ω'', dann ω ci ω''

Vergleichbarkeit: für alle ωєΩ und ω'єΩ giltentweder ω' ci ω oder ω ci ω'

Multiagent Encounters Agenten wählen gleichzeitig und ohne Wissen über den anderen Aktionen Zwei Aktionen: C (kooperieren) und D (defektieren) Menge Ac = C,D dieser Aktionen Daraus ergibt sich die Umweltfunktion

Agent I's Aktion Agent J's Aktion

τ: Ac x Ac → Ωτ: Ac x Ac → Ω

Multiagent EncountersBeispiele

τ(D,D) = ω1 , τ(D,C) = ω

2 , τ(C,D) = ω

3, τ(C,C) = ω

4

Unempfindliche Umgebungτ(D,D) = ω

1 , τ(D,C) = ω

1 , τ(C,D) = ω

1, τ(C,C) = ω

1

Und hier ?τ(D,D) = ω

1 , τ(D,C) = ω

2 , τ(C,D) = ω

1, τ(C,C) = ω

2

Empfindliche Umgebung

=> Nur empfindlich gegenüber J

Multiagent EncountersKombination aus Umweltfunktion &

Nutzwertfunktion

Nutzwertfunktionen

ui(ω1) = 1, ui(ω2) = 1, ui(ω3) = 4, ui(ω4) = 4uj(ω1) = 1, uj(ω2) = 4, uj(ω3) = 1, uj(ω4) = 4

Empfindliche Umgebung τ(D,D) = ω

1 , τ(D,C) = ω

2 , τ(C,D) = ω

3, τ(C,C) = ω

4

ui(D,D) = 1, ui(D, C) = 1, ui(C, D) = 4, ui(C, C) = 4 uj(D,D) = 1, uj(D, C) = 4, uj(C, D) = 1, uj(C, C) = 4

ui(D,D) = 1, ui(D, C) = 1, ui(C, D) = 4, ui(C, C) = 4 uj(D,D) = 1, uj(D, C) = 4, uj(C, D) = 1, uj(C, C) = 4anders

geschrieben

Multiagent EncountersAuszahlungsmatrix

4 14 4

4 11 1

I defektiert I kooperiertJ defektiert

J kooperiert

ui(D,D) = 4, ui(D, C) = 4, ui(C, D) = 1, ui(C, C) = 1uj(D,D) = 4, uj(D, C) = 1, uj(C, D) = 4, uj(C, C) = 1

Agent I's Präferenzen für das BeispielD,D ci D,C _i C,D ci C,C

Dominante Strategien & Nash Equlibrium

Dominante Strategien

Ω1 dominiert Ω2 für Agent I wenn gilt:

Für strenge Dominanz gilt:

ω1 ci ω2 ∀ω1∈Ω1, ω2∈Ω2 ω1 ci ω2 ∀ω1∈Ω1, ω2∈Ω2

ω1 _i ω2 ∀ω1∈Ω1, ω2∈Ω2 ω1 _i ω2 ∀ω1∈Ω1, ω2∈Ω2

Was tu ich denn nun?


In der Spieletheorie werden Aktionen als „Strategien“ bezeichnet

Für Dominanz bei Strategien gilt:

Ein rationaler Agent wählt also in so einer Situation immer s1, da er so garantiert ein besseres Ergebnis erzielt als mit s2

Ω = ω1, ω2, ω3, ω4Ω1 = ω1, ω2Ω2 = ω3, ω4ω1 ci ω2 ci ω3 ci ω4

Beispiel

Ω1 dominiert Ω2

s* = Menge aller Ausgänge, die bei Strategie s auftreten können

s1 dominiert s2, wenn s1* s2* dominiert

s* = Menge aller Ausgänge, die bei Strategie s auftreten können

s1 dominiert s2, wenn s1* s2* dominiert


Nash Equilibrium

Unter der Annahme, dass Agent I s1 spielt, bleibt Agent J keine bessere Wahl als s2 zu spielen.

Unter der Annahme, dass Agent J s2 spielt, bleibt Agent I keine bessere Wahl als s1 zu spielen.

Unter der Annahme, dass Agent I s1 spielt, bleibt Agent J keine bessere Wahl als s2 zu spielen.

Unter der Annahme, dass Agent J s2 spielt, bleibt Agent I keine bessere Wahl als s1 zu spielen.

in nicht-kooperativen Spielen ein Zustand eines strategischen Gleichgewichts

ein einzelner Agent kann für sich keinen Vorteil erzielen, indem er einseitig von seiner Strategie abweicht.


BeispielAgent J

Links Mitte Rechts2 1 0

Oben 4 1 23 1 4

Agent I Mitte 2 1 10 2 3

Unten 3 0 1

gegeben Agent J spielt Rechts: Für Agent I ist oben optimal gegeben Agent J spielt Mitte: oben und mitte ist optimal gegeben Agent J spielt Links: oben ist optimal

gegeben Für Agent I spielt Oben: Für Agent J ist Links optimal gegeben Agent I spielt Mitte: Rechts ist optimal gegeben Agent I spielt Unten: Rechts ist optimal

Das Nash Equilibrium ist hier die Strategie 4 - 2 (Oben/Links)

Das Nash Equilibrium ist hier die Strategie 4 - 2 (Oben/Links)


Was könnten die Probleme sein?


Aber:

Noch nicht die Antwort auf die Frage, was in einem Szenario zu tun ist!

Nicht jedes Szenario hat ein Nash Equilibrium

Einige Szenarien haben mehr als ein Nash Equilibrium

Trotzdem ein sehr wichtiges Konzept für die Analyse von Multiagentensystemen!

Trotzdem ein sehr wichtiges Konzept für die Analyse von Multiagentensystemen!

Konkurrenz- & Nullsummeninteraktion

Konkurrenz

ω _i ω′ genau dann, wenn ω′ _j ω Interessen genau entgegengesetzt Ein Agent kann einen höheren Nutzwert nur auf Kosten des Anderen erzielen

Konkurrenz- & Nullsummeninteraktion

Nullsummen-Interaktion

Spezialfall der Konkurrenzinteraktion ui(ω)+ uj(ω) = 0 ∀ω∈Ω bösartigste Art der Interaktion, da Kooperation ausgeschlossen ist

Beispiel1 -2

-1 2-3 4

3 -4

I defektiert I kooperiertJ defektiert

J kooperiert

Prisoner's Dilemma Gestehen oder nicht?

Gesteht nur einer wird er freigelassen und der andere bekommt 20 Jahre

Gestehen beide, beide 5 Jahre

Gesteht keiner, beide 1 Jahr

Prisoner's Dilemma

Was würdest du tun?

Prisoner's Dilemma

kooperieren: schweigen defektieren: gestehenAuszahlungswerte:

20 Jahre -> 0 (ziemlich schlecht)5 Jahre -> 2 (schlecht)1 Jahr -> 3 (etwas besser)frei -> 5 (gut)

Präferenzordnungi: D,C _i C,C _i D,D _i C,Dj: C,D _j C,C _j D,D _j D,C

schweigen: bestes garantiertes Ergebnis= PayOff 0gestehen: bestes garantiertes Ergebnis= PayOff 2Logischer Agent würde Gestehen

2 02 5

5 30 3

i D i Cj D

j C

Prisoner's Dilemma

Fällt jemanden ein Beispiel für eine reale Situation ein?

Prisoner's Dilemma iteriert

Endlos: logisch wäre im 1.Zug zu kooperierenein Fehlschlag ließe sich über die Wiederholungen ausgleichen

Endlich: 100 mal=> Runde 100 = Prisoner's Dilemma

=> Runde 99 = Prisoner's Dilemma=> Runde 98 = Prisoner's Dilemma=> ...kein Unterschied, womit defektieren in jeder Runde rational wäre

Prisoner's Dilemma iteriert

damit Kooperation rationales Verhalten ist muß der vorherige Zug des Gegeners bekannt sein

Hat jemand eine Idee für eine Strategie?

Axelrod's Tournament 1980

Politikwissenschaftler, Psychologen, Wirtschaftswissenschaftler und Spieltheoretiker sollten ein Programm für das iterierte Prisoner's dilemma einreichen

Spielregeln: Jeder gegen jeden, 5 Spiele zu 200 Runden

Gewinner: insgesamt größter PayOff

Axelrod's Tournament Strategien

ALL-D „Hauptsache dagegen“

RANDOM „Mal so mal so“

TIT-FOR-TAT „Wie du mir so ich dir“Runde r=1 kooperierenRunde t>1 tu was der Gegner vorher (r-1) getan hat

(simpelste Strategie mit nur 5 Zeilen Fortran Code)


TESTER „Erstmal die Lage sondieren“r=1: defektierenif (Gegner defektieren) do (TIT-FOR-TAT)if (Gegnger cooperate) do (Schleife 2xkooperieren und 1xdefektieren)

JOSS „meistens – wie du mir so ich dir“wie TIT-FOR-TAT, ersetzt in 10% der Fälle kooperieren mit defektieren

Axelrod's TournamentWer hat gewonnen?

Wer hat gewonnen?

Axelrod's Tournament Wer hat gewonnen?

TIT-FOR-TAT

Schlussfolgerung: aus rationalem Verhalten folgt Kooperation

doch: TFT gewann da es hauptsächlich gegen kooperierende Strategien spieltegegen ALL-D verlor TFT


Axelrod's 4 Regeln für den Erfolg

Nicht Neidisch seinNicht als erster defektierenGerecht seinNicht zu schlau sein

The stag hunt"trust dilemma"

kooperieren: tauche mit lächerlicher Fisur in der Schule auf

defektieren: kneifei: C,C _i D,C _i D,D _i C,Dj: C,C _j C,D _j D,D _j D,C

1 01 2

2 30 3

i D i Cj D

j C

The game of chicken

… denn sie wissen nicht, was sie tun

„Rebell ohne Grund“

Symbolfigur für den

aufmüpfigen, unangepaßten Jugendlichen

The game of chicken

mit Vollgas auf eine Klippe zufahren

kooperieren: kneifen defektieren: weiterfahrenD,C _i C,C _i C,D _i D,D

0 10 3

3 21 2

i D i Cj D

j C

Abhängigkeiten in Multiagentensystemen

Unbhängigkeit der Agenten

Einseitig – Ein Agent abhängig von anderem aber nich andersrum

Gegenseitig – beide voneinander abhängig

Reziprok – voneinander abhängig aber evtl unterschiedliche Ziele

Fragen?

Danke für eure Aufmerksamkeit!

Documents

Ein Vortrag von: Rhena Möller und Svenja Heitländer Für ... · Dominante Strategien & Nash Equlibrium Nash Equilibrium Unter der Annahme, dass Agent I s1 spielt, bleibt Agent J