Eco514-Game Theory Lecture 4: Games with Payoff Uncertainty(1 Marciano siniscalchi September 28, 1999 Introduction The vast majority of games of interest in economics, finance, political economy etc. involve some form of payoff uncertainty. A simple but interesting example is provided by auctions an object is offered for sale, and individuals are required to submit their bids in sealed envelopes. The object is then allocated to the highest bidder at a price which depends on every bid, according to some prespecified rule(e. g. a" first-price "or "second-price"rule). In many circumstances(e. g. mineral rights auctions) it is reasonable to assume that the value of the object is not known to the buyers, but that they receive some signal correlated with it. In other cases, each buyer knows the value of the object to her, but not the other players valuation We can model this situation assuming that the set of actions available to every player is the nonnegative real half-line, or some subset of it, representing allowable bids. While a profile of bids specifies the "outcome"of the auction, i. e. who receives the object and what price she pays for it, it does not specify the payoff to the winning bidder Her payoff is determined by the(uncertain) value of the object; the uncertainty may even be resolved only after the bidding game is over(e.g. when drilling or mining actually begins in the“ mineral rights”case) Thus, we need to extend our basic model of simultaneous games in order to account for payoff uncertainty The second issue is related to the solution concept(s) to apply in this setting. In the auction example, it is reasonable to assume that players will condition their bid on whatever signal they receive. In particular, in the "mineral rights"case, for any profile of bids, players cannot compute their actual payoff because of the underlying uncertainty, but they can at least compute their conditional expected payoff given their signal This implies that a solution concept for games with payoff uncertainty should specify an action(or a set of actions) for each player and for each realization of whatever signal that
Eco514—Game Theory Lecture 4: Games with Payoff Uncertainty (1) Marciano Siniscalchi September 28, 1999 Introduction The vast majority of games of interest in economics, finance, political economy etc. involve some form of payoff uncertainty. A simple but interesting example is provided by auctions: an object is offered for sale, and individuals are required to submit their bids in sealed envelopes. The object is then allocated to the highest bidder at a price which depends on every bid, according to some prespecified rule (e.g. a “first-price” or “second-price” rule). In many circumstances (e.g. mineral rights auctions) it is reasonable to assume that the value of the object is not known to the buyers, but that they receive some signal correlated with it. In other cases, each buyer knows the value of the object to her, but not the other players’ valuation. We can model this situation assuming that the set of actions available to every player is the nonnegative real half-line, or some subset of it, representing allowable bids. While a profile of bids specifies the “outcome” of the auction, i.e. who receives the object and what price she pays for it, it does not specify the payoff to the winning bidder. Her payoff is determined by the (uncertain) value of the object; the uncertainty may even be resolved only after the bidding game is over (e.g. when drilling or mining actually begins, in the “mineral rights” case). Thus, we need to extend our basic model of simultaneous games in order to account for payoff uncertainty. The second issue is related to the solution concept(s) to apply in this setting. In the auction example, it is reasonable to assume that players will condition their bid on whatever signal they receive. In particular, in the “mineral rights” case, for any profile of bids, players cannot compute their actual payoff because of the underlying uncertainty, but they can at least compute their conditional expected payoff given their signal. This implies that a solution concept for games with payoff uncertainty should specify an action (or a set of actions) for each player and for each realization of whatever signal that 1
player may observe However, several subtle issues arise regarding the interpretation of "signals. If the latter can be literally take en to be phy I observations(e. g. samples or geological then it makes sense to assume that players share a common probabilistic description of the underlying uncertain quantities and their correlation with each player's signal. Such description could even be said to be part of the formulation of the game If, however, signals do not have a readily available physical interpretation(consider the value, i. e, the maximum amount one is willing to pay for a painting, which presumably includes a subjective element), then it does not make much sense to postulate that players agree on any given probabilistic model of the underlying uncertain quantities-let alone make such description part of the formulation of the game. Rather, a specification of players beliefs about the underlying uncertainties should be considered as part of the solution concept Further observations will be in order once we specify a formal model of games with payoff uncertainty Games with Payoff uncertainty I follow OR (with minimal expository deviations) and begin by providing a rather general definition Definition 1 A(finite)normal-form game with payoff uncertainty is a tuple=(N, Q, (Ai, ui, TiieN) where N is a finite set of players, Q2 is a set of states of the world, and for each i E N, Ai is a set of actions, u;: Ai x A-ix Q-r is Player i' s payoff function, and Ti is a partition of Q, referred to as Player i's type partition It may be helpful to relate normal-form games with payoff uncertainty with the decision- eoretic framework introduced in Lecture 1. Taking the perspective of Player i, the set of states of nature for i is Q2= A-i X Q; the set of acts is(isomorphic to) Ai, with each act ai E Ai mapping a state(a-i, w)En to the outcome determined by the tuple(ai, a-i, w) finally, Player i's preferences over outcomes are represented by u Thus, Player i is not only uncertain about her opponents'actions: she is also uncertain as to the prevailing state of the world w E Q. In keeping with our general framework, a solution concept should specify a probability distribution over whatever a player is uncertain about hence, it must also specify her beliefs about the prevailing state of the world Note: the usual textbook"presentation of the situations referred to herein uses the terminology "games with incomplete information, and includes a specification of a common prior over the set of states of the world as part of the description of the strategic situation We use the somewhat nonstandard term"payoff uncertainty'"to emphasize that we do not wish to regard probabilities over states of the world as part of the model, but rather as part
player may observe. However, several subtle issues arise regarding the interpretation of “signals.” If the latter can be literally taken to be physical observations (e.g. samples or geological surveys), then it makes sense to assume that players share a common probabilistic description of the underlying uncertain quantities and their correlation with each player’s signal. Such description could even be said to be part of the formulation of the game. If, however, signals do not have a readily available physical interpretation (consider the value, i.e, the maximum amount one is willing to pay for a painting, which presumably includes a subjective element), then it does not make much sense to postulate that players agree on any given probabilistic model of the underlying uncertain quantities—let alone make such description part of the formulation of the game. Rather, a specification of players’ beliefs about the underlying uncertainties should be considered as part of the solution concept. Further observations will be in order once we specify a formal model of games with payoff uncertainty. Games with Payoff Uncertainty I follow OR (with minimal expository deviations) and begin by providing a rather general definition. Definition 1 A (finite) normal-form game with payoff uncertainty is a tuple G = (N, Ω,(Ai , ui , Ti)i∈N ), where N is a finite set of players, Ω is a set of states of the world, and for each i ∈ N, Ai is a set of actions, ui : Ai × A−i × Ω → R is Player i’s payoff function, and Ti is a partition of Ω, referred to as Player i’s type partition. It may be helpful to relate normal-form games with payoff uncertainty with the decisiontheoretic framework introduced in Lecture 1. Taking the perspective of Player i, the set of states of nature for i is Ω = ˜ A−i × Ω; the set of acts is (isomorphic to) Ai , with each act ai ∈ Ai mapping a state (a−i , ω) ∈ Ω to the outcome determined by the tuple ˜ (ai , a−i , ω); finally, Player i’s preferences over outcomes are represented by ui . Thus, Player i is not only uncertain about her opponents’ actions: she is also uncertain as to the prevailing state of the world ω ∈ Ω. In keeping with our general framework, a solution concept should specify a probability distribution over whatever a player is uncertain about; hence, it must also specify her beliefs about the prevailing state of the world. Note: the usual “textbook” presentation of the situations referred to herein uses the terminology “games with incomplete information, and includes a specification of a common prior over the set of states of the world as part of the description of the strategic situation. We use the somewhat nonstandard term “payoff uncertainty” to emphasize that we do not wish to regard probabilities over states of the world as part of the model, but rather as part 2
of the solution to the model. In particular, we do not wish to assume that such probabilities are commonly agreed upon among the players. Notice that OR follows the same approach The key elements are the set of states of the world, which also affect payoffs(otherwise there could be no payoff uncertainty! ) and the players' type partitions The idea is that, if the prevailing state is w E Q, each player i E N is only notified that the prevailing state is in the unique cell ti E Ti such that w E ti; that is, Player i rules out any w' ti, but regards any w'e ti as possible. We denote by ti(w) the set of states that Player i deems possible at w E S: that is, ti(w)is the unique ti E T such that w E Ti Indeed, in order to interpret the partition Ti correctly, one should think of states in each cell ti E Ti as virtually indistinguishable from the point of view of Player i. This will be clear from our use of the model To fix ideas, consider the following version of the"mineral rights " auction settin are two bidders, i=1, 2, and each receives a signal s; E 10,1,..., 10); the value of the object (concession)is v(s1, $2)=S1+S2 Thus,9={0,1 }×{0,1,…,10};T={{ k}:k=0, ui(ai, a-i,(S1, $2))=S1+S2-ai if ai>a-i,(S1+S2-ai)if ai=a-i, and 0 otherwise Si. On the other hand, both her signal and her opponent's signal determine payoffs e value The key observation is that each bidder i E N only observes her "part"of the tru Elements of the partition Ti are also referred to as types. Each type arguably captures a possible information state of Player i: it tells us all she knows about the prevailing state of the world Note well that, on the other hand, a type generally does not uniquely determine a player's payoff corresponding to each action profile: this is illustrated in the mineral rights auction example above. Perhaps more interestingly, one could think of different information states sayt,t∈T, such that, for all c,u’∈tu2t(a,a-1,)=t1(a1,a-;u) for all(a;,a-i)∈A: for example, this might be the case if, at w and w, player i attaches the same value to a painting, but holds different beliefs as to the prevailing state of the world(hence, about her opponents valuation). More on this point later Bayesian Nash Equilibrium The standard analysis of normal-form games with payoff uncertainty(suitably extended to accommodate our decision-theoretic view) is centered upon the notion of Bayesian Nash Equilibrium, due to John Harsany Definition 2 A Bayesian Nash Equilibrium of a normal-form game with payoff uncertaint G=(N,9,(A2,t1,T)eN) is a tuple(P,(at);∈n;)∈ v such that, for all i∈N (1)n2∈△()and, for all t∈T1,p1(t2)>0
of the solution to the model. In particular, we do not wish to assume that such probabilities are commonly agreed upon among the players. Notice that OR follows the same approach. The key elements are the set of states of the world, which also affect payoffs (otherwise there could be no payoff uncertainty!), and the players’ type partitions. The idea is that, if the prevailing state is ω ∈ Ω, each player i ∈ N is only notified that the prevailing state is in the unique cell ti ∈ Ti such that ω ∈ ti ; that is, Player i rules out any ω 0 6∈ ti , but regards any ω 0 ∈ ti as possible. We denote by ti(ω) the set of states that Player i deems possible at ω ∈ Ω: that is, ti(ω) is the unique ti ∈ Ti such that ω ∈ Ti . Indeed, in order to interpret the partition Ti correctly, one should think of states in each cell ti ∈ Ti as virtually indistinguishable from the point of view of Player i. This will be clear from our use of the model. To fix ideas, consider the following version of the “mineral rights” auction setting: there are two bidders, i = 1, 2, and each receives a signal si ∈ {0, 1, . . . , 10}; the value of the object (concession) is v(s1, s2) = s1 + s2. Thus, Ω = {0, 1, . . . , 10} × {0, 1, . . . , 10}; Ti = {{(s1, s2) : si = k} : k = 0, 1, . . . , 10}; and ui(ai , a−i ,(s1, s2)) = s1 + s2 − ai if ai > a−i , 1 2 (s1 + s2 − ai) if ai = a−i , and 0 otherwise. The key observation is that each bidder i ∈ N only observes her “part” of the true value, si . On the other hand, both her signal and her opponent’s signal determine payoffs. Elements of the partition Ti are also referred to as types. Each type arguably captures a possible information state of Player i: it tells us all she knows about the prevailing state of the world. Note well that, on the other hand, a type generally does not uniquely determine a player’s payoff corresponding to each action profile: this is illustrated in the mineral rights auction example above. Perhaps more interestingly, one could think of different information states, say ti , t0 i ∈ Ti , such that, for all ω, ω0 ∈ ti∪t 0 i , ui(ai , a−i , ω) = ui(ai , a−i , ω0 ) for all (ai , a−i) ∈ A: for example, this might be the case if, at ω and ω 0 , player i attaches the same value to a painting, but holds different beliefs as to the prevailing state of the world (hence, about her opponents’ valuation). More on this point later. Bayesian Nash Equilibrium The standard analysis of normal-form games with payoff uncertainty (suitably extended to accommodate our decision-theoretic view) is centered upon the notion of Bayesian Nash Equilibrium, due to John Harsanyi: Definition 2 A Bayesian Nash Equilibrium of a normal-form game with payoff uncertainty G = (N, Ω,(Ai , ui , Ti)i∈N ) is a tuple (pi ,(αi,ti )ti∈Ti )i∈N such that, for all i ∈ N: (1) pi ∈ ∆(Ω) and, for all ti ∈ Ti , pi(ti) > 0; 3
(2) For all t∈T; and for all a∈A, E{.()(- )}≥0 Note that it is of course sufficient to check for profitable deviations to pure actions. The product in parentheses is the probability that the action profile a-i will be played in state wE Q. This is the product of the probability that each a;,j+i, gets played, given that, in state w, player j i is of type t;(w) Next, the expression in curly braces is the difference in expected payoff from playing a and a! in state w Finally, these differences are weighted by the posterior probability that the state is actu- ally w, given that the true state must lie in ti Observe that, it is also possible to formulate the best-reply property for type-contingent randomized actions ai =(ai. ieN. As long as condition(1)above holds, it can be shown that the resulting definition is actually equivalent to the one given above: I will ask you to provide the details Where does this come from? We now take a step back and try to provide a rationale for this seemingly complex construc- tion(due largely to John Harsanyi, a recent Nobel laureate). It turns out that, indeed, this framework greatly simplifies the problem of describing strategic interaction in games with payoff uncertainty To keep the exposition simple(and in view of the fact that auctions will be the subject of a forthcoming lecture), let us consider a simple two-firm Cournot model with uncertainty about firn1’ s cost. Denote the latter variable by c E 10,5. Recall the setup: demand is given by P(Q) 2-Q and each firm can produce qi E [ 0, 1]. Firm 2's cost is zero It is probably easiest to think in standard equilibrium terms. Suppose that we are told that a given tuple(1.0, 11, 2 )is "an equilibrium outcome "of the game. Let us ask ourselves exactly what this implies At first blush, there is little action on Firm I's side: she(? )expects Firm 2 to produce g2 units, as per the equilibrium prescription, and best-responds to this: 1. c= BR1(92, c) (1-)-是g,forc∈{0.是 Now let us concentrate on Firm 2. Clearly, the latter cannot compute a best reply to his opponent's actions without formulating a conjecture about the relative likelihood of the Iso note that, strictly speaking, what is defined above is Bayesian Nash equilibrium for the mixed extension of the original game C
(2) For all ti ∈ Ti and for all a 0 i ∈ Ai , X ω∈ti pi(ω) pi(ti) X a−i∈A−i Y j6=i αj,tj (ω)(aj ) ! " X ai∈Ai αi,ti (ai)ui(ai , a−i , ω) ! − ui(a 0 i , a−i , ω) # ≥ 0 Note that it is of course sufficient to check for profitable deviations to pure actions.1 The product in parentheses is the probability that the action profile a−i will be played in state ω ∈ Ω. This is the product of the probability that each aj , j 6= i, gets played, given that, in state ω, player j 6= i is of type tj (ω). Next, the expression in curly braces is the difference in expected payoff from playing ai and a 0 i in state ω. Finally, these differences are weighted by the posterior probability that the state is actually ω, given that the true state must lie in ti . Observe that, it is also possible to formulate the best-reply property for type-contingent randomized actions αi = (αi,ti )i∈N . As long as condition (1) above holds, it can be shown that the resulting definition is actually equivalent to the one given above: I will ask you to provide the details. Where does this come from? We now take a step back and try to provide a rationale for this seemingly complex construction (due largely to John Harsanyi, a recent Nobel laureate). It turns out that, indeed, this framework greatly simplifies the problem of describing strategic interaction in games with payoff uncertainty. To keep the exposition simple (and in view of the fact that auctions will be the subject of a forthcoming lecture), let us consider a simple two-firm Cournot model with uncertainty about Firm 1’s cost. Denote the latter variable by c ∈ {0, 1 2 }. Recall the setup: demand is given by P(Q) = 2 − Q and each firm can produce qi ∈ [0, 1]. Firm 2’s cost is zero. It is probably easiest to think in standard equilibrium terms. Suppose that we are told that a given tuple (q1,0, q1, 1 2 , q2) is “an equilibrium outcome” of the game. Let us ask ourselves exactly what this implies. At first blush, there is little action on Firm 1’s side: she (?) expects Firm 2 to produce q2 units, as per the equilibrium prescription, and best-responds to this: q1,c = BR1(q2, c) = (1 − c 2 ) − 1 2 q2, for c ∈ {0, 1 2 }. Now let us concentrate on Firm 2. Clearly, the latter cannot compute a best reply to his opponent’s actions without formulating a conjecture about the relative likelihood of the 1Also note that, strictly speaking, what is defined above is Bayesian Nash equilibrium for the mixed extension of the original game G. 4
events c=0 and c=5. Denote by T the probability of the former event; then, since Firm 2s best reply is Br2(Tq1,0+(1-T)q1, 2), if we are given the information that q2 is a best reply, we can "reverse-engineer"the value of T (in this case, it is unique) n terms of our mode lel, we could let Q2=10,, Ti=10, 03, T2=Q2 and p2(0) T. It is easy to see that specifying pi is not relevant for the purposes of Definition 2 what matters there are the beliefs conditional on each ti E Ti, but these will obviously be degenerate Let us think about the value of the parameter T(or, equivalently, of the probability P2). We have just noted that, given the equilibrium outcome, it is possible to derive Firm 2 s conjecture T. Hence, since Firm 1 expects Firm 2 to play g2 and(according to the equilibrium assumption) believes that Firm 2 expects Firm 1 to play q1.c, for each value of the cost parameter c, it follows that Firm 1 can infer that Firm 2's assessment of the probability that c=0 is T. In other words, implicit in the specific equilibrium we are looking at is an assumption about Firm 1s beliefs regarding Firm 2's beliefs. It is easy to see that we can continue in this fashion to build a whole hierarchy of interactive beliefs x In terms of our model, note that Player 2's type partition is degenerate. As a consequence, any state w E S, Player 2's conditional beliefs about Q2, pi (It2(w)) are the same--they are given by the unconditional probability p2 We can represent this observation formally by defining, for any probability measure q∈△(9) and player i∈N, an event [al:={:n(u|t(∞)=q.Then, in this game, [p2]2=Q2. By way of comparison, it is easy to see that it cannot be the case that pil1=Q (why? regardless of how we specify P1 Now take the point of view of Player 1. Since []2=Q2, it is trivially true that p1(p2]2|t1()=1u∈9; in words, at any state w, Player 1 is certain that Player 2s beliefs are given by p2 (i.e. by T). By the exact same argument, at any state w, Player 2 is certain that Player 1 is certain that Player 2's beliefs are given by p2, and so on and so forth I wish to draw your attention to two key conclusions that can be drawn based on this anaIvsis 1. The standard model of games with payoff uncertainty is capable of generating infinite hierarchies of interactive beliefs about the underlying state of the world Indeed, this was precisely Harsanyi's original objective: he realized that, in the pi esence of payoff uncertainty, the players' strategic reasoning necessarily involves this sort of infinite regress, and devised a very clever way to generate this information in a compact, manageable
events c = 0 and c = 1 2 . Denote by π the probability of the former event; then, since Firm 2’s best reply is BR2(πq1,0 + (1 − π)q1, 1 2 ), if we are given the information that q2 is a best reply, we can “reverse-engineer” the value of π (in this case, it is unique). In terms of our model, we could let Ω = {0, 1 2 }, T1 = {{0}, { 1 2 }}, T2 = {Ω} and p2(0) = π. It is easy to see that specifying p1 is not relevant for the purposes of Definition 2: what matters there are the beliefs conditional on each t1 ∈ T1, but these will obviously be degenerate. Let us think about the value of the parameter π (or, equivalently, of the probability p2). We have just noted that, given the equilibrium outcome, it is possible to derive Firm 2’s conjecture π. Hence, since Firm 1 expects Firm 2 to play q2 and (according to the equilibrium assumption) believes that Firm 2 expects Firm 1 to play q1,c, for each value of the cost parameter c, it follows that Firm 1 can infer that Firm 2’s assessment of the probability that c = 0 is π. In other words, implicit in the specific equilibrium we are looking at is an assumption about Firm 1’s beliefs regarding Firm 2’s beliefs. It is easy to see that we can continue in this fashion to build a whole hierarchy of interactive beliefs. In terms of our model, note that Player 2’s type partition is degenerate. As a consequence, at any state ω ∈ Ω, Player 2’s conditional beliefs about Ω, pi(·|t2(ω)) are the same—they are given by the unconditional probability p2. We can represent this observation formally by defining, for any probability measure q ∈ ∆(Ω) and player i ∈ N, an event [q]i = {ω : pi(ω|ti(ω)) = q}. Then, in this game, [p2]2 = Ω. By way of comparison, it is easy to see that it cannot be the case that [p1]1 = Ω (why?) regardless of how we specify p1. Now take the point of view of Player 1. Since [p2]2 = Ω, it is trivially true that p1([p2]2|t1(ω)) = 1 ∀ω ∈ Ω; in words, at any state ω, Player 1 is certain that Player 2’s beliefs are given by p2 (i.e. by π). By the exact same argument, at any state ω, Player 2 is certain that Player 1 is certain that Player 2’s beliefs are given by p2, and so on and so forth. I wish to draw your attention to two key conclusions that can be drawn based on this analysis. 1. The standard model of games with payoff uncertainty is capable of generating infinite hierarchies of interactive beliefs about the underlying state of the world. Indeed, this was precisely Harsanyi’s original objective: he realized that, in the presence of payoff uncertainty, the players’ strategic reasoning necessarily involves this sort of infinite regress, and devised a very clever way to generate this information in a compact, manageable way. 5
2. The standard definition of Bayesian Nash equilibrium is deceivingly simple it hides a whole infinite hierarchy of implicit assumptions about higher-order beliefs It is not my objective to argue whether or not these assumptions are reasonable. Rather I wish to emphasize that, just because they are not apparent in Definition 2(or in any textbook definition of Bayes Nash equilibrium, for that matter), one should not conclude that these assumptions are not necessary! On the other hand, one should not assume that these assumptions are the only ones consistent with Bayesian Nash equilibrium analysis. In fact, relaxing them leads to interesting modelling possibilities-as I shall illustrate in the next lecture
2. The standard definition of Bayesian Nash equilibrium is deceivingly simple: it hides a whole infinite hierarchy of implicit assumptions about higher-order beliefs. It is not my objective to argue whether or not these assumptions are reasonable. Rather, I wish to emphasize that, just because they are not apparent in Definition 2 (or in any textbook definition of Bayes Nash equilibrium, for that matter), one should not conclude that these assumptions are not necessary! On the other hand, one should not assume that these assumptions are the only ones consistent with Bayesian Nash equilibrium analysis. In fact, relaxing them leads to interesting modelling possibilities—as I shall illustrate in the next lecture. 6