"""Module for performing actions on restrictions
A restriction is a subset of strategies that are considered viable. They are
represented as a bit-mask over strategies with at least one true value per
role."""
import numpy as np
from gameanalysis import rsgame
from gameanalysis import utils
[docs]def num_deviation_profiles(game, rest):
"""Returns the number of deviation profiles
This is a closed form way to compute `deviation_profiles(game,
rest).shape[0]`.
"""
rest = np.asarray(rest, bool)
assert game.is_restriction(rest)
num_role_strats = np.add.reduceat(rest, game.role_starts)
num_devs = game.num_role_strats - num_role_strats
dev_players = game.num_role_players - np.eye(game.num_roles, dtype=int)
return np.sum(utils.game_size(dev_players, num_role_strats).prod(1) *
num_devs)
[docs]def num_deviation_payoffs(game, rest):
"""Returns the number of deviation payoffs
This is a closed form way to compute `np.sum(deviation_profiles(game, rest)
> 0)`."""
rest = np.asarray(rest, bool)
assert game.is_restriction(rest)
num_role_strats = np.add.reduceat(rest, game.role_starts)
num_devs = game.num_role_strats - num_role_strats
dev_players = (game.num_role_players - np.eye(game.num_roles, dtype=int) -
np.eye(game.num_roles, dtype=int)[:, None])
temp = utils.game_size(dev_players, num_role_strats).prod(2)
non_deviators = np.sum(np.sum(temp * num_role_strats, 1) * num_devs)
return non_deviators + num_deviation_profiles(game, rest)
[docs]def num_dpr_deviation_profiles(game, rest):
"""Returns the number of dpr deviation profiles"""
rest = np.asarray(rest, bool)
assert game.is_restriction(rest)
num_role_strats = np.add.reduceat(rest, game.role_starts)
num_devs = game.num_role_strats - num_role_strats
pure = (np.arange(3, 1 << game.num_roles)[:, None] &
(1 << np.arange(game.num_roles))).astype(bool)
cards = pure.sum(1)
pure = pure[cards > 1]
card_counts = cards[cards > 1, None] - 1 - \
((game.num_role_players > 1) & pure)
# For each combination of pure roles, compute the number of profiles
# conditioned on those roles being pure, then multiply them by the
# cardinality of the pure roles.
sp_dev = np.eye(game.num_roles, dtype=bool) & (game.num_role_players == 1)
pure_counts = num_role_strats * ~sp_dev + sp_dev
dev_players = game.num_role_players - np.eye(game.num_roles, dtype=int)
unpure_counts = utils.game_size(dev_players, num_role_strats) - pure_counts
pure_counts = np.prod(pure_counts * pure[:, None] + ~pure[:, None], 2)
unpure_counts = np.prod(unpure_counts * ~pure[:, None] + pure[:, None], 2)
overcount = np.sum(card_counts * pure_counts * unpure_counts * num_devs)
return num_deviation_payoffs(game, rest) - overcount
[docs]def deviation_profiles(game, rest, role_index=None):
"""Return strict deviation profiles
Strict means that all returned profiles will have exactly one player where
rest is false, i.e.
`np.all(np.sum(profiles * ~rest, 1) == 1)`
If `role_index` is specified, only profiles for that role will be
returned."""
rest = np.asarray(rest, bool)
assert game.is_restriction(rest)
support = np.add.reduceat(rest, game.role_starts)
def dev_profs(players, mask, rs):
rgame = rsgame.emptygame(players, support)
non_devs = translate(rgame.all_profiles(), rest)
ndevs = np.sum(~mask)
devs = np.zeros((ndevs, game.num_strats), int)
devs[:, rs:rs + mask.size][:, ~mask] = np.eye(ndevs, dtype=int)
profs = non_devs[:, None] + devs
profs.shape = (-1, game.num_strats)
return profs
if role_index is None:
profs = [dev_profs(players, mask, rs) for players, mask, rs
in zip(game.num_role_players - np.eye(game.num_roles,
dtype=int),
np.split(rest, game.role_starts[1:]),
game.role_starts)]
return np.concatenate(profs)
else:
players = game.num_role_players.copy()
players[role_index] -= 1
mask = np.split(rest, game.role_starts[1:])[role_index]
rs = game.role_starts[role_index]
return dev_profs(players, mask, rs)
[docs]def additional_strategy_profiles(game, rest, role_strat_ind):
"""Returns all profiles added by strategy at index"""
# This uses the observation that the added profiles are all of the profiles
# of the new restricted game with one less player in role, and then where
# that last player always plays strat
rest = np.asarray(rest, bool)
assert game.is_restriction(rest)
new_players = game.num_role_players.copy()
new_players[game.role_indices[role_strat_ind]] -= 1
base = rsgame.emptygame(new_players, game.num_role_strats)
new_mask = rest.copy()
new_mask[role_strat_ind] = True
profs = base.restrict(new_mask).all_profiles()
expand_profs = np.zeros((profs.shape[0], game.num_strats), int)
expand_profs[:, new_mask] = profs
expand_profs[:, role_strat_ind] += 1
return expand_profs
[docs]def translate(profiles, rest):
"""Translate a strategy object to the full game"""
assert profiles.shape[-1] == rest.sum()
if rest.all():
return profiles
else:
new_profs = np.zeros(profiles.shape[:-1] + (rest.size,),
profiles.dtype)
new_profs[..., rest] = profiles
return new_profs
[docs]def to_id(game, rest):
"""Return a unique integer representing a restriction"""
bits = np.ones(game.num_strats, int)
bits[0] = 0
bits[game.role_starts[1:]] -= game.num_role_strats[:-1]
bits = 2 ** bits.cumsum()
roles = np.insert(np.cumprod(2 ** game.num_role_strats[:-1] - 1), 0, 1)
return np.sum(roles * (np.add.reduceat(
rest * bits, game.role_starts, -1) - 1), -1)
[docs]def from_id(game, rest_id):
"""Return a restriction mask from its unique id"""
rest_id = np.asarray(rest_id)
bits = np.ones(game.num_strats, int)
bits[0] = 0
bits[game.role_starts[1:]] -= game.num_role_strats[:-1]
bits = 2 ** bits.cumsum()
roles = 2 ** game.num_role_strats - 1
rolesc = np.insert(np.cumprod(roles[:-1]), 0, 1)
return (np.repeat(rest_id[..., None] // rolesc % roles + 1,
game.num_role_strats, -1) // bits % 2).astype(bool)
[docs]def maximal_restrictions(game):
"""Returns all maximally complete restrictions
This function returns an array of restrictions, such that no restriction is
a sub_restriction (i.e. `np.all(sub <= rest)`) and that no restriction
could be increased, and still contain complete payoff data for the game.
This is reducible to clique finding, and as such is NP Hard"""
# invariant that we have data for every restriction in queue
# The reverse order is necessary for the order we explore
pure_profs = game.pure_profiles()[::-1]
queue = [p > 0 for p in pure_profs if p in game]
maximals = []
while queue:
rest = queue.pop()
maximal = True
devs = rest.astype(int)
devs[game.role_starts[1:]] -= np.add.reduceat(
rest, game.role_starts)[:-1]
devs = np.nonzero((devs.cumsum() > 0) & ~rest)[0][::-1]
for dev_ind in devs:
profs = additional_strategy_profiles(game, rest, dev_ind)
# TODO Some anecdotal evidence suggests that when checking multiple
# profiles, np.isin(profs, game.profiles()) is faster for checking
# multiple profiles. We can potentially avoid using a dictionary
# and instead use numpy set operations
if all(p in game for p in profs):
maximal = False
rest_copy = rest.copy()
rest_copy[dev_ind] = True
queue.append(rest_copy)
# This checks that no duplicates are emitted. This algorithm will
# always find the largest subset first, but subsequent 'maximal'
# subsets may actually be subsets of previous maximal subsets.
if maximal and not any(np.all(rest <= s) for s in maximals):
maximals.append(rest)
return np.array(maximals)