05 Unanimity games
Unanimity or veto game is defined as follows. The game has a chosen subset \(S\) of players, which are the veto subset. Any subset \(T\) that has all the veto players i.e. \(S\subseteq T\) receives the reward and if it doesn’t have all the veto players it doesn’t.
You can import UnanimityGame class from shapley_numba.examples. But it has a easy implementation in shapley_numba:
import numba
import numpy as np
from shapley_numba import numba_game
@numba_game(gamespec=[('veto_set', numba.int32[:])])
class UnanimityGame:
"""Unanimity game class.
Unanimity game is the simplest game where if coalition contains a veto set
it wins and if the coalition does not contain the whole veto set it loses.
"""
def __init__(self, veto_set):
"""Initialize unanimity game."""
self.veto_set = np.array(veto_set, dtype=np.int32)
def value(self, subset) -> np.float64:
"""Return the value of coalition."""
if sum(subset * self.veto_set) >= sum(self.veto_set):
return 1.0
return 0.0
Let’s look at sample game payoffs.
from shapley_numba.common import subsets
veto_subset = [0, 1, 0, 1]
game = UnanimityGame(veto_subset)
print('Game Payoffs')
print('============')
print('Subset Payoff')
for subset in subsets(4):
similarity = sum(subset * veto_subset)
elements = sum(subset)
match (similarity, elements):
case (x, _) if x < 2:
print(subset, game.value(subset))
case (2, 2):
print(subset, game.value(subset), 'This is the veto subset!')
case (2, _):
print(subset, game.value(subset), 'Contains the veto subset')
Game Payoffs
============
Subset Payoff
[0 0 0 0] 0.0
[1 0 0 0] 0.0
[0 1 0 0] 0.0
[1 1 0 0] 0.0
[0 0 1 0] 0.0
[1 0 1 0] 0.0
[0 1 1 0] 0.0
[1 1 1 0] 0.0
[0 0 0 1] 0.0
[1 0 0 1] 0.0
[0 1 0 1] 1.0 This is the veto subset!
[1 1 0 1] 1.0 Contains the veto subset
[0 0 1 1] 0.0
[1 0 1 1] 0.0
[0 1 1 1] 1.0 Contains the veto subset
[1 1 1 1] 1.0 Contains the veto subset
Shapley for unanimity games
Shapley values for unanimity games are the classic demonstration of Shapley values axioms.
The player not in the veto subset are zero players, they should all get zero shapley values.
The players in the veto are all equivalent, so they should all split the payoff of 1 equally. Hence the payoff for a veto player is \(\frac{1}{\text{veto subset size}}\).
Let’s verify this for our example:
from shapley_numba.shapley import shapley
shapley(game, num_players=4)
array([0. , 0.5, 0. , 0.5])
Harsanyi dividends and unanimity games
Unanimity games have a very easy representation in terms of Harsanyi dividends - the veto set has dividend of one, while all other subsets have dividend of zero.
from shapley_numba.harsanyi_large import HarsanyiDividendsLarge
print('Game Dividends')
print('==============')
print('Subset Dividend')
hd = HarsanyiDividendsLarge(game, num_players=4)
for subset in subsets(4):
similarity = sum(subset * veto_subset)
elements = sum(subset)
match (similarity, elements):
case (x, _) if x < 2:
print(subset, hd(subset))
case (2, 2):
print(subset, hd(subset), 'This is the veto subset!')
case (2, _):
print(subset, hd(subset), 'Contains the veto subset')
Game Dividends
==============
Subset Dividend
[0 0 0 0] 0.0
[1 0 0 0] 0.0
[0 1 0 0] 0.0
[1 1 0 0] 0.0
[0 0 1 0] 0.0
[1 0 1 0] 0.0
[0 1 1 0] 0.0
[1 1 1 0] 0.0
[0 0 0 1] 0.0
[1 0 0 1] 0.0
[0 1 0 1] 1.0 This is the veto subset!
[1 1 0 1] 0.0 Contains the veto subset
[0 0 1 1] 0.0
[1 0 1 1] 0.0
[0 1 1 1] 0.0 Contains the veto subset
[1 1 1 1] 0.0 Contains the veto subset
The connection between unanimity games and Harsanyi Dividends.
This leads to the fundamental observation for transferable utility cooperative games: Every game payoff can be written as a linear combination of payoffs of unanimity games where the coefficients are Harsanyi Dividends.
Typically, this observation is not very useful because for a general game, the Harsanyi Dividends can grow very large and they can also oscillate in sign.
Airport game as sum of unanimity games
Indeed the airport game can be thought as a sum (linear combination) of unanimity games. We can verify this with shapley-numba.
from shapley_numba.examples import AirPortGame
# we will take the classical example from wikipedia:
length_requirements = [8, 11, 13, 18]
game = AirPortGame(np.array(length_requirements, dtype=np.float64))
hd = HarsanyiDividendsLarge(game, num_players=4)
print('Length Requirements - ', length_requirements)
print('Game Dividends')
print('==============')
print('Subset Dividend')
for subset in subsets(4):
dividend = hd(subset)
match tuple(subset):
case (0, 0, 0, 1):
print(subset, dividend, 'Longest company, last increment')
case (0, 0, 1, 1):
print(subset, dividend, 'Second increment')
case (0, 1, 1, 1):
print(subset, dividend, 'First increment')
case (1, 1, 1, 1):
print(subset, dividend, 'Shortest, initial segment')
case _:
print(subset, dividend)
Length Requirements - [8, 11, 13, 18]
Game Dividends
==============
Subset Dividend
[0 0 0 0] 0.0
[1 0 0 0] 8.0
[0 1 0 0] 11.0
[1 1 0 0] -8.0
[0 0 1 0] 13.0
[1 0 1 0] -8.0
[0 1 1 0] -11.0
[1 1 1 0] 8.0
[0 0 0 1] 18.0 Longest company, last increment
[1 0 0 1] -8.0
[0 1 0 1] -11.0
[1 1 0 1] 8.0
[0 0 1 1] -13.0 Second increment
[1 0 1 1] 8.0
[0 1 1 1] 11.0 First increment
[1 1 1 1] -8.0 Shortest, initial segment
Let us now verify the statement regarding combination of unanimity games. Currently, shapley_numba does not support summing and multiplying games by a scalar, so we will do it ourselves.
def unanimity_game_combination(hd, num_players):
"""Use Harsanyi dividends to combine unanimity games"""
all_unanimity_games = [UnanimityGame(subset) for subset in subsets(num_players)]
def combination(another_subset):
return sum(
[
hd(subset) * unanimity_game.value(another_subset)
for subset, unanimity_game in zip(
subsets(num_players), all_unanimity_games, strict=True
)
]
)
return combination
airport_game_comb = unanimity_game_combination(hd, 4)
print('Comparison of airport game and combination of unanimity games')
print('Game payoffs')
print('=============')
print('Subset Game payoff Combination payoff')
for subset in subsets(4):
print(subset, f'{game.value(subset):10f}', f'{airport_game_comb(subset):10f}')
Comparison of airport game and combination of unanimity games
Game payoffs
=============
Subset Game payoff Combination payoff
[0 0 0 0] 0.000000 0.000000
[1 0 0 0] 8.000000 8.000000
[0 1 0 0] 11.000000 11.000000
[1 1 0 0] 11.000000 11.000000
[0 0 1 0] 13.000000 13.000000
[1 0 1 0] 13.000000 13.000000
[0 1 1 0] 13.000000 13.000000
[1 1 1 0] 13.000000 13.000000
[0 0 0 1] 18.000000 18.000000
[1 0 0 1] 18.000000 18.000000
[0 1 0 1] 18.000000 18.000000
[1 1 0 1] 18.000000 18.000000
[0 0 1 1] 18.000000 18.000000
[1 0 1 1] 18.000000 18.000000
[0 1 1 1] 18.000000 18.000000
[1 1 1 1] 18.000000 18.000000
Unfortunately, the Harsanyi Dividends are not very sparse. An example where they are sparse is the dual of the airport game.
from shapley_numba.tools import dual_game
dual_airport = dual_game(game, num_players=4)
hd = HarsanyiDividendsLarge(dual_airport, num_players=4)
print('Length Requirements - ', length_requirements)
print('Game Dividends')
print('==============')
print('Subset Dividend')
for subset in subsets(4):
dividend = hd(subset)
match tuple(subset):
case (0, 0, 0, 1):
print(subset, dividend, 'Longest company, last increment')
case (0, 0, 1, 1):
print(subset, dividend, 'Second increment')
case (0, 1, 1, 1):
print(subset, dividend, 'First increment')
case (1, 1, 1, 1):
print(subset, dividend, 'Shortest, initial segment')
case _:
print(subset, dividend)
Length Requirements - [8, 11, 13, 18]
Game Dividends
==============
Subset Dividend
[0 0 0 0] 0.0
[1 0 0 0] 0.0
[0 1 0 0] 0.0
[1 1 0 0] 0.0
[0 0 1 0] 0.0
[1 0 1 0] 0.0
[0 1 1 0] 0.0
[1 1 1 0] 0.0
[0 0 0 1] 5.0 Longest company, last increment
[1 0 0 1] 0.0
[0 1 0 1] 0.0
[1 1 0 1] 0.0
[0 0 1 1] 2.0 Second increment
[1 0 1 1] 0.0
[0 1 1 1] 3.0 First increment
[1 1 1 1] 8.0 Shortest, initial segment