Agent-based Systems
Paolo Turrini
www.dcs.warwick.ac.uk/~pturrini R p.turrini@warwick.ac.uk
Coalitional Games The value of a group
Paolo Turrini Coalitional Games Agent-based Systems
Plan for Today
The coming lectures are about cooperative game theory, where we study so-called coalitional games and the formation of coalitions.
The first step is to talk about transferable-utility games. Today we focus on stability for such games:
definition of transferable-utility games examples for transferable-utility games
the core: set of surplus divisions that are stable
Much of this is also covered in Chapter 8 of the Essentials.
K. Leyton-Brown and Y. Shoham.
Essentials of Game Theory: A Concise, Multidisciplinary Introduction
Claypool Publishers, 2008. Chapter 8.
Paolo Turrini Coalitional Games Agent-based Systems
Coalitional Games
A transferable-utility coalitional game in characteristic-function form (or simply: a TU game) is a tuple ⟨N,v⟩, where
N = {1,…,n} is a finite set of players and
v : 2N → R0, with v({}) = 0, is a characteristic function, mapping every
possible coalition C ⊆ N to its surplus v(C). Note:
The surplus v(C) is also known as the value or the worth of C.
The players are assumed to form coalitions (thereby partitioning N). Each coalition C receives its surplus v(C) and—somehow—divides it amongst its members (possible due to utility being transferable).
Remark: We’ll see a type of nontransferable-utility games later on.
Paolo Turrini Coalitional Games Agent-based Systems
Example: A Network Flow Game
Each pipeline is owned by a different player (1, 2, . . . ). Each pipeline is annotated as (owner) : (capacity). The surplus v(C) for coalition C is the amount of oil it can pump through the part of the network it owns.
1:4 2:2 3:2
4:3 5:5
Thus: We obtain v(12) = 2, v(45) = 3, v(15) = 0, v(134) = 0, v(135) = 2, v(1345) = 5, v(12345) = 7, and so forth.
Exercise: What coalition(s) will form? How to divide the surplus?
Paolo Turrini Coalitional Games Agent-based Systems
Example: A Bankruptcy Game
Alice goes bankrupt. She owes £30k, £60k, £90k to three creditors. But the combined worth of her remaining estate is just £100k.
Model this as a TU game ⟨N,v⟩, with N = {1,2,3}, and use v to represent the amount a coalition C of creditors is guaranteed to get:
v(C) = max0,E−di
i∈N\C
Here E = £100k is the value of the estate and di is the debt owed to creditor i ∈ N
(i.e., d1 = £30k, and so forth).
Exercise: Decide on an amount xi to award to each creditor i that seems fair and is
stable (no coalition should want to break off).
Paolo Turrini Coalitional Games Agent-based Systems
Simple Games
A simple game is a TU game ⟨N,v⟩ for which it is the case that v(C) ∈ {0,1} for every possible coalition C ⊆ N.
Thus: every coalition is either winning or losing.
Paolo Turrini Coalitional Games Agent-based Systems
Voting Games
A (weighted) voting game is a tuple ⟨N, w, q⟩, where
N = {1,…,n} is a finite set of players;
w = (w1,…,wn) ∈ Rn0 is a vector of weights; and q ∈ R0 is a quota.
Coalition C ⊆ N is winning, if the sum of the weights of its members meets or exceeds the quota. Otherwise it is losing.
Thus, a voting game ⟨N, w, q⟩ is in fact a simple game ⟨N, v⟩ with:
1 ifi∈Cwiq v (C ) = 0 otherwise
Paolo Turrini
Coalitional Games Agent-based Systems
Power and the EU
In the Treaty of Rome (1957) the founding countries of the EU fixed the voting rule to be used in the Council of the European Commission:
To pass, a proposal had to get at least 12 votes in favour.
France, Germany, and Italy each had 4 votes. Belgium and the Netherlands each
had 2 votes. Luxembourg had 1 vote. This is a weighted voting game ⟨N, w, q⟩ with
N = {BE, DE, FR, IT, NL, LU}
wDE =wFR =wIT =4,wBE =wNL =2,andwLU =1 q = 12
Question: Is this fair? What about Luxembourg in particular?
Paolo Turrini Coalitional Games Agent-based Systems
Properties of Coalitional Games
Some TU games ⟨N,v⟩ have certain properties (for all C,C′ ⊆ N): additive: C∩C′ ={}impliesv(C∪C′)=v(C)+v(C′) superadditive: C∩C′ ={}impliesv(C∪C′)v(C)+v(C′) convex: v(C∪C′)v(C)+v(C′)−v(C∩C′) cohesive:N=C1⊎···⊎CK impliesv(N)v(C1)+···+v(CK) monotonic: C ⊆ C′ implies v(C) v(C′)
Remark: Additive games are not interesting. No synergies between players: every coalition structure is equally good for everyone.
Exercise: Show that convexity can equivalently be expressed as v(S′∪{i})−v(S′)v(S∪{i})−v(S)forS⊆S′ ⊆N\{i}.
Exercise: Show that additive ⇒ convex ⇒ superadditive ⇒ cohesive, and also that superadditive ⇒ monotonic.
Paolo Turrini Coalitional Games Agent-based Systems
Examples
What are the properties of the special types of games we have seen?
Network flow games are easily seen to be monotonic as well as superadditive, but they usually are not convex.
Voting games, with weights w = (w1, . . . , wn) and quota q, are monotonic, but
not necessarily convex or even cohesive.
Yet, they are convex in the natural case of q > 1 ·(w1 +···+wn). 2
Bankruptcy games, where v(C) represents the part of the estate the coalition C can guarantee for its members, are convex, and thus also superadditive, cohesive, and monotonic.
Paolo Turrini Coalitional Games Agent-based Systems
Issues
The central questions in coalitional game theory are:
Which coalitions will form?
How should the members of coalition C divide their surplus v(C)?
What would be a division that ensures stability? (this lecture) What division would be fair? (next lecture)
Often, the forming of the grand coalition N is considered the goal. This is particularly reasonable for games that are superadditive.
Paolo Turrini Coalitional Games Agent-based Systems
Example
Consider the following 3-player TU game ⟨N , v ⟩, with N = {1, 2, 3}, in which no single player can generate any surplus on her own:
v({1}) = 0 v({2}) = 0 v({3}) = 0
v({1,2}) = 7 v(N) = 10 v({1, 3}) = 6
v({2, 3}) = 5
Exercise: What coalition(s) will form? How to divide the surplus?
Paolo Turrini Coalitional Games Agent-based Systems
Payoff Vectors and Imputations
Suppose the grand coalition has formed. How to divide its surplus? Recall: v(N) is the surplus of the grand coalition N, and n = |N|.
A payoff vector is a vector x = (x1, . . . , xn) ∈ Rn0. Properties:
x is feasible if xi v(N): do no allocate more than there is.
i∈N
x is efficient if xi = v(N): allocate all there is.
i∈N
x is individually rational if xi v({i}) for all players i ∈ N: nobody should be
able to do better on her own.
An imputation is a payoff vector that is both individually rational and efficient (and thus also feasible). Reasonable to focus on imputations.
Paolo Turrini Coalitional Games Agent-based Systems
The Core
Which imputations incentivise players to form the grand coalition?
Probably the most important solution concept for coalitional games, formalising this kind of stability notion, is the so-called “core” . . .
An imputation x = (x1,…,xn) is in the core of the game ⟨N,v⟩ if no coalition C ⊆ N can benefit by breaking away from the grand coalition:
xi v(C) i∈C
Remark: Individual rationality is a special case of this (with C = {i⋆}).
D.B. Gillies.
Some Theorems on n-Person Games
PhD thesis, Department of Mathematics, Princeton University, 1959..
Paolo Turrini Coalitional Games Agent-based Systems
Example: Game with an Empty Core
Consider the following 3-player TU game ⟨N , v ⟩, with N = {1, 2, 3}, in which no single player can generate any surplus on her own:
v({1}) = 0 v({2}) = 0 v({3}) = 0
v({1,2}) = 7 v(N) = 8 v({1, 3}) = 6
v({2, 3}) = 5
For an imputation x = (x1, x2, x3) to be in the core, we must have: forstability: x1 +x2 7andx1 +x3 6andx2 +x3 5
for efficiency: x1 + x2 + x3 = 8
But this clearly is impossible. So the core is empty.
Question: What games have a nonempty core? Characterisation?
Remark:QThe above game happens to be superadditive but not convex.
Paolo Turrini Coalitional Games Agent-based Systems
Characterisation for Simple Games
Recall: ⟨N,v⟩ is a simple game if v(C) ∈ {0,1} for all C ⊆ N. Player i ∈ N is said to be a veto player in the simple game ⟨N,v⟩, if for all C ⊆ N it is the case that i ̸∈ C implies v(C) = 0.
Proposition
A simple game (and thus also a voting game) has a nonempty core iff it has at least one veto player.
(⇐) Suppose there are k 1 veto players. Choose imputation x s.t. xi = 1 if i is a veto k
player, and xi = 0 otherwise. Then x is in the core: foreverywinningcoalitionC: xi =k·1 =1=v(C)
i∈C k
for every losing coalition C: i∈C xi 0 = v(C) holds vacuously
(⇒) Suppose the core is nonempty and x is in it. Let i⋆ ∈ argmax xi . i∈N
Will show that i⋆ can veto. By efficiency, xi⋆ > 0 and i∈N xi = 1. Take any C ⊆ N s.t. i⋆ ̸∈ C. Then i∈C xi < 1. Hence, v(C) = 0.
Paolo Turrini Coalitional Games Agent-based Systems
Convexity is a Sufficient Condition
Recall: ⟨N,v⟩isconvexifv(C∪C′)v(C)+v(C′)−v(C∩C′). Theorem (Shapley, 1971)
Every TU game that is convex has got a nonempty core.
Proof: Let [i] := {1,...,i} for any i ∈ N. Define an imputation x:
xi = v([i]) − v([i−1])
By monotonicity, xi 0. And: xi = v(N), i.e., x is efficient. Now take any C ⊂ N and i⋆ ∈ N such that [i⋆−1] ⊆ C and i⋆ ̸∈ C. By convexity: v(C ∪ {i⋆}) v(C) + v([i⋆]) − v([i⋆−1]). Thus:
−v(C) xi⋆ − v(C ∪ {i⋆})
i∈C xi − v(C) i∈C∪{i⋆} xi − v(C ∪ {i⋆})
Repeat: i∈Cxi−v(C) ··· i∈Nxi−v(N) = 0.
L.S. Shapley.
Cores of Convex Games.
International Journal of Game Theory, 1(1):11–26, 1971.
Paolo Turrini Coalitional Games Agent-based Systems
Cohesiveness is a Necessary Condition
Recall: ⟨N,v⟩iscohesiveifv(N)v(C1)+···+v(CK)foreverypossiblepartition C1∪···∪CK =N.
Proposition
Every TU game with a nonempty core is cohesive.
Proof: Consider any game ⟨N,v⟩ that is not cohesive. So there exists a partition C1 ⊎···⊎CK = N with v(C1)+···+v(CK) > v(N).
For the sake of contradiction, suppose the core is nonempty. So there’s an imputation x = (x1,…,xn) with i∈Ck xi v(Ck) for all k K.
Putting everything together, we get:
xi = xi +···+ xi v(C1)+···+v(CK) > v(N)
i∈N i∈C1 i∈CK
But this contradicts efficiency of x, i.e., it cannot be an imputation.
Exercise: Find a game with a nonempty core that is not superadditive.
Paolo Turrini Coalitional Games Agent-based Systems
The Bondareva-Shapley Theorem
Thus: convex ⇒ has nonempty core ⇒ superadditive. Getting close. We can do better and give a complete characterisation (w/o proof):
Theorem (Bondareva, 1962; Shapley 1967)
A TU game has a nonempty core iff that game is balanced.
A collection of weights λC ∈ [0,1], one for each coalition C ⊆ N, is called balanced if, forallplayersi∈N,wehaveC∋iλC =1.
A TU game ⟨N,v⟩ is called balanced if, for all balanced collections of weights λC, we haveC⊆NλC ·v(C)v(N).
Interpretation: “Grand coalition beats dividing time over coalitions.”
O.N. Bondareva.
The Theory of the Core of an n-Person Game (in Russian) Vestnik Leningrad University, 17(13):141–142, 1962.
L.S. Shapley.
On Balanced Sets and Cores.
Naval Research Logistics Quarterly, 14(4):453–460, 1967.
Paolo Turrini Coalitional Games Agent-based Systems
Summary
This has been an introduction to coalitional games, which include: network flow games: surplus = capacity of coalition’s network bankruptcy games: surplus = coalition’s guaranteed payment voting games: surplus = coalition’s ability to win vote
We’ve modelled them as transferable-utility games, i.e., the members of a coalition can freely distribute the surplus amongst themselves.
We’ve then asked: when will the grand coalition form and be stable?
Arguably, if we can find a payoff vector that is in the core.
So nonemptiness of the core is important. Results:
for simple (and voting) games: possible iff there is a veto player for general TU games: possible iff the game is balanced
What next? Matching
Paolo Turrini Coalitional Games Agent-based Systems