AGTA Tutorial Sheet 4
Please read and attempt these questions before coming to the tutorial.
1. Use iterated elimination of strictly dominated strategies in order to find the unique in this finite 2-player (bimatrix) game, by first reducing the game to a 2 × 2 game. (Recall that a pure strategy may be strictly dominated by a mixed strategy.)
(5,2) (22,4) (4,9) (7,6)
Copyright By PowCoder代写 加微信 powcoder
(16, 4) (15, 12)
(18, 5) (16, 9) (23, 9)
(1, 10) (18, 10) (11, 5)
(10, 2) (11, 3) (5, 13)
2. Recall that a finite n-player normal form game, G, is given by the payoff table that specifies, for each player i ∈ {1, . . . , n}, and for each combination (s1, . . . , sn) of pure strategies for the n players the payoff ui(s1, . . . , sn) for player i. (Here each sj ∈ Sj is a pure strategy for player j = 1,…,n.)
In this question we shall consider how to compute an important notion of equilibrium which generalizes Nash equilibrium, called “correlated equilibrium”.
For a finite n-player game, G, with pure strategy sets S1, . . . , Sn, a correlated distribution is a probability distribution, p(·), on the set of possible pure-strategy combinations (i.e., pure- strategy profiles), (s1,…,sn) ∈ S1 × … × Sn = S. In other words, for all (s1,…,sn) ∈ S, p(s1,…,sn) ≥ 0, and (s1,…,sn)∈S p(s1,…,sn) = 1.
Note: a correlated distribution p(·) is not necessarily a distribution on combinations of pure strategies that arises from a mixed strategy profile x = (x1, . . . , xn), where the probability of each pure combination (s1,…,sn) is the product of the probabilities ni=1xi(si) with which each player i randomly (independently) chooses its own pure strategy si according to distribution xi(·). Such a joint distribution on pure-strategy profiles is called a product distribution on S = S1 × . . . × Sn, whereas a correlated distribution can be any distribution on S.
Interpretation: imagine that there is a “randomized recommender”, who uses the proba- bility distribution p(·) to randomly select a pure-strategy profile (s1, . . . , sn), and who then suggests to each player i to play pure strategy si. Assume every player knows the distribution p.
For a given correlated distribution p, for a given pure strategy si ∈ Si for player i, and for a given combination s−i = (s1, s2, . . . , si−1, empty, si+1, . . . , sn) ∈ S−i of pure strategies for all the other players (other than player i), let
p(s−i; si) p(s−i | si) = t−i∈Si p(t−i; si)
denote the conditional probability of the combination of strategies s = (s1, . . . , sn), given that the pure strategy si was recommended to player i by the “random recommender” (who uses joint distribution p to pick everyone’s recommendation).
Now suppose player i believes that other players are inclinded to follow the recommendation of the recommender. If player i is recommended pure strategy si ∈ Si, and chooses to play pure strategy s′i ∈ Si, let
Us′i(p|si):= p(s−i |si)·ui(s−i;s′i) i
denote the conditional expected payoff to player i, for playing pure strategy s′i, assuming other players play according to their recommendations from correlated distribution p on pure-strategy profiles, conditioned on the fact that player i itself was recommended the pure strategy si.
Definition: A correlated distribution p(·) is a correlated equilibrium (CE) for the game if for all players i and all pure strategies si, s′i ∈ Si,
U i(p|si)≥U i(p|si)
In other words, no single player would be strictly better off by unilaterally deviating from its own recommendation si under the distribution p (its expected payoff, conditioned on the pure strategy si that it was recommended, would not be increased by deviating) using a different strategy s′i.
Questions:
(a) Explain why every Nash equilibrium x = (x1, . . . , xn) necessarily also gives a CE, defined by the correlated distribution p(·) given by the product distribution p(s1,…,sn) = ni=1 xi(si). Thus, conclude that every finite game does have at least one CE.
(b) Given a n-player game G, show how to construct a linear program (without any objective function), such that the set of feasible solutions of the linear program is precisely the set of CE of the game G. Use this to conclude that the set of CE of the game G must form a convex set (in fact a convex polytope), meaning that any convex combination (i.e., weighted average) of CEs of G is itself a CE of G.
(c) Consider a 2-player bimatrix game, given by:
(5,2) (0,0)
(0, 0) (2, 5)
We can interpret this game as follows: two people want to meet each other, at one of two locations, a or b. Player 1 prefers to meet at a, giving him payoff 5, whereas if they meet at b he gets payoff 2. Player 2 prefers to meet at b, giving her payoff 5, otherwise if they meet at a she gets payoff 2. The two of them definitely do want to meet somewhere (they really like each other), because if they don’t meet (i.e., if they go to different locations), they would both get payoff zero. The two can of course try to randomize their choice. Compute a CE for this game, which is not a Nash equilibrium, and which gives the same expected payoff to both players, and such that the total welfare (i.e., sum of the expected utilities to both players) in the CE is as high as in any Nash equilibrium. Conclude that the set of CEs constitutes a superset of the set of Nash equilibria.
Notice, by the way that the set of Nash equilibria of the above game does not form a convex set. (In fact there are exactly 3 Nash equilibria for the above game, and thus clearly, not all convex combinations of them form a Nash equilibrium. Otherwise, there would be infinitely many Nash equilibria.)
(d) (Vague question) can you imagine any situations where a CE may make more “sense” as a solution concept than a Nash equilibrium? What about in the game above?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com