AGT by C.H. Papadimitriou

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。

如果上面两点成立,那么存在一个效用函数U : O \rightarrow \mathbb{R}O指所有的结果)使得V(lottery) = \sum\limits_{o}Pr(o)U(o)。即U不依赖于其他选项的值。一个更完整的证明(一致性和结果的传递性)见von Neumann-Morgenstern效用理论。

Section 5. Nash均衡

纳什均衡是一个解概念,使得没有一个参与人可以通过改变自己的策略来提高自己的状况。

尽管他们并不一定是在其他参与人的策略被忽略时的最优的结果,但也可以看作是一个game的稳定状态(参与人在给定其他参与人的选择的情形下作出自己的最优选择)。

  • 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

超过两个参与人时情况更为复杂了,如何处理?

就要用到succinct expression了。

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s