AGTA Tutorial sheet 4 (solutions)
1 Question 1
Given the finite 2 player bimatrix game from below, we will use iterated elimi- nation of strictly dominated strategies.
c1 c2 c3 c4
Copyright By PowCoder代写 加微信 powcoder
r1 (5,2) r2 (16,4) r3 (15, 12) r4 (9, 15)
(22,4) (18,5) (16, 9) (23, 9)
(4,9) (1,10) (18, 10) (11, 5)
(7,6) (10,2) (11, 3) (5, 13)
Consider Player 1 = Row player and Player 2 = Column player. We know that a pure strategy can be dominated by either a pure strategy or a mixed one. Observe that c2 is strictly dominated by (21c1; 12c3) (easy to check). Therefore, we prune strategy c2 and obtain a 4 × 3 residual game.
r1 (5,2) r2 (16,4) r3 (15, 12) r4 (9, 15)
(4,9) (1,10) (18, 10) (11, 5)
(7,6) (10,2) (11, 3) (5, 13)
Observe that r1 and r4 are strictly dominated by the pure strategy r3. Also, from the new residual game, strategy c4 is strictly dominated by c3. The final residual game is:
c1 r2 (16,4)
c2 (1,10)
r3 (15, 12)
Applying the same principles as in question 2 from tutorial 2, we obtain the
unique Nash equilibrium ((1r2; 3r3);(17c1; 1 c2)). Therefore, the final answer:
((0; 1; 3;0);(17;0; 1 ;0)) 44 18 18
2 Question 2
Suppose x = (x1, x2, …xn) is a Nash equilibrium. Consider the product distribu- tion p(s1, s2, …sn) = ni=1 xi(si). We will show that any such Nash equilibrium is also a correlated equilibrium (CE).
Recall that, by definition, for all players i and for all pure strategies si,s′i ∈ Si,
Us′i(p|si)= p(s−i |si)·ui(s−i;s′i) i
is the conditional expected payoff of player i, for playing pure strategy s′i, having received recommendation si from the distribution p, assuming other players play according to their recommendation sj. Here, by definition,
p(s1,…,sn) p(s−i | si) = t−i∈S−i p(t−i; si)
Recall that we define p to be a correlated equilibrium iff, for all players i and si, s′i ∈ Si, we have
Usi(p | si) ≥ Us′i(p | si) i
(In other words, the conditional expected payoff of using the strategy rec- ommended by the recommender is at least as high as choosing any other pure strategy.)
Recall that from the Claim on page 6 of Lec.3, the fact that x = (x1,…,xn) is a Nash equilibrium is equivalent to the following statement: for all pure strategies s′i ∈ Si, Ui(x) ≥ Ui(x−i; s′i). In other words:
(xi(si))·ui(s1,…,sn) ≥ (xj(sj))·ui(s1,…,si−1,s′i,si+1,…,sn)
(s1 ,…,sn )∈S i=1 s−i ∈S−i j ̸=i Since p(s1,…,sn) = nj=1 xj(sj), we see that
nj=1 xj(sj) nj=1 xj(sj) p(s−i | si) = p(t−i;si) = xi(si)
nj=1 xj(sj)
xj(tj) = Usi(p|si)= (xj(sj))·ui(s−i;si).
t−i ∈S−i t−i ∈S−i j ̸=i Thus, by definition,
s−i ∈S−i j ̸=i
Note that therefore Usi(p | si) = Ui(x−i;si), where Ui(x−i;si) is the ex-
pected payoff to player i if it were to unilaterally switch to pure strategy si,
assuming everybody else plays according to the mixed profile x. Moreover, for any pure strategy s′i for player i, we have
Us′i(p|si)= (xj(sj))·ui(s−i;s′i) i
s−i ∈S−i j ̸=i
In other words, Us′i(p | si) = Ui(x−i;s′i) is the same as the expected payoff
to player i if it were to unilaterally switch to pure strategy s′i, assuming everyone
else plays according to the mixed profile x. 2
Our aim is to show that, under the assumption that x is an NE, and that player i was recommended si under the joint distribution p(s1 , . . . , sn ) =
xi(si), we must have U i(p | si) ≥ U i(p | si), or equivalently, that we
i=1 i i must have Ui(x−i; si) ≥ Ui(x−i; s′i).
But this follows immediately from the “useful corollary to Nash’s theorem”, because in order for si to be recommended to player i, si must be in the support of xi (meaning xi(si) > 0), and since we are assuming x is a , this means that the pure strategy si itself must be a best response to x−i. Hence Ui(x−i; xi) = Ui(x−i; si) ≥ Ui(x−i; s′i), and hence p is a correlated equilibrium.
We can express the fact that p is a Correlated Equilibrium via a system of LP constraints as follows. Firstly, we express that p must define a distribution on the set S of combinations of pure strategies, as follows:
p(s1, …, sn) ≥ 0, ∀(s1, …, sn) ∈ S (1)
p(s1, …, sn) = 1 (2) Next, we need to express all constraints of the form: Usi (p | si) ≥ Us′i (p | si),
(s1 ,s2 ,…sn )∈S
for every pair of pure strategies si, s′i such that si can possibly be recommended
to player i, in other words, such that t−i∈S−i p(t−i;si) > 0.
If we write these out explictly the constraint Usi(p | si) ≥ Us′i(p | si), it i
looks as follows:
p(s−i | si) · ui(s−i; si) ≥ p(s−i | si) · ui(s−i; s′i) s−i ∈S−i s−i ∈S−i
Which is equivalent to:
p(s−i | si) · (ui(s−i; si) − ui(s−i; s′i)) ≥ 0 (3)
But since p(s−i | si) = p(s−i;si) , and since we know the denominator
t−i∈S−i p(t−i;si)
is positive, by mulitplying both sides of the inequality by this denominator, we
can rewrite the inequality (3) as:
p(s−i; si) · (ui(s−i; si) − ui(s−i; s′i)) ≥ 0 (4) s−i ∈S−i
Note that this is an LP constraint.
Thus the set of Correlated Equilibria of a game can be defined as the set of feasible solutions to a system of linear inequalities. The fact that the set of feasible solutions to a system of linear inequalities is convex is of course well- known, and was discussed in the lectures on LP. (You can prove this yourself easily if you wish, from the definition of convexity.)
Given the game
a (5,2) (0,0)
b (0,0) (2,5)
Using the methods we have already learned, we see that the only three NE
in this game are:
• [(5, 2),(2, 5)] with expected payoff both for pl.1 and for player 2 : 10.
• [(0, 1), (0, 1)] with exp. payoff for player 1 = 2 and exp. payoff for player 2 = 5.
• [(1, 0), (1, 0)] with exp. payoff for player 1 = 5 and exp. payoff for player 2 = 2.
Now consider the correlated distribution, p, with probabilities: p(a,A) = 1/2,p(a,B) = 0,p(b,A) = 0,p(b,B) = 1/2.
We claim that p is a correlated equilibrium, which is not a NE. To see that p is a CE, we need to show that the constraints
Usi(p | si) ≥ Us′i(p | si) (5) i
are satisfied for all pure strategies si,s′i for each player i.
But in the context of this specific game, for example, if we let i = 1 and we let si = a and s′i = b, we have that inequality (5) is equivalent to:
U1a(p | a) = p(A|a)ui(a,A) = 5 ≥ 0 = p(A | a)ui(b,A) = U1b(p | a)
In the same way, it can be checked that all the inequalities of form (5) hold true. Thus, p is a CE. It is clearly not a NE.
Moreover, the expected payoff to each player under this CE is basically the weighted average of their payoff, weighted by the probabilities of the two possible recommendations p(a, A) and p(b, B). Thus, the expected payoff to each player is 5 + 2/2 = 3.5, yielding a sum total expected utility of 7 for both players, which is as high as in any Nash equilibrium (and note that this CE is also not “biased” toward either player, unlike the two NEs where the sum total expected payoff is 7).
Open discussion. Relevant arguments might include:
• the CE could give higher expected utilities than a Nash equilibrium; in the game above, for the CE given as example, t he total welfare is as high as any N.E.
• CE is less computationally expensive to compute.
• Nash equilibrium is relevant if one assumes that each player knows which strategies the other players are using. In CE, we do not make such as- sumption, players do not know in general how others are playing, but they know the prior distribution p of the recommendations. CE does not re- quire any explicit randomization on the part of the players. Each player always chooses a pure strategy with no attempt to randomize. The prob- abilistic nature of the strategies reflects the uncertainty of other players about his choice.
• NE⊆CE,i.eCEisasupersetofNE.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com