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 where:

  • is a finite set of players
  • is the set of all possible combinations of simultaneous actions, where is the finite set of actions for player
  • 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 (): At least two actions played with positive probability
    • is the probability that player chooses action

Other convention: refers to player ’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.