Source code for nashpy.algorithms.vertex_enumeration

"""A class for the vertex enumeration algorithm"""

import numpy as np
import numpy.typing as npt
from typing import Generator, Tuple, Any
from nashpy.polytope import build_halfspaces, non_trivial_vertices


def vertex_enumeration(
    A: npt.NDArray, B: npt.NDArray
) -> Generator[Tuple[float, float], Any, None]:
    """
    Obtain the Nash equilibria using enumeration of the vertices of the best
    response polytopes.

    Algorithm implemented here is Algorithm 3.5 of [Nisan2007]_

    1. Build best responses polytopes of both players
    2. For each vertex pair of both polytopes
    3. Check if pair is fully labelled
    4. Return the normalised pair

    Parameters
    ----------
    A : array
        The row player utility matrix.
    B : array
        The column player utility matrix


    Yields
    -------
    Generator
        The equilibria.
    """

    if np.min(A) < 0:
        A = A + abs(np.min(A))
    if np.min(B) < 0:
        B = B + abs(np.min(B))

    number_of_row_strategies, row_dimension = A.shape
    max_label = number_of_row_strategies + row_dimension
    full_labels = set(range(max_label))

    row_halfspaces = build_halfspaces(B.transpose())
    col_halfspaces = build_halfspaces(A)

    for row_v, row_l in non_trivial_vertices(row_halfspaces):
        adjusted_row_l = set(
            (label + number_of_row_strategies) % (max_label) for label in row_l
        )

        for col_v, col_l in non_trivial_vertices(col_halfspaces):
            if adjusted_row_l.union(col_l) == full_labels:
                yield row_v / sum(row_v), col_v / sum(col_v)