Static games of complete information Flashcards
Common knowledge
A fact E is a common knowledge among players {1,2,…,n} if for every sequence i1, i2, …, ik from {1,….,n} we have that i1 know that i2 knows … that ik knows E.
Strategic-form game
G = (N, (Si), (ui))
N = {1,…,n} finite set of players
Si is a set of pure strategies of player i. A strategy profile is a vector of strategies of all players (s1, s2, …, sn) from S1 x S2 x … x Sn. Set of all strategy profiles is S
ui: S -> R is a function associating each strategy profile with payoff to player i, for every player.
Zero-sum game
G in which for all s from S we have that u1(s) + u2(s) + … + un(s) = 0
Solution concept
method of analysing games with the objective of restricting the set of all possible outcomes to those that are more reasonable than others
Solution concept assumptions
1 Players are rational (choose a strategy to maximise their payoff)
2 Players are intelligent (they know everything about the game and can make any inferences about the situation that we can make)
3 Common knowledge (the fact that players are rational and intelligent is a common knowledge)
4 Self enforcement (any prediction of a solution concept must be self enforcing - noncooperative)
Solution concept examples
strictly dominant strategy eq., IESDS, rationalizability, NE
Strictly dominated strategy
Let si, si’ from S be strategies of player i. Then si’ is strictly dominated by si (si>si’) if for any possible combination of the other players strategies s-i we have that ui(si, s-i) > ui(si’, s-i) for all s-i
Strictly dominant strategy equilibrium
A strategy profile s is a strictly dominant strategy equilibrium if si is strictly dominant for all i from N. If it exists, it is unique and players will play it.
IESDS algorithm
Define a sequence Di0, Di1,… of strategy sets of player i. GDSk is a game obtained by restriction to Dik)
1 Initialize k=0 and Di0 = Si for i in N
2 For all players: Let Dik+1 be the set of all pure strategies of Dik that are not strictly dominated in GDSk
3 let k=k+1 and go to 2
IESDS equilibrium
A strategy profile where each si survives IESDS. If the equilibrium is unique, the game is IESDS solvable
Belief
A belief of player i is a pure strategy profile s-i of his opponents
Best response
A strategy si is a best response to a belief s-i if ui(si, s-i) >= ui(si’, s-i) for all si’
Never best response
A strategy si that is not a best response to any belief s-i
Rationalizability algorithm
1 Initialize k=0 and Ri0 = Si for all i
2 For all players: Let Rik+1 be the set of all strategies of Rik that are besf response to some beliefs in GRatk
3 Let k=k+1 and go to 2
Rationalizable equilibrium
Strategy profile where each si is rationalizable (survives the algorithm).
Game is solvable by rationalizability if it has an unique rationalizable equilibrium.
Nash equilibrium
Pure strategy profile where each si* is a best response to s-i* for each i, that is ui(si, s-i) >= ui(si, s-i*) for each si and i.
IESDS x Rationalizability x Nash equilibria
1 If s* is a strictly dominant strategy equilibrium then it is the unique NE
2 Each NE is rationalizable and survives IESDS
3 If S is finite, then neither rationalizability nor IESDS create new equilibria
4 If S is finite, and IESDS and Rationalizability equilibria are unique, then it is also a NE
Probability distribution over A
Let A be a finite set. A probability distribution over A is a function sigma: A->[0,1] such that sum over A sigma(a) = 1.
Delta(A) is set of all probability distributions over A
Mixed strategy
Probability distribution sigma over Si
We denote by Sigmai=Delta(Si) the set of all mixed strategies of player i.
Expected payoff
The expected payoff of player i under a mixed strategy profile sigma is ui(sigma) = sum over S sigma(s) ui(s) = sum over S1, sum over S2 sigma1(s1) sigma2(s2) ui(s1, s2)
Mixed belief
A mixed belief of player 1 is a mixed strategy sigma2 of player 2
Never best response in mixed strategies
A pure strategy s1 of player 1 is a never best response to any belief sigma2 iff s1 is strictly dominated by a strategy sigma1.
Strategy survives IESDS iff it is rationalizable.
Mixed strategy Nash equilibrium
A mixed strategy profile sigma* where sigma1* is the best response to sigma2* and vice versa.
That is u1(sigma1, sigma2) >= u1(s1, sigma2) and u2(sigma1, sigma2) >= u1(sigma1, s2) for all s1, s2.
Payoffs in mixed strategy NE
Every NE sigma* satisfies
u1(s1, sigma2) = u1(sigma) for s1 in supp1(sigma1)
u2(sigma1, s2) = u2(sigma) for s2 in supp2(sigma2)
Equations for payoff functions in mixed profile
u1(s1, sigma2) = w1 for s1 in supp(sigma1)
u1(s1, sigma2) <= w1 for s1 not in supp(sigma1)
u2(sigma1, s2) = w2 for s2 in supp(sigma2)
u2(sigma1, s2) <= w2 for s2 not in supp(sigma2)
Then u1(sigma) = w1 and u2(sigma) = w2, and sigma* is a NE
Support Enumeration equations
For all k in supp1: Sum over l’ from S2 sigma2(l’) * u1(k, l’) = w1
For all k not in supp1: Sum over l’ from S2 sigma2(l’) * u1(k, l’) <= w1
For all l in supp2: Sum over k’ from S1 sigma1(k’) * u2(k’, l) = w2
For all l not in supp2: Sum over k’ from S1 sigma1(k’) * u2(k’, l) <= w2
For all i from {1,2}: sigmai(1) + … + sigmai(mi) = 1
For all i from {1,2} and all k from suppi: sigma(k) >= 0
For all i from {1,2} and all k not in suppi: sigma(k) = 0
MaxMin strategy
sigma1* is a maxmin strategy of player 1 if sigma1* in argmax_sigma1 min_s2 u1(sigma1, s2)
Von Neumanns Theorem
Assume two-player zero-sum game. Then max_sigma1 min_s2 u1(sigma1, s2) = min_sigma2 max_s1 u1(s1, sigma2).
Moreover, sigma* is a NE iff both sigma1* and sigma2* are maxmin strategies
Computing NE in zero-sum games using linear programming
Assume s1 = {1,…m1}, s2 = {1,…,m2}. We want to compute sigma1* in argmax_sigma1 min_s2 u1(sigma1, s2). Consider a linear program with variables sigma1(1), …, sigma1(m1), v: maximize v, subject to
sum k in 1..m1 sigma1(k) * u1(k, s2) >= v for s2 = 1..m2. The sum of sigma(k) has to be 1 and sigma1(k) >= 0
