Lecture 3

Definition 2

game of perfect information: 一个抉择树每个节点都有一个条件。也就是说任意玩家在任意时间都知道自己所在的位置。反之则是imperfect information。
zero-sum: 每一个叶子上所有用户的总和payoff是0。也就是说用户不会从中得到什么。
without chance：节点没有被自然控制。反之是game with chance。

ep: 棋类是 2-person zero-sum games of perfect information without chance.
ep: Poker is a zero-sum1 game of imperfect information with chance.

Definition 3

fully specified strategy : 对一个特定的玩家，有多少种战略。把所有可能性走法加起来。

Generating all strategies for

如果玩家i第一步先走的话： Ni(t) = Ni(t1) + Ni(t2) + · · · + Ni(tn).
如果玩家i第一步后走的话： Ni(t) = Ni(t1) × Ni(t2) × · · · × Ni(tn).

week3

Nash Equilibrium

Def

Definition: A strategy profile (s1,s2,s3…sk) for a game with k
players, is a Nash equilibrium if each strategy is a best
response to all of the others.

It is not a strategy; it is a choice of strategy for all players in
the game.
If the players are playing the Nash, no player has any
incentive to change its strategy unilaterally

Mini-max approach

解释上图：

寻找Amelia的min ， 1，2，3，1
寻找Scott的max， 7，3，5，6
找Amelia的min中的max 和 Scott的max中的min 的那个点。

Dominance

Dominance can be used to eliminate some strategies

mixed strategies

A mixed strategy is a strategy for a player in which:

I plays probabilistic combination of pure strategies;
I receives a probabilistic combination of payoffs

Extensive form

一个路径上有权重比例的树

At each node where the player has a
decision, assign a probability function to each
of the possible choices.

con

Only for a special class of games do strategies which beat
all opponents always exist (two-player, zero-sum, perfect
information, no chance).
A Nash equilibrium is a collection of strategies for all
players such that each player is playing best response to
all the others.
For a zero-sum, two-player game in normal form, a
strategy pair which is maximal in its columns and minimal
in its rows is a Nash equilibrium.
Dominance can be used to reduce the number of
strategies.
Nash equilibria also exist in general-sum games.