Gliederung 1.Problemstellung 2.Spieltheoretische Konzepte der Verhandlungsspiele (axiomatisch, strategisch) 3.Multiagentensysteme: 1.Kriterien für Mechanismen

Gliederung

1. Problemstellung

2. Spieltheoretische Konzepte der Verhandlungsspiele (axiomatisch, strategisch)

3. Multiagentensysteme:

1. Kriterien für Mechanismen

2. Umgebungsabhängige Mechanismen

3. Einbeziehung des Zeitaspekts

4. Berücksichtigung einer Deadline

5. Beschränkte Rationalität bei der Lösung von Aufgaben

4. Kooperation im Gefangenendilemma, insbesondere Simulationen von Axelrod

5. Schlussbemerkungen

Agent-Based Computational Economics: Game Theoretic Foundations

Problemstellung

Systeme werden immer häufiger von verschiedenen Teilnehmern mit eigenen Präferenzen und Zielen genutzt (auch durch verstärkten Einsatz des Internets)

Das System kann deshalb nicht mehr zentral kontrolliert werden

Zentral können Mechanismen (sozus. Spielregeln) vorgegeben werden, die konkreten Strategien werden aber lokal von den verschiedenen Agenten ausgewählt

Agenten müssen Anreize erhalten, so zu handeln, dass ein gewünschtes Ergebnis erzielt wird

Konzepte der Spieltheorie, um Mechanismen für Multiagentensysteme zu entwickeln.

Agent-Based Computational Economics: Game Theoretic Foundations 1

Problemstellung

Probleme bei der Anwendung der Spieltheorie:

Traditionell Annahme der vollständigen Rationalität der Spieler. Computer unterliegen aber insbesondere Rechenzeitrestriktionen Dann gilt das Gleichgewicht aus der traditionellen Spieltheorie u.U. nicht mehr. Beschränkte Rationalität lässt sich für Computer-Agenten besser darstellen als für menschliche.

Verhandlungen benötigen Zeit und verursachen u.U. sehr viel Kommunikation


Verhandlungsspiele

Verhandlungsspiel:

• Menge von Spielern

• Menge aller möglichen Nutzenvektoren u = (u1, ..., un)

• Konfliktpunkt c = (c1, ..., cn)

Eigenschaften der Lösung:

• Individuell rational

• Pareto-optimal


Axiomatische Lösungskonzepte

Nash-Lösung:

Axiome:

• Unabhängigkeit von äquivalenter Nutzentransformation

• Symmetrie

• Unabhängigkeit von irrelevanten Alternativen

• Pareto-Optimalität

Nutzenvektor u, der für beide Spieler besser ist als der Konfliktpunkt, und der außerdem folgendes maximiert:

(u1 – c1) (u2 – c2)


Axiomatische Lösungskonzepte (2)

Problem:

Verschiedene Lösungskonzepte, die auf intuitiven Axiomen aufbauen, aber zu verschiedenen Ergebnissen führen. Welches davon ist das „Richtige“?

Nicht beachtet: wie ist das tatsächliche Verhalten in Verhandlungen?

Stattdessen: nichtkooperatives Verhandlungsspiel, Suche nach Gleichgewicht


Strategisches Lösungskonzept

Rubinstein:

• Unendlicher Zeithorizont

• Abwechselnd Gebote

• Nutzen sinkt im Zeitablauf

Teilspielperfektes Gleichgewicht:

Konstante Kosten: c1 > c2: (c2, 1-c2) falls 1. Spieler das 1. Angebot macht, sonst (0,1)

Diskontfaktor:

Vorteilhaft:

• Niedrige Zeitpräferenz („geduldiger“)

• 1. Gebot


)1

11,

1

1(

21

2

21

2

Strategisches Lösungskonzept (2)

Probleme:

In Realität keine beliebig kleine Teilung des „Kuchens“ möglich (dann steigt die Anzahl der teilspielperfekten Gleichgewichte)

Experimente führen zu anderen Ergebnissen (Ultimatum Game)

Was passiert, wenn jemand vom teilspielperfekten Gleichgewicht abweicht? Theorie: der andere Spieler geht davon aus, dass dies ein Versehen war und in Zukunft nicht mehr vorkommen wird. Was passiert aber, wenn man die Rationalitätsannahme aufgibt?

Vollständige Information


Kriterien für Mechanismen (nach Kraus, Wilkenfeld, Zlotkin)

• Verteilt (dezentralisierte Entscheidungen)

• Augenblicklich (ohne Verzögerung)

• Effizient (pareto-optimal)

• Einfach (auch was Berechnungs- und Kommunikationsaufwand betrifft)

• Symmetrisch (kein Unterschied, falls es nur Unterschiede bei nichtrelevanten Eigenschaften der Agenten gibt)

• Stabil (Gleichgewichte, d.h. kein Designer eines Agenten würde davon profitieren, von bestimmten Strategien abzuweichen)

• Zugang/Erfüllbarkeit (zu Ressourcen oder gemeinsames Ziel erreicht)


Umgebungsabhängige Mechanismen

Zlotkin, Rosenschein (1996)

State oriented domains: Aktionen eines Agenten können Auswirkungen auf die Zielerreichung eines anderen Agenten haben.

Annahmen:

• Zwei Spieler maximieren ihren Erwartungsnutzen

• Keine langfristigen Verträge

• Vergleichbarkeit der Nutzen der Agenten

• Symmetrische Fähigkeiten

• Bindende Vereinbarungen

• Kein expliziter Nutzentransfer


Umgebungsabhängige Mechanismen (2)

Vollständige Information:

Nutzen aus Kooperation für Agent i: Kosten bei individueller Problemlösung – Kosten für i aus gemeinsamer Lösung

Notwendige und hinreichende Bedingung für eine individuell rationale und pareto-optimale Lösung:

• Gesamte Kosten für gemeinsames Ziel Summe aus der Erreichung beider Einzelziele. (Summenbedingung)

• Kleinste Kosten aus einem Einzelziel minimale Kosten, die Agent bei gemeinsamer Lösung tragen muss. (Minimumbedingung)

Kooperationssituation

Nash-Lösung



Kompromisssituation:

Mindestens eine der beiden Bedingungen ist verletzt.

Nutzen für Agent i: Wertschätzung des individuellen Ziels – Kosten für i aus gemeinsamer Lösung

Analog zu Kooperationssituation

Eine höhere Wertschätzung führt dazu, dass man einen höheren Anteil der Kosten tragen muss.



Konfliktsituation:

Es gibt keine Möglichkeit mehr, beide Ziele gemeinsam zu erreichen.

• Münzwurf

• Zwischenziel, dann Münzwurf (semi-kooperativer Handel)

• Münzwurf, dann gemeinsames Erreichen des Ziels (Multi-Plan-Handel. Vereinbarung muss verbindlich sein.)



Unvollständige Information:

Ziele nicht bekannt: Anreiz, leichtere Ziele anzugeben, dabei muss aber bei einer gemeinsamen Lösung das tatsächliche Ziel erreicht werden.

Werte nicht bekannt: Anreiz, weniger zu berichten, um einen kleineren Anteil der Kosten tragen zu können.

Generelles Problem: nicht wahrheitsinduzierend


Einbeziehung des Zeitaspekts

Kraus, Wilkenfeld, Zlotkin (1995)

Annahmen:

• Keine Seitenzahlungen möglich

• Zeitaspekt wichtig bei Nutzenbestimmung (Unterschied zu Zlotkin, Rosenschein)

• Keine langfristigen Verträge möglich

• Abwechselnd Gebote

Gesucht:

Teilspielperfekte Gleichgewichte für verschiedene Szenarien


Einbeziehung des Zeitaspekts (2)

Betrachtete Situationen:

1. Zwei vollständig informierte Agenten, keine Möglichkeit des Verhandlungsabbruchs Rubinstein: Einigung in erster Periode, Vorteil für geduldigeren Spieler, für 1. Bieter

2. Zwei vollständig informierte Agenten, Möglichkeit des Verhandlungsabbruchs, beide Spieler verlieren im Zeitablauf, es gibt einen Zeitpunkt, zu dem eine Einigung für beide besser ist als ein Abbruch Einigung in erster Periode. Der geduldigere Spieler hat einen Vorteil.



3. Zwei vollständig informierte Spieler, Möglichkeit des Verhandlungsabbruchs, ein Spieler gewinnt (A), der andere verliert (W) im Zeitablauf zwei Fälle:

i. W verliert weniger als A gewinnt: maximal eine Periode Verzögerung, da W mit einem Abbruch drohen kann. Nicht pareto-optimal, da A später mehr bekäme und dies aufteilen könnte. Hat aber Anreiz, diesen Zeitpunkt immer weiter hinauszuzögern. Die Verzögerung entsteht, wenn W zuerst bietet, da A ablehnt und dann ein Angebot macht, das W annimmt. Dieser würde sonst aus der Verhandlung aussteigen.

ii. W verliert mehr als A gewinnt: Einigung in erster Periode, da A sonst zuviel bezahlen müsste.



4. Wie Situation 3, aber unvollständig informierte Agenten. Es gibt verschiedene A- und W-Typen.

Hier nun gesucht: sequentielles Gleichgewicht

Jeder W verhält sich in der 1. Periode wie der der Typ, der am wenigsten im Zeitablauf verliert und am ehesten die Verhandlung abbricht, da er sonst befürchten muss, dass A ein schlechteres Angebot macht.

A lehnt in der 1. Periode jedes Angebot ab und macht aufgrund seiner Einschätzungen über den Typ W ein Angebot. Manche Ws brechen dann die Verhandlungen ab, andere nehmen an. A legt sein Gebot so fest, dass sein erwarteter Nutzen maximiert wird.

Insgesamt evt. Einigung in 2. Periode, u.U. kommt es aber auch zu keiner Einigung.


Berücksichtigung einer Deadline

Sandholm, Vulkan (2002)

Kritik an Rubinstein:

unendlicher Zeithorizont ist unrealistisch, Ergebnisse ändern sich, wenn es eine Deadline gibt. Annahme der vollständigen Information unrealistisch.

Annahmen:

Deadline ist private Information, Verteilung common knowledge

Zu jedem Zeitpunkt geben beide Agenten ein Angebot ab, welchen Anteil der Ressource sie haben möchten. Zunächst beanspruchen beide alles.

Deadline eines Agenten erreicht: der andere erhält gesamte Ressource


Berücksichtigung einer Deadline (2)

Betrachtete Situationen:

1. stetige Zeitintervalle, keine Diskontierung, risikoneutrale Agenten sequentielles Gleichgewicht: Agent mit späterer Deadline erhält gesamte Ressource zum Zeitpunkt der früheren Deadline. Jeder verlangt bis zu diesem Zeitpunkt alles, da Angebote Signale darstellen, die die Einschätzung über die Deadline des Gegenspielers verändern.

2. Wie 1., mit Diskontierung sequentielles Gleichgewicht wie in Situation 1. Einziges sequentielles Gleichgewicht, falls das Produkt der beiden Diskontfaktoren größer als 0,5 ist. D.h. der Einfluss der Deadline ist größer als der Einfluss der Diskontierung, wenn der „Kuchen“ im Zeitablauf nicht zu sehr abnimmt.


Berücksichtigung einer Deadline (3)

3. Wie 1, aber keine Annahme mehr zur Risikoeinstellung sequentielles Gleichgewicht wie in Situation 1. Einziges sequentielles Gleichgewicht, falls das Produkt der beiden maximalen Risikoaversionen (Maximum von ui(x)/x über alle x) kleiner als 2 ist.

4. diskrete Zeitintervalle beide Spieler erreichen mit positiver Wahrscheinlichkeit die Deadline zum gleichen Zeitpunkt falls diese Deadline die maximal mögliche ist, ist jeder Split möglich.

Sonst einziges sequentielles Gleichgewicht wie oben.

Mechanismus: beide berichten Deadline. Agent mit späterer Deadline erhält alles zum Zeitpunkt der früheren Deadline. Wahrheitsgemäßer Bericht ist dominante Strategie. Verringert Kommunikationsaufwand.


Beschränkte Rationalität

Larson, Sandholm (2001)

Möglichkeit, eine Aufgabe gemeinsam zu lösen (Verhandlungsgegenstand), oder jeder Agent löst sein individuelles Problem

Problem: beschränkte Rationalität. Der Wert des Verhandlungsgegenstandes ist u.U. noch gar nicht bekannt, d.h. die Agenten wissen noch gar nicht, wie hoch der Nutzen aus dem Gewinn der Verhandlung ist.

Es gibt Anytime-Algorithmen zur Berechnung des Werts des Verhandlungsgegenstandes.

Es gibt statistische Leistungsprofilbäume, die angeben, wie sich die Lösungsqualität nach t Rechenschritten verändern kann.


Beschränkte Rationalität (2)

Deadline T. Dann wird ein Gebot abgegeben. Vorher gibt es keine Kommunikation.

Möglichkeit, die Verhandlungen abzubrechen (die Agenten lösen dann ihre individuellen Probleme)

Strategie:

• Welches Problem wird näher untersucht? (eigenes, das des anderen oder gemeinsames)

• Welches Gebot?

Gesucht: „deliberation equilibrium“



Bieter bekannt:

Dominante Strategie des anderen Agenten: berechnet nur eigenes Problem und nimmt jedes Angebot an, das zu einem höheren Nutzen führt als die Lösung seines eigenen Problems.

Bieter:

Zeitpunkt der Deadline bekannt, es gibt deterministischen Leistungsprofilbaum: Berechnet das Problem, das ihm den größten Nutzen bringt

Stochastischer Baum: höchster erwarteter Nutzen bei Auswahl des Problem



Deadline nicht bekannt:

Agenten haben eine Einschätzung über den Zeitpunkt der Deadline. Diese Einschätzung wird in jeder Periode revidiert. Bieter entscheidet über die Berechnung seines eigenen und des gemeinsamen Problems anhand des erwarteten Nutzens daraus. Optimale Strategie des anderen Agenten ist analog zur Basissituation.

Falls der Bieter nicht bekannt ist, haben beide keine dominante Strategie. Es gibt Situationen, in denen es kein Gleichgewicht in reinen Strategien gibt. Außerdem gibt es Fälle, in denen das einzige Nash-Gleichgewicht nicht zu einem pareto-optimalen Ergebnis führt.


Kooperation im Gefangenendilemma

Dominant: keine Kooperation. Kooperation führt aber zu höherem Nutzen.

Wiederholtes Spiel: Reputation möglich.

Endliche Wiederholung: wie einmaliges Spiel

Unendliche Wiederholung: unendlich viele Nash-Gleichgewichte


Spieler 2: Kooperation Spieler 2: keine Kooperation

Spieler 1: Kooperation (3, 3) (1, 4)

Spieler 1: keine Kooperation (4, 1) (2, 2)

Simulationen von Axelrod

Simulation verschiedener Strategien im wiederholten Gefangenendilemma

Beste Strategie: Tit for Tat

Bleibt auch beste Strategie bei evolutionärer Betrachtung, wenn bessere Strategien sich in der Menge aller Strategien der Simulation tendenziell stärker verbreiten, wenn der Diskontfaktor ausreichend groß ist.


Zusammenspiel Multiagentensysteme - Spieltheorie

Die verschiedenen Ansätze zeigen, dass spieltheoretische Konzepte beim Design von Multiagentensystemen eine hilfreiche Unterstützung liefern können.

Umgekehrt können Simulationen mit Hilfe von Multiagentensystemen auch zu neuen Erkenntnissen im Rahmen der Spieltheorie führen. Dies wird vor allem im Bereich der evolutionären Spieltheorie verwendet.


Documents

Gliederung 1.Problemstellung 2.Spieltheoretische Konzepte der Verhandlungsspiele (axiomatisch, strategisch) 3.Multiagentensysteme: 1.Kriterien für Mechanismen