• Non ci sono risultati.

Silvia Rossi

N/A
N/A
Protected

Academic year: 2021

Condividi "Silvia Rossi"

Copied!
28
0
0

Testo completo

(1)

Lezione n.

Corso di Laurea:

Insegnamento:

Email:

A.A. 2014-2015

Silvia Rossi

Coalitions

18

Informatica

Sistemi

multi-agente

silrossi@unina.it

(2)

Cooperative Games - Coalizioni

W 13

2

(3)

Assumptions in Non-Cooperative Games

•  Cooperation can’t occur in the prisoner’s

dilemma because the conditions required for cooperation are not present, in particular:

•  binding agreements are not possible.

•  Utility is given directly to individuals as a result of individual action

•  But suppose we drop this assumptions?

•  In the real world, the role of contracts is to enable binding agreements.

3

(4)

Coalitional games

• Coalitional games model scenarios where:

•  agents can benefit by cooperating;

•  binding agreements are possible.

4

(5)

What is a Coalition?

• Coalitions are (temporary) collections of individuals working together for the purpose of achieving a task

• Coalition formation is the process whereby an agent decides to cooperate with other agents

• Because

•  Either: task cannot be performed by a single agent

•  Or: task could be performed more efficiently by several Agents bring different, complementary capabilities to the coalition

• When the task is completed, the payoff is distributed and agents continue to pursue their own agenda

5

(6)

Cooperation via Coalitions

• To perform a task and increase benefits, agents may need to cooperate via coalition formation

• A coalition: a set of agents that agree to cooperate to perform a task

• Given n agents, k tasks, there are k (2n − 1) different possible coalitions

• The number of configurations is O(n

(n/2)

) Hence, exhaustive search is infeasible

6

(7)

Issues in Coalition Formation

• Given a task and other agents, which coalitions should an agent attempt to form?

• What mechanism can an agent use for coalition formation?

• What guarantees regarding efficiency and quality can the mechanism provide?

• Once a coalition is created, how should its members handle distribution of work/payoff?

• When, and how, does a coalition dissolve?

7

(8)

Phases of Cooperative Action

•  Issues in coalitional games (Sandholm et al, 1999):

•  Coalition structure generation.

•  Teamwork.

•  Dividing the benefits of cooperation.

8

(9)

Coalition Structure Generation

•  Deciding in principle who will work together.

•  The basic question:

•  Which coalition should I join?

•  The result: partitions agents into disjoint coalitions.

•  The overall partition is a coalition structure.

9

(10)

Coalition formation: external

• By imposition: an external agency makes decisions

•  Agents advertise skills and prices

•  Requestor defines properties of coalition

•  External process computes optimal coalition

•  Essentially the same as combinatorial auction – same complexity

•  See “Generating Coalition Structures with Finite Bound from the Optimal Guarantees”, [Dang and Jennings, 2004]

10

(11)

Coalition formation: internal

• By self-organization: coalitions are established by group (inter)actions

•  Process: multi-lateral negotiation

•  Identification of tasks (responsibilities)

•  Negotiation of outcomes (self-interested agents)

•  Examples: Robocup, Robocup rescue

•  See “Methods for Task Allocation via Agent

Coalition Formation”, [Shehory and Kraus, 1998]

•  And “Self-organization through bottom-up coalition formation”, [Sims et al., 2003]

11

(12)

Solving the optimization problem of each coalition

•  Deciding how to work together.

•  Solving the “joint problem” of a coalition.

•  Finding how to maximise the utility of the coalition itself.

•  Typically involves joint planning etc.

12

(13)

Dividing the Benefits

•  Deciding “who gets what” in the payoff.

•  Coalition members cannot ignore each

other’s preferences, because members can defect: if you try to give me a bad payoff, I can always walk away.

•  We might want to consider issues such as fairness of the distribution.

13

(14)

Coalitional Games

• A coalitional game is a pair:

•  where:

•  N = {1, … , n} is a set of players;

•  is the characteristic function of the game.

• Usual interpretation: if v(C) = k, then coalition C can cooperate in such a way they will obtain utility k, which may then be distributed amongst team members.

•  Does not specify distribution of utility

•  Does not explain how ν is derived

14

(15)

Which Coalition Should I Join?

• Most important question in coalitional games:

•  is a coalition stable?

• that is, is it rational for all members of coalition to stay with the coalition, or could they benefit by defecting

from it?

•  (There is no point in me trying to join a coalition with you unless you want to form one with me, and vice

versa.)

•  Stability is a necessary but not sufficient condition for coalitions to form.

15

(16)

Outcomes

• The core of a coalitional game is the set of

feasible distributions of payoff to members of a coalition that no sub-coalition can reasonably object to.

•  An outcome for a game <N,v> is a vector of payoffs to members of N, x = <x

1

,…,x

n

> which represents a feasible and efficient distribution of payoff to members of N.

16

(17)

Outcomes

• “Feasible” means:

• Example: if v({1})=5, v({2})=5 and v({1,2})=20, then possible outcomes are

<20,0>, <19,1>, <18,2>, … , <0,20>.

(Actually there will be infinitely many!)

•  An imputation is an outcome in which everybody is

paid atleast what they could earn themselves (individual rationality).

17

(18)

Objections

• Intuitively, a coalition C objects to an outcome if there is some outcome for them that makes ALL of them

strictly better off.

•  Where x is an outcome and C in N, we let

• Formally, C in N objects to an outcome x = <x

1

,…, x

n

>

iff

•  An outcome is not going to happen if a coalition

objects to it, because this coalition could do better by

defecting.

18

(19)

The Core

•  The core, C of a game G = <N,v> is the set of outcomes to which no coalition objects:

•  If the core is non-empty then the grand coalition is stable, since nobody can benefit from defection.

•  Thus, asking

•  is the grand coalition stable?

• is the same as asking:

•  is the core non-empty?

19

(20)

A game with an empty core

•  Let G = <N,v> be a game with N = {1,2,3} and

• Then C(G) = 0 any two players will always be able to deviate and share some “surplus”.

20

(21)

Problems with the Core

•  Sometimes, the core is empty; what happens then?

•  Sometimes it is non-empty but isn’t “fair”.

•  Suppose N = {1,2}, v({1})=5, v({2})=5, v({1,2})=20.

•  Then outcome <20,0> (i.e., agent 1 gets

everything) is not in the core, since the coalition {2} can object. (He can work on his own and do better.)

•  However, outcome <15,5> is in the core: even though this seems unfair to agent 2, this agent has no

objection.

•  Why unfair? Because the agents are identical!

21

(22)

Fair Distribution: The Shapley Value

•  The Shapley value is best known attempt to define how to divide benefits of cooperation fairly.

•  Payments based on how much an agent contributes.

•  The Shapley value sh

i

(G) of agent i in game G is the average amount that i is expected to contribute to a coalition.

•  Axiomatically: a value which satisfies axioms:

•  efficiency, symmetry, dummy player, and additivity.

22

(23)

Shapley’s Axioms: (1) Efficiency

•  The Shapley value sh(G) is an imputation, i.e., a tuple of payoffs sh(G) = (sh

1

(G), … , sh

n

(G)).

•  It defines how the payoff of the grand coalition is

distributed (standard assumption: superadditive games)

•  The efficiency axiom says that no utility is wasted: all utility is distributed:

23

(24)

Shapley’s Axioms: (2) Symmetry

• The symmetry axiom says that agents which make the same contribution should get the same payoff

•  Let δ

i

(S) be the amount that i adds by joining S in N:

•  . . . the marginal contribution of i to S.

•  If δi(S) = vi(S) -> no added value

•  Then i and j are interchangeable if δ

i

(C) = δ

j

(C) for every C in N \ {i,j}.

•  The symmetry axiom: if i and j are interchangeable

then sh

i

(G) = sh

j

(G).

24

(25)

Shapley’s Axioms: (3) Dummy Player

• The dummy player axiom says that agents which make no contribution should get nothing.

•  Formally, i in N is a dummy if v({i})=δ

i

(S) for every S in N \ {i}.

•  The dummy player axiom: if i is a dummy player then sh

i

= v({i}).

25

(26)

Shapley’s Axioms: (4) Additivity

•  This one is a bit technical! It basically says that if you combine two games, then the value a player gets should be the sum of the values in the individual games.

•  You can’t gain or lose by playing more than once.

•  Formally, where G

1

=(N, v

1

) and G

2

=(N,v

2

) are games, define game G

1

+G

2

=(N,v

1

+v

2

) with:

•  v

1

+ v

2

(C) = v

1

(C) + v

2

(C):

•  Then addititivy says:

•  sh

i

(G

1

+ G

2

) = sh

i

(G

1

) + sh

i

(G

2

):

26

(27)

Shapley Defined

• The Shapley value for i, denoted sh

i

, is:

• where R is the set of all orderings of N and S

i

(r) is the set of agents preceding i in ordering r.

•  The average marginal contribution it makes to a coalition

27

(28)

Computational Issues in Coalitional Games

• It is important for an agent to know (eg) whether the core of a coalition is non-empty . . .

•  so, how hard is it to decide this?

•  Problem: naive, obvious representation of coalitional game is exponential in the size of N!

•  Now such a representation is:

•  utterly infeasible in practice; and

•  so large that it renders comparisons to this input size meaningless: stating that we have an algorithm that runs in (say) time linear in the size of such a

representation means it runs in time exponential in the size of N!

28

Riferimenti

Documenti correlati

Since we are comparing two polynomials, it follows that the identity holds for all x

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.. We will show a more

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.. Let π ∈

[r]

[r]

Assume by contradiction that f has not a periodic point then X 0 is not finite and therefore it is countable.. Now, we will show that there is a one-to-one map Φ of the set of

Say if the following statements are unambiguously true (TRUE), unambiguously false (FALSE) or impossible to classify the way they are stated (CAN’T SAY).. Write the mo- tivations

In my efforts to develop my skills and build on the yearning to communicate through art I turned to the Art institute in Brera University in Milan.. There the transition from an