Source

Basic notions – Normal-form game, player actions, strategy, utility

Normal form of a game can be described as a matrix where each cell contains payoffs for each player. Formally we have a triple $(P,A,u)$ where $P$ is a set of $n$ players, $A = A_1 \times \dots \times A_n$ is a set of action profiles, and $u=(u_1,\dots,u_n)$ is a $n$-tuple where $u_i: A \rightarrow \mathbb{R}$ is the utility function.

  • Player – (hopefully) Intelligent entity, which aims to maximize his payoff. He may only choose what action to choose from his action profile, however his payoff is determined not only from his action, but also actions of the remaining players.
  • Player’s action profile – List of possible actions which a player can take.
  • Player’s action – An action from action profile chosen by the player.
  • Utility / Payoff – Given actions of each player, it says how many ‘points’ players will receive (each player may get different amount). Players aim to maximize their payoff.
  • Strategy – Determines how player will chose his action.
  • Strategy profile – List of all strategies chosen by respective players.
  • Pure strategy – Player chooses one action from his action profile.
  • Mixed strategy – Player chooses his action according to a probability distribution over his action profile. In this case, player maximizes expected payoff.
    • support – Action which has non-zero probability in a mixed strategy.
  • Zero-sum game – Game with 2 players where sum of their utilities for any combination of actions is 0.

Equilibria

Nash equilibrium

  • Best response – Assuming that all players chose their action, best response is player’s mixed strategy with the best payoff.
  • Nash equilibrium – Is a strategy profile where every player has best response to other players’ strategies.
    • It is implied that if each player knows what other players chose it is not benefitial to change their strategy.
    • Pure Nash equilibrium / Mixed Nash equilibrium – is Nash equilibrium which is Pure / Mixed strategy respectively.

Nash’s theorem

Every normal-form game has a mixed Nash equilibrium.

Pareto optimality

  • Pareto domination – Strategy profile $S$ dominates $S’$ if all players’ payofs are not worse, and at least one player has better payoff.
  • Pareto optimal – Strategy profile is Pareto optimal if there is not pareto dominated by any other strategy profile.
    • Note that a set of pareto optimal strategy profiles is incomparable to Nash equilibria. In particular in prisoner’s dillema we have both profiles present, but they do not overlap.

Game classes

Zero-sum games

  • We can find Nash equilibria of zero-sum games using linear programming. By assigning $x=(x_1,\dots,x_n)$ for first player and the same for $y$ for second player, we have variables representing the mixed strategies. We constraint their sum to be $1$. First player maximizes $\beta(x)=\min_{x\in S_1}x^T M y$, i.e., the worst outcome over all oponent’s choices – this strategy is worst-case optimal.

  • Value of a zero-sum game – The payoff which is unique and can be determined by LP.

Minimax Theorem

For every zero-sum game, worst-case optimal strategies for both players exist and can be efficiently computed using linear programming. Moreover, there is a number $v$ such that, for any worst-case optimal strategies $x^$ and $y^$ of players 1 and 2, respectively, the strategy profile $(x^,y^)$ is a Nash equilibrium and $\beta(x^)=(x^)^T M y^* = \alpha(y^*) = v$.