Consider the game matrix below for two players, and the mixed strategy profile s
ID: 3834366 • Letter: C
Question
Consider the game matrix below for two players, and the mixed strategy profile s_1: (0.2, 0.4, 0.4) and s_2: (0.3, 0.1, 0.6) where s_1 is the strategy for the row player and s2 is the strategy for the column player. a. Calculate the expected payoff for each player when the players play the strategy profile (s_1, s_2). b. Now, calculate the expected value of playing each of the row players pure strategies against the column players strategy s_2. c. What is the best response for the row player to s_2?Explanation / Answer
Definition 2 A strategy profile (1, ..., I ) is a Nash equilibrium of G if for every i, and every si Si, ui(i, i) ui(si, i). And recall Nash’s famous result: Proposition 1 Nash equilibria exist in finite games. A natural question, given the wide use of Nash equilibrium, is whether or why one should expect Nash behavior. One justification is that rational players ought somehow to reason their way to Nash strategies. That is, Nash equilibrium might arrive through introspection. A second justification is that Nash equilibria are self-enforcing. If players agree on a strategy profile before independently choosing their actions, then no player will have reason to deviate if the agreed profile is a Nash equilibrium. On the other hand, if the agreed profile is not a Nash equilibrium, some player can do better by breaking the agreement. A third, and final, justification is that Nash behavior might result from learning or evolution. In what follows, we take up these three ideas in turn. 2 Correlated Equilibrium 2.1 Equilibria as a Self-Enforcing Agreements Let’s start with the account of Nash equilibrium as a self-enforcing agreement. Consider Battle of the Sexes (BOS). Here, it’s easy to imagine the players jointly deciding to attend the Ballet, then playing (B,B) since neither wants to unilaterally head off to Football. However, a little imagination suggests that Nash equilibrium might not allow the players sufficient freedom to communicate. Example 2, cont. Suppose in BOS, the players flip a coin and go to the Ballet if the coin is Heads, the Football game if Tails. That is, they just randomize between two different Nash equilibria. This coin flip allows a payoff ( 3 2 , 3 2 ) that is not a Nash equilibrium payoff. 2 So at the very least, one might want to allow for randomizations between Nash equilibria under the self-enforcing agreement account of play. Moreover, the coin flip is only a primitive way to communicate prior to play. A more general form of communication is to find a mediator who can perform clever randomizations, as in the next example. Example 3 This game has three Nash equilibria (U, L), (D, R) and ( 1 2U + 1 2D, 1 2L + 1 2R) with payoffs (5, 1), (1, 5) and ( 5 2 , 5 2 ). L R U 5, 1 0, 0 D 4, 4 1, 5 Suppose the players find a mediator who chooses x {1, 2, 3} with equal probability 1 3 . She then sends the following messages: • If x = 1 tells Row to play U, Column to play L. • If x = 2 tells Row to play D, Column to play L. • If x = 3 tells Row to play D, Column to play R. Claim. It is a Perfect Bayesian Equilibrium for the players to follow the mediator’s advice. Proof. We need to check the incentives of each player. • If Row hears U, believes Column will play L play U. • If Row hears D, believes Column will play L, R with 1 2 , 1 2 probability play D. • If Column hears L, believes Row will play U, D with 1 2 , 1 2 probability play L. • If Column hears R, believes Row will play D play R. Thus the players will follow the mediator’s suggestion. With the mediator in place, expected payoffs are ( 10 3 , 10 3 ), strictly higher than the players could get by randomizing between Nash equilibria. 2.2 Correlated Equilibrium The notion of correlated equilibrium builds on the mediator story. Definition 3 A correlating mechanism (, {Hi}, p) consists of: 3 • A finite set of states • A probability distribution p on . • For each player i, a partition of , denoted {Hi}. Let hi() be a function that assigns to each state the element of i’s partition to which it belongs. Example 2, cont. In the BOS example with the coin flip, the states are = {Heads, Tails}, the probability measure is uniform on , and Row and Column have the same partition, {{Heads}, {Tails}}. Example 3, cont. In this example, the set of states is = {1, 2, 3}, the probability measure is again uniform on , Row’s partition is {{1}, {2, 3}}, and Column’s partition is {{1, 2}, {3}}. Definition 4 A correlated strategy for i is a function fi : Si that is measurable with respect to i’s information partition. That is, if hi() = hi(0 ) then fi() = fi(0 ). Definition 5 A strategy profile (f1, ..., fI ) is a correlated equilibrium relative to the mechanism (, {Hi}, p) if for every i and every correlated strategy ˜fi: X ui (fi(), fi()) p () X ui ³ ˜f(), fi() ´ p () (1) This definition requires that fi maximize i’s ex ante payoff. That is, it treats the strategy as a contingent plan to be implemented after learning the partition element. Note that this is equivalent to fi maximizing i’s interim payoff for each Hi that occurs with positive probability – that is, for all i,, and every s0 i Si, X 0hi() ui(fi(), fi(0 ))p(0 |hi()) X 0hi() ui(s0 i, fi(0 ))p(0 |hi()) Here, p(0 |hi()) is the conditional probability on 0 given that the true state is in hi(). By Bayes’ Rule, p(0 |hi()) = Pr (hi()|0 ) p(0 ) P 00hi() Pr (hi()|00) p(00) = p(0 ) p(hi()) 4 The definition of CE corresponds to the mediator story, but it’s not very convenient. To search for all the correlated equilibria, one needs to consider millions of mechanisms. Fortunately, it turns out that we can focus on a special kind of correlating mechanism, callled a direct mechanism. We will show that for any correlated equilibrium arising from some correlating mechanism, there is a correlated equilibrium arising from the direct mechanism that is precisely equivalent in terms of behavioral outcomes. Thus by focusing on one special class of mechanism, we can capture all possible correlated equilibria. Definition 6 A direct mechanism has = S, hi(s) = {s0 S : s0 i = si}, and some probability distribution q over pure strategy profiles. Proposition 2 Suppose f is a correlated equilibrium relative to (, {Hi}, p). Define q(s) Pr(f() = s). Then the strategy profile ˜f with ˜fi(s) = si for all i, s S is a correlated equilibrium relative to the direct mechanism (S, {H˜i}, q). Proof. Suppose that si is recommended to i with positive probability, so p(si, si) > 0 for some si. We check that under the direct mechanism (S, {H˜i}, q), player i cannot benefit from choosing another strategy s0 i when si is suggested. If si is recommended, then i’s expected payoff from playing s0 i is: X siSi ui(s0 i, si)q(si|si). The result is trivial if there is only one information set Hi in the original mechanism for which fi(Hi) = si. In this case, conditioning on si is the same as conditioning on Hi in the original. More generally, we substitute for q to obtain: 1 Pr(fi() = si) · X |fi()=si ui(s0 i, fi())p(). Re-arranging to separate each Hi at which si is optimal: 1 Pr(fi() = si) · X Hi|fi(Hi)=si Pr (Hi) X Hi ui(s0 i, fi())p(|Hi) Since (, {Hi}, p, f) is a correlated equilibrium, each bracketed term for which Pr(Hi) > 0 is maximized at fi(Hi) = si. So si is optimal given recommendation si. Q.E.D. 5 Thus what really matters in correlated equilibrium is the probability distribution over strategy profiles. We refer to any probability distribution q over strategy profiles that arises as the result of a correlated equilibrium as a correlated equilibrium distribution (c.e.d.). Example 2, cont. In the BOS example, the c.e.d. is 1 2 (B,B), 1 2 (F, F). Example 3, cont. In this example, the c.e.d is 1 3 (U, L), 1 3 (D, L), 1 3 (D, R). The next result characterizes correlated equilibrium distributions. Proposition 3 The distribution q (S) is a correlated equilibrium distribution if and only if for all i, every si with q(si) > 0 and every s0 i Si, X siSi ui (si, si) q (si|si) X siSi ui(s0 i, si)q(si|si). (2) Proof. () Suppose q satisfies (2). Then the “obedient” profile f with fi(s) = si is a correlated equilibrium given the direct mechanism (S, {Hi}, q) since (2) says precisely that with this mechanism si is optimal for i given recommendation si. () Conversely, if q arises from a correlated equilibrium, the previous result says that the obedient profile must be a correlated equilibrium relative to the direct mechanism (S, {Hi}, q). Thus for all i and all recommendations si occuring with positive probability, si must be optimal – i.e. (2) must hold. Q.E.D. Consider a few properties of correlated equilibrium. Property 1 Any Nash equilibrium is a correlated equilibrium Proof. Need to ask if (2) holds for the probability distribution q over outcomes induced by the NE. For a pure equilibrium s, we have q(s i|s i) = 1 and q(si|s i)=0 for any si 6= s i. Therefore (2) requires for all i, si : ui(s i , s i) ui(si, s i). This is precisely the definition of NE. For a mixed equilibrium, , we have that for any s i in the support of i , q(si|s i) = i(si). This follows from the fact that in a mixed NE, the players mix independently. Therefore (2) requires that for all i, s i in the support of i , and si, X siSi ui (s i , si) i (si) X siSi ui(si, si)i(si), again, the definition of a mixed NE. Q.E.D. 6 Property 2 Correlated equilibria exist in finite games. Proof. Any NE is a CE, and NE exists. Hart and Schmeidler (1989) show the existence of CE directly, exploiting the fact that a CE is just a probability distribution q satisfying a system of linear inequalities. Their proof does not appeal to fixed point results! Q.E.D. Property 3 The sets of correlated equilibrium distributions and payoffs are convex. Proof. Left as an exercise. 2.3 Subjective Correlated Equilibrium The definition of correlated equilibrium assumes the players share a common prior p over the set of states (or equivalently share the same probability distribution over equilibrium play). A significantly weaker notion of equilibrium obtains if this is relaxed. For this, let p1, p2, ..., pI be distinct probability measures on . Definition 7 The profile f is a subjective correlated equilibrium relative to the mechanism (, {Hi}, p1, ..., pI ) if for every i, and every alternative strategy ˜fi, X ui(fi(), fi())pi() X ui( ˜f(), fi())pi() Example 3, cont. Returning to our example from above, L R U 5, 1 0, 0 D 4, 4 1, 5 Here, (4, 4) can be obtained as a SCE payoff. Simply consider the direct mechanism with p1 = p2 = 1 3 (U, L) + 1 3 (D, L) + 1 3 (D, R). This is a SCE, and since there is no requirement that the players have objectively correct beliefs about play, it may be that (D, L) is played with probability one! 7 2.4 Comments 1. The difference between mixed strategy Nash equilibria and correlated equilibria is that mixing is independent in NE. With more than two players, it may be important in CE that one player believes others are correlating their strategies. Consider the following example from Aumann (1987) with three players: Row, Column and Matrix. 0, 0, 3 0, 0, 0 1, 0, 0 0, 0, 0 2, 2, 2 0, 0, 0 0, 0, 0 2, 2, 2 0, 0, 0 0, 0, 0 0, 1, 0 0, 0, 3 No NE gives any player more than 1, but there is a CE that gives everyone 2. Matrix picks middle, and Row and Column pick (Up,Left) and (Down,Right) each with probability 1 2 . The key here is that Matrix must expect Row to pick Up precisely when Column picks Left. 2. Note that in CE, however, each agent uses a pure strategy – he just is uncertain about others’ strategies. So this seems a bit different than mixed NE if one views a mixed strategy as an explicit randomization in behavior by each agent i. However, another view of mixed NE if that it’s not i’s actual choice that matters, but j’s beliefs about i’s choice. On this account, we view i as what others expect of i, and i as simply doing some (pure strategy) best response to i. This view, which is consistent with CE, was developed by Harsanyi (1973), who introduced small privately observed payoff perturbations so that in pure strategy BNE, players would be uncertain about others behavior. His “purification theorem” showed that these pure strategy BNE are observably equivalent to mixed NE of the unperturbed game if the perturbations are small and independent. 3. Returning to our pre-play communication account, one might ask if a mediator is actually needed, or if the players could just communicate by flipping coins and talking. With two players, it should be clear from the example above that the mediator is crucial in allowing for messages that are not common knowledge. However, Barany (1992) shows that if I 4, then any correlated equilibrium payoff (with rational numbers) can be achieved as the Nash equilibrium of an extended game where prior to play the players communicate through cheap talk. Girardi (2001) shows the same can be done as a sequential equilibrium provided I 5. For the case of two players, Aumann and Hart (2003) characterize the set of attainable payoffs if players can communicate freely, but without a mediator, prior to playing the game.