程序代写代做代考 AI game graph C Cooperative games

Cooperative games
COMP4418 Knowledge Representation and Reasoning
Haris Aziz1,2
1School of Computer Science and Engineering, UNSW Australia
2Data61, CSIRO 2019
H. Aziz (UNSW) Cooperative games 2019 1 / 59

Outline
1 Coalitional games: introduction
2 Coalitional games: solution concepts
3 Coalitional games: representations
4 Coalitional games: computational issues
5 Conclusions
H. Aziz (UNSW) Cooperative games 2019
2 / 59

Coalitional games
‘… we wish to concentrate on the alternatives for acting in cooperation with, or in opposition to, others, among which a player can choose. I.e. we want to analyze the possibility of coalitions the question between which players, and against which player, coalitions will form….’ – von Neumann and O. Morgenstern
H. Aziz (UNSW) Cooperative games 2019 4 / 59

Coalition games
Definition (Coalitional game)
A coalitional game is a pair (N,v) N = {1,…,n} is the set of players
v : 2N → R is a valuation function that associates with each coalition S ⊆ N a value v(S) where v(∅) = 0.
v(S) can be considered as the value generated when players in coalition S cooperate.
Usual assumptions: valuations are non-negative and v is monotonic i.e., S⊆T ⊆N impliesthatv(S)≤v(T),
H. Aziz (UNSW) Cooperative games 2019 5 / 59

Coalitional game
Example
S ∅ {1} {2} {3} {1,2} {1,3} {2,3} {1,2,3} v(S) 0 4 2 1 7 10 11 15
H. Aziz (UNSW) Cooperative games 2019 6 / 59

Simple coalitional game
Definition (Simple coalitional game)
A simple coalition game is a monotone coalitional game (N,v) with v:2N →{0,1}suchthatv(N)=1.
AcoalitionS⊆N iswinningifv(S)=1andlosingifv(S)=0. Also called simple voting game.
H. Aziz (UNSW) Cooperative games 2019 7 / 59

Solution concepts
v(N) is the amount which the players can earn if they work together. The aim is to divide v(N) among the players in a stable or fair manner.
Definition (Payoffs)
A payoff vector (x1,…,xn) ∈ RN specifies for each player i ∈ N the payoff xi which is player i’s share of v(N).
Definition (Efficient payoffs)
A payoff vector (x1,…,xn) ∈ RN is efficient if 􏰁i∈N xi = v(N), where xi denotes player i’s share of v(N).
Notation: x(S) = 􏰁i∈S xi
Definition (Individual rational payoffs)
A payoff vector x = (x1, . . . , xn) satisfies individual rationality if xi ≥ v({i}) for all i ∈ N.
H. Aziz (UNSW) Cooperative games 2019 9 / 59

Solution concepts
Definition (Solution concept)
A solution concept associates with each coalitional game (N,v) a set of payoff vectors(x1,…,xn)∈RN whicharestableorfairinsomesense.
H. Aziz (UNSW) Cooperative games 2019 10 / 59

Solution concepts: core Definition (Core)
A payoff vector x = (x1,…,xn) is in the core of a coalitional game (N,v) if for all S ⊂ N, x(S) ≥ v(S),
H. Aziz (UNSW) Cooperative games 2019 11 / 59

Solution concepts: core Definition (Core)
A payoff vector x = (x1,…,xn) is in the core of a coalitional game (N,v) if for all S ⊂ N, x(S) ≥ v(S), i.e., e(x,S) ≥ 0.
H. Aziz (UNSW) Cooperative games 2019 11 / 59

Solution concepts: core
Definition (Core)
A payoff vector x = (x1,…,xn) is in the core of a coalitional game (N,v) if for all S ⊂ N, x(S) ≥ v(S), i.e., e(x,S) ≥ 0.
Given a coalitional game (N, v) and payoff vector x = (x1, …, xn), the excess of a coalition S under x is defined by
e(x, S) = x(S) − v(S).
Recall that a payoff satisfies individual rationality if xi ≥ v({i}) for all i ∈ N.
Question
Does the core satisfy individual rationality?
H. Aziz (UNSW) Cooperative games 2019
11 / 59

Solution concepts: core
Definition (Core)
A payoff vector x = (x1,…,xn) is in the core of a coalitional game (N,v) if for all S ⊂ N, x(S) ≥ v(S), i.e., e(x, S) = x(S) − v(S) ≥ 0.
Formally proposed by Gillies (1959).
Donald Gillies
H. Aziz (UNSW) Cooperative games 2019 12 / 59

Solution concepts: core
Definition (Core)
A payoff vector x = (x1,…,xn) is in the core of a coalitional game (N,v) if for all S ⊂ N, x(S) ≥ v(S).
Example
There are three people and it takes at least two people to complete the task.
N = {1, 2, 3}
S ∅ {1} {2} {3} {2,3} {1,2} {1,3} {1,2,3}
v(S) 0 0 0 0 1 1 1 1
Question
Compute a core payoff of the game.
H. Aziz (UNSW) Cooperative games 2019 13 / 59

Solution concepts: least core
For ε > 0, a payoff vector x is in the ε-core if for all S ⊂ N, e(x,S) ≥ −ε. The least core is the intersection of all non-empty ε-cores.
The least core is the refinement of the ε-core and is the solution of the following LP:
min ε
s.t. x(S)≥v(S)−ε forallS⊂N,
xi ≥0foralli∈N, 􏰁i=1,…,n xi = v(N) .
(1)
H. Aziz (UNSW)
Cooperative games
2019 14 / 59

Solution concepts: least core
For ε > 0, an efficient payoff vector x is in the ε-core if for all S ⊂ N, e(x, S) ≥ −ε.
The least core is the intersection of all non-empty ε-cores.
The least core is the refinement of the ε-core and is the solution of the following LP:
min ε
s.t. x(S)≥v(S)−ε forallS⊂N,
xi ≥0foralli∈N, 􏰁i=1,…,n xi = v(N) .
Introduced in [Shapley and Shubik, 1966]
(2)
H. Aziz (UNSW) Cooperative games
2019 15 / 59
Lloyd Shapley Martin Shubik

Solution concepts: nucleolus Definition (Excess vector)
The excess vector θ(x) of a payoff vector x, is the vector (e(x, S1), …, e(x, S2n )) where e(x, S1) ≤ e(x, S2) ≤ e(x, S2n ).
Example
Player 1 has a right hand glove, player 2 has a left hand glove and player 3 also has a left hand glove. A group of players has gets value 1 for a proper pair of gloves and 0 otherwise.
S {1,2} {1,3} {1,2,3} ∅ {2} {3} {1} {2,3} v(S) 1 1 1 0 0 0 0 0
Table: Glove Game Compute the excess vector for payoff vector (1/2, 1/4, 1/4)
H. Aziz (UNSW) Cooperative games 2019 16 / 59

Solution concepts: nucleolus
Definition (Excess vector)
The excess vector of a payoff vector x, is the vector (e(x, S1 ), …, e(x, S2n )) where e(x, S1) ≤ e(x, S2) ≤ e(x, S2n ).
Definition (Nucleolus)
The nucleolus is the efficient payoff vector that has the largest excess vector lexicographically
θ(x) >lex θ(y) if the first coordinate in which the entry a in θ(x) is different than entry b in θ(y), it must be that a > b.
The nucleolus is in the least core.
It is in the core if the core is non-empty. The nucleolus is unique [Schmeidler, 1969]
H. Aziz (UNSW) Cooperative games 2019 17 / 59

Compute the nucleolus
S {1,2} {1,3} {1,2,3} ∅ {2} {3} {1} {2,3} v(S) 1 1 1 0 0 0 0 0
Table: Glove Game
H. Aziz (UNSW) Cooperative games 2019 18 / 59

Compute the nucleolus
S {1,2} {1,3} {1,2,3} ∅ {2} {3} {1} {2,3} v(S) 1 1 1 0 0 0 0 0
Table: Glove Game
Nucleolus: γ1 =1;γ2 =0;γ3 =0;
H. Aziz (UNSW) Cooperative games 2019 18 / 59

Core of simple games
Definition (Vetoer)
A player i is a vetoer if v(S) = 0 for any S ⊆ N \ {i}. Theorem
A simple game (N,v) has a non-empty core iff it has a vetoer. Moreover, an outcome (x1, . . . , xn) is in the core iff xi = 0 for all non-veto players.
Proof.
Assume there exist at least one vetoer i. Set xi = 1. Then consider any coalition S. If v(S) = 0, S cannot have an incentive to deviate. If v(S) = 1 then i ∈ S. Thus x(S) = v(S).
Assume there is no vetoer. Consider any payoff x. There exists a player i suchthatxi >0. Sinceiisnotavetoer,thenv(N\{i})=1. Thus x(N \ {i}) < v(N \ {i}). H. Aziz (UNSW) Cooperative games 2019 19 / 59 Bonderva-Shapley Theorem Definition (Balanced weights) λ:2N →R+ λ is balanced if ∀i ∈ N, 􏰁S:i∈S λ(S) = 1. Definition (Balanced game) A game (N,v) is balanced if for all balanced weights, v(N) ≥ 􏰁S⊆N λ(S)v(S). Theorem (Bondareva [1963]; Shapley [1967]) A coalitional game has a non-empty core if and only if it is balanced. H. Aziz (UNSW) Cooperative games 2019 20 / 59 Core of convex games I Definition (Convex Game) (N, v) is convex if v(S ∪ T) ≥ v(S) + v(T) − v(S ∩ T) for all S,T ⊂ N. Equivalently, (N, v) is convex if v(A ∪ {i}) − v(A) ≥ v(B ∪ {i}) − v(B) for all A, B ⊆ N \ {i} such that B ⊆ A. Theorem (Shapley, 1971) A convex game has a non-empty core. H. Aziz (UNSW) Cooperative games 2019 21 / 59 Core of convex games II Proof. x1 =v({1}),x2 =v({1,2})−v({1}),...xn =v(N)−v(N\{n}) We first show that v(N) = 􏰁i∈N xi x1 = x2 = xi = xn = 􏰂xi = i∈N Hence v(N) = 􏰁i∈N xi H. Aziz (UNSW) v({1}) − v(∅) v({1,2})−v({1}) v({1,2,...,i})−v({1,2,...,i−1}) v({1,...,n})−v({1,2,...,n−1}) v({1,...,n}) = v(N) Cooperative games 2019 22 / 59 Core of convex games I Theorem (Shapley, 1971) A convex game has a non-empty core. H. Aziz (UNSW) Cooperative games 2019 23 / 59 Core of convex games II Proof. x1 =v({1}),x2 =v({1,2})−v({1}),...xn =v(N)−v(N\{n}) Consider any coalition C = {j1,...jk} such that j1 < ··· < jk. We now show that 􏰁i∈C xi ≥ v(C). kk 􏰂xji =􏰂(v({1,...,ji})−v({1,...,ji −1})) i=1 i=1 k ≥􏰂(v({j1,...,ji})−v({j1,...,ji−1})) i=1 =(v(j1) − v(∅))+ (v({j1, j2}) − v(j1))+ ···+ (v({j1,...,jk})−v({j1,...,jk−1})) =v({j1,...,jk}) = v(C) Cooperative games H. Aziz (UNSW) 2019 24 59 / Solution concepts: Shapley value Definition (Shapley value) φi(N,v)= 1 􏰂 (|S|!)(|N|−|S|−1)!(v(S∪{i})−v(S)) v(S ∪ {i}) − v(S): marginal contribution of player i to coalition S Shapley value of a player is his expected marginal contribution in a uniformly random permutation Introduced by Shapley [1953] |S|! 􏰃􏰆􏰅􏰄 S 􏰅􏰄􏰃􏰆 i (|N|−|S|−1)! 􏰃 􏰆􏰅 􏰄 N \ (S ∪ {i}) |N |! S⊆N\{i} v(S) 􏰅 􏰄􏰃 􏰆 v(S∪{i}) H. Aziz (UNSW) Cooperative games 2019 25 / 59 Solution concepts: Shapley value Sπ(i) = {j | π(j) < π(i)} Sπ(i) is the set of players that come before i in permutation π. ∆Gπ (i) = v(Sπ(i) ∪ {i}) − v(Sπ(i)) is the marginal contribution of player i in permutation π. Definition (Shapley value) φi(G)= 1 􏰂 ∆Gπ(i) n! π∈ΠN Introduced by Shapley [1953] H. Aziz (UNSW) Cooperative games 2019 26 / 59 Shapley value of a simple game |S|! 􏰃􏰆􏰅􏰄 S 􏰅􏰄􏰃􏰆 i (|N|−|S|−1)! 􏰃 􏰆􏰅 􏰄 N \ (S ∪ {i}) v(S)=0 􏰅 􏰄􏰃 􏰆 v(S∪{i})=1 Shapley value φi = # permutations in which i has a marginal contribution of 1. |N |! H. Aziz (UNSW) Cooperative games 2019 27 / 59 Compute the Shapley value φi = 1 􏰂 (|S|!)(|N| − |S| − 1)!(v(S ∪ {i}) − v(S)) S {1,2} {1,3} {1,2,3} ∅ {2} {3} {1} {2,3} v(S) 1 1 1 0 0 0 0 0 Table: Glove Game |N |! S⊆N\{i} H. Aziz (UNSW) Cooperative games 2019 28 / 59 Compute the Shapley value 123 132 213 231 312 321 φi = 1 􏰂 (|S|!)(|N| − |S| − 1)!(v(S ∪ {i}) − v(S)) S {1,2} {1,3} {1,2,3} ∅ {2} {3} {1} {2,3} v(S) 1 1 1 0 0 0 0 0 Table: Glove Game |N |! S⊆N\{i} Shapley value: φ1 = 4/6; φ2 = 1/6; φ3 = 1/6 H. Aziz (UNSW) Cooperative games 2019 28 / 59 Compute the Shapley value φi = 1 􏰂 (|S|!)(|N| − |S| − 1)!(v(S ∪ {i}) − v(S)) S ∅ {1} {2} {3} {2,3} {1,2} {1,3} {1,2,3} v(S) 0 0 0 0 500 500 750 1000 Shapley value of player 2: 213: v({2}) − v(∅) = 0 231: v({2}) − v(∅) = 0 123: v({1, 2}) − v({1}) = 500 321: v({3, 2}) − v({3}) = 500 312: v({1, 2, 3}) − v({1, 3}) = 250 132: v({1, 2, 3}) − v({1, 3}) = 250 φ2 =(500+500+250+250)/6=250. |N |! S⊆N\{i} H. Aziz (UNSW) Cooperative games 2019 29 / 59 Compute the Shapley value φi = 1 􏰂 (|S|!)(|N| − |S| − 1)!(v(S ∪ {i}) − v(S)) S ∅ {1} {2} {3} {2,3} {1,2} {1,3} {1,2,3} v(S) 0 0 0 0 500 500 750 1000 Shapley value of player 2: 213: v({2}) − v(∅) = 0 231: v({2}) − v(∅) = 0 123: v({1, 2}) − v({1}) = 500 321: v({3, 2}) − v({3}) = 500 312: v({1, 2, 3}) − v({1, 3}) = 250 132: v({1, 2, 3}) − v({1, 3}) = 250 φ2 =(500+500+250+250)/6=250. φ1 =φ3 =375 H. Aziz (UNSW) Cooperative games 2019 29 / 59 |N |! S⊆N\{i} Shapley value: efficiency Shapley satisfies efficiency. Sπ(i) = {j | π(j) < π(i)} ∆Gπ (i) = v(Sπ (i) ∪ {i}) − v(Sπ (i)) ai = π−1(i) for i ∈ N ai is the player who appears in position i in π. Then, n 􏰂 ∆Gπ (i) =v({a1}) − v(∅)) + v({a1, a2}) − v({a1}) + · · · + i=1 v({a1, . . . , an}) − v({a1, . . . , an−1}) = v(N) n1n1n1 􏰂φi(G)= 􏰂 􏰂 ∆Gπ(i)= 􏰂 􏰂∆Gπ(i)= 􏰂 v(N)=v(N) π∈ΠN i=1 n! n! n! i=1 π∈ΠN π∈ΠN i=1 H. Aziz (UNSW) Cooperative games 2019 30 / 59 Shapley value: characterization The symmetry axiom says that players which make the same contribution should get the same payoff. v(S∪{i})−v(S)=v(S∪{j})−v(S)forallS⊆N\{i,j}⇒φi =φj The dummy player axiom says that players which make no contribution shouldgetnopayoff: ifv(S∪{i})−v(S)=0forallS⊆N\{i},⇒φi =0. (N, v1 + v2) is the game such that (v1 + v2)(S) = v1(S) + v2(S) for all S ⊆ N. Additivity axiom says that ∀i ∈ N, φi(N, v1 + v2) = φi(N, v1) + φi(N, v2) Theorem (Shapley, 1953) The Shapley value uniquely satisfies efficiency, symmetry, dummy player, and additivity. H. Aziz (UNSW) Cooperative games 2019 31 / 59 Shapley value: characterization The symmetry axiom says that players which make the same contribution should get the same payoff. v(S∪{i})−v(S)=v(S∪{j})−v(S)forallS⊆N\{i,j}⇒φi =φj The dummy player axiom says that players which make no contribution shouldgetnopayoff: ifv(S∪{i})−v(S)=0forallS⊆N\{i},⇒φi =0. (N, v1 + v2) is the game such that (v1 + v2)(S) = v1(S) + v2(S) for all S ⊆ N. Additivity axiom says that ∀i ∈ N, φi(N, v1 + v2) = φi(N, v1) + φi(N, v2) Theorem (Shapley, 1953) The Shapley value uniquely satisfies efficiency, symmetry, dummy player, and additivity. H. Aziz (UNSW) Cooperative games 2019 32 / 59 Shapley value: another characterization The symmetry axiom says that players which make the same contribution should get the same payoff. v(S∪{i})−v(S)=v(S∪{j})−v(S)forallS⊆N\{i,j}⇒φi =φj A solution φ satisfies marginality if for every pair of games (N,v) and (N, w) and every player i, if then v(S ∪ {i}) − v(S) = w(S ∪ {i}) − w(S), ∀S ⊆ N \ {i}, φi(N, v) = φi(N, w). Theorem (Young, 1985) The Shapley value uniquely satisfies efficiency, symmetry, and marginality. H. Aziz (UNSW) Cooperative games 2019 33 / 59 Fairness versus stability S {1,2} {1,3} {1,2,3} ∅ {2} {3} {1} {2,3} v(S) 1 1 1 0 0 0 0 0 Table: Glove Game Shapley value: φ1 = 4/6; φ2 = 1/6; φ3 = 1/6 Nucleolus: γ1 = 1;γ2 = 0; γ3 = 0; H. Aziz (UNSW) Cooperative games 2019 34 / 59 Banzhaf index for Simple Games Definition (Banzhaf index) A player i is critical in a coalition C if the player’s exclusion results in C changing from winning to losing. Banzhaf value ηi of a player i is the number of coalitions for which i is critical. Banzhaf index ηi βi = 􏰁i∈N ηi John Banzhaf H. Aziz (UNSW) Cooperative games 2019 35 / 59 Compute the Banzhaf indices Definition (Banzhaf index) A player i is critical in a coalition C if the player’s exclusion results in C changing from winning to losing. Banzhaf value ηi of a player i is the number of coalitions for which i is critical. Banzhaf index ηi βi = 􏰁i∈N ηi S {1,2} {1,3} {1,2,3} ∅ {2} {3} {1} {2,3} v(S) 1 1 1 0 0 0 0 0 Table: Game H. Aziz (UNSW) Cooperative games 2019 36 / 59 Compute the Banzhaf indices Definition (Banzhaf index) A player i is critical in a coalition C if the player’s exclusion results in C changing from winning to losing. Banzhaf value ηi of a player i is the number of coalitions for which i is critical. Banzhaf index ηi βi = 􏰁i∈N ηi S {1,2} {1,3} {1,2,3} ∅ {2} {3} {1} {2,3} v(S) 1 1 1 0 0 0 0 0 Table: Game Banzhaf indices: ? H. Aziz (UNSW) Cooperative games 2019 36 / 59 Compute the Banzhaf indices Definition (Banzhaf index) A player i is critical in a coalition C if the player’s exclusion results in C changing from winning to losing. Banzhaf value ηi of a player i is the number of coalitions for which i is critical. Banzhaf index ηi βi = 􏰁i∈N ηi S {1,2} {1,3} {1,2,3} ∅ {2} {3} {1} {2,3} v(S) 1 1 1 0 0 0 0 0 Table: Game Banzhaf indices: ? β1 =3/5;β2 =1/5;β3 =1/5. H. Aziz (UNSW) Cooperative games 2019 36 / 59 Outline 1 Coalitional games: introduction 2 Coalitional games: solution concepts 3 Coalitional games: representations 4 Coalitional games: computational issues 5 Conclusions H. Aziz (UNSW) Cooperative games 2019 37 / 59 Coalitional game representations Mathematically interesting to examine valuation functions which have more structure Need for succinct representations Modeling requirements Some representations: weighted voting games, graph games, and marginal contribution nets. H. Aziz (UNSW) Cooperative games 2019 38 / 59 Weighted Voting Games Definition (Weighted voting game) Players, N = {1, ..., n} with corresponding voting weights {w1, ..., wn} Quota, 0 ≤ q ≤ 􏰁1≤i≤n wi v(S)=1ifandonlyif􏰁i∈Swi ≥q. Notation: [q;w1,...,wn] Example S {1,2} {1,3} {1,2,3} ∅ {2} {3} {1} {2,3} v(S) 1 1 1 0 0 0 0 0 [3;2,1,1] H. Aziz (UNSW) Cooperative games 2019 39 / 59 Weighted Voting Games Definition (Weighted voting game) Players, N = {1, ..., n} with corresponding voting weights {w1, ..., wn} Quota, 0 ≤ q ≤ 􏰁1≤i≤n wi v(S)=1ifandonlyif􏰁i∈Swi ≥q. Notation: [q;w1,...,wn] Example S {1,2} {1,3} {1,2,3} ∅ {2} {3} {1} {2,3} v(S) 1 1 1 0 0 0 0 0 [3;2,1,1] Can every simple game be represented by a weighted voting game? Question H. Aziz (UNSW) Cooperative games 2019 39 / 59 Weighted Voting Games Proposition Every simple game cannot be represented by a weighted voting game. Proof. Consider the simple game (N, v) where N = {1, 2, 3, 4} and the minimal winning coalitions are {1, 2}, {1, 4}, {2, 3}. Assume (N,v) can be represented by a weighted voting game. w1 + w4 ≥ q, w2 + w4 < q =⇒ w1 > w2
w1 + w3 < q; w2 + w3 ≥ q =⇒ w2 > w1
H. Aziz (UNSW) Cooperative games 2019 40 / 59

Shapley value and Banzhaf value
Consider a weighted voting game in which the quota is 12 and the countries have the following weights:
France: 4 Germany: 4 Italy: 4 Belgium: 2 Netherlands: 2 Luxembourg: 1
What is the Banzhaf and Shapley value of Luxembourg?
H. Aziz (UNSW) Cooperative games 2019
41 / 59

Graph game
Definition (Graph game)
Graph game: Let G = (V, E, w) be a weighted undirected graph. The graph game for S ⊆ N, corresponding to G is the coalitional game (N,v) with
N=V
for each S ⊆ N, the value v(S) is the sum of the weight of the edges in the
subgraph induced by S.
253 −3 10 6
144
H. Aziz (UNSW) Cooperative games 2019 42 / 59

Graph game
Definition (Graph game)
Graph game: Let G = (V, E, w) be a weighted undirected graph. The graph game for S ⊆ N, corresponding to G is the coalitional game (N,v) with
N=V
for each S ⊆ N, the value v(S) is the sum of the weight of the edges in the
subgraph induced by S.
253 10
−3 6
144
H. Aziz (UNSW) Cooperative games 2019
43 / 59

Graph game
Definition (Graph game)
Graph game: Let G = (V, E, w) be a weighted undirected graph. The graph game for S ⊆ N, corresponding to G is the coalitional game (N,v) with
N=V
for each S ⊆ N, the value v(S) is the sum of the weight of the edges in the
subgraph induced by S.
−3 6
144
This representation is not complete (fully expressive).
253 10
H. Aziz (UNSW) Cooperative games 2019
43 / 59

Graph game
Definition (Graph game)
Graph game: Let G = (V, E, w) be a weighted undirected graph. The graph game for S ⊆ N, corresponding to G is the coalitional game (N,v) with
N=V
for each S ⊆ N, the value v(S) is the sum of the weight of the edges in the
subgraph induced by S.
Xiaotie Deng Christos Papadimitriou
H. Aziz (UNSW)
Cooperative games 2019 44 / 59

Marginal Contribution Nets
Definition (Marginal Contribution Nets)
Valuation function represented as rules: pattern → value. Pattern is conjunction of players (negation of a player is allowed).
Value of a coalition is the sum over the values of all the rules that apply to the coalition.
Example
x1 ∧ x2 → 4, x1 → 1, ¬x3 → 2 . Then we have v({1, 2}) = 4 + 1 + 2 = 7 as all three rules apply to coalition {1, 2}.
This representation is complete (fully expressive) and was introduced by Ieong and Shoham [2005]
H. Aziz (UNSW) Sam Ieong Cooperative gYaomaesv Shoham 2019 45 / 59

Marginal Contribution Nets
Example
1 x1 ∧ x2 −→ 5
2 x2−→2
3 x3−→4
4 x2 ∧ ¬x3 −→ −2
v({1}) = 0 (no rules apply)
v({2}) = 0 (rules 2 and 4 apply) v({3}) = 4 (rules 3 applies)
v({1, 2}) = 5 (rules 1, 2, 4 apply) v({1, 3}) = 4 (rule 3 applies) v({2, 3}) = 6 (rules 2 and 3 apply) v({1, 2, 3}) =
H. Aziz (UNSW) Cooperative games 2019
46 / 59

Marginal Contribution Nets
Example
1 x1 ∧ x2 −→ 5
2 x2−→2
3 x3−→4
4 x2 ∧ ¬x3 −→ −2
v({1}) = 0 (no rules apply)
v({2}) = 0 (rules 2 and 4 apply)
v({3}) = 4 (rules 3 applies)
v({1, 2}) = 5 (rules 1, 2, 4 apply)
v({1, 3}) = 4 (rule 3 applies)
v({2, 3}) = 6 (rules 2 and 3 apply)
v({1, 2, 3}) =11 (rules 1, 2, and 3 apply)
H. Aziz (UNSW) Cooperative games 2019
46 / 59

Marginal Contribution Nets
Proposition
MC-nets are universally expressive.
Proof.
For each coalition S we can have a separate rule where literal xi is in the rule if i∈Sandliteral¬xi isintheruleifi∈/S.Thevalueoftheruleisthevalueof coalition S.
Not that the rule only applies to its corresponding coalition.
H. Aziz (UNSW) Cooperative games 2019 47 / 59

Computational issues
How to represent the valuation function succinctly? For a given game G and solution concept X
Is X empty for G?
Compute a payoff in X for G. IsapayoffinX forG?
H. Aziz (UNSW) Cooperative games 2019
49 / 59

Computing the payoffs
Core: LP with an exponential number of constraints:
min x(N )
s.t. x(S)≥v(S) for all S ⊆N
xi ≥0foralli∈N,
Shapley value involves an exponential number of permutations
H. Aziz (UNSW) Cooperative games 2019 50 / 59

WVGs
Deciding if a player is a dummy: coNP-complete [Prasad and Kelly, 1990]. Implies that computing the Shapley value and Banzhaf indices is NP-hard.
Checking core non-emptiness/checking if an outcome is in the core: polynomial-time (since weighted voting games are simple games).
Computing a least core payoff is coNP-hard [Elkind et al., 2007]
Hard problems become polynomial-time solvable if weights are bounded (use of dynamic programming).
H. Aziz (UNSW) Cooperative games 2019
51 / 59

Graph games
Theorem (Deng and Papadimitriou [1994])
Computing Shapley: in polynomial time. A player gets half the payoff from its edges: φi = 􏰁i̸=j w({i, j})/2
However, determining emptiness of the core is NP-complete. Checking whether a specific outcome is in the core is coNP-complete.
H. Aziz (UNSW) Cooperative games 2019 52 / 59

Marginal Contribution Nets
Theorem (Ieong and Shoham [2005])
Shapley value: in polynomial time.
Checking whether an outcome is in the core is coNP-complete Checking whether the core is non-empty is coNP-hard.
A complete representation, but not necessarily succinct.
H. Aziz (UNSW) Cooperative games 2019 53 / 59

Marginal Contribution Nets Proposition
Shapley value of an MC-nets can be computed in linear time.
Proof.
By additivity of the Shapley value, it is sufficient to compute the Shapley value of each game induces by a single rule separately and then adding the Shapley values.
Consider a rule for which the value is x. Let us say there are p positive literals and s negative literals. For all players corresponding to positive literals, their marginal value is x if it appears after all players corresponding to positive literals and before all players corresponding to negative literals. The Shapley value of a positive player is ((p − 1)!s!/(p + s)!) × x
For all players corresponding to negative literals, the player will be responsible for cancelling the application of the rule if all positive literals come before the negative literals in the ordering, and the negative player is the first among the negative players.
The Shapley value of a negative player is (p!(s − 1)!/(p + s)!) × (−x)
H. Aziz (UNSW) Cooperative games 2019 54 / 59

Summary
Coalitional games model how and when coalitions form; how to distribute payoffs.
Solution concept Existence Uniqueness Core – –
Least Core Nucleolus Shapley value
􏰇 – 􏰇 􏰇 􏰇 􏰇
Table: Solution concepts for coalitional games
Some representations of coalitional games: WVGs, graph games, marginal
contribution nets.
H. Aziz (UNSW) Cooperative games 2019 56 / 59

Further Reading
G. Chalkiadakis, E. Elkind, and M. Wooldridge. Computational Aspects of Cooperative Game Theory. Morgan and Claypool, 2011.
H. Aziz (UNSW) Cooperative games 2019 57 / 59

References I
O. N. Bondareva. Some applications of linear programming methods to the theory of cooperative games (In Russian). Problemy Kybernetiki, 10:119–139, 1963.
X. Deng and C. H. Papadimitriou. On the complexity of cooperative solution concepts. Math. Oper. Res., 19(2):257–266, 1994.
E. Elkind, L. A. Goldberg, P. W. Goldberg, and M. J. Wooldridge. Computational complexity of weighted threshold games. In Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI), pages 718–723. AAAI Press, 2007.
S. Ieong and Y. Shoham. Marginal contribution nets: a compact representation scheme for coalitional games. In Proceedings of the 6th ACM Conference on Electronic Commerce (ACM-EC), pages 193–202. ACM, 2005.
K. Prasad and J. S. Kelly. NP-completeness of some problems concerning voting games. Int. J. Game Theory, 19(1):1–9, 1990.
D. Schmeidler. The nucleolus of a characteristic function game. SIAM J. Appl. Math., 17(6):1163–1170, 1969.
L. S. Shapley. A value for n-person games. Contrib. to the Theory of Games, pages 31–40, 1953.
H. Aziz (UNSW) Cooperative games 2019
58 / 59

References II
L. S. Shapley. On balanced sets and cores. Naval Research Logistics Quarterly, 14:453–460, 1967.
L. S. Shapley and M. Shubik. Quasi-cores in a monetary economy with non-convex preferences. Econometrica, 34:805–827, 1966.
H. Aziz (UNSW) Cooperative games 2019 59 / 59

Related Posts