game theory note

gistfile1.md

Game Theory Class on Coursera

chapter 1

• stable pair of pure strategies
• constant-sum game
• strictly(weakly) dominant strategy
• best response
• pure strategy Nash equilibrium (if $a_i$ a best response to $a_{-i}$ for all i)

---

chapter 2

Keynes’ "Beauty Contest Game"

Guess an integer between 1 and 100 that is closest to 2/3 of the mean of the guesses.

Everybody wanting to announce a number below the average, leads all to announce 1!

A Traffic Game 交通流量

N = [0,1] continuum, A$_i$ = {L, R}, f = fraction of population choosing R

U$_i$(L/R, f)= -(population choosing L/R)

solution: U(L,f) = U(R,f)

Braess’ Paradox

Tragedy of the commons 钓鱼

Fishing total time per day is $a_i$+ ... + $a_n$

stock over time is (1000 - $\sum_ia_i$)

Fisherman j catches $a_j$(1000 - $\sum_ia_i$)

max for per: $a_i( 1000 - (a_i+ \sum_{j \neq i}a_j)) $ , and $\sum_{j \neq i}a_j = (n-1)a_i$, so $a^*=\frac{1000}{n-1}$, so $catch=(\frac{1000}{n+1})^2$

max for all: $\sum_ia_i(1000 - \sum_ia_i)$ , and $a_*=\frac{500}{n}$, and $catch = \frac{500^2}{n}$

mixed strategy

Mixed strategy Nash Equilibrium

solution: my probility is p, make the other indifferent

Q. In general, how hard computationally is it to find even a single NE in games with more than two strategies?
A. Hard (“PPAD complete”)

---

chapter 3

Solving Zero-Sum Games and the Minimax Theorem

Minimax Theorem

(s1, s2) is an equilibrium of a zero-sum game iff s1 make player 1 maximize his minimum and s2 player 2 minimize the 1`s maximum

solution: 列出1的payoff方程, 对2的概率求导, 得到1的概率, 2类似, 详见 ppt 3.2

Mixed Strategy Equilibrium change as payoffs change

公司市场争夺战

One player’s strategy is determined by making the other indifferent

Nash Equilibrium theorem

Every game in which each player has a finite number of pure strategies has at least one equilibrium (possibly in mixed strategies).

example: Players each name an integer, whoever names the highest integer wins a prize

---

chapter 4

Extensive Form Games

Perfect information

What if the row player could choose before column, and column would see what the row player did?

Game Tree 决策树 ppt 4.1

Extensive Form Strategies

• Pure strategies
• Mixed strategies
• Behavioral strategies ???

Centipede Game

stop or pass

Entry Game

Example of a game of Perfect Information: Entry Game

Find all pure strategy Nash equilibria 非backward induction, 要考虑全!!!

backward induction 一定能找到NE但不全!

---

chapter 5

Imperfect information

changes on game tree: some note are unioned to a information set

Subgame

• In games of perfect information: A proper subgame is the entire game that remains starting from any nonterminal node.

• In general: A subgame is the entire remaining game starting from some (nonterminal node) that has a singleton information set.

Subgame Perfection

A collection of strategies that form a Nash equilibrium in every proper subgame

The set of subgame perfect equilibria coincide with those found via backward induction.

The set of subgame perfect equilibria are a subset of the Nash equilibria.

Ultimatum Bargaining

player 1 makes an offer and player 2 can accept or reject

backward induction 2就吃亏了, 所以如果2要和1博弈

---

chapter 6

###repeated game

$a_i^t$ action of player i taken in period t

$S_i(h^t)$ specifies what i will do after a history $h^t$, is a choice of $a_i$ play in period t+1
after observing what happened in all previous periods

payoffs

• Limit average reward
• Future-discounted reward

Subgame Perfect Equilibrium (SPE)

Indefinite Repetition

Probability p that the game continues next period, probability (1-p) that it ends.

根据p决定defect与否： $3+3p+3p^2+ ... < 5+p+p^2+... $

"Grim Trigger" Equilibrium

threat of reversion

---

chapter 7

"Folk" Theorems

characterize payoffs in infinite repeated games with avg reward

"grim trigger" strategy, every n-1 agents doing it to the remaining one

a payoff vector $r=r_1,…r_n$, is enforceable if $r_i>v_i$, where $v_i$ is agent i's minmax value

a payoff vector $r=r_1,…r_n$, is feasible if it is the payoff under some mixed strategy with rational weights (a technical condition)

Then:

• If r is an equilibrium payoff vector in G’ then e is enforceable
• If r is enforceable and feasible, then it is an equilibrium payoff vector in G’

OPEC game

World demand for oil (very roughly!): $P = 300 - 5Q$

Payoff/Profit for country i: $(P-c)q_i = (300–5(q_{-i}+ q_i)–20)q_i$

Best response for country i: $q_i = 28–\frac{q_{-i}}{2}$

设置$q_{-i}=3q_i$得到NE

wether can support for a high enough $\beta$ ?

计算背叛时的$\beta$

Taking Turns Game

肯定是在逆风局背叛

$0 + \beta_{i}10 + \beta_{i}^{2}0 + \beta_{i}^{3}10 + \beta_{i}^{4}0 + \beta_{i}^{5}10 + ....$
vs
$1 + \beta_{i}1 + \beta_{i}^{2}1 + \beta_{i}^{3}1 + \beta_{i}^{4}1 + \beta_{i}^{5}1 + ....$

---

chapter 8, 9

Bayesian Games

look for the uncentain one's dominant strategy first

Auction

First price auction: $ \theta _i\frac{n-1}{n} $

Second price (Sealed-Bid) auction: true value $ \theta _i $

Theorem:
Any auction can be converted to an equivalent truthful auction.

the revenue is not the direct expectation of a player’s bid, instead it should be the expectation of the higher type’s bid among these two bidders;

Theorem:
In IPV setting with IID values, all single-item auctions in which:

• Item goes to bidder with highest (true) value
• Bidder with value 0 pays 0

have the same expected revenue

so for FPA and SPA: $E[rev]=\theta_{max}\frac{n-1}{n+1}$

Winner's curse

More generally:
Agents payoff functions are uncertain and may depend on others’ information

common(more generally, affiliated) value auctions:
see low or see high

Winning the auction this means that you were the most optimistic
If you bid naively, this means that you were overly optimistic