Spieltheoretische Koalitionsverhandlungen
Thema:
Agentenbasierte Koalitionsverhandlungen
Paper:
Coalitions among Computationally Bounded Agents
Spieltheorie - Peter Kaczmarczyk 2
Themen
Grundlagen Bedingungen für Koalitionsstrukturen Core- Stabilität der Koalitionsstrukturen Stabilität von Koalitionsstrukturen
Spieltheorie - Peter Kaczmarczyk 3
Set aller Agenten: A niedrigste Kosten, die eine Gruppe S erzielen kann:
Charakteristische Funktion, Wert einer Koalition S angibt: Auszahlung eines Agenten i: xi Є R
Allgemeinwohl ist die Summe der Auszahlung aller Agenten
wenn für alle disjunkte Koalitionengilt:
dann ist das Spiel superadditiv
sonst:
ist das Spiel subadditiv
Grundlagen
AS C S
cv SS
ATS ,
vvv TSTS
vvv TSTS
Spieltheorie - Peter Kaczmarczyk 4
Grundlagen
Agenten koordinieren ihre Berechnungen und Weltaktionen innerhalb jeder Koalition
keine Koordination zwischen Koalitionen
In verteilten, kooperativen Problemlösungssystemen bestimmt ein Designer ein Interaktionsprotokoll und eine Strategie Frage: welche Struktur bei gegebenem Protokoll und Strategie
In Multiagentensystemen können die Agenten jedoch ihre eigene Strategie auswählen Selbstorientierte Agenten wählen die beste Strategie, für sich selbst Frage: Bei gegebenem Protokoll, welche Struktur entsteht, die
garantiert, dass die lokale Strategie eines jeden Agenten am besten für ihn ist?
Diese Strategie wird somit von diesem Agenten benutzt.
Spieltheorie - Peter Kaczmarczyk 5
Grundlagen
Core
Wert jeder Teilgruppe S an Agenten ist nicht größer als die Summe der Auszahlungen der Agenten in CS
perfekte Rationalität:Algorithmen, die die optimale Lösung mit Null Berechnungskosten finden
Rationalität der Agenten ist jedoch durch die Berechnungskomplexität begrenzt bei harten Problemen entstehen nicht zu begründende Kosten für die
optimale Lösung Folge: Qualität der Lösung wird gegen ihre Berechnungskosten
aufgewogen Erweiterung der klassischen Spieltheorie, die perfekte Rationalität annimmt
},|),{(
Si Ai CSj
SiSi jvxundvxASCSxC
Spieltheorie - Peter Kaczmarczyk 6
Spieltheorie - Peter Kaczmarczyk 7
Modell der beschränkten Rationalität Berechnungsgrenzen quantitativ modelliert:Berechnungskosteneinheiten:
ccomp ≥ 0 pro CPU Time
Koalitionkosten von S, nachdem Berechnungsressourcen rS verbraucht wurden:
cS(rS) ≥ 0
cS(rS) entspricht dem Leistungsprofil für den Problemlösungsalgorithmus
Spieltheorie - Peter Kaczmarczyk 8
Modell der beschränkten Rationalität Jede Koalition minimiert die Summe aus den
Koalitionskosten und den Berechnungskosten
Wert einer Koalition S:
vS(ccomp)= minrS[cS(rS) + ccomp * rS]
Dieser Wert sinkt mit steigenden Berechnungskosten ccomp
Spieltheorie - Peter Kaczmarczyk 9
Beispiele
vS(ccomp)= minrS[cS(rS) + ccomp * rS]
Spieltheorie - Peter Kaczmarczyk 10
Koalitionen für das Allgemeinwohlbeschränkt rational superadditives Spiel (BRSUP)
Wenn für alle disjunkte Koalitionen
und Berechnungskosteneinheit ccomp
gilt:
dann ist das Spiel BRSUP
BRSUP Spiele sind immer Spiele, bei denen die große Koalition {A} das Algemeinwohl maximiert
bei gegebenen ccomp kann ein Spiel entweder superadditiv, BRSUP, beides oder keines von beiden sein
)(c)(c)(c compcompcomp vvv TSTS
ATS ,
Spieltheorie - Peter Kaczmarczyk 11
Koalitionen für das Allgemeinwohlbeschränkt rational subadditives Spiel (BRSUB)
Wenn für alle disjunkte Koalitionenund Berechnungskosteneinheit ccomp
gilt:
dann ist das Spiel BRSUB
In BRSUB Spielen arbeiten die Agenten am besten alleine. {{a1},{a2},{a3},…,{a|A|},} maximiert das Algemeinwohl nur einige nicht-BRSUP Spiele sind beschränkt rational subadditiv
)(c)(c)(c compcompcomp vvv TSTS
ATS ,
Spieltheorie - Peter Kaczmarczyk 12
Beispiel
vS(ccomp)= minrS[cS(rS) + ccomp * rS]
Spieltheorie - Peter Kaczmarczyk 13
Koalitionen für das Allgemeinwohl Wenn die Leistungsprofile cS(rS) und die Berechnungskosten ccomp
bekannt sind, kann man den Ertrag einer jeden Koalitionsstruktur über ihre Koalitionen berechnen mit:
vS(ccomp)= minrS[cS(rS) + ccomp * rS]
Es gibt jedoch einige generelle Ergebnisse, die diese Aufzählung über alle Koalitionen unnötig machen
Frage: Welche Leistungsprofile machen ein Spiel zu einem BRSUP oder BRSUB Spiel für beliebige Berechnungskosteneinheiten
Bei Ausführungen auf remote Rechnern sind die Berechnungskosten unbekannt
Spieltheorie - Peter Kaczmarczyk 14
Garantie für Zusammenschlüsse Hilfe bietet Theorem 3.1, dass eine hinreichende Bedingung darstellt, die
garantiert, dass 2 beliebige, disjunkte Koalitionen unabhängig von den Berechnungskosteneinheiten ccomp fusionieren sollten
Theorem 3.1 BRSUP (hinreichende Bedingung):
Wenn für alle disjunkten Koalitionenund alle Berechnungszuteilungen gilt:
dann ist das Spiel BRSUP für alle Berechnungskosteneinheiten ccomp
0, TS rrATS ,
)(c)(c)(c TTSSTSTS rrrr
Spieltheorie - Peter Kaczmarczyk 15
Garantie für Zusammenschlüsse In der Theorie ist Theorem 3.1 immer erfüllbar, da der
Problemlösungsalgorithmus c(r) zuerst rS verbrauchen kann um Problem von S zu lösen und dann rT für T
Folge: beste Koalitionsstruktur ist die große Koalition {A} Theorem 3.1 ist keine notwendige Bedingung im allgemeinen
Theorem 3.2:
Gilt:für alle disjunkten Koalitionenund alle Berechnungszuteilungen
das Spiel ist BRSUP für beliebige Berechnungskosteneinheiten ccomp
0, TS rrATS ,
)(c)(c)(c TTSSTSTS rrrr
Spieltheorie - Peter Kaczmarczyk 16
Garantie für ZusammenschlüsseTheorem 3.3 BRSUP (notwendige und hinreichende Bedingung):
Ist cU(r) fallend und convex in r, für jedes
und gilt:
für alle disjunkten Koalitionenund alle Berechnungszuteilungen genau dann ist das Spiel BRSUP für beliebige
Berechnungskosteneinheiten ccomp
cU(r ) ist oft konvex, da größere Verbesserungen am Anfang mit wenigen Rechenschritten gefunden werden können, als später bei fast optimalen Zuständen
0, TS rrATS ,
)(c)(c)(c TTSSTSTS rrrr
AU cU(r)
r
Spieltheorie - Peter Kaczmarczyk 17
Beispiel Zusammenschlüsse
vS(ccomp)= minrS[cS(rS) + ccomp * rS]
Spieltheorie - Peter Kaczmarczyk 18
Garantie für Aufteilungen
Theorem 3.4 BRSUB (hinreichende Bedingung):
Gilt:für alle disjunkten Koalitionenund alle Berechnungszuteilungen =>dann ist das Spiel BRSUB für beliebige
Berechnungskosteneinheiten ccomp
Ein Spiel kann beschränkt rational subadditiv sein auch wenn Theorem 3.4 nicht gilt
Anders als bei der beschränkt rationalen Supperadditivität wird diese Implikation nicht zu einer Äquivalenz
0, TS rrATS ,)(c)(c)(c TTSSTSTS rrrr
Spieltheorie - Peter Kaczmarczyk 19
BeispielvU(ccomp)= minrU[cS(rU) + ccomp * rU]
Wenn z.B. Kosten bei Koalitionsbildung entstehen, die nichtdurch Optimierung der Kostenfunktion wieder weggemachtwerden können, dann ist dieses Spiel BRSUB
)(c)(c)(c)(c , TSJoinTTSSTSTS rrrrrr
Spieltheorie - Peter Kaczmarczyk 20
Core- Stabilität der Koalitionsstruktur Stabilität der Auszahlungskonfiguration analysiert
anhand des „Core“ –Lösungskonzepts
Wiederholung:
Core: „Der Core eines Spiels ist ein Set von stabilen Auszahlungskonfigurationen (x, CS), x ist ein Vektor von Auszahlungen an die Agenten“
stabil: „Konfiguration wird als stabil angesehen, wenn keine Untergruppe von Agenten ihre Auszahlung vergrößern kann, indem sie die Koalition verlässt und eine neue Koalition gründet“
},|),{(
Si Ai CSj
SiSi jvxundvxASCSxC
Spieltheorie - Peter Kaczmarczyk 21
Core- Stabilität der Koalitionsstrukturbeschränkt rationale Core (BRC)
bei Berechnungskosteneinheiten ccomp
ist der
Wenn der BRC nicht leer ist, können beschränkt rationale Agenten ihre Erträge untereinander verteilen, ohne dass eine Teilgruppe die Koalitionsstruktur verlassen will
)(,|),{()( compSSi
icomp cvxASCSxcBRC
)}( comp
CSjS
Aii cvxund
j
Spieltheorie - Peter Kaczmarczyk 22
Core- Stabilität der KoalitionsstrukturTheorem 4.1 BRC in BRSUB Spielen:
Wenn ein Spiel, bei gegebenen ccomp, BRSUB ist
=>
dann ist
In Spielen, die nicht BRSUB sind ist BRC manchmal leer
Erinnerung BRSUB:
0)( compcBRC
)(c)(c)(c compcompcomp vvv TSTS
Spieltheorie - Peter Kaczmarczyk 23
Definitionen
Seien B1,…,Bp verschiedene, nicht leere Teilmengen von A.
Das Set B = {B1,…,Bp} nennt man balanciert,wenn positive Koeffizienten existieren, sodass gilt:
ein minimal balanciertes Set enthält keine anderen balancierten Sets
Ein minimal balanciertes Set wird proper genannt, wenn kein Paar disjunkt ist.
1,}|{
jBij
iAi
Spieltheorie - Peter Kaczmarczyk 24
Beispiele
: proper sets
Spieltheorie - Peter Kaczmarczyk 25
Core- Stabilität der KoalitionsstrukturTheorem 4.3 BRC in BRSUP Spielen (notwendige und hinreichende Bedingungen):
Wenn bei gegebenen ccomp, ein Spiel BRSUP ist,und für jedes proper minimal balanciertes Set B = {B1,…,Bp} gilt:
<=>genau dann ist
Dieses Set an Ungleichungen ist minimal, kein kleineres Set ist ausreichend als Bedingung
0)( compcBRC
)()(1
compA
p
j
compBi cvcvj
Spieltheorie - Peter Kaczmarczyk 26
Core- Stabilität der KoalitionsstrukturTheorem 4.2 BRC in beschränkt rationalen großen
Koalitionsspielen (notwendige und hinreichende Bedingungen):
Wenn bei gegebenen ccomp, {A} den Allgemeinwohl maximiert,
und für jedes minimal balanciertes Set B = {B1,…,Bp} gilt:
<=>genau dann ist
0)( compcBRC
)()(1
compA
p
j
compBi cvcvj
Spieltheorie - Peter Kaczmarczyk 27
Core- Stabilität der KoalitionsstrukturTheorem 4.5 BRC in BRSUP Spielen (hinreichende Bedingungen über Kostenfunktion):
Wenn bei gegebenen ccomp, das Spiel BRSUP ist,
und [für jedes proper minimal balanciertes Set β = {B1,…,Bp}gilt:
=>dann ist
0)( compcBRC
)]()()0,(11
p
jBjA
p
jBBjB jjj
rcrcrB
Spieltheorie - Peter Kaczmarczyk 28
Core- Stabilität der KoalitionsstrukturTheorem 4.4 BRC in beschränkt rationalen großen
Koalitionsspielen(hinreichende Bedingungen über Kostenfunktion):
Wenn bei gegebenen ccomp, {A} den Allgemeinwohl maximiert,
und [für jedes minimal balanciertes Set β = {B1,…,Bp}
gilt:
=>dann ist 0)( compcBRC
)]()()0,(11
p
jBjA
p
jBBjB jjj
rcrcrB
Spieltheorie - Peter Kaczmarczyk 29
Zusammenfassung
Multiagentensysteme in denen Agenten ihre Strategie selbst wählen dürfen
BRSUPhinreichende, notwendige Bedingung die Garantie für
Zusammenschlüsse liefern BRSUB
nur hinreichende Bedingung die Garantie für Aufteilungen liefern
Core- Stabilität der Koalitionsstruktur BRC in BRSUB Spielen BRC in BRSUP Spielen und großen Koalitionsspielen BRC in BRSUP Spielen abhängig von Kostenfunktion
Spieltheorie - Peter Kaczmarczyk 30
Danke für Ihre Aufmerksamkeit
Fragen?