Ba y esian-Nash gam es∗ Sergei Izmalko v 14.129 Advanced Contract Theory February 23, 2005 1 A general incom plete information setting 1.1 Primitive s A finite group of players (economic agents), denoted by N = {1,...,n}, interact. Any interaction can be represented as a simultaneous non-cooperative choice of individual plans of action.1 A set of possible decisions or choices (a set of all possible contingent plans of action) is a set of strategies.Denote Si to be a set of strategies available to player i (si ∈ Si is a generic element); s =(s1,...,sn)={si}i∈N is a profile of strategies of all the players, s ∈ S = ×i∈N Si; s−i = s r {si}, S−i = S \ Si, s =(si,s−i).A set of alternatives (allocations), A, is a set of all possible outcomes. A mechanism is a rule that for any collection of strategies selects a probability distribution over the set of alternatives A, M : S ∆(A).→Example 1: Voting.A set of alternatives A is a set of possible candidates to be chosen from. Players are individuals with a right to vote. Sets of strategies are determined b y a voting procedure. In a simple ballot voting, for example, each player submits a ballot for some candidate, so Si = A. In a multistage voting, like a procedure to select a city to hold Olympics, a strategy has to name a city in the first round of voting, a city in the second round of voting conditional on results of the first round, and so on, for each round conditional on previous results. A voting mechanism specifies how the winner is selected. For instance, in a simple majority voting, bar ties, M (s) = arg maxa∈A #i∈N {si = a}. Example 2: Auctions. A set of alternatives A is a set of all possible allocations of goods for sale and transfers involved. For example, with one object for sale and only the winner paying, a set of alternatives is A = N × R+,apair (w, m) ∈ A says that player w ∈ N is the winner and has to pay m.A set of strategies depends on an auction format. In sealed-bid auctions, a strategy is a bid, Si = R+. Inopenor dynamic auctions, like an English (a usual ascending price) auction, a strategy has to specify how to act (bid) for an y possible scenario that can occur in the auction. The winner is determined according to the rules of the specific format. In the first-price sealed-bid auction the winner is the highest bidder and has to pay own bid. Thus, bar ties, w =argmaxi∈N si and m = sw. In the second-price sealed-bid auction the winner is also the highest bidder but pays the highest bid among the rest of the participants, m =maxj=w sj .6Example 3: Public good provision (discrete setting). There is a public project that can be built if sufficient funds are collected from citizens (to cover a cost c ∈ R+). Thus, an allocation (b, m1,...mn) ∈ ∗To app ear as part of “Secure d irect implementation” by Sergei Izmalkov, M att Lepinsky, and S ilvio Micali. 1 Th is is called a nor mal or strategic form represe nta tio n . For a deta iled coverag e of game theor y and o f incomple te info r m a t io n games in particular the reader is referred to two excellent textbo oks on the subject, Fudenb erg and Tirole (1991) an d Osb o rne and Rubinstein (1997). 1{0, 1}×Rn specifies whether a project is built (b =1)ornot (b =0), and for each i atransfer mi.+ The strategies depend on the procedure that is used to decide on whether to build and on con tributions. For example, for the case of private voluntary contributions, each pla yer contributes ci = R+.The P ∈ Si corresponding mec hanism sets mi = ci, the project is built, b =1,onlyif i∈N mi ≥ c. To complete description of a game players’ preferences over alternatives have to be specified. In a complete information setting players preferences are commonly known. In an incomplete information setting some players are not certain about preferences of the others. In reality, essentially in an y interaction something is not known to all participants. How much money or other resources a player has? What are the costs of production? What does a player know (or think) about what others know? Often, the answers to these questions are only known to the player in focus. Following Harsanyi (1967-68), players’ uncertain ty is added as follows. A special player, Nature,moves first and selects a profile of types, t = {ti}i∈N , ti ∈ Ti, for each of the players according to some commonly known distribution p over T = ×i∈N Ti.A type is a complete description of all relevant characteristics of a given player. A player observes her type, beliefs about the types of the others, t−i = t r {ti},are calculated using conditional distribution p(t−i|ti).2 To complete specification, each players’ preferences over lotteries over T × A need to be defined. We will assume that these preferences satisfy expected utility axioms of von Neumann and Morgenstern, thus it will suffice to specify payoff functions, ui : T × A → R for each i. Altogether, a game of incomplete information, or Bayesian game, is described by a septuple, Γ =(N, {Ti}i∈N , {Si}i∈N ,A,M,{ui}i∈N ,p).3 Note that essentially an incomplete information game can be thought of as a very large game with complete but imperfect information. Players in that game are all possible player-type combinations, and, P given any selected profile of strategies, a payoff to player (i, ti) is t−i p(t−i|ti)ui(t, M (s)). Definition: A pure strategy of player i is a function si(ti) that for each ti ∈ Ti selects an element of Si.A mixed strategy of player i is a function σi(ti) that for each ti ∈ Ti selects a probability distribution over Si.We denote s(t)=(s1(t1),...sn(tn)),s−i(t−i)= s(t) r {si(ti)},mixed profiles σ(t) and σ−i(t−i) are defined similarly. Without an y confusion we can define ui(t, s)= ui(t, M(s)),apayoff toamixed σ(t) is ui(t, σ(t)) = Eσ1(t1),...,σn(tn)ui(t1,...tn,s1,...,sn). Definition: A selection of (mixed) strategies {σ∗ i (ti)}i∈N is: a Bayesian-Nash equilibrium of game Γ if, for each type ti of player i, for any σi(ti), Eu(ti,σi ∗(ti),t−i,σ∗−i)) ≥ E u(ti,σi(ti),t−i,σ∗−i)); (1)t−i −i(tt−i −i(ta dominant strategy equilibrium of game Γ if, for each type ti of player i, for any σi(ti) and any