Title: Algorithmic Game Theory
Tags: chap1

Q: The cost matrix of [...] is .
A: the prisoners' dilemma

Q: The cost matrix for [...] is .
A: the battle of the sexes

Q: The payoff matrix for the [...] is .
Intuitively, [...].
A: matching pennies game; player 1 wins if the outcomes match, while player 2 wins if the outcomes are different

Q: Formally, a game consists of [...], and [...].
A: a set \(n=\{1, 2, \dots, n\}\) of players, with each player \(i\) having a set of possible strategies \(s_i \in S_i\); a utility function \(u_i: S \mapsto ℝ\) that assigns values to strategies

\(s=(s_1, \dots, s_n)\) stands for the vector of strategies selected by players, and \(S=\times_i S_i\) stands for the set of all possible ways in which players can pick strategies.

Front: What is the relation of utilities \(u\) and costs \(c\) in games?
Back: Costs are simply negated utilities, \(u_i(s)=-c_i(s)\).

Q: The [...] of a game [...].
A: standard/normal/matrix form representation; is the matrix of all possible strategies for all players, each cell containing the payoffs for the different players

Q: [...] stands for [...].
A: \(s_{-i}\); the strategies played by all players except \(i\)

Q: A strategy \(s \in S\) is a [...] iff [...].
Mathematically, [...].
A: dominant strategy solution; for each player \(i\), for \(i\) their strategy from \(s\) the utility for \(i\) is at least \(\ge\) to any other strategy; \(u_i(s_i, s_{-i}) \ge u_i(s_i', s_{-i}')\) for all \(s'\)

Front: What is the Vickrey auction an alternative name for?
Back: The second-price auction.

Q: A strategy vector \(s \in S\) is [...] iff [...].
Mathematically, [...].
A: a Nash equilibrium; for all players, no player can strictly benefit from unilaterally deviating from \(s\) to another strategy \(s'\); for each player \(i\) and alternative strategy \(s_i' \in S_i\), it holds that \(u_i(s_i, s_{-i}) \ge u_i(s_i', s_{-i}) \)

Front: What is the relation between dominant strategies and Nash equilibria?
Back: \(s\) is a dominant strategy solution \(\Rightarrow\) \(s\) is the only Nash equilibrium.
The reverse does not hold.

Q: When looking for Nash equilibria, we assume players are seeking to [...].
A: maximize their expected payoff, i. e. they are risk-neutral

Q: Conceptually, a [...] is an equilibrium where [...].
Mathematically, [...].
A: correlated equilibrium; if we know that the strategies of all other players are drawn from a distribution \(p\) (conditional on a know action assigned to us), we would not want to deviate from our current action; \(\sum_{s_{-i} } p(s_i, s_{-i})u_i(s_i, s_{-i}) \ge \sum_{s_{-i} } p(s_i, s_{-i}) u_i(s_i', s_{-i})\)

Q: A game is [...] if [...].
A: a zero-sum game; the sum of the payoffs for the players is zero for any choice of strategies

Front: In two-player zero-sum games, how can we find the Nash equilibrium?
Back: By computing the minimax strategies of the two players.

Q: For player \(i\), the change from a strategy \(s_i\) to some other strategy \(s_i'\), with \(s_{-i} \) staying the same, is [...] iff [...]. Mathematically, [...].
A: an improving response; with the other strategies staying fixed, the utility for \(i\) strictly improves; \(u_i(s_i', s_{-i})>u_i(s)\)

Q: A strategy \(s_i'\) is a [...] to a strategy \(s\) iff [...]. Mathematically, a best response is [...].
A: best response; it maximizes the utility of player \(i\), with \(s_{-i}\) staying fixed; \(\text{max}_{s_i' \in S_i} u_i(s_i', s_{-i})\)