Dynamic games of complete information

Question 1

Perfect-information extensive-form game

Answer 1

Tuple G = (N, A, H, Z, chi, ro, pi, h0, u)
N = {1,…,n} set of players
A = set of all actions
H = set of non-terminal nodes
Z = set of terminal nodes
chi: H -> A is an action function, assigning enabled functions
ro: H -> N is a player function, assigning owner of the node
pi: H x A -> H U Z is the successor function
h0 = root node
u = (u1, …, un) where ui: Z -> R is a payoff action for the player i

Question 2

Path

Answer 2

A path from h to h’ is a sequence h1,a2,…,ak,hk where h1 = h and hk = h’, and pi(hj-1, aj) = hj for every 0 < j <= k.

Question 3

Pure strategy in Extensive-form game

Answer 3

A pure strategy of player i in G is a function si: Hi -> A such that for every h we have that si(h) in chi(h)

Question 4

Subgame

Answer 4

A subgame Gh of G rooted in h is the restriction of G to nodes reachable from h in the game tree. More precisely, Gh = (N, A, Hh, Zh, chih, roh, pih, h, uh)

Question 5

SPE

Answer 5

A subgame perfect equilibrium in pure strategies is a pure strategy profile s such that for any subgame Gh of G, the restriction of s to Hh is a NE.

Question 6

Backward induction

Answer 6

Algorithm for cumputing SPE for finite perfect-information extensive-form games
Initially: attach to each terminal node the empty profile and the payoff vector u(z)
1. Let K be the set of all children of h
2. Let hmax from argmax_h’inK u_ro(h)(h’)
3. Attach to h a strategy profile sh shere sh_ro(h)(h) = hmax,
for all i in N and all h’ in Hi \ h define sih(h’) = sih-(h’) where h- in K and h- in Hh- intersection Hi
4. Attach to h the vector of expected payoffs u(h) = u(hmax)

Question 7

Mixed strategy

Answer 7

A mixed strategy of player i is probability distribution sigma in Delta(Si) over Si

Question 8

Behavioral strategy

Answer 8

A behavioral strategy of player i in G is a function betai: Hi -> Delta(A), such that for every h in Hi and every a in A: betai(h)(a) iff a in chi(h)

Question 9

Probability of reaching z

Answer 9

P_beta(z) = Pi_l=1 to k beta_ro(hl-1) (hl)(al) where h0a1…hk is the unique path from root to leaf

Question 10

Payoff function of behavioral strategy

Answer 10

ui(beta) = sum over z P_beta(z) * ui(z)

Question 11

Imperfect-information game

Answer 11

Gimp = (Gperf, I)
Gperf = (N, A, H, Z, chi, ro, pi, h0, u]
I = (I1, … In) where for each i in N Ii = {Ii1, Ii2,…,Iimi} is a collection of information sets for player i.
Ii is a partition of Hi
For all h, h’ in Ii,j, we have ro(h) = ro(h’) and chi(h) = chi(h’)

Question 12

Pure strategy in imperfect-information game

Answer 12

A pure strategy of player i in Gimp is a pure strategy si in Gperf such that for all j = 1,…,k and all h,h’ in Ii,j holds si(h) = si(h’)

Question 13

Subgame in i-i games

Answer 13

For every Hproper we define a subgame Gimph to be the imperfect-information game (Gperfh, Ih) where Ih is the restriction of I to Hh

Question 14

Behavioral strategy in Gimp

Answer 14

A behavioral strategy of player i in Gimp is a behavioral strategy betai in Gperf such that for all j = 1,…,ki and all h,h’ in Ii,j: betai(h) = betai(h’)

Question 15

Kuhns Theorem

Answer 15

Assuming perfect recall, every mixed strategy can be translated to a behavioral strategy (and vice versa) so that the payoff for the resulting strategy is the same in any mixed profile.

Question 16

Perfect recall

Answer 16

Player i has a perfect recall in Gimp if the following holds:
1. every information set of player i intersects every path from the root to a terminal node at most once
2. every two paths from the root that end in the same information set of player i pass through the same information sets of player i and in the same order, and in every such information set the two paths choose the same action.
I.e. each information set J of player i determines the sequence of the information sets of player i and actions taken by player i along any path J

Question 17

T-stage game

Answer 17

A game GT-rep based on G, proceeds in T stages so that in stage t >= 1, players choose a strategy profile st = (s1t, s2t).
After T stages players collect the average payoff Sum over T ui(s1t, s2t) * 1/T

Question 18

History

Answer 18

A history of length 0<=t<=T is a sequence h=s1…st in St of t strategy profiles.
H(t) is the set of all strategy profiles of length t.

Question 19

Pure strategy in a T-stage game

Answer 19

A pure strategy of player i in a T-stage game is a function taui: U_t=0toT-1 H(t) -> Si, which for every history chooses a next step for player i.

Question 20

T-stage game as a game in extensive form

Answer 20

Gimprep = (Gperfrep, I), such that Gperfrep = ({1,2}, A, H, Z, chi, ro, pi, h0, u) where
A = S1 U S2
Z = (S1xS2)T
H = (S1xS2)<=T U (S1xS2)<T * S1
(S1xS2)<=T possible histories
(S1xS2)<T * S1 used to simulate a simultaneous play of sigma by letting player 1 choose first and player 2 second
chi(eps) = s1, chi(hs1) = S2, chi(h(s1,s2)) = S1
ro(eps) = 1, ro(hs1) = 2, ro(h(s1,s2)) = 1
pi(eps, s1) = s1, pi(hs1, s2) = h * pi(s1, s2), pi(h(s1,s2), s1’) = h(s1,s2)s1’
h0 = eps
ui((s11,s21),….,(s1T,s2T)) = sum over T ui(s1t, s2t) / T

I: Let h in H1 be a node of player 1, then there is exactly one information set of player 1 containing h as the only element, and there is exactly one information set of player 2 containing all nodes of the form h*s1

Question 21

NE in T-stage game

Answer 21

A strategy profile tau in a T-stage game GT-rep is a NE if for every i in {1, 2} and every taui’ we have ui(tau1, tau2) >= ui(taui’, tau-i)

Question 22

SPE in T-stage game

Answer 22

A strategy profile tau is a SPE if for every history h the profile tauh is a NE in the (T-|h|)-stage game based on G.

Question 23

Pure strategy in Girep

Answer 23

A pure strategy is a function taui = Ut=0toInf H(t) -> Si

Question 24

delta-discounted payoff

Answer 24

Given 0<delta<1 we define a delta-discounted payoff by uidelta(tau) = (1-delta) * Sum_t=0 deltat * ui(st+1)

Question 25

Infinitely repeated game

Answer 25

Given a strategic-form game based on G together with the delta-discounted payoff, we denote the game as Girepdelta

Question 26

Simple version of Folk theorem

Answer 26

Let G = ({1,2}, (S1, S2), (u1, u2)) be a two-player strategic-form game where u1 and u2 are bounded on S = S1 x S2 and let s* be a NE in G.
Let S be a strategy profile in G satisfying ui(s) > ui(s) for all i in N.
Consider the following grim trigger for s using s strategy profile tau in Girep where taui(s1…sT) = si if T=0 or sl=s for all 1<=l<=T, si* otherwise
Then for delta >= max_i (max_si’ ui(si’, s-i) - ui(s))/(max_si’ ui(si’, s-i) - ui(s)) we have that tau is SPE in Girepdelta and uidelta(tau) = ui(s)

Question 27

Long-run average payoff

Answer 27

We define a long-run average payoff for player i by uiavg(tau) = lim_T sup 1/T sum_t=1toT ui(st)

Question 28

NE with long-run average payoff

Answer 28

A strategy profile tau is a NE if uiavg(tau) is well-defined for all i in N, and for every i and every taui’ we have that uiavg(taui, tau-i) >= uiavg(taui’, tau-i)

Question 29

Feasable vector of payoffs

Answer 29

Vector of payoffs v = (v1, v2) is feasible if it is a convex combination of payoffs for pure strategy profiles in G with rational coefficients.
I.e. if there are rational numbers betas satisfying betas >= 0 and Sum_s betas = 1 such that for both i holds vi = Sum_s = betas * ui(s).
We assume that there is m from N such that each betas can be written as gammas/m.

Question 30

Folk Theorem SPE

Answer 30

Let s* be a pure strategy NE in G and let v = (v1, v2) be a feasible vector of payoffs satisfying vi >= ui(s*) for both i. Then there is a strategy profile tau in Girep such that tau is a SPE in Girepavg and uiavg(tau) = vi.

Question 31

Individually rational vector

Answer 31

Vector v is individually rational if for both i holds vi >= min_s-i max_si ui(s, s-i).
(vi is at least as good as playing best response to the most hostile player)

Question 32

Folk Theorem NE

Answer 32

Let v = (v1,v2) be a feasable and individually rational vector of payoffs. Then there is a strategy profile tau in Girep such that tau is a NE and uiavg(tau) = vi for i