Multi-Agent Systems

5. Game Theory (III)

Florin Leon
“Gheorghe Asachi” Technical University of Iași, Romania
Faculty of Automatic Control and Computer Engineering

http://florinleon.byethost24.com/lect_mas.html

2024
Game Theory (III)
N-Agent Cooperative Games
1. Shapley Value
2. Nucleolus
Sequential Games
3. Minimax Algorithm
4. Information Sets

2
Game Theory (III)
N-Agent Cooperative Games
1. Shapley Value
2. Nucleolus
Sequential Games
3. Minimax Algorithm
4. Information Sets

3
Shapley Value
 The core offers a set of solutions for a game
 Some games do not have a core
 There is no way of evaluating the “fairness” of the imputations in
the core
 The Shapley value is a payoff distribution in which each agent
receives a payoff according to its marginal contribution to the
coalitions it can join
 For n agents, there are n! orderings in which an agent can join
other agents
 The Shapley value represents the average on all possible
orderings

4
Example 1

5
The Shapley Value: Definition
 Let B(π, i) be the set of agents in the ordering π which appear before agent i
 The Shapley value of agent i in the set A of all agents is:

1
𝜑 𝐴, 𝑖 = 𝑣 𝐵 𝜋, 𝑖 ∪ 𝑖 − 𝑣 𝐵 𝜋, 𝑖
|𝐴|!
𝜋∈Π𝐴

 where ΠA is the set of all possible orderings of set A

 Another way to express the same formula, with |A| = n and |S| = s is:
1
𝜑𝑖 = 𝑛 − 𝑠 ! ⋅ 𝑠 − 1 ! ∙ 𝑣 𝑆 − 𝑣 𝑆 − {𝑖}
𝑛!
𝑖∈𝑆⊆𝐴

 There are more identical coalitions to which an agent can be added, e.g.,
B can be added to AC and CA, resulting in ABC and CAB, but B ’s contribution
is the same
6
Example 2
Properties
 The Shapley value always exists, is unique and efficient (the sum of
the agents’ payoffs is the maximum)
 It may not belong to the core, even if the core of the game is
non-empty. In this case, the Shapley value is unstable
 For example, the game with v(A) = v(B) = v(C) = 0, v(AB) = 1,
v(AC) = 1, v(BC) = 0, v(ABC) = 1 has a core with only one
imputation: (1, 0, 0), but its Shapley value is: (2/3, 1/6, 1/6)

8
Discussion
 It may involve a considerable computational effort
 It is feasible for only a small number of agents
 However, there are approximate computational methods
(e.g., averaging the contributions in a large number of random
coalitions)

 In a real multi-agent system, even computing the values of

subcoalitions can be a very complex task

9
Convex Games
 A game is convex if its characteristic function is supermodular:
𝑣 𝑆 ∪ {𝑖} − 𝑣 𝑆 ≤ 𝑣 𝑇 ∪ 𝑖 − 𝑣 𝑇 , ∀𝑆 ⊆ 𝑇 ⊆ 𝐺

 The motivation to join a coalition (the additional payoff)

increases as the coalition grows
 Convexity is a stronger condition than superadditivity:
all convex games are superadditive, but not all superadditive
games are convex
 The core of a convex game is always non-empty, and the
Shapley value belongs to the core and is at its center of gravity

10
Example
 Consider this game: v(A) = 2, v(B) = 3, v(C) = 4, v(AB) = 6,
v(AC) = 7, v(BC) = 8, v(ABC) = 10
 This game is superadditive (𝑣 𝑆 ∪ 𝑇 ≥ 𝑣 𝑆 + 𝑣(𝑇)), but not convex
 E.g., adding agent C to subcoalitions S={A} and T={AB}
 v(ABC) − v(AB) = 10−6 = 4
 v(AC) − v(A) = 7−2 = 5
 Here 4 < 5, i.e., adding C to a larger coalition {AB} results in a lower
marginal gain than adding C to {A}
 If v(ABC) = 12, the game becomes convex

11
Banzhaf Power Index
 The power index is a numerical way of looking at power in a
weighted voting situation
 The Shapley-Shubik power index relies on permutations, like
the Shapley value
 The Banzhaf power index is less computationally demanding
 To calculate the Banzhaf power index:
 List all winning coalitions
 In each coalition, identify the agents who are critical
 Count up how many times each agent is critical
 Normalize these counts by dividing by the total times any agent is
critical

12
Example
 Computing the Banzhaf power index for the voting system [8 : 6, 3, 2]
 There are 3 parties/agents: P1 has 6 members, P2 has 3 members, and
P3 has 2 members
 A decision is made with at least 8 votes (out of 11)

 We list all winning coalitions

 We can list all coalitions, then eliminate the non-winning coalitions

 No agent is a dictator, so we only consider 2 and 3 agent coalitions

 {P1, P2}: total weight 9 ≥ 8

 {P1, P3}: total weight 8 ≥ 8

 {P2, P3}: total weight: 5 < 8

 {P1, P2, P3}: total weight: 11 ≥ 8

13
Example ([8 : 6, 3, 2])
 Next we determine which agents are critical in each winning coalition
 In the winning two-agent coalitions, both agents are critical since no agent
can meet the quota alone. We underline the critical agents:
 {P1, P2}
 {P1, P3}
 In the three-agent coalition, either P2 or P3 could leave the coalition and the
remaining agents could still meet the quota, so neither is critical. If P1 were
to leave, the remaining agents could not reach quota, so P1 is critical:
 {P1, P2, P3}
 P1 is critical 3 times, P2 is critical 1 time, and P3 is critical 1 time
 Finally, we convert the counts to percents:
 P1 → 3/5 = 60%
 P2 → 1/5 = 20%
 P3 → 1/5 = 20%
14
Example: The Scottish Parliament
 The voting system is [65 : 47, 46, 17, 16, 2]

15
Example: The Scottish Parliament

 Even though the Liberal Democrat party (16) has only one less
representative than the Conservative party (17), and fourteen more than
the Scottish Green party (2), its Banzhaf power index is the same as the
Scottish Green party’s
 In politics, forming coalitions is an essential part of getting results, and a
party’s ability to help a coalition reach quota defines its influence

16
Game Theory (III)
N-Agent Cooperative Games
1. Shapley Value
2. Nucleolus
Sequential Games
3. Minimax Algorithm
4. Information Sets

17
Computational Method
 For each imputation x and coalition S, the excess of S in x is:
𝑒𝑆 𝐱 = 𝑣 𝑆 − 𝑥𝑖
𝑖∈𝑆
 In the core, 𝑒𝑆 𝐱 ≤ 0, meaning that the payoffs in x are better than
in S, so the agents would prefer x
 The excess can be considered as a measure of the “unhappiness” of
coalition S for imputation x
 The goal is to find the imputation which minimizes the greatest
excess es(x), i.e., to make the unhappiest coalition less unhappy

18
Example 1
 Let us consider a game with the following characteristic form:
v(A) = v(B) = v(C) = 0, v(AB) = 60, v(AC) = 80, v(BC) = 100, v(ABC) = 105
 We start with an arbitrary imputation, x = (20, 35, 50)
 We compute the excesses:

𝑒𝑆 𝐱 = 𝑣 𝑆 − 𝑥𝑖
𝑖∈𝑆

 BC could get 100 in {BC}, but with imputation x they only get 35 + 50 = 85

19
Example 1
 The greatest excess is eBC(x) = 15
 We can minimize it by choosing an imputation which offers a greater payoff
to the BC coalition (less to A)
 Because eAC(x) > eAB(x), we can take 5 from A and give it to C
 We obtain a new imputation y = (15, 35, 55)

 The result is the minimum: further decreasing any excess will lead to an
increase in another one

20
Example 2
 Let us consider a game with the following characteristic form:
v(A) = v(B) = v(C) = 0, v(AB) = 4, v(AC) = 0, v(BC) = 3, v(ABC) = 6
 We start with x = (2, 3, 1)

the greatest excess

21
Example 2
 eABC(x) cannot be minimized (the excess of the grand coalition is
always 0)
 We choose the next maximum excess: eC(x) = eAB(x) = eBC(x) = –1
 We take 0.5 from A and give it to B
 We obtain the nucleolus y = (1.5, 3.5, 1)

22
Computation
 The previous examples were solved empirically. In the general case,
it is computed iteratively, by successively solving a series of linear
programs
 For n agents, the nucleolus can be computed in at most n steps
(with n successive linear programs)
 If there multiple solutions in the first LP, the coalition value with
the greatest excess is fixed in the second LP with the excess value
obtained in the first LP, and so on

23
LPSolve (First LP)
Computation
 For 3 agents, there are direct formulas (the next slide)

25
26
Results

27
Properties
 The nucleolus always exists and is unique
 It belongs to the core if the core is non-empty (it is stable)
 It is the most interior point of the core

28
Shapley Value vs. Nucleolus

 Shapley value - 𝜑  Nucleolus - 𝜈

29
The Partition of Bosnia-Herzegovina
 The Dayton Accord was a peace agreement reached in 1995 by
the presidents of BH, Croatia and Serbia to end the war in BH
 It resulted in the division of BH into the Federation of Bosnia
and Herzegovina (Muslim/Bosniak + Croat, 51%) and
Republika Srpska (Serb, 49%), based on census data from 1991

Federation of Bosnia
Republika Srpska
and Herzegovina

30
Conditions
 Multiple partition criteria are possible; below are the ones that best match the
final partition (C. Papahristodoulou, The Dayton Division of Bosnia and Other
Core Allocations, Applied Economics Letters, vol. 7(5), pp. 325-336, 2000)
 Single majority rule is applied ( > 50% of the opstina’s territory), in order to define an opstina’s
ethnicity (opština = municipality). As mentioned earlier, opstinas where no ethnic group is in
single majority are defined as M-opstinas
 Neither foreign nor M-opstina will separate and isolate (from ground) two ethnically
homogenous opstinas. At least one main and free road will connect two ethnically homogenous
opstinas when these opstinas build their own connected or united stand alone coalition
 Assumption (1) above applies to two parts coalition as well, so that if two parts are in single
majority, the opstina belongs to them. The excluded part in the same opstina cannot block their
coalition. Even adjacent and relevant M-opstinas will be included in two parts coalitions, if the
colluded parts’ share is at least 50%
 In accordance with assumption (2) above, the two parts coalitions are not allowed to include
own opstinas which are disconnected by the excluded foreign part being in single majority. The
isolated own opstinas will be included though, if the adjacent and separating opstina is a relevant
M-opstina and included in the two parts coalitions, as in (3) above. In that case the relevant
M-opstina connects in fact these disconnected opstinas

31
Game Theoretic Analysis
 Coalition values based on criteria like the previous ones, expressed in
terms of area
 M = Muslim/Bosniak, S = Serb, C = Croat

 v({M}) = 13214, v({S}) = 10549, v({C}) = 3813

 v({M,S) = 44659, v({M,C}) = 26267 , v({S,C}) = 30577
 v({M,S,C}) = 51233 (total area of BH: 51233 km2)

 Shapley value: (20717, 21540, 8976) ⇒ {S} – 42%, {M,C} – 58%

 Nucleolus: (20335, 24645, 6253) ⇒ {S} – 48%, {M,C} – 52%
 Final partition: {S} – 49%, {M,C} – 51%

32
The Marriage Contract Problem
 Babylonian Talmud, Ketuboth 93a

 A man dies leaving 3 wives with claims on his estate based on their
marriage contracts
 Wife 1 claims 100 silver coins, Wife 2 claims 200 coins, and
Wife 3 claims 300 coins: claims = (100, 200, 300)
 If the estate is worth less than the total claims, it is divided as
follows:
 If the estate is worth 100 coins, they are divided equally among the
wives: 100 ⇒ (33.3, 33.3, 33.3)
 If the estate is worth 200 coins, Wife 1 gets 50, while Wives 2 and 3
receive 75 each: 200 ⇒ (50, 75, 75)
 If the estate is worth 300 coins, Wife 1 receives 50, Wife 2 gets 100, and
Wife 3 gets 150: 300 ⇒ (50, 100, 150)
33
Game Theoretic Analysis
𝑣 𝑆 = max 0, 𝑡 − 𝑐𝑖 , 𝑐𝑖 ∈ 100, 200, 300
𝑖∈𝐺∖𝑆

 v(1) = v(2) = v(3) = v(12) = v(13) = v(23) = 0, v(123) = 100

 Nucleolus: (33.3, 33.3, 33.3), t = 100

 v(1) = v(2) = v(3) = 0, v(12) = v(13) = 0, v(23) = 100, v(123) = 200

 Nucleolus: (50, 75, 75), t = 200

 v(1) = v(2) = v(3) = 0, v(12) = 0, v(13) = 100, v(23) = 200, v(123) = 300
 Nucleolus: (50, 100, 150), t = 300

34
Cost Allocation Problems
 Allocating hydroelectric costs in India

35
(Mysore)

36
Costs

37
Coalitions values

The coalition values represent

the savings by cooperating:

38
The Shapley Values

39
Core, Nucleolus, Shapley Value

40
Allocating Costs
 Cφ(T ) = C(T ) – φT = 533 – 48.33 = 484.67
 Cφ(A) = C(A) – φA = 187 – 28.33 = 158.67
 Cφ(K) = C(K) – φK = 86 – 76.33 = 9.67

 Tamil Nadu (T ) should pay around 75%

 Andhra Pradesh (A) the rest of 25%
 Kerala-Mysore (K) has important resources and therefore should not pay much

 With the nucleolus: Cν(T ) = 493, Cν(A) = 169, Cν(K) = – 9

41
Game Theory (III)
N-Agent Cooperative Games
1. Shapley Value
2. Nucleolus
Sequential Games
3. Minimax Algorithm
4. Information Sets

42
Sequential Games
 Games where the decisions of the agents are made sequentially,
one after the other
 The solution method involves the analysis of the game tree
 Two-agent sequential games (with game trees) can be
transformed into strategic games (with game matrices)
 In practice, game trees are very large, and the corresponding
game matrices would be even larger

43
Deterministic Games with Perfect
Information

Chess Checkers Go

Othello Tic-tac-toe

44
Game Tree Example
 Rose and Colin are playing a zero-sum game
 Rose goes first and can choose the number y as: 2, 5 or 8
 Then Colin can choose x as: y – 1, y or y + 1
 Rose’s payoff is: 2x – y
 The terminal nodes show Rose’s payoffs

45
Equivalent Game Matrix

 If we write the game matrix with direct combinations of strategies,

some strategy profiles are undefined (e.g., if Rose chooses 2, Colin
cannot choose 4)
46
Equivalent Game Matrix

 In this (correct) formulation, Colin’s strategies depend on Rose’s

 C1-C4-C7 means: “if Rose chooses 2, Colin chooses 1; if Rose chooses
5, Colin chooses 4; if Rose chooses 8, Colin chooses 7”
47
Zermelo’s Theorem, Minimax Algorithm
 Since game matrices can become very large, it is easier to solve these
games based on their game trees
 Zermelo’s theorem is a proof stating that in two-agent perfect
information games, an optimal winning or drawing strategy always
exists
 The strategy can be found by backward induction: starting from the
last move, each agent anticipates the other’s strategies, choosing
actions that maximize its payoffs until reaching the game beginning
 The Minimax algorithm is a practical method for choosing moves in
two-agent games
 Zermelo’s theorem proves existence of an optimal strategy
theoretically, while Minimax computes the optimal moves

48
 Minimax Algorithm

choose this move

heuristic
evaluation
function 49
Evaluation Function
 Evaluates the value of a board configuration (position)
 It is a heuristic function and encompasses expert knowledge about the
problem domain
 The computer’s intelligence largely depends on the evaluation function

 We assume that the game is zero-sum

 We can use a single evaluation function for both agents
 f(n) > 0 : position n is good for the computer and bad for the opponent
(human)
 f(n) < 0 : position n is bad for the computer and good for the opponent

50
Multi-Player Games
 The evaluation function returns a vector with the utilities of all
agents

51
Alliances
 Alliances may result from the application of individual optimal
strategies
 Cooperation may result from following the (selfish) individually
rational behavior

52
Simple Games
 For simple games (e.g., Hex), the game tree can be fully solved
 Hex is a two-agent game played on a rhombic board with hexagonal cells
 A move consists of labeling a vacant hexagon on the board. The hexagon
then becomes part of the territory of the agent who claimed it
 At the beginning, each agent’s territory consists of two opposite sides of the
board (sides A-C or B-D)
 The winner is the first to link their two sides of the board by a continuous
chain of hexagons. Hex cannot end in a draw

53
Swap Rule in Hex
 To keep the game interesting, in Hex, a swap rule is used
 The swap can be made after the first or the third move
 The pie rule for swapping: after the first agent A makes, e.g., its first
move, the second agent B has two options:
 Let the move stand ⇒ B remains the second agent and moves or
 Switch places ⇒ B is now the first agent, and A makes the next move
 The rule gets its name from the problem of sharing a pie between
two persons
 It is fair for the first person to cut the pie and the second person to choose
one of the slices

54
Other Examples of Applications of
Cooperative Games in Agent-Based Systems
 Resource allocation in networked systems: Agents in distributed networks
(e.g., sensors) can cooperatively allocate bandwidth and energy, and optimize
resource use for reliable network performance
 Robotic swarm coordination: Multi-robot systems can coordinate tasks
(e.g., area coverage, object transport) to maximize efficiency and avoid
redundant movements or collisions
 Electric vehicles charging and grid load balancing: EV charging stations can
use cooperative scheduling to balance grid load, minimize peak demand,
and enhance energy distribution stability
 Supply chain and logistics optimization: Agents in supply chains can align
inventory and routes, reduce costs and improve order fulfillment by
collaborating on shared goals
 Collaborative autonomous driving: Autonomous vehicles can use cooperative
decisions in merging and lane changes to improve traffic flow and safety

55
Game Theory (III)
N-Agent Cooperative Games
1. Shapley Value
2. Nucleolus
Sequential Games
3. Minimax Algorithm
4. Information Sets

56
Information Sets
 An information set is a set of indistinguishable states, which
represent the agents’ uncertainty about previous moves
 It is a concept used in imperfect information games, such as
Poker

57
Example: Matching Pennies
 Rose puts a coin either “head up” (H) or “tail up” (T)
 Colin, not knowing Rose’s choice, calls either “head” or “tail”
 “Not knowing Rose’s choice” is represented with a dotted line
 Colin does not know what node he is at when he makes his decision
 Both nodes are in the same information set
 Colin knows he is at a node in this information set, but he does not know which one
 If Colin guesses correctly, Rose pays him 1 unit, otherwise Colin pays Rose 1

58
Example: Matching Pennies
 Rose has two pure strategies: H and T
 Although Colin has 4 branches coming out from his two nodes, the two
nodes are on the same information set
 Thus they will be considered as one “supernode”, and Colin can only choose
H or T at that information set

59
Simple Poker

60
Simple Poker
 Colin has two information sets: Ace and King
 For each information set, he has two choices: bet or drop
 Colin’s pure strategies: BB, BD, DB, DD
 BB = always bet; BD = he bets if he has an Ace and drops if he has a King

 Rose also has two information sets: Ace and King

 For each set, she also has two choices: call or fold
 Rose’s pure strategies: CC, CF, FC, FF
 CF = she calls if she has an Ace and folds if she has a King

61
62
The Full Game Matrix
Another example
Colin has three nodes, but the right two nodes are in the same information set, so in fact,
Colin has just two supernodes: a normal node (the left one with 3 possible moves), and
a supernode (combining the right two nodes with 2 possible moves)
Thus Colin has 3 x 2 = 6 pure strategies: DG, DH, EG, EH, FG, and FH
Rose has 5 supernodes with 3 (the root node), 2, 2, 2, and 2 possible moves, respectively
The non-redundant strategies are: AIK, AIL, AJK, AJL, BM, BN, CO, and CP

65
66
And Yet Another Example
 Combining the minimax algorithm with information sets
 Colin makes the first move (H or T) without letting Rose to know it
 Then Rose makes her decision (l or r) and announces it to Colin
 Finally Colin makes his second decision (L-S)

67
Conclusions
 The Shapley value and nucleolus are methods for determining
“fair” imputations
 In sequential games, agents move in turns, and each decision
influences future moves and outcomes
 The minimax algorithm minimizes an agent’s potential loss by
assuming the opponent will play optimally and selecting moves
that maximize its own minimum payoff
 An information set is a set of indistinguishable states, which
represent the agents’ uncertainty about previous moves in
imperfect information games

68
References
 Raymond Chan: Games and Strategic Thinking, Department of
Mathematics, The Chinese University of Hong Kong
 Philip D. Straffin: Game Theory and Strategy, Washington, The
Mathematical Association of America, 1993

69