# Silvia Rossi

## Full text

(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

3

(4)

### •  binding agreements are possible.

4

(5)

What is a Coalition?

### • 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

(n/2)

### ) Hence, exhaustive search is infeasible

6

(7)

Issues in Coalition Formation

7

(8)

8

(9)

### •  The overall partition is a coalition structure.

9

(10)

Coalition formation: external

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

10

(11)

Coalition formation: internal

11

(12)

12

(13)

13

(14)

### • 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)

15

(16)

1

n

16

(17)

17

(18)

1

n

18

(19)

19

(20)

20

(21)

### •  Why unfair? Because the agents are identical!

21

(22)

Fair Distribution: The Shapley Value

i

### •  efficiency, symmetry, dummy player, and additivity.

22

(23)

Shapley’s Axioms: (1) Eﬃciency

1

n

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

23

(24)

Shapley’s Axioms: (2) Symmetry

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

i

j

i

j

### (G).

24

(25)

Shapley’s Axioms: (3) Dummy Player

i

i

25

(26)

1

1

2

2

1

2

1

2

1

2

1

2

i

1

2

i

1

i

2

26

(27)

Shapley Defined

i

i

### •  The average marginal contribution it makes to a coalition

27

(28)

Computational Issues in Coalitional Games

### •  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

Updating...

## References

Related subjects :