 tags:[ notes ]
Algorithmic game theory notes
Source
Basic notions – Normalform 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 nonzero probability in a mixed strategy.
 Zerosum 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 normalform 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
Zerosum games

We can find Nash equilibria of zerosum 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 worstcase optimal.

Value of a zerosum game – The payoff which is unique and can be determined by LP.
Minimax Theorem
For every zerosum game, worstcase optimal strategies for both players exist and can be efficiently computed using linear programming. Moreover, there is a number $v$ such that, for any worstcase 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$.