Transcript Using Dialogue Games to Form Coalitions with Self

Using Dialogue Games to Form
Coalitions with Self-Interested
Agents
Luke Riley
Department of Computer Science
University of Liverpool
[email protected]
Supervisors: Katie Atkinson & Terry Payne
1.
 Coalition
Click to edit
Formation
the outline
in Cooperative
text format
Game Theory.

Second Outline Level
2. Coalition
Formation
 Third
Outline in
Level
Argumentation.
 Fourth Outline Level
3. The Issues and
 Fifth
Problems
OutlineBetween
Level
these Two Approaches.
 Sixth Outline Level
 Seventh Outline Level
4. My Research.
 Eighth Outline Level

Ninth Outline LevelClick to edit
Master text styles

Second level

Third level

Fourth level

Fifth level
2
1. Coalition Formation in
Cooperative Game Theory (CGT)
3
Background

N-person cooperative games (coalition games)
were proposed in 1944 by von Neumann &
Morgenstern [1]:
Where...
Agent set:
Characteristic Function:
[1] J. von Neumann and O. Morgenstern. The Theory of Games and Economic
Behavior. Princeton University Press, 1944.
4
Solving a Coalition Game

In its most traditional style the CGT outcome of a
coalition game is:
Where...
CS = a set of coalitions (the coalition structure)
x = a vector of each individual agent's payoff in the
game.
5
Finding a Stable Outcome – The Core


A Coalition Structure is core-stable if no subset
of agents can benefit from defecting to another
coalition.
The core [2] is the set where:
e.g.
e.g.Example
Example2:
1:Given
Givenaacoalition
coalitiongame
gamewhere
whereN
N==
{1,2}, v({1}) = v({2}) = 5 and v({1,2}) = 20 the
proposed core outcome is <{1,2}, x(10,10)
x(15,5) >>

Yet core payoffs can sometimes be unfair
[2] D. Gillies. Some theorems on n-person games. PhD thesis, Princeton University, 1953.
6
Epsilon-Core

Also the core can sometimes be empty
e.g. Example 3: Given a coalition game where N =
{1,2,3}, forall subsets C if |C| = 2 then v(C) = 1 else
v(C) = 0


Solution [3] →
The epsilon value can be seen as the cost of
deviating.
e.g. Example 4: Given the coalition game of
example 3, the payoff vector x(1/3,1/3,1/3) is 1/3core stable.
[3] Shapley, Lloyd S. and Shubik, M. Quasi-cores in a monetary economy with non-convex
preferences , Econometrica (The Econometric Society) 34(4): 805–827, 1966.
7
1. Coalition Formation in
Argumentation
8
Dung's Initial Work

Dung showed that Argumentation Frameworks
were natural ways to represent n-person games,
for example theorem 6 of [4]:
The AF represents 3 possible
payoff vectors of the coalition
game:
x(3,4,8)
v({1}) = v({2}) = v({3}) = 3
v({1,3}) = 8
x(3,3,5)
x(3,3,3)
v({2,3}) = 12
or v(C) = 0
[4] P. M. Dung. On the acceptability of arguments and its fundamental role in nonmonotonic
reasoning, logic programming and n-person games. Artificial Intelligence, 77:321–357, 1995.
9
Amgoud's Further Research

Amgoud in [5] extended this research, where she
highlighted:



How to always find a solution to a coalition
game
Outlines how agents can collaboratively
build AFs for coalition games
How a dialogue game can be used to check
if a certain coalition was in the best coalition
structure
[5] L. Amgoud. An argumentation-based model for reasoning about coalition
structures. In ArgMAS, pages 217-228, 2005.
10
2. The Issues of Joining the Two
Approaches
11
Various Issues

CGT: Lacks flexible communication protocols to
form stable coalitions.
CGT: Generally does not take into account the
computation and communication costs of finding
stable coalition structures from a MAS
perspective.
 Arg: There is little research showing how payoff
vectors are found and justified by MAS.



Arg: No research on how to stabilise coalitions
games, using the epsilon-core
Arg: Only some limited direct mapping between
the argumentation models and the CGT coalition
game types (e.g. static, dynamic, skill games,...)
12
My Current Research Question
How can self-interested agents make
use of argumentation within their
communication to enable them to form
a stable optimal coalition structure
with an approximately fair payoff
distribution?
13
3. The Proposed Method
14
Dialogue Games & Argumentation
Schemes



Dialogue Games can be used to build argumentation
frameworks in real time, where agents can assert and
retract arguments.
Argumentation schemes are patterns of reasoning that
when instantiated provide presumptive justification for the
particular conclusion of the scheme
e.g:...
15
Approximately fair payoffs

AFs can easily represent the core

...But the core can be unfair

Solution – restrict the payoffs allowed:



agents have to propose an equal split of v(C)
or each agent should be given at least the
same value it can get from a coalition of
agents willing to defect
Agents can object to a proposed payoff by
finding a better one for itself.
Once a core payoff is found, the dialogue
stops
16
Dialogue Games & Argumentation
Schemes


I have devised a dialogue game [6] to find an
optimal coalition structure with a restricted core
payoff
Moves:
e.g:
[6] L. Riley, K. Atkinson, and T. Payne. Coalition structure generation for self interested agents in a
dialogue game. Technical Report ULCS-12-004, University of Liverpool, 2012.
17
Core example
Move
Coalition
{1}
{2}
{3}
{1,2}
{1,3}
{2,3}
{1,2,3}
Coalition
value
4
3
2
14
18
5
7
1
[3]
2
[9/9]
[2]
3
[3]
[10/4]
[11/7]
FINISH
Coalition Structure of move 3 is {{1,3}, {2}}, the payoff vector is
x(11,3,7) and is core stable
18
Epsilon-Core Example
Move
e value
Coalition
{1}
value
5
0
5
{3}
5
{1,2}
5
{1,3}
18
{2,3}
20
[5]
{1,2,3}
22
10
[11/11]
6
1 value
6
{2}
1
6
6
19
17
[6]
21
[7/12]
Coalition Structure of move 8 is {{1},{2,3}}, the payoff vector is
7 stable
7
7
18
2 value and is 3-core
16
20
x(8,9.5,9.5)
7
2
[7]
8
3 value
8
3
8
[8/8]
8
15
17
[8]
19
[9.5/9.5]
19
4 value
FINISH
9
9
9
14
16
18
Potential Future


Modify argumentation scheme and attack
relations so that other coalition games can be
modeled (e.g stochastic, dynamic, skill games,...).
Optimise process: Combine mechanism design
approach of [7] with efficient distribution
methods of [8].
[7] Tuomas Sandholm, Kate Larson, Martin Andersson, Onn Shehory and Fernando Tohmé,
Coalition structure generation with worst case guarantees, Artificial Intelligence, Volume 111,
Issues 1–2, July 1999, Pages 209-238.
[8] T. Rahwan. Algorithms for Coalition Formation in Multi-Agent Systems. PhD thesis,
University of Southampton, 2007.
20
Thanks For Listening
21
Questions?