Nashpy Documentation

Nashpy is organized into several functional areas for game theory analysis:

• nashpy.algorithms: Contains algorithms for finding Nash equilibria.
• nashpy.learning: Contains implementations for learning algorithms in games.
• nashpy.game: The core module for defining and interacting with game structures.
• nashpy: The top-level package providing the primary entry points for the library.

The nash.algorithms package provides different algorithmic approaches for finding Nash equilibria in 2-player games. Depending on the game structure and size, you can choose from the following submodules:

• nashpy.algorithms.support_enumeration: Used for finding equilibria by enumerating supports.
• nashpy.algorithms.vertex_enumeration: Used for finding equilibria via vertex enumeration.
• nashpy.algorithms.lemke_howson: Implements the Lemke-Howson algorithm, a pivoting algorithm for finding Nash equilibria in non-degenerate games.

In game theory, a strategy is a probability distribution over the set of available actions $\mathcal{A}$.

For a player with an action set $\mathcal{A}$, a strategy $\sigma$ is represented as a vector in $[0, 1]^{|\mathcal{A}|}_{\mathbb{R}}$ such that the sum of all probabilities equals 1:

$$\sum_{i=1}^{\mathcal{A}}\sigma_i = 1$$

Example: Rock Paper Scissors In a Rock Paper Scissors game where actions are {Rock, Paper, Scissors}:

• A strategy of always choosing Paper is $\sigma = (0, 1, 0)$.
• A strategy of randomly choosing between Rock and Paper with equal probability is $\sigma = (1/2, 1/2, 0)$.

The support of a strategy $\sigma$, denoted as $\mathcal{S}(\sigma)$, is the set of all actions $i \in \mathcal{A}$ for which the probability of choosing that action is greater than zero ($\sigma_i > 0$).

Examples:

• If $\sigma = (1, 0, 0)$, the support is $\mathcal{S}(\sigma) = {1}$.
• If $\sigma = (1/3, 1/3, 1/3)$, the support is $\mathcal{S}(\sigma) = {1, 2, 3}$.
• If $\sigma = (2/5, 0, 3/5)$, the support is $\mathcal{S}(\sigma) = {1, 3}$.

A game is considered a Prisoners Dilemma if its payoff matrices $A$ (for the row player) and $B$ (for the column player) follow this structure:

$A = \begin{pmatrix} R & S \ T & P \end{pmatrix}, \quad B = \begin{pmatrix} R & T \ S & P \end{pmatrix}$

Subject to these constraints:

1. $T > R > P > S$ (Ensures 'Defect' dominates 'Cooperate')
2. $2R > T + S$ (Ensures a social dilemma where mutual cooperation is collectively optimal)

Where:

• $R$: Reward for mutual cooperation
• $S$: Sucker's payoff
• $T$: Temptation to defect
• $P$: Punishment for mutual defection

The Regret Minimization algorithm follows an iterative process to help players learn optimal strategies:

1. Initialize: Set starting strategies for all players.
2. Iterate: At each time step $t$:
   • Calculate Regret: Determine the regret for each player based on their current strategy compared to alternative strategies.
   • Update Strategies: Select the strategy that minimizes regret for each player.
3. Repeat: Continue the process until a convergence criterion or a predefined stopping condition is met.

A linear program (the primal) is defined by a matrix $M imes n$, a vector $b imes m$, and a vector $c imes n$. It seeks to maximize the objective function $c^Tx$ subject to the following constraints:

• $Mx ≤ b$
• $x_i ≥ 0$ for all $i$

In a zero-sum game, one player's gain is exactly balanced by the other player's loss. For a game defined by a payoff matrix $A \in \mathbb{R}^{m \times n}$:

• Max-min strategy ($x$): The row player seeks to maximize their minimum possible payoff. This is solved via a linear program to find $x$ such that $xA \geq \mathbb{1}u$, where $u$ is the max-min value.
• Min-max strategy ($y$): The column player seeks to minimize the row player's maximum possible payoff. This is solved via a linear program to find $y$ such that $Ay^T \leq \mathbb{1}v$, where $v$ is the min-max value.

The Minimax Theorem: For zero-sum games, the max-min value $u$ and the min-max value $v$ are equal ($u = v$). This ensures that both players can achieve the game's value through their respective optimal strategies.

Nashpy provides several algorithms for solving or simulating games. While the README provides high-level links, the following features are implemented:

• Equilibrium Solvers:
  • Support enumeration
  • Vertex enumeration
  • Lemke-Howson algorithm
• Dynamics and Simulations:
  • Fictitious play
  • Stochastic fictitious play
  • Replicator dynamics
  • Replicator-mutation dynamics
  • Asymmetric replicator dynamics
  • Moran processes (including on interaction and replication graphs)
  • Introspection dynamics
• Game Generation:
  • Generating games from repeated games

In game theory, Regret is the difference between a player's actual payoff and the payoff they would have received by playing a different strategy.

Regret Minimization is a process where players iteratively update their strategies to minimize this difference. By minimizing regret over time, players adapt their strategies, which can lead to convergence towards a Nash Equilibrium (a state where no player has an incentive to deviate from their strategy unilaterally).