# Source code for nashpy.algorithms.support_enumeration

"""A class for a normal form game"""
import numpy as np
from itertools import chain, combinations

import warnings

[docs]def powerset(n):
"""
A power set of range(n)

Based on recipe from python itertools documentation:

https://docs.python.org/2/library/itertools.html#recipes
"""
return chain.from_iterable(combinations(range(n), r) for r in range(n + 1))

[docs]def solve_indifference(A, rows=None, columns=None):
"""
Solve the indifference for a payoff matrix assuming support for the
strategies given by columns

Finds vector of probabilities that makes player indifferent between
rows.  (So finds probability vector for corresponding column player)

Parameters
----------

A: a 2 dimensional numpy array (A payoff matrix for the row player)
rows: the support played by the row player
columns: the support player by the column player

Returns
-------

A numpy array:
A probability vector for the column player that makes the row
player indifferent. Will return False if all entries are not >= 0.
"""
# Ensure differences between pairs of pure strategies are the same
M = (A[np.array(rows)] - np.roll(A[np.array(rows)], 1, axis=0))[:-1]
# Columns that must be played with prob 0
zero_columns = set(range(A.shape)) - set(columns)

if zero_columns != set():
M = np.append(M, [[int(i == j) for i, col in enumerate(M.T)]
for j in zero_columns], axis=0)

# Ensure have probability vector
M = np.append(M, np.ones((1, M.shape)), axis=0)
b = np.append(np.zeros(len(M) - 1), )

try:
prob = np.linalg.solve(M, b)
if all(prob >= 0):
return prob
return False
except np.linalg.linalg.LinAlgError:
return False

[docs]def potential_support_pairs(A, B, non_degenerate=False):
"""
A generator for the potential support pairs

Returns
-------

A generator of all potential support pairs
"""
p1_num_strategies, p2_num_strategies = A.shape
for support1 in (s for s in powerset(p1_num_strategies) if len(s) > 0):
for support2 in (s for s in powerset(p2_num_strategies)
if (len(s) > 0 and not non_degenerate) or
len(s) == len(support1)):
yield support1, support2

[docs]def indifference_strategies(A, B, non_degenerate=False, tol=10 ** -16):
"""
A generator for the strategies corresponding to the potential supports

Returns
-------

A generator of all potential strategies that are indifferent on each
potential support. Return False if they are not valid (not a
probability vector OR not fully on the given support).
"""
if non_degenerate:
tol = min(tol, 0)

for pair in potential_support_pairs(A, B, non_degenerate=non_degenerate):
s1 = solve_indifference(B.T, *(pair[::-1]))
s2 = solve_indifference(A, *pair)

if obey_support(s1, pair, tol=tol) and obey_support(s2, pair, tol=tol):
yield s1, s2, pair, pair

[docs]def obey_support(strategy, support, tol=10 ** -16):
"""
Test if a strategy obeys its support

Parameters
----------

strategy: a numpy array
A given strategy vector
support: a numpy array
A strategy support

Returns
-------

A boolean: whether or not that strategy does indeed have the given
support
"""
if strategy is False:
return False
if not all((i in support and value > tol) or
(i not in support and value <= tol)
for i, value in enumerate(strategy)):
return False
return True

[docs]def is_ne(strategy_pair, support_pair, payoff_matrices):
"""
Test if a given strategy pair is a pair of best responses

Parameters
----------

strategy_pair: a 2-tuple of numpy arrays
support_pair: a 2-tuple of numpy arrays
"""
A, B = payoff_matrices
# Payoff against opponents strategies:
u = strategy_pair.reshape(strategy_pair.size, 1)
row_payoffs = np.dot(A, u)

v = strategy_pair.reshape(strategy_pair.size, 1)
column_payoffs = np.dot(B.T, v)

# Pure payoffs on current support:
row_support_payoffs = row_payoffs[np.array(support_pair)]
column_support_payoffs = column_payoffs[np.array(support_pair)]

return (row_payoffs.max() == row_support_payoffs.max() and
column_payoffs.max() == column_support_payoffs.max())

[docs]def support_enumeration(A, B, non_degenerate=False,
tol=10 ** -16):
"""
Obtain the Nash equilibria using support enumeration.

Algorithm implemented here is Algorithm 3.4 of [Nisan2007]_

1. For each k in 1...min(size of strategy sets)
2. For each I,J supports of size k
3. Solve indifference conditions
4. Check that have Nash Equilibrium.

Returns
-------

equilibria: A generator.
"""
count = 0
for s1, s2, sup1, sup2 in indifference_strategies(
A, B, non_degenerate=non_degenerate, tol=tol):
if is_ne((s1, s2), (sup1, sup2), (A, B)):
count += 1
yield s1, s2
if count % 2 == 0:
warning = """
An even number of ({}) equilibria was returned. This
indicates that the game is degenerate. Consider using another algorithm
to investigate.
""".format(count)
warnings.warn(warning, RuntimeWarning)