Spieltheoretische Koalitionsverhandlungen Thema: Agentenbasierte Koalitionsverhandlungen Paper: Coalitions among Computationally Bounded Agents

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


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


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.


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



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


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


Beispiele



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 ,


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


ATS ,


Beispiel



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:


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


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


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 ,



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 ,


AU cU(r)

r


Beispiel Zusammenschlüsse



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


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


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


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


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



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


Beispiele

: proper sets


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


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


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


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


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


Danke für Ihre Aufmerksamkeit

Fragen?

Documents

Spieltheoretische Koalitionsverhandlungen Thema: Agentenbasierte Koalitionsverhandlungen Paper: Coalitions among Computationally Bounded Agents