Normal-Form Game

A normal-form game is a game where each player only makes a single choice, like RPS.

We define a normal-form game as a tuple $(N,A,u)$ where:

• $N=\{1,\dots ,n\}$ is a finite set of $n$ players
• $A=S_1\times S_2\times \cdots \times S_n$ is the set of all possible combinations of simultaneous actions, where $S_i$ is the finite set of actions for player $i$
• $u$ is a vector of utilities/payoffs/rewards that we define

Two types of strategies:

• Pure strategy (deterministic policy): Chooses a single action with probability 1.
• Mixed strategy ($\sigma$): At least two actions played with positive probability
  • ${\sigma }_i(s)$ is the probability that player $i$ chooses action $s\in S_i$

Other convention: $-i$ refers to player $i$’s opponents

To find the optimal strategy to win a normal-form game, we use Regret Matching to find the Regret Matching to find the Nash Equilibrium.