### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Adv Microeconomic Theory II ECON 521

Yale

GPA 3.87

### View Full Document

## 11

## 0

## Popular in Course

## Popular in Economcs

This 49 page Class Notes was uploaded by Rowan Ferry III on Thursday October 29, 2015. The Class Notes belongs to ECON 521 at Yale University taught by Dirk Bergemann in Fall. Since its upload, it has received 11 views. For similar materials see /class/231027/econ-521-yale-university in Economcs at Yale University.

## Similar to ECON 521 at Yale

## Reviews for Adv Microeconomic Theory II

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/29/15

Advanced Mioroeoonomio Theory 521B Dirk Bergemann Jorge Balat April 30 2008 Abstract The following notes contain the main material of the second part of 521b 2008 1 Bayesian Games Information Knowledge Uncertainty There are two important contributions in the literature 1 Harsanyi 196768 Models without common knowledge are transformed into games of incomplete information and then into imperfect information games The idea is to introduce a notion of type which represents private information E0 Mertens and Zamir 1985 Type information is represented by an hierarchical construction77 11 Applied models Let 9139 denote agent is type and let uiz 91494 be the payoff relevant types We say 9139 is payoff relevant if 39 941 such that uiz 91494 ill19594 Agents have some common knowledge regarding the distribution of types 109 ie common prior Let pit9ilt9i be is belief about other agents7 types 111 Type space 9 primitives of the model payoff relevant states t 6 Ti agent is type Agent is private info m T gt A X T4 For the moment we will assume 9 nite and T11 countable A type space is a collection T Ti1 m1 1 1 2 Example Envelopes Two agents Alice and Bob Both receive a closed envelope It is common knowledge that the number of dollars in Alice s envelope is odd and the number of dollars in Bob s envelope is even and that both amounts are 1 apart ie they are adjacent numbers Before opening the envelopes the information can be represented as in Table l where the stars denote the possible states of the world Lecture Notes 5211 April 30 2008 2 Table 1 Bo Alice After each player opens its own envelope hence private information we can ask both of them Is A richer than B and except if B gets 0 neither know which one is richer Now lets make a public announcement No one has more than or equal to 1000 i After the announcement we ask repeatedly Are you sure you are richer than your opponent the answer is public and continue asking until a someone answers Yesi Can anything be learned Say A lt 999 then both answer No Thus B immediately learns that A lt 999 Having common knowledge on some event is important for the inference process even in envi ronments where there is no hope of learning In the previous example say A 3 and B 4 there will be no learning without any further information but after the announcement of the public event A B lt 1000 they end up learning which one is richer Let E be the event nobody has strictly more than 5771 This is represented in table 2 Table 2 Bo Alice How about the event everybody knows that nobody has strictly more than 5 This is shown in table 31 Lets now introduce probabilities Let p1 7 p be the probability that the smaller envelope contains n dollars This information is represented in Table 4 Now we ask Is A richer than B Alice s belief at state n is p1 7 p 1 1 1 PTAA1s r1cher than Bln plt17pnilp1ipn 27 gt 2 1 And Bob s belief is 1 7 p n 1 7 p 1 2 1 PT A1sr1cherthaan i B H plt17pgtn71plt17pgtn 27p 2 Lecture Notes 5211 April 30 2008 3 Table 3 Bo Alice Table 4 Bob 0 2 4 6 1 p 101 7 0 3 100710 101 703 Alice 5 201 7 m4 201 7 m5 Thus each one believes he or she is richer at each state Now x an n Ask the question they will answer Yes and No respectively Ask again They will converge to the same posterior this is Aumann s Agreeing to disagree77 113 Coordinated attack77 problem Two agents A B A has the resources to attack while B may or may not have the resources A and B want to attack if 1 agent i has the resources 2 agent j also attacks hence this is a coordination problem Communication protocol B can send messages to A but 0 B sends a message if he has the resources 0 the message may get lost Let n be the maximum number of messages that could have been sent The possible states are represented in table 5 Coordinated attack problem for the attack to occur we need both players to have the re sources and ii both to attack That is we need to nd nA n3 number of messages suf ciently large Lecture Notes 52H April 30 2008 4 Table 5 B s resources As resources Claim 1 Coordinated attack is impossible for all n Proof Suppose 3n njg such that Vn such that rm 2 n2n3 2 it they attack The requirement that both have the resources imply that njg gt 0 and the requirement that both attack requires n2 2 njg l and mg 2 n2 l which is a contradiction l Therefore there is no coordination when there is less than common knowledge 2 Games with Incomplete Information Jeffrey Ely Example Envelopes Two players are given envelopes with money inside and are asked if they want to exchange the envelopes There are two important questions Will they trade and How is the decision to trade related to the amount of money in the envelope There are two approaches to model these games 1 Type space a player has a type that summarizes all that he knows and the beliefs about other players7 types 2 States of the world Going back to the example list of things we need to specify in the model 0 To trade each player hast to ask himself what is the amount of money that both envelopes have So the belief of the amount of money in the other envelope is going to matter But this is not the only thing 0 The players also care about what the beliefs of the other players are That is the players also need to form a belief of what amount of money is on the other envelope conditional on that the other player is willing to trade Hence we will need to incorporate the belief of how much money is in the other players envelope and the belief of what the other player s belief is Let Q set of realizations of underlying uncertainty In our example 9 R X R Also let AQ be the rst order belief that is the set of all probability distributions over 9 the player will have one belief in that set Now let the 2nd order belief be A X that is the player has to form a belief about 9 and what the belief of player 7i is But this is not enough i3 Q X 53 Therefore are necessary elements of the model This is the language that we need Maybe it is not enough but it is necessary Lecture Notes 52H April 30 2008 5 Now the problem is evident we cannot even write down the model less we can analyze it The solution will be to model it in a different way such that still captures the relevant features Harsanyi Type Space We will introduce an auxiliary object set of types for i Ti and the belief mapping for i h T gt AQ X T note that Mi for any 3 Note that this is a simpler model and captures everything from the starting model We require M to be measurable and the conditional belief over 9 given ti and t4 M t4 6 AQ to be jointly measurable Claim 2 The type space and M fully describes the hierarchies of beliefs Proof Fix a type ti for i and a mapping M Then 532 margniti Since the marginal is measurable we have that the mapping T gt AQ is measurable Now we need to nd E AQ gtlt A9 Let E C Q X A9 be a measurable set then de ne 51392tiE Milttiw7tei 1 ma1a E F Now continue in the same fashion for the higher order beliefs I 21 Relationship Between the Type Space and Hierarchies 0f Beliefs Question Is there any restriction that our simple model puts into the type of we can model There are four valid answers 1 I can model everything Mertens Zamir 2 I can model even more than that Rationalizability Type space is a richer language 3 I can model essentially nothing 4 I can model only nonrobust assumptions Answer 1 Mertens Zamir There exists a single universal type space such that for all hierarchies of beliefs Main idea Suppose we take an hierarchy how can we be assured that there exists a type space that describes it Lets pick an hierarchy i i17i27 6 Uim Reinterpret it as a probability measure over 9 ie AQ gtlt UiQ and denote it a Thus taking marginals of this probability measure we can get a l the Note that we need to require 9 to be a complete separable metric space Coherence any hierarchy captured by the probability measure AQ gtlt UiQ has to be coherent for example the marginal of each with respect to Q has to be the same Brandenburger and Dekel 1993 ldea use the Kolmogorov extension Now take UiQi and this will be our type space l Every hierarchy has a representative in the type space universal type space When we write down a type space ie a subset of the universal type space we are implic itly making assumptions of what hierarchies we can represent hence making restrictions in the hierarchies Counterexample Heifetz and Samet 1888 Lecture Notes 52lb April 30 2008 6 Answer 2 Rationalizability Say we have a game with two players and let Ai be the set of actions of player i1 De ne A A1 gtlt A21 The type relevant payoffs which summarize everything what matters to make a decision are given by ui A X 9 A R1 Denote a behavioral strategy by a T gt A1413 A solution concept is a mapping from the description of the game into strategies or sets of A strategy a for i is a best reply to 0 if for every ti o E argarzneaii EM1tluZai aitiw Once we have a de nition of best reply we then have a notion of rationalizabilityi For example throw away everything that is not a best reply in the rst round 1 1 1 If T and Ai are nite then we will eventually stop eliminatingi Note that the best reply de nition given above is an ex ante de nitioni Another de nition of best reply is the following a is an interim best reply to a strategy 0 for a given type ti if at E argyle Eo1zuialy040570701 Note that in this de nition we are xing ti and choosing 041 Also note that al is an interim best reply if for each t there is a 0 against which aiti is an interim best reply We say that a pro le of strategies 6 6162 has the best reply property if for each i for each a 6 e the strategy a is an interim best reply given 67139 and it has the xedpoint property if there is no 01 61 with this feature Correlated rationalizability Consider 2players gamesi Replace the de nition 0 T7 gt AA with 071211 X 9 A AA that is player i may think that the type of 7i could be correlated with the state of nature Example 2 types 2 players 2 states of nature with probabilities given by 12 t 12 t n n ta n LA It is common knowledge that each player assigns equal probability to the states of nature given their type Now suppose the game they play is b a2 2 62 a2 b2 62 a1 1 11 1 7107101 71001 a1 1 7107101 11 1 71001 b1 1 7107101 11 1 7100 1 a1 1 11 1 710710 1 7100 1 511 0710 1 0710 1 00 1 a11 0710 1 0710 1 00 1 w of Note that all a b and e are rationalizable because they are all part of a Bayesian Nash Equilib riumi But there is a much simpler type space representation with only one type and probabilities given by Lecture Notes 52H April 30 2008 7 t3 t t n w 0 With this type space representation they play c7 c Hence the two representations give different results ie7 they imply different behavior predictions in the game even though they represent the same hierarchy of beliefs l The point is that the same beliefs can be represented by different type spaces which in turn give different predictions about behavior Thus we need a much richer language to distinguish the two Aihierarchies Ely and Peski 2006 Aihierarchies are necessary and sufficient to predict behavior for rationalizability in all 2player games If two type spaces have the same Aihierarchy then they will have the same rationalizable strategies in all games the players are presented with Answer 4 There exist hierarchies that are similar but give us different predictions We call them critical types Universal type space IiA9 endowed with a product topology lt has a partial order7 and this order is nontrivial in Mertens Zamir is trivial Common p belief F C UAQ C17 F C UAQ where CpF is the subset of common p belief of the universal type space that attaches p belief to the set F Theorem 1 Ah hierarchy ui E UiAQ is a critical type i there is a closed uppercontour proper subset W C UAQ such that ui E CpW for some p gt 0 The idea is that common p belief is important for behavior De nition ui is a critical type if there is a game C an action ai such that ai is rationalizable for ui but for some sequence of A ui and for some 6 gt 07 ai is not e rationalizable for any of All type spaces modeled in the literature are fragile Answer 3 The idea is that the measure of hierarchies that we can model with critical types is really small 3 Robust Mechanism Design Bergemann and Morris 2005 31 Introduction Theoretical and practical success of Auction7 Mechanism Design and lmplementation literature Mechanisms seem too complicated to use in practise Successful applications of theory include ad hoc restrictions Simplicity7 nonparametric7 detail free7 ex post equilibrium7 Wilson doctrine 32 The Wilson Doctrine Game theory has a great advantage in explicitly analyzing the consequences of trading rules that presumably are really common knowledge it is de cient to the extent that it assumes other features to be common knowledge7 such as one agentls probability assessment about anotherls preferences or information I foresee the progress of game theory as depending on successive reductions in the base of common knowledge required to conduct useful analyses of practical problems Only by repeated weakening of common knowledge assumptions will the theory approximate reality77 Wilson 1987 Lecture Notes 52H April 30 2008 8 33 Weakening Common Knowledge ln game theory Harsanyi 196768 Mertens and Zamir 1985 established that relaxing common knowledge assumptions is equivalent to adding types Environments with incomplete information can be modeled as a Bayesian game where wlog there is common knowledge among players of each player s type spaces and each type s beliefs over types of other players onomic analysis assumes smaller type spaces than universal type space yet maintains common knowledge Are the implicit common knowledge assumptions that come from working with small type spaces problematic Especially in mechanism design 7 on surplus extraction Especially in auctions i no strategic uncertainty among bidders ii designer and bidder i have identical information about all other bidders 34 Bergemann and Morris7 Approach lntroduce rich higher order belief types into mechanism design literature Fix payoff types and social choice correspondence objective of designer is to implement social choice correspondence For xed environment we can construct many type spaces where a player s type speci es i his payoff type and ii his belief type Crucially there may be many types of a player with the same payoff type 35 Comparative Statics Study role of common knowledge assumptions by comparative statics on the type space going from naive type space to universal type space The larger the type space is the more incentive constraints there are the harder it becomes to implement scc ore robust the resulting mechanism will be Smallest type space naive type space possible types equal to payoff types Standard con struction in mechanism design Largest type space universal type space allow any higher order beliefs about other players7 payoff relevant type 36 Ex Post Equivalence This paper focusses on ex post equivalence Question When is Bayesian equilibrium par tial implementation on the universal type space equivalent to ex post implementation Answer sometimes yes sometimes no ln private values case ex post implementation is equivalent to dominant strategies implemen tation Thus we answer the question when is Bayesian implementation equivalent to dominant strategies implementation 37 Payoff Environment 0 Agent 239 GI 12I o is payoff type 9139 E 1 o payoff type pro le 9 E 9 91 X X 91 0 social outcome a E A Lecture Notes 52H April 30 2008 0 utility function ui A X G A R 0 social choice correspondence F G A 2A g 0 social choice function f G H Al Examples ef cient allocation7 ef cient allocation With budget balancei 38 Type Spaces Richer type spaces than set of payoff types 9 o is type is ti 6 Tl ti includes description of 7 payoff type Tl gt Gil is is payoff type of til 7 beliefs about types of other players i Tl gt A T4 i is is belief type of til 0 type space is a collection T 11 Example Small Type Space Ti 17 h 6Z7 9h Payoff type 9139 Tl gt 9139 here identity mapping a l H 9 51 h H 9h Belief type given by common prior 7r t l h l l l i i h a E Here i E A t4 Her belief type identi es payoff typei Example Large Type Space Ti 1 lh7 h7 1 197 6h Payoff type Tl gt 9139 2 Hal Maw a hawk Lecture Notes 5211 April 30 2008 Belief type given by common prior 7r t 1 Hz h l 2 a 1 X 1 Hz a 2a2 2a 66a2a2 h 1 2a 2 For a 0 large type space small type spacer Foragt01 A 2 a 1 ma 7 lta37a37a3gt ye 1 2a 2 A lh A h 7 7 m M lt2a3 2a3 2a3gt Here belief type does not identify payoff typei 381 Properties of Type Spaces 0 Type Space T is naive if Tl 1 and each is the identity map 0 Type Space T is nite if each T1 is nite 0 Finite Type Space T has full support if i t4 gt 0 for all i and ti 0 Finite Type Space T satis es the common prior assumption if there exists 7r 6 A T such that ZN ti7t7i gt 0 for all i and ti LI A 7 7r 7513754 m ti Li 7 gt 0 382 Richer Type Spaces 0 A Fixed Full Support Naive Common Prior Type Space 0 All Full Support Naive Common Prior Type Spaces 0 All Naive Common Prior Type Spaces 0 All Common Prior Type Spaces 0 All Type Spaces modulo some technical details7 union of all type spaces is identical to universal type space constructed a la Mertens Zamir from payoff types 1 i Lecture Notes 52H April 30 2008 II 39 Interim Implementation Can we nd a mechanism such that one equilibrium delivers outcomes consistent With F We appeal to the revelation principle and restrict attention to direct mechanisms Where player i reports his type ti 6 Ti H De nition 1 A social choice function f 6 AT is interim incentive compatible on type space T if ui f 7513754 7505137570 d i 2 f 7527754 750513754 d i t 72 for all i te T and t 6 Ti De nition 2 Social choice function f 6 AT on T is a selection from F f t e F 9 for all t E T Set of permissible allocations is conditioned on Selection of f can be conditioned on t De nition 3 A social choice correspondence F is interim implementable on T there exists f 6 AT such that f is interim incentive compatible on T and f is a selection from F 310 Ex Post Implementation De nition 4 A social choice function f E A9 is ex post incentive compatible if for alli andt E G M f 9 79 2 W 16092797079 for all 9 E 9139 Compare A scf is dominant strategy incentive compatible if for all i and all 949 ui f gag7139 79 2 ui f 92794 719 De nition 5 A social choice correspondence F is ex post implementable if there exists f E A9 such that f is ex post incentive compatible and f 9 E F 9 for all 9 E 9 311 Ex Post Equivalence EX post equivalence77 holds for a given environment if SCC F is ex post implementable if and only if it is interim implementable on the union of all type spacesi Ex post equivalence holds if 0 the SCC is a function Lecture Notes 52lb April 30 2008 12 o if SCC represents ef cient outcomes in quasilinear environment Without budget balance Ex post equivalence fails in general If SCC represents ef cient outcomes in quasilinear environment With budget balance7 then ex post equivalence holds i 0 9i 1 for some i 0 i S 2 for all i o I S 2 Ex post equivalence fails in an example With I 37 91 3 and 92 93 2 312 Example 1 Easy to interim implement on any type spacer Impossible to ex post implementi 91 9179 1LG2 92792 A 17576 o Payoffs a 92 9 2 b 92 9 c 92 9 2 91 l 10 l 712 91 l 712 l 10 91 00 00l 9 1 00 00l 9 1 00 00l 9 1 11 11l 0 Social Choice Correspondence F 92 9g 91 ab ab 9 1 313 Example 2 Allowing Lotteries Easy to interim implement on any type spacer Impossible to ex post implementi 0 91 91791799 0 92 927 92 o A A a7 b7 e7 o Payoffs Lecture Notes 5211 April 30 2008 13 Consider the following randomized mechanism 92 9 91 1 1071 on 717 l 10 71710 on 717 l 1 l c l c 9 1 l d l d l For 91 to tell the truth if he is sure that 92 1 2 717 gt7 gt7 p 03 gtp3 For 91 to tell the truth if he is sure that 9 1 1 7 17gt7 lt7 p in3 gt 103 But for 92 to tell the truth if he is sure that 91 217p2217p 42gt pZpi Thus 10 2 10A 0 this example has interdependent values and F independent of 92 we can dispense With both these assumptions easilyw 314 Example 3 scc is not ex post implementable interim implementable on ANY naive type space not interim implementable on some larger type spaces 0 I 2 9 919191 9 OLOE o A 7173031 X 7 0 Preferences over location ui a6i6j uj a 91491 191397 9139ai 0 Utility from having own name 0 Planner maximizes sum of utility minus a2 315 General Environments Proposition 1 If F is ex post implementable then F is interim implementable on any type space Proposition 2 If F is single valued then F is ex post implementable if and only F is interim implementable on every Proposition 3 F is ex post implementable if and only ifF is interim implementable on every T using WITH loss of generality mechanisms where players ONLY report their payo type cifi Ledyard 1978 and Dasgupta Hammond and Maskin 1979 Lecture Notes 52H April 30 2008 14 316 Augmented EX Post Incentive Compatibility 0 strengthen equilibrium conditions to obtain general equivalence 0 each agent i reports 9139 and mi 6 Mi De nition 6 A social choice rule f 6 AM is augmented ex post incentive compatible given M if for all i 91 E 1 and M E A M4 there exists mi 6 Mi such that 9imi is a maximizer of AZ w mo at f lt6 64gt mama elm De nition 7 A social choice 1 7 F is i quotm m J ex post 39 l 39 t L39 there exists M and f 6 AM such that f is augmented ex post incentive compatible and f 97m 6 F 9 for all 9721 6 M Proposition 4 Social Choice Correspondence F is augmented ex post implementable if and only F is interim implementable on every T 317 QuasiLinear Environment 0 A Z X R 0 ui 279 719 vi 2791L yz39 1769 Zyy 6 A12 59 0 viZXGHRforeachiandEIGHZi Lemma 1 If F6 is interim implementable on every full support common prior naive type space T then F6 is ex post implementa e Proposition 5 The following are equivalent 1 F6 is interim implementable on all type spaces 2 F6 is interim implementable on all common prior type spaces 5 F6 is interim implementable on all common prior naive type spaces 4 F6 is interim implementable on all common prior full support naive type spaces 5 F6 is ex post equilibrium implementable in the naive type space 3171 Interim Implementability for QuasiLinear Environments Key properties of type spaces De nition 8 T satis es onetoone property 1 75 a ti ti tih De nition 9 TAsatis es product property if for all 9139 and m in the range of i Hti 6 T1 st i rri and 91 91 Lecture Notes 5211 April 30 2008 3172 Large Payoff Beliefs o is beliefs about other agents7 payoff types 111139 E A 911 0 type depedent payoff beliefs7 let A 1L i HZ gt A i 1 m 67 Z a ti Li z z9 be de ned by 3173 Interim Payoffs 0 player is expected utility of outcome 567 911 z 5i givgi Ji Z 111139 970 794 7 91794 976972 o is beliefs over opponent7s payoff type 0 i has payoff type 9139 o i reports payoff type 9 3174 Large Interim Implementability Theorem 2 5 is interim implementable Vi 3 Z A R sth V 913m 67 E Zi vi 9139791712139 7 9 WM 2 vi 91792712139 0 y 927M 0 holds if type space satis es oneto one property 0 if oneto one property fails7 reduces to conditions With independent types in naive type space 0 if enough beliefs over payoff types of opponent are consistent With a given belief type reduces to ex post implementability conditions 318 QuasiLinear Environment With Budget Balance 0 A Z X RI 0 ui 279 7 9 vi 279 M I Fae m eAzz5lt6gt and m 0 i1 oviIZXGHRforeachiandEIGHZ Lecture Notes 52H April 30 2008 16 3181 Ex Post Implementability o gains from misrepresentation Oi 96i E vi 5 94 9 7 vi 5 91494 19 0 transfer functions y y1y17 each yi 9 A R 0 ex post incentive compatibility 913909139797139 9139 19 97139 2 Ci 9139 97139 for all i 91 t9 and 94 0 budget balance I Z 9139 19139 97139 0 i1 for all 9 E 9 3182 Linear Programming Ex post implementation as linear programming problem I max 2 2a lt9 y 6 3quot i1 gee subject to M 19139 97139 M 19 97139 2 Ci 19139 19 97139 7 i 19139 19 97139 subject to I 29239 623 67239 07 V 9 i1 With associated multipliers A149 X 71 gt R45 and 1 9 A R 3183 Dual Approach 0 ldea of argument 7 proof by contrapositive 7 not ex post implementable implies not interim implementable 0 Theorem of alternative farkas lemma for dual characterization o Recover ex post constraints in interim constraints through rich type space Dual Characterization of Ex Post Implementability Lecture Notes 5211 April 30 2008 17 o multipliers 1 and A satisfy the ow condition if v 9 Zn Oi6 91 7 2A1 em6 9 9 o mulitpliers A satisfy the weighting condition if I Z Z ZAZ 61 6 671 lt1 61 6 64 gt 0 i1 see 9 Lemma 2 SCC F6 is ex post implementable if and only there exists 1A satisfying F and W Dual Characterization of Interim Implementability 0 transfer functions y y1yN7 each yi T A R o interim incentive compatibility Za tii Li a two 7 yz tamH 2 2amp ti Li lt1 62 2751 tgt 611 m vim LI 0 budget balance I 2 1754 07 W i1 o multipliers 17 T A R and X X1 X1gt each Xi T A R o satisfy the ow condition if 179 Z i til Li Xi toil Z i til Li xi 2 z z 0 satis es the weighting condition if I Z Z 2amp ti to AZ ltti 2 lt1 a m ltt2gt 1 ltLigt gt 0 i1 LET z Lemma 3 SCC F6 is interim implementable if and only there exists lt17 satisfying F and W 319 Results Proposition 6 If N 2 Fg is ex post implementable and only Fg is interim implementable on all common prior type spaces Example 3 showed that Fg may fail to be interim implementable on all common prior type spaces7 even when it is interim implementable on all common prior naive type spaces Lecture Notes 5211 April 30 2008 18 Proposition 7 If Gi g 2 the following are equivalent 1 F6 is inteiim implementable on all type spaces 2 F6 is inteiim implementable on all common piior type spaces 5 F6 is interim implementable on all common piior naive type spaces 4 F6 is inteiim implementable on all common piior full support naive type spaces 5 F6 is ex post equilibrium implementable in the naive type space An example with N 3 and i 2 3 for some shows that Fg may be interim implementable on all type spaces7 even when it is not ex post implementablei 320 Future Questions 0 Full Implementation 0 Revenue Maximization 0 Single Crossing Conditions in Rich Type Spaces 4 Dynamic Allocation Problems Dynamic allocation problems are also known as multiarmed bandit problems This terminology comes from Las Vegas Onearmed bandits are machines where you pull an arm causing a dial with possible outcomes to spin7 and where after the dial stops spinning you only see one outcome but do not see the other possible outcomes in the dial Hence7 there is uncertainty about the dial iiei7 the distribution of returns Now suppose we face many such dials hence7 the term multi armed With many bandits the problem is to identify the highest expected return banditi You can sample the banditsi To make it an economically interesting problem7 you can sample one bandit at a time and you discount the future Basically7 this is a sequence of stopping problems but not terminal stopping problems because you can go back to a previous bandit This literature started in the 7SOs760s for testing drugs and later to determine for how long to try a new techno ogyi 41 Deterministic Problem Say we have N alternatives denoted by i 17 i i i N7 with returns 11 6 Fur where ti is the count of times or periods of usage of alternative ii Note that the return depends on how many times we have used the alternative7 but it is inde pendent of the usage of alternative j Vj i It could be the case that ti 1 lt ziti that is7 the alternative experiences depreciation or it could be that ti 1 gt ziti for example from learningbydoingi Also note that in this problem the mapping zl N A R is known and deterministici Let t 01 M denote time7 then ti ti Also let 0 lt 6 lt 1 be the discount factor Our problem is to allocate the alternatives across time In fact7 this is a classical scheduling problem we can use one alternative at a time and we need to nd the optimal order of tasks Now lets denote a policy by tquot ti7 i i i 7tjv7 where t z N A N is the counter of alternative i7 with t t 1 E tt t 17 that is7 the counter ofi can stay the same or increase by 1 We also require the policy to satisfy t t t Vti Lecture Notes 52H April 30 2008 We can now state the problem as 00 N max 2 6 Zzitittit 1 7 tit 3 ROME 10 i1 subject to t t1 t tvt t1 4 N 2t t t Vt 5 Note that a suf cient condition for the problem to be well de ned is Vi 0 VIZt lt co We are going to solve this problem using dynamic programming Rewrite the problem as V Vt1mtN Zzititit1itit6Vt1t1iHtNt1 6 max tzt1fvi subject to 4 and7 N Etit1t1 7 i1 Suppose for a moment that zit1 1 lt Vi tit The optimal solution will be to pick 2quot such that 239quot argmaxizllti at t17 i i i tNi Hence7 the solution is myopici Now suppose that Ozi eiti with 0113976139 6 Bar all i We are going to suggest a solution criterion based on the individual stopping timei De ne for alternative 239 the average payoff if previous usage of i is 3139 Eli VIN Si M31 7 Ingx Ego 6t 8 where Ti is the stopping time We also call vi the index of alternative ii The optimal index policy is to choose at each state 8 81 i i i 7 SN alternative 239 with the highest index vi Note that we now have N 1dimensional optimization problems l A simple proof is the following Say the use of alternatives prescribed under the optimal policy z j z 39 PHz A time 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 i payoffs 121 122 123 124 11 5 125 127 123 129 1110 1111 lts v10 with 74 ltgt v15 with 73 ltgt v1 8 with 754 Note that for each chunk we can replace the payoffs with the average or index It is easy to see that the average for each successive chuck of alternative 239 should be decreasing over time otherwise we can stick them together in a bigger chunk7 iiei7 stop later Now since the averages are decreasing we are back to the myopic rule but replacing payoffs with averagesi Going back to dynamic programming Say we now have to choose between alternative 239 and a constant retirement option mi The problem is now Vitim maxzitimti1m 9 Lecture Notes 5211 April 30 2008 The question is now how to choose the largest m such that m gt zt6Vt1m16 5 Dynamic Marginal Contribution Mechanism Bergemann and Valim39aki 2007 51 Introduction Intertemporal Efficiency with Private Information The idea is to extend VCG to dynamic environ ments in which the auctions andor information change over time Motivation 0 random arrival of buyers sellers andor objects 7 selling seats for an airplane with random arrival of buyers 7 bidding on ebay 7 bidding for construction projects with uncertain arrival of new projects 0 bidding for links in sponsored search Google Yahoo etc 7 uncertainty about clickthrough probability 7 uncertainty about conversion probability 0 leasing resource over time 7 auction of renewable license right capacity over time 7 web serving computational resource bandwidth CPU 511 Benchmark Static Ef ciency with Private Information In private value environment 0 Vickrey 1961 single or multiple unit discriminatory auctions implement socially efficient allocation 7 in private value environments 7 in weakly dominant strategies 0 Clarke 1971 and Groves 1973 extend to general allocation problems in private value envi ronments 7 agent i internalizes the social objective and is led to report her type truthfully Pivot Mechanism 0 Green and Laffont 1977 analyze speci c VCG mechanism 0 i internalizes social objective ifi pays her externality cost 0 externality cost of i Lecture Notes 52H April 30 2008 21 utility of i when i is absent utility of i when i is present 0 marginal contribution ofi utility ofi externality cost ofi o in Pivot mechanism 1 payoff ofi is her marginal contribution to social value 2 participation constraint holds ex post and no budget de cit 512 Dynamic Marginal Contribution Mechanism 0 payoff in Pivot mechanism marginal contribution 0 develop marginal contribution mechanism in intertemporal environments with new arrival of information regarding 7 preferences 7 agents 7 allocations 0 design sequence of payments so that each agent receives ow marginal contribution in every period 0 solve intertemporal problem as a completely contigent plan 0 embed intertemporal problem in a static problem as in an Arrow Debreu economy o and then appeal to the classic VCG results BUT the contingent view fails to account for strategic possibilities of the agents in the sequen tial model 513 Sequential Incentive and Participation Constraints 0 information arrives over time 0 report of agent i in period t responds to private information of agent i but may also respond to past reports of other agents possibly inferred from allocative decisions truthtelling generally fails to be a weakly dominant strategy with forward looking agents7 participation constraint is required to be satis ed at every point in time and not only in the initial period 514 Results 0 marginal contribution mechanism is dynamically efficient o periodic ex post with respect to information available at period t 0 satis es periodic ex post incentive constraints 0 satis es periodic ex post participation constraints 0 adding efficient exit condition weak online condition if agent i does not impact future deci sions7 then agent i does not receive future payments7 uniquely identi es marginal contribution mechanism Lecture Notes 52lb April 30 2008 22 52 Literature 0 Dolan 1978 priority queuing o Parkes et al 2003 delayed VCG Without participation or budget balance constraints 0 Bergemann and Valimaki 2006 complete information repeated allocation of single object over time rst price bidding o Athey and Segal 2007 balanced budget rather than participation constraints 53 Scheduling o scheduling tasks 0 discrete time in nite horizon t 0 l 0 common discount factor 6 o nite number of agents 239 E 0 l I 0 each agent i has a single task 0 value of task for i is vi gt 0 o quasilinear utility vi 7 pi 0 values are given Wlog in descending order v0gtv1gtgtv1gt0 o marginal contribution of task i difference in welfare With 239 and without 239 o ef cient task assignment policy policy without 239 0 l i 7 l il i2 l policy With 239 0 l i 7 l i il i2 l T Marginal Contribution 0 insert valuable task i o raise the value of all future tasks t gt i o marginal contribution Mi 1 l 39 1 I M 26w 7 Etltthr Zla vtgt ti 10 10 I Mi 26 v 7 vt12 0 til Lecture Notes 52H April 30 2008 23 Externality o from marginal contribution to externality pricing Mi vi Pi o externality cost of task i is I gt0 tii Pi Ui1 Z 6 U Uz1gt ti1 o task 239 directly replaces task i 17 but also 0 task i raises the value of all future tasks Incomplete Information 0 vi is private information to agent i at t 0 o incentive compatibility and efficient sorting when would i like to win against j versus j l I I Vi v1 2517071 U Wu 2 5 Vi vj1 Z 517139 v Uta tj 7 1 0 reduces to cost of delay 176 2 17611139 0 report thruthful if others report truthful ex post equilibrium Bidding vs Direct Revelation Mechanism 0 an ascending English auction in every period 0 winning bidder i pays bid of second highest bidder 0 bid by agent i in period t b 0 bid should re ect value of task but 0 value of task today versus value of task tomorrow 0 value utility option value 0 bidding strategy 12 determined recursively in i and t 0 option value is value of realizing task tomorrow 6 vi 7 p2 and the price tomorrow is n1 A n1 pi 7 bj Lecture Notes 52H April 30 2008 24 0 net value of realizing task today is 7 6 vi 7 20 Dynamic Bidding o bidding strategy of agent i is given bi vi 6 vi Pi1l1 515 Shiii o ascending auction gives efficient assignment in all periods 0 Bergemann and Valimaki 2006 dynamic price competition complete information first price bidding o Edelman Ostrovsky and Schwartz 2007 static price competition incomplete information second price bidding 54 Information Arrival Licensing o sequential allocation of a single indivisible object With initially uncertain value to the bidders o bidder 239 receives additional information only in periods in Which i is assigned the object 0 license to use facility or to explore resource for a limited time Examples 0 renting store space in mall 7 current Winner lessee gets traf c data purchase behavior 7 current looser does not get traf c data purchase behavior 0 bidding for keywords 7 current Winner gets information about clickthrough rate sales conversion rate 7 current looser doesnlt get information about clickthrough rate sales conversion rate Single Unit Auction 0 single unit auction repeated over time o discrete time in nite horizon t 0 l o nite number of bidders i6 1 M I o realized value of object for Winning bidder in period t is Um wz 5m 0 51 is iiiidi over time With E an 0 0 M is true value of object 0 51 is random noise Lecture Notes 5211 April 30 2008 Information Flow 0 at t 0 common prior distribution Fi for each agent i 0 at t 2 0 Winning bidder receives informative signal Sit1l 3it1 Um wz 5m o realized value in period t constitutes private information for period t l 0 at t 2 0 loosing bidders don t receive additional information 3it1 313 Histories 0 private history of bidder i s 3130 7 3m 0 superscript for vector of histories7 subscript t for periodic event 0 expected value for bidder 239 in perid t vi lE mi 541 Dynamic Direct Mechanism 0 bidder i is asked to report her signal in every period t 0 initial reports 7 0 7 107 0 o inductively7 a history of reports 7 T171 7 17 gt 6 Rt 0 allocation rule It Rquot1 X Rt 4011 0 transfer or pricing rule is given by pt Rquot1 X RE a R1 Strategies 0 reporting strategy for agent 239 Ti R171 X 51 gt Si 0 expected payoff for bidder i E 26 11quot 7 vi 7 pi TEN Lecture Notes 52H April 30 2008 26 o reporting strategy ofi solves sequential optimization problem V432 it l 31129 E In 0 vi 8 Par 0 5 Silly W m I 0 taking expectation lE Wrt 3 7 Equilibrium 0 denote by 301 3 Si 0 Bayesian incentive compatible if Tm Si solves 113 Tan 803 vi Pm Tim 814131 lli Tim 3itgt o periodic ex post With respect to all the information available at period t o periodic ex post incentive compatible if Ti 3i solves 113 Tim 803 vi i 101 Sandal1 5W Tit73itgt for all 371 6 571 Social Ef ciency 0 socially ef cient assignment policy 00 N W cu max E Z Z tiuzm 3 vi REASON tu i1 o optimal assignment is a multifarmed bandit problem 0 optimal policy is an index policy 7 61 n2 7i3maxEEzo 1 SI 20 5 o socially ef cient allocation policy x 0 zit gt 0 if 71 2 7139 for all j Marginal Contribution 0 value of social program after removing bidder i W71 ltsugt 1133ng E 2 EM lt8 v1 lt82 tu jgi o marginal contribution Mi 3 of bidder i at history 3 is Lecture Notes 52H April 30 2008 27 0 value M conditional on history 8 and allocation zu M su mu 0 flow marginal contribution mi 3 Mi 8 7 ml lts gt 7 ml 82 1 Flow Marginal Contribution 0 ow marginal contribution o expanding ow term With respect to time M starting at t M starting at t1 and x m lt8 7 W lt8 7 W71 e 7 6 W M 7 W71 mm o expanding ow term With respect to identity rearranging current va1ue with a current Value without i but x m 3 7 W lt8 7 W mm 7 W71 M 7 6W4 mm Ef cient Assignment mi 8 7 W 8 7 SW 8310 7 W4 8 7 SW748310 0 consider ef cient assignment I 239 0 information about I 239 is worthless without 239 W4 321 W4 3 leads to m 8 7 vi 8 7 1 7 6 W4 8 0 consider inef cient bidder I f j leads to Dynamic Second Price Auction 0 match net payoff to ow marginal contribution o for Winner 239 o for losers7 j y 239 Result Lecture Notes 5211 April 30 2008 28 Theorem 3 Dynamic Second Price Auction The socially e cient allocation rule x satis es ex post incentive and participation constraints with payment pquot g 7 i V St 17 6 Wd 3 if I 1 p 0 if 0i 0 price equals intertemporal opportunity cost 0 delay 1 7 6 of the optimal program for all but j 55 Dominant versus Ex Post Incentive Compatibility 0 With private values7 static mechanism satis es incentive compatibility in weakly dominant strategies 0 in dynamic mechanism7 dominant incentive compatibility fails to hold in private value envi ronment o truthtelling after all histories fails to be a weakly dominant strategy as it removes the ability to respond to past announcements 0 yet ex post incentive compatibility can be satis ed in dynamic mechanism 56 General Allocation Problems 0 description of a dynamic VickreyClarke Groves mechanism 0 general speci cation of utility of each agent and arrival of private information over time 0 dynamic VCG mechanism is time consistent 7 social choice function can be implemented by a sequential mechanism Without ex ante commitment by the designer 7 thruthtelling strategy in the dynamic setting forms an expost equilibrium rather than an equilibrium in weakly dominant strategies 0 extend single unit auction to general allocation model 0 net expected ow utility of agent i in period t vi 175 Pm private signal of agent i in period t 1 is generated by conditional distribution function 3it1 N Gil1t73gl generalize information ow by allowing signal snarl of agent i in period t 1 to depend on current decision It and entire past history of private signals ofi Dynamic VCG Mechanism 0 efficiency 0 marginal contribution pricing Lecture Notes 52H April 30 2008 29 Theorem 4 Dynamic VCG Mechanism The socially e cient allocation rule satis es ex post incentive and ex post participation constraint with payment pquot pit 1 3 781 vi 1 st 73 7 mi 3 o characterization of transfer prices via marginal contribution o in speci c environments additional insights from observing how social policies are affected by removal of agent i Ef cient Exit 0 many transfer rules support ex post incentive and ex post participation constraints in dynamic setting 0 temporal separation between allocative in uence and monetary payments may be undesirable for may reasons 7 agent i could be tempted to leave the mechanisms and break her commitment after she ceases to have a pivotal role but before her payments come due 7 if arrival and departure of agents is random7 then an agent could falsely claim to depart to avoid future payments 0 in intertemporai environment if agent i ceases to in uence current or future allocative decisions in period t7 then she also ceases to have monetary obligations 0 presence ofi is not pivotal for the future at 739 and 87 if I 8 Iii1 8 for all t 2 739 and for all s 37374r17iii781 De nition 10 Ef cient Exit A mechanism satis es the e cient ezit condition if for all i 739 7 pi st 07 for all t 2 7quot Uniqueness 0 weak online requirement decisions regarding agent i have to be made in the presence of agent i Theorem 5 Uniqueness If a dynamic direct mechanism is e cient satis es ex post incentive and participation constraints and the e cient exit condition then it is the dynamic marginal con tribution mechanism 57 Conclusion 0 direct dynamic mechanism in private value environments With transferable utility 0 design of monetary transfers relies on notions of marginal contribution and ow marginal contribution 0 transfer the insights of VCG mechanism from static to dynamic settings 0 many interesting questions are left open 7 current contribution is silent on issue of revenue maximizing mechanisms 1 i 1 1 n i 7 cliaiacteii atiou of 39 in dynamic setting Will rst be necessary 7 restriction to private value environments Lecture Notes 5211 April 30 2008 30 6 Dynamic Mechanism Design 0 t 011 Ti H iiei nite or in nite time horizon o 0 lt 6 S 1 discount factor 0 91 willingness to pay of player i at time t i 1111 Note that the type ofi is evolving over time 0 evolution of type Plt6it1l 9it i P9iz1 ie we have some persistence Special case fully persistent type 913144 91 o dynamics come from 7 evolution of types 7 evolution of beliefs posteriors 61 Coase Conjecture mechanisms Without commitment Coase formulated in 1937 his conjecture about durable goods We will follow Gul Sonnenschein and Wilson 1986 We have one 1 informed buyer with 9 N Ft9 and one uninformed selleri In nite horizon t 011 1 H Let pt be the price of the single object at time t In the static problem myb FP which is the monopolist problemi Now if the monopolist sets p0 and the buyer does not buy in the next period the seller will want to lower the pr1ce my 7 F1p where F1 is the truncated priori Note that the monopolist faces competition iiei himself tomorrowi Without commitment the selling policy tomorrow competes with the selling policy today In this context Coase conjecture is that as 6 A 1 7r 6 1 1 Extensions Hart and Tirole 1988 and Schmidt 1990 look at the Coase conjecture with rentals rather than sales but the problem does not go away Feinberg and Skrypacz 2005 Coase conjecture relies heavily on the informed party to fully predict the future behavior of the seller What if there is some uncertainty in higher order beliefs Skreta and H generalization to multiagent allocation problemsi 62 Mechanisms With Commitment What if now there is commitment from the principals point of view Lecture Notes 5211 April 30 2008 31 621 Baron and Besanko 1984 Now the seller can commit to an entire price path Result cannot do better than the static price at all t 622 Freixas7 Guesnerie and Tirole 19857 Bullow and Stockey 1984 These authors introduced the term rachet effect77 a rachet is a dial that allows movement in only one direction Regulation model a rm produces q with cost Cq t97 where 9 is the rm s private information The rm is a natural monopolist and is supervised by a regulator We have two periods t 07 1 Note that any information revealed at t 0 will be used against the rm at t 17 hence this is an incentive to overstate costs in the rst period Thus7 there will be some information rent 63 Sequential Screening Courty and Li 2000 Two periods t 01 Two types of consumers which need to make a single transaction Say both have to make a trip in the future7 and hence need to buy an airline ticket The idea is that as time passes and they approach the date of the trip they have more information about the value of the trip This is stated as7 Plt6it1l6it Plt6it1 Let the marginal cost of a seat in a plane be e 1 There are two types of travelers leisure and business travelers At time t 07 leisure travelers have a valuation distributed uniform127 and business travelers have a valuation distributed uniform01 U uniformp 3 ie7 the meeting may be of low or high value The airlines knows that are leisure travelers and business travelers At time t 1 all information is realize Now7 what is the optimal selling policy of the airline at t 1 Valuation in the market will be distributed uniformp 3 hence the problem of the rm is mg p 7 C1 FP The optimal price will be 10 27 with pro ts 7r 1 X Note that at t 1 we have a lot of types7 in fact the continuum 07 3 But at t 0 we only have 2 types leisure and business t 0 the rm will offer for leisure travelers an unconditional ticket ie7 with no refund at price p 15 Ewul And for business travelers it will offer a ticket at a higher price but with the option to a refund if the the realized value at t 1 is low Note that all business travelers have to pay p5 but of them will use the refund Tb Hence the following must hold for business travelers E9ib high value meeting 7 p5 Tb 7 p5 25 7 p5 gm 2 0 Under ef cient exit7 Tb 1 Thus7 p5 1 75 Lecture Notes 5211 April 30 2008 32 And the pro ts will be 1 2 1 1 0 gkli QHg EQL E VLHEQLS il 17 cost 171 cost 171 7 5 7 2 7 3 gt 1 3 Note that 1 Over time incentive constraints multiply thus more private info 42gt more info rent rm wants to sell the object earlier to avoid the info rent 2 Participation constraint only has to hold eXante thus less private info means less public info less ef cient decision This is the tradeoff in dynamic mechanism design Also note that we need commitment otherwise if the rm offers pf 15 p 175T 1 at both times everyone will wait until the valuation is realized and the only ticket sold will be the leisure ticket thus half of the leisure travelers and half of the business travelers buy a ticket Now assume that there is only one buyer 1 with valuation vi N uniform01 and that the marginal cost is e 0 Design problem choose the information structure for the agent and the choice variable to max imize the pro ts of the rm Hence the designer can choose 1 info structure I v gt A8 2 10 The info structure will determine PrvilsiIZ where 3139 is the privately observed signal Given this the buyer will have a realization of the valuation and decide to buy or not 64 Sequential Screening E50 and Szentes 2007 Recall that in Courty and Li 2000 9 was the valuation or willingness to pay for a single object and this valuation evolves over time following a markov process 10091441191 ie more information arrives over time The choice variable from the sellers point of view is the optimal time tquot to sell the object And hence the participation and incentive constraints have to hold at time tquot remember the seller can commit not to sell before or after t and the consumers have to want to participate at tquot no later nor before E50 and Szentes 2007 allow for decisioncommitment by the agents in all time periods ie not only at it Let the value of the object to a buyer be 1 190 1 7 191 a 6 01 where 90 is realized at t0andt91att1 We will look at a mechanism for agents to reveal their information at t 0 and t 1 Now the participation and incentive constraints should be satis ed in period 0 an Suppose for example the problem of selling a single good to a single agent We want to design a revenue maximizing selling contract for the seller The timing is as follows Lecture Notes 5211 April 30 2008 33 t 0 t 1 90 is PC 91 is PC consumption realized 1C realized 1C takes are are Place satis ed satis ed A mechanism comprises a transfer at t 0 t0t90 a transfer at t 1 t1t90t91 and a quantity or probability of getting the object 409091 1 Ex post utility ie after the realization of the 97s is given by 110907 904907 91 75090 751907 91 Assume the seller has no valuation for the good Let 90 N F0lt60 91 N F1091 be the common prior and let 1 91 be private information to the buyer Consider the following special cases 1 a 1 That is late information has no value for the buyer The seller chooses the optimal monopoly pricing rule in the static case 03 6 arg mix a 7 F0 10 And the interim 1C and IR hold 2 a 0 That is the initial information has no value Then the optimal contract at t 0 is P0 Elgll P1 0 By backwards induction at t 1 if the buyer entered the contract at t 0 the PC holds because p1 0 Also at t 0 since 91 is still not realized the PC is satis ed Note 1 Why isnlt p0 0 p1 pi E arg maxpp1 7 f1 the optimal contract There is a tradeoff between ef ciency and rent extraction by the seller Say we set a price 10 Lecture Notes 52H April 30 2008 34 v v 91 info rent not extracted p surplus extracted inef ciency 10 91 9 Note 2 Generalization to auctions many bidders Let Ui6i 190139 1 7 ah 911 Vii Also let 9139 N F6i iidi From an expost point of view the seller wants to wait till the 917s are realized and pick 9f maxt911 i i i 491 Thus use a second price auction without reserve price This will give us the ef cient assignment but we donlt extract all the rent Other suggestion charge p0 Ewi or can we combine the two contracts We can charge the net gain to participate in the auction ie the info rent at the beginning That is p0 entry fee expected net value of the SPA 1 Eo mm 7 max ma maxvi p1 second price max If the seller can charge a price before 9 is realized he can extract all rent a 6 01 lntuitively we should combine is some way the two special cases There will be a tradeoff between ef ciency and informational rentsi We want to offer 2 prices an unconditional payment to 90 unconditional to the nal trans action but can depend on 90 ie this is a payment for 90types unconditional on wether the 90buyer buys the object at t 1 or not This is like an entrance fee and a conditional payment t1t90t91 ie a payment conditional on being type 90 91 and buying the object First guess for t1 it should be monotonic in 91 90 Second guess for t1 t1t90 ie does not depend on 91 this is the logic in the SPA Hence we have 2 payments that depend only on 90 one with probability 1 the other with positive probability Now remember U6061 160 1 7 191 Lecture Notes 52H April 30 2008 35 ay 1 12 then the isoutilities ie the combinations of 90 and 91 that give the same level of utility will take the following form 91 90 Now consider the utility levels that the buyer can achieve given a value of 90 90 91 9 0 90 Then it must be the case that Btl 6750 s1gn 660 s1gn 660 otherwise the 1C won7t holdi In fact in the optimal contract Btg Bti 0 660 gt 660 65 Pavan Segal and Toikka 2008 As before 110 91 190 1 7 0091 Previously we had i 90 and 91 independent and ii one nal decision The rst assumption is not important we only have to take the new information 91 90 to be independent of 90 91 90L90 and then we can implement the same mechanism as before The big insight of PST is the relaxation of the second assumptioni They consider a stream of decisions and analyze dynamic allocationsi Lecture Notes 52H April 30 2008 36 7 Internet Auctions What do we mean by internet or ebay auctions There are various characteristics 0 Large number of buyers and sellers of course a large number of objects similar or not 0 Similar objects are auctioned at different times Objects are offered at random times from the point of View of the buyers 0 The seller can decide the length of the action Thus there will be overlapping auctions and nonsynchronized buyers and sellers do not show at the same time thatls why we need to have a window Note Traditional art auctions performed in auction houses are synchronized hence no need for window i Now the sellers have to choose the entry time the window and the reserve price And the buyers have to choose the entry time in a given auction and across auctionsi Simultaneous auctions introduce strategic effects To see this suppose we have two parallel auctionsi The bidder has an incentive to enter by the end of the auction because if he enters earlier he reveals how much he values the item and hence all other bidders jump to the other auction hoping there is no high bidder in the other auctioni 71 Peters and Severinow 1997 Suppose we have lots of buyers and sellers for an identical goodi All auctions are run at the same time Also suppose that the number of buyers is greater than the number of sellers gtltgtltgtltgtltgtltgtlt buyersgtsellers At t 0 the sellers choose the price and quantity rules pi 41 for example a reserve price 2nd price auctioni At t 1 buyers decide what auction to enter and can only enter in only one auction this is a physical restriction suppose you have to be present in the auction i Lecture Notes 52H April 30 2008 37 buyers sellers 72 Peters and Severinow 2006 Now allow buyers to participate in more than one auction at a time The format of the auctions are as English ascending price auctionsi Suppose we have N buyers and M sellersi From the point of View of the sellers the buyers enter randomlyi The sellers have to decide a reserve price reserve 39 ascending auction X 174 4gt X 173 4gt X 172 4gt X 171 4gt buyers sellers In this setting we have M simultaneous ascending price auctionsi Main result There exists a Perfect Bayesian Equilibrium which leads to an ex post ef cient allocation subject to a reserve price And as N 7gt 00 the reserve price goes to 0 73 Nekipelov 2007 This paper provides an empirical and theoretical contribution to eBay auctions One way to model asynchronous auctions is the following Suppose we have continuous time and buyers and sellers entering at random timesi Buyers arriving at a rate A3 with valuation 1 identical to all buyers and sellers arriving at a rate AS with cost of selling e identical to all sellers Clearly a transaction occurs if the price p is such that v 7 p 2 0 and p 7 e 2 0 For example buyers and sellers can appear as follows t05 1 B1 B2 B3 52 B4 53 Let the discounted payoffs be e TO SQ PL for the buyer and e rquot5pt 7 e for the seller Denote by an the seller is asking price and by 12quot the buyer j s offering price If a transaction occurs the price is set at p bit ajt Let A3 As 1 and e be common knowledge In the previous gure note that Buyer 1 cannot set 21 too low because the seller has the option to wait for the next buyeri In equilibrium the price will be determined by the number of sellers and the number of buyers in fact what matters for the price determination is just the difference between the number of sellers and the number of buyers Also note that in equilibrium sellers and buyers match instantaneously What is missing in this model from eBay auctions For example buyers arrive with different valuationsi Think of a single seller with cost es and random arrival of buyers with valuations vi Lecture Notes 5211 April 30 2008 38 t 7 0 7o o o o gt seller B1 B2 B3 CS 3901 3902 3903 We want ef cient trade lf1 1 Vi then the optimal policy is to sell to the rst buyeri If the 1i7s differ then the seller can wait for a better offer but waiting is costly then the problem is how long does the seller want wait for a new sample 74 Satterthwaite and Shneyerov 2007 This paper takes a different approach It is an incomplete information model of decentralized trade There is a large number of buyers and sellers actually a continuum of themi Let buyers have valuation 1 distributed as GB 1 with 93 1 gt E and let sellers have valuation e distributed as Gse with 950 gt E1 The price formation rule is a 1st price auctioni Denote 121 the bids and 10 the reserve price 6 see a transaction if and only if max121 7 10 2 0 and the transaction occurs at the 1stprice rule Net utilities realized are 1 7 121 for the winning buyer and 121 7 e for the seller Suppose we have a measure 1 of sellers and a measure a of buyers Let 6 be the period length The benchmark for this model is the static centralized market or Walrasian market where all buyers and sellers are present at the same time and time in the auction oor We want to nd the price pW that clears demand and supply GS 12W a1 7 GB pW note that the supply GS 12W is increasing in 12W and demand a1 7 GB pW decreasing hence a unique crossing 1 Now consider the more realistic model of dynamic decentralized markets The idea is to allow for an in nite time horizon and analyze the steady state We will have many simultaneous auctions created by a matching process every buyer is matched with a single seller Suppose for the moment a discrete number of buyers 12 1 i i i B and sellers 3 1 i i i S In every period t buyers are matched uniformly but randomly across sellersi That is each seller gets a buyer with probability 1Bi For example in period t the following match is realized sellers buyers If there is a transaction the buyer and seller get out they are replaced by a new buyer and seller there is a new matching H i In the continuous case after each period 6 new sellers enter and a6 new buyers enter At every period buyers and sellers decide 10 and 121 before the market volume is realized that is before the matching he idea is that each seller at every period faces a small sample of buyers then by setting a high enough can reject a low realization of buyers and defer the auction to the next period ie the seller can choose to postpone the auction and get a new sample of buyers from the distribution of buyers Let K be the cost of participation per unit of time hence if a time period is 6 the cost of participation at each period is 6K and the total cost of participation is 6K times the number of periods it takes the seller buyer to sell acquire the itemi Also let 6 be the discount factor Fix K we want to analyze the equilibrium as 6 7gt 0 ie new transactions come at a fast rate and B 7gt 0 Lecture Notes 52H April 30 2008 39 Theorem 6 Fix K gt 0 and x 6 2 0 Suppose there exits a 6 gt 0 such that an equilibrium with positive trade exists Then 139 l39 l39 l39 l39 613366 6133 5 613326 626 6131 pW where 55 is the maximum cost type present in equilibrium E5 is the minimum acceptable bid 13 is the maximum bid Q is the minimum bid and 35 is the lowest valuation in equilibrium To see what an equilibrium looks like consider the following Fix 6 gt 0 NC 51 buyers participating participating int e int e market market In the Walrasian market 55 7 E 0 but now 55 7 E gt 0 and what determines this difference is the participation costi Now consider the steady state distributions of buyers and sellers h and hs when a gt 1 and the incoming ow distributions GB and G5 are Uniform 01 and bidding and reserve price strategies are as in the above grap hB hs steady state steady state dist of dist of sellers buyers All sellers that have at least one bidder matched are going to make a transaction then the steady state distribution is the same as the incoming ow distributioni But for the buyers v5 type will only make a transaction if she is lucky to be the only bidder matched with a buyer hence they will stay more often than the higher typesi Now think about types and willingness to pay in the auction A buyer can get the item today or wait and get it tomorrow then her valuation is going to v 7 e wWB v Lecture Notes 52H April 30 2008 40 where W3 1 is the continuation valuei Hence bids in steady state should be based on this intertem poral value ie 121 7 e st Similarly for the buyers we have C e st e and the steady state reserve price will be 7 C e st As 63 7 0 equot3 7gt tus W3 1 maxv 7 pm 0 W5 1 maxpW 7 e 0 W 7 v 7 law 4 Wow TC PW 0 A TCUW What happens to the private information lt7s gone it becomes irrelevanti The continuation value imposes the heterogeneous players to behave as a homogeneous agent 8 Information Constraints 81 Introduction In the real world economic agents face constraints when solving for their optimization problems We can think of these constraints in two ways under perfect information the problem that the agent faces is difficult to solve or if the agent can solve the problem he faces imperfect information 1 Perfect information 0 Complexity of economic decision making First introduced by Hi A Simon satisfycing 0 Early 70 s Gilboa et al showed that the complexity of computing a Nash Equilibrium is as difficult as an NP complete problemi Then agents may relax the optimality conditions to allow for easier to solve problems In experiments player biases may be explained by simple decision rules such as a rule of thumb that they adopt 0 Complexity of the optimal decision 2 lmperfect information 0 Maybe the decision maker can solve the optimization problem but the constraint she faces is from information processing 0 There is a limit on the information that the decision maker can process 0 With limited information ie with less variance in the information we will have less variance in the decision Let id be the true state of the world An agent chooses an action y to miny 7 w2 In a world with perfect information the decision rule would be y w wt What happens if we have imperfect information Say that instead of observing w we observe a noisy signal zwe Lecture Notes 52H April 30 2008 41 with 675 N N0 0 w N N0aii Then the optimal policy cannot depend on m but will depend on I y z i Let the agent know the conditional probability distribution pzlwi The agent wants to infer w after observing I that is pwlzi We can use Bayes7 rule was 713338 An estimate of w given that we observe a signal I is Then the problem of the agent is to minimize the expected loss min Egg y 7 w2 and the optimal decision rule will be y 1 1 W5 One way of saying that we have less information77 is to say that a is large limited information means a gt 0 Thus we are going to have less variance in our posterior and less variance in our decision y e idea is that information constraints lead to slow or sticky decision making This idea is formalized in Sims 1998 Sims 2003 Sims 2006 and Woodford 2007 82 Introduction to Information Theory Say we have an input w and an output 1 information encodes the input into the output Thus information constraints are constraints on the capacity We are going to use some notions of Information Theory from engineering Shannon 1948 We have a random variable w N p w For example consider a discrete random variable w 6 M1 i i i Lon i De nition 11 The entropy of a random variable pw is de ned by Hun 7 Zpw10g2pw I w lo 7 91 g2 100 1 E lo 7 p 32100 Lecture Notes 5211 April 30 2008 42 Example Coin toss outcomes HT with probabilities p 1 7 p Then Hp 7plogp 7 17 010g17 0 H P O new H 6 Remark Why do we use base 2 logarithms in the de nitions This comes from encoding data into bits Consider the following example Suppose there is a horse race there are 32 horses n 1 i i i 32 there is one winner and all horses are equally likely to win ire Prn wins 132Vn1 The problem is how to communicate the identity of the winner to someone else In fact we need 5 bits to carry the information of the winners identity since 25 32 Now lets compute the entropy 1 1 We 7 732 log2 5 which is exactly the number of bits needed Now suppose we have 8 horses again one winner but the probabilities ofwinning are i i 5714 5714 i it How many bits do we need to communicate the identity of the winner An upperbound ie one code for each horse is 3 bits since 23 8 but Hp 2 and Hp still captures the amount of information that we can transmit How can we reconciliate the two ote that some horses are more likely to win than others then we can reencode the message to minimize the number of bits used Say for example we use a 0 to inform that horse 1 won and a 1 to say some other horse won and a second bit to say that horse 2 won or not etc The entropy measures the expected number of bits needed Entropy is the average minimal number of bits to communicate the realization of a random variable We can think of entropy as the cost of communicating the realization of a random variable In many environments we may not observe the random variable I but a signal y Let I and y be two discrete random variables with joint distribution pz De nition 12 The joint entropy is de ned by HX7 Y 7 ZZML y 10g2p17y 06 11 De nition 13 The conditional entropy is de ned by Hle 7 7 Zrltrly1og2prly De nition 14 The expected conditional entropy is de ned by HX1Y 7 Z ZpyPIly10g2 atly Lecture Notes 52H April 30 2008 43 De nition 15 Let 171 and 41 be two distribution functions the relative entropy is given by D 1 lo amp 0th 213 g2 WE The idea is that relative entropy measures the loss in information or increase in cost ofcommunicating the outcome of p through qr Note that Dqu 2 0 and equals 0 if and only if 171 41 Vzl Also note that is not symmetric and does not satisfy the triangular inequalityl We now want to de ne a concept to measure how much information does a random variable carries about another random variable De nition 16 Given two random variables I y Their mutual information is given by 1X7 Y DWI yHPIpy Note that IXY HXHY7HXY HX7HXY HYHYlX IltKXgt since HX Y HX HYlX HY HXlYi Example Noiseless binary channell Say we have an input I with two possible realizations 01 and an outcome y with two realizations 01 an I y 04gt0 1A1 The information is noiseless because observing the output we can infer the input without error The channel is giving us the information The capacity of the information channel is given by C max 11 y 171 that is C is the number of bits we need to transfer information without error In this example C 1 Example Noisy system binary channel In this example C gt 1 Lecture Notes 52H April 30 2008 44 83 Slow Decision Making The rst models of slow decision making were those of Simon Calvo and Mankiwi Those models introduced a physical cost of change In particular the sticky prices models of Calvo and Mankiw assume that there is a ced cost to change pricesi Hence we will observe infrequent price changes and when they change they change by a big amount The xed cost leads to the well known 3 S policyi Instead of physical costs Sims 2003 Woodford 2007 Reis 2006a and Reis 2006b consider information costs In Woodford 2007 agents cannot process all the information and hence they face a marginal price for information Reis considers a xed cost in the sense that if the information changes from the last period it does not matter if it changes just a bit or a lot to process it again the agents have to pay a xed cost of processing 831 Sims 2003 Consider an agent choosing consumption over two periods With complete information the problem is simp y Orgncagxw ue uw 7 e where ue log e We now add information constraintsi Let Cw be the true distribution of wealth and gw its corresponding densityi In the rst period the agent still doesnlt know the realization of wealth information about wealth only arrives in the second period Now the problem is max logew 7 efe wdedw aw OScSw subject to Dfmmzo a tggwfewwdc79m vw 3 0505 log fe wfe wdwde 7 lochDo fe wdw face fe wdedwde 7 f0 loggwgwdw S K In other words constraint 3 says 1w e 7Hw e He S Ki Note that this is a reduced form model where e is the signal and the optimal decisioni Let the Lagrange multipliers associated with constraints 1 3 be e w 00 and A respec tivelyi We can solve the problem by pointwise optimizationi Fix 0 w e S w differentiate with respect to to get the FCC assuming an interior solution logew 7 e ew 00 A lt1 log fe w 7 log fewdwgt 71gt i Now let qwle E a E 1 and vw E e D MW7 then logco W C logqWC mm wma fr A 0 Setting w e 0 we get logca u 6 1ogqwlc Lecture Notes 52H April 30 2008 45 4wl6 vw6 w 6 Since qwle is a conditional distribution regardless of e we must have vwe0 w 7 e dw 1 but this requires vw olt w h l 832 Woodford 2007 The idea in this paper is that the state of the world a random variable 1 determines the optimal price q E argmaxVq optimal price with full information Price revision is costly The decision maker wants to know if it is the time to revise the price or not Let K be the cost of conducting a review of the pricing policy and let Vq be a smooth strictly concave function Let 1 denote the price gap 1 7 4 De ne the loss of failing to review the policy Mr 7 W 7 W z 7 K In the case of full information the optimal pricereview policy is to review the price if and only if the value of 1 prior to the review is in the range such that Lz 2 0 ie an Ss policy The problem is that we don7t know what the value of z is Recall that entropy is de ned as 7 f log Hence the entropy reduction when signal 8 is received is given y 15 7 fltrlslogfzlsdr7 fltzgtlogfltzgtdz and let I E E5Isi Now the theory of rational inattention posits that both the design of this signal and the decision about whether to conduct a price review conditional upon the signal observed will be optimal in the sense of maximizing 7 L E63Lz 7 OI where 9 is the cost per unit of information and 68 0 price review not undertaken 1 price review is undertaken The optimal solution will be Lemma 4 Binary signal This leads to a hazard function Az olt 7r1lz indicating the probability of a price review occurring given that the state is 1 With two possible signals A f11 MI I 0 7 f w gt 1 A M1 7 7 0ng where IX The information measure I is then equal to I AI117 AI0 7 A fz1logfz1dz1 7A fzl0logfzl0dz7 fltzgtlogfltzgtdz Lecture Notes 52H April 30 2008 46 833 Reis 2006 We have a monopolist providing a quantity y with a cost Cy 3 where 3 is the state of the world Let the demand faced by the monopolist be Qp st and let 3 be a stochastic process a Brownian motion with Markov propertyi At any point in time the rm can choose to observe or not the state Observing the state is costly Let K 2 0 be the cost of observing 3 If the rm chooses not to observe the state it has its last observation In addition let the rm know pst1lsti Let td be the last point in time the rm chose to observe the state Then the ow payoff at time t given the information std is W 821775 75d Ig xElszWmSz CQCDm 3073 std t 7 id Assume continuous time ie t 6 000 and let the discount factor be r gt 0 Let i index observations of the state variable and let denote the time at which the i 1th observation occursi Then the rm s problem is 00 di391 I e 7rsdit 7 didt 7 e rde do Note that this problem has a recursive structure hence we can rewrite it as max mm H d d Vs E max e 7rstdt e rd7K Vsd 0 subject to 5d Maud where ud are the increments in s from time 0 to di Taking the FCC we have e rdrrsd 7 re rd7K Vsd e TdVsd 0 7rs d rK rEVsd EVsd note that the right hand side are the gains from postponing observing the state and the left hand side the costs De ne Csd R51 7gt R as the expected differences between pro ts earned with full informa tion and pro ts earned with the optimal plani Proposition 8 A perturbation around the situation when planning is costless is 2Ks Cs 0 d s Note that second order costs of planning lead to rstorder long inattentiveness Proposition 9 With isoelastic demand with price elasticity e gt 1 subject to d multiplicative shocks while marginal costs follow a geometric Brownian motion with variance 02 and planning costs a xed share K of pro ts the producer sets a plan for prices pt stl In the vicinity ofK 0 optimal inattentiveness approximately equals 418 d SHm Lecture Notes 52H April 30 2008 47 Note that the price rule does not depend on the state of demand Aggregation Letls consider the case Where inattentiveness varies randomly With changes in the pro ts of rms and the costs of planning The arrival of decision dates then takes the form of a stochastic point processi Denote the arrival densities by and assume they are mutually independent independent across producers and the same for all producersi Let p denote the intensity of attention7 de ned as the longrun mean number of planning dates in a unit of time p Ewla as t A 00 Proposition 10 The only stationary equilibrium 7 t i39wti t of 39 quot is the l quot 39 distribution with parameter p Lecture Notes 5211 April 30 2008 48 References ATHEY 8 AND I SEGAL 2007 Designing Ef cient Mechanisms for Dynamic Bilateral Trading Games American Economic Review Papers and Proceedings 97 1317136 BERGEMANN D AND S MORRIS 2005 Robust Mechanism Design Econometrica 73 17717 1813 BERGEMANN D AND J VALIMAKI 2006 Dynamic Price Competition Journal of Economic Them 127 2327263 BERGEMANN D AND J VALIMAKI 2007 Dynamic Marginal Contribution Mechanism Dis cussion paper Yale University and Helsinki School of Economics BRANDENBURGER A AND E DEKEL 1993 Hierarchies of Belief and Common Knowledge Journal of Economic Theory 59 1897198 CLARKE E 1971 Multipart Pricing of Public Goods Public Choice 8 19733 DASGUPTA P P HAMMOND AND E MASKIN 1979 The Implementation of Social Choice Rules Some General Results on Incentive Compatibility Review of Economic Studies 66 1857 216 DOLAN R 1978 Incentive Mechanisms for Prioroty Queuing Problems Bell Journal of Eco nomics 9 4217436 EDELMAN B M OSTROVSKY AND M SCHWARTZ 2007 Internet Advertising and the Gener alized Second Price Auction Selling Billions of Dollars Worth of Keywords American Economic Review 97 2427259 ELY J C AND M PESKI 2006 Hierarchies of Belief and Interim Rationalizability Theoretical Economics 1 ESO P AND B SZENTES 2007 Optimal Information Disclosure in Auctions Review of Eco nomic Studies forthcoming FEINBERG Y AND A SKRYPACZ 2005 Uncertainty About Uncertainty and Delay in Bargain ing Econometrica 73 69791 FREIXAS X R GUESNERIE AND J TIROLE 1985 Planning under Incomplete Information and the Ratchet Effect Review of Economic Studies 52 1737191 GREEN I AND J LAFFONT 1977 Characterization of Satisfactory Mechanisms for the Revela tion of the Preferences for Public Goods Econometrica 45 4277438 GROVES T 1973 Incentives in teams Econometrica 41 6177631 GUL 13 H SONNENSCHEIN AND R WILSON 1986 Foundations of Dynamic Monopoly and the Coase Conjecture Journal of Economic Theory 39 1557190 HARSANYI J 196768 Games With Incomplete Information Played by 7Bayesian7 Players Man agement Science 14 1597189 3207334 4857502 HART 0 AND J TIROLE 1988 Contract Renogiation and Coasian Dynamics Review of Economic Studies 55 5097540 Lecture Notes 52H April 30 2008 49 HEIFETZ A AND D SAMET 1888 TopologyFree Typology of Beliefs Journal of Economic Theory 82 3247341 LEDYARD J O 1978 Incentive Compatibility and Incomplete Information Journal of Eco nomic Theory 18 1717189 MERTENS I AND S ZAMIR 1985 Formalization of Bayesian Analysis for Games With Incom plete Information International Journal of Game Theory 14 1729 REIS R 2006a Inattentive Consumers Journal of Monetary Economics 53 176171800 7 2006b Inattentive Producers Review of Economic Studies 73 7937821 SCHMIDT K 1990 Commitment Through Incomplete Information in a Simple Repeated Bar gaining Model mimeo University of Bonn SIMS C 2003 Implications of Rational Inattention Journal of Monetary Economics 50 6657 690 2006 Rational Inattention Beyond the LinearQuadratic Case American Economic Review 96 1587163 VICKREY W 1961 Counterspeculation Auctions and Competitive Sealed Tenders Journal of Finance 16 8737 WILSON R 1987 GameTheoretic Analyses of Trading Processes in Advances in Economic Theory Fifth World Congress ed by T Berey pp 33770 Cambridge Cambridge University ress WOODFORD M 2007 InformationConstrained StateDependent Pricing Discussion paper Columbia University

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I made $350 in just two days after posting my first study guide."

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.