Static games of complete information

Question 1

Common knowledge

Answer 1

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.

Question 2

Strategic-form game

Answer 2

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.

Question 3

Zero-sum game

Answer 3

G in which for all s from S we have that u1(s) + u2(s) + … + un(s) = 0

Question 4

Solution concept

Answer 4

method of analysing games with the objective of restricting the set of all possible outcomes to those that are more reasonable than others

Question 5

Solution concept assumptions

Answer 5

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)

Question 6

Solution concept examples

Answer 6

strictly dominant strategy eq., IESDS, rationalizability, NE

Question 7

Strictly dominated strategy

Answer 7

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

Question 8

Strictly dominant strategy equilibrium

Answer 8

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.

Question 9

IESDS algorithm

Answer 9

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

Question 10

IESDS equilibrium

Answer 10

A strategy profile where each si survives IESDS. If the equilibrium is unique, the game is IESDS solvable

Question 11

Belief

Answer 11

A belief of player i is a pure strategy profile s-i of his opponents

Question 12

Best response

Answer 12

A strategy si is a best response to a belief s-i if ui(si, s-i) >= ui(si’, s-i) for all si’

Question 13

Never best response

Answer 13

A strategy si that is not a best response to any belief s-i

Question 14

Rationalizability algorithm

Answer 14

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

Question 15

Rationalizable equilibrium

Answer 15

Strategy profile where each si is rationalizable (survives the algorithm).
Game is solvable by rationalizability if it has an unique rationalizable equilibrium.

Question 16

Nash equilibrium

Answer 16

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.

Question 17

IESDS x Rationalizability x Nash equilibria

Answer 17

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

Question 18

Probability distribution over A

Answer 18

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

Question 19

Mixed strategy

Answer 19

Probability distribution sigma over Si
We denote by Sigmai=Delta(Si) the set of all mixed strategies of player i.

Question 20

Expected payoff

Answer 20

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)

Question 21

Mixed belief

Answer 21

A mixed belief of player 1 is a mixed strategy sigma2 of player 2

Question 22

Never best response in mixed strategies

Answer 22

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.

Question 23

Mixed strategy Nash equilibrium

Answer 23

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.

Question 24

Payoffs in mixed strategy NE

Answer 24

Every NE sigma* satisfies
u1(s1, sigma2) = u1(sigma) for s1 in supp1(sigma1)
u2(sigma1, s2) = u2(sigma) for s2 in supp2(sigma2)

Question 25

Equations for payoff functions in mixed profile

Answer 25

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

Question 26

Support Enumeration equations

Answer 26

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

Question 27

MaxMin strategy

Answer 27

sigma1* is a maxmin strategy of player 1 if sigma1* in argmax_sigma1 min_s2 u1(sigma1, s2)

Question 28

Von Neumanns Theorem

Answer 28

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

Question 29

Computing NE in zero-sum games using linear programming

Answer 29

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