Lecture 1 : What is Game Theory?

1. Game的定义
1. Rational
2. Conflict
3. Predict
2. CS领域为何研究GT？
3. 例子
1. 2 player
2. n players
4. 效用(Utility)理论
5. Nash均衡
1. 混合
2. Nash均衡研究过程中重要发展
3. 寻找Nash均衡
4. 简明表达式的重要性

Section 1 Game的定义

• 理性(Rational):这里的理性指的是如果对一个参与人来说，存在任何的动作能投使得其比之前更好，那么他将选择这个动作。“比之前更好”我们使用效用函数（utility function）来刻画。另一种方式是最大化其期望效用。“但是事实上这的确是一个天大的谎。”
• 冲突(Conflict):与传统的优化思想不同的是，GT同时优化多个有竞争关系的效用函数。每个agent都有一个自己的效用函数，其输出不仅依赖自身的选择也依赖其余的agent。
• 预测(Predict):GT预测agent进入一个博弈中将怎么行动。解决Game的方式是给出一个解的概念(solution concept)

Section 2. Why study GT in CS?

Internet!

Mechanism Design.

Section 3. 例子(2-player and n-players)

• Prisoner’s Dilemna
 Prisoner’s Dilemna Silent Rat out Silent 3,3 0,4 Rat out 4,0 1,1
• Tragedy in the Commons
 Tragedy in the commons Water Don’t water Water 2,2 2,3 Don’t water 3,2 0,0
• Penalty Shot
 Penalty Shot Left Right Left 1,-1 -1,1 Right -1,1 1,-1
• Rock Paper Scissor
 Pock Paper Scissors Rock Paper Scissors Rock 0,0 -1,1 1,-1 Paper 1,-1 0,0 -1,1 Scissors -1,1 1,-1 0,0
• Battle of the Sexes
 Battle of the Sexes Football Theatre Football 3,2 0,0 Theatre 0,0 2,3
n-players:
2/3 of the mean: n 个人每人下赌注1美元，然后在 [0,100]间选数，最靠近平均值的2/3的那位获胜。
Section 4. 效用理论

• Money and Utility
St. Peterburg Paradox: [from Wikipedia]In economics, the St. Petersburg paradox is a paradox related to probability theory and decision theory. It is based on a particular (theoretical) lottery game (sometimes called St. Petersburg Lottery) that leads to a random variable with infinite expected value, i.e., infinite expected payoff, but would nevertheless be considered to be worth only a very small amount of money. The St. Petersburg paradox is a classical situation where a naïve decision criterion (which takes only the expected value into account) would recommend a course of action that no (real)rational person would be willing to take. Several resolutions are possible.The paradox is named from Daniel Bernoulli‘s presentation of the problem and his solution, published in 1738 in the Commentaries of the Imperial Academy of Science of Saint Petersburg (Bernoulli 1738). However, the problem was invented by Daniel’s cousin Nicolas Bernoulli who first stated it in a letter to Pierre Raymond de Montmort of September 9, 1713 (de Montmort 1713).The classical resolution of the paradox involved the explicit introduction of a utility function, an expected utility hypothesis, and the presumption of diminishing marginal utility of money.
• Lotteries and Risk Valuation
Definition 1. Lottery is a finite collection of (probability, payoff) pairs. Payoff为实数，这些pair中的概率之和应该为1.
Definition 2. 定义$\Delta \mathbb{R}$为在实数上的一个分布。函数$V : \Delta \mathbb{R} \rightarrow \mathbb{R}$被称为一个Risk Valuation函数，当一个理性的agent总是更愿意接受一个大于给定的分布的值的payoff而非从分布中sample出的一个值的payoff.
Note:
1. $V$是关于概率的线性组合。i.e. 对所有在lottery中的结果有：$V(lottery) = \sum\limits_{o}Pr(o)U(o,lottery)$
2. $V$不在乎lottery的结果(outcome).$V$不能说：我不管它的概率，总是分配第二个结果值为0。

Section 5. Nash均衡

• Pure
• Mixed : Probability distribution over the set of the pure strategies.
• $xRy \leq x'^T R y + x'$, where $x$ is the probability vector of Player 1’s strategy set and $y$ is the probability vector of Player 2’s strategy set. $R$ represents the utility matrix for player 1
• support : subset of all available pure strategies that are used to build a particular mixed strategy.
• Nash证明任何处于纳什均衡的support中的策略都是一个最优反应。

1. von Neumann(1928)证明了所有的零和博弈拥有纳什均衡
2. Dantzig(1947)创造了线性规划
3. Khachiyan(1979)给出了多项式时间的解决线性规划的算法
4. Nash(1950)证明了所有博弈都有纳什均衡

1. support enumeration: find all Nash equilibria
1. brute-force technique
2. solve m+n linear equations with m+n unknowns
3. iterates over all possible subsets of strategies, for each subset, it computes $v=\sum x_i b_{ij}$$v=\sum y_i a_{ij}$, where $x$ and $y$ are the probability of choosing the current strategy and $a$ and $b$ are the gain in utility if the strategy is chosen. Goal is to discover a vector of values for $x$ and $y$ that lead to a maximum value for both $v$ and $u$
2. Lemke-Howson: find a sample Nash equilibria
1. 2-player
2. not practical (worst-case) exponential runtime
3. output one Nash equilibrium
3. Linear programming: Nash equilibria in zero-sum games

Succinct expression