The Dynamic Pivotal MechanismDirk Bergemann19th May 2010, DIWDirk Bergemann The Dynamic Pivotal MechanismIntertemporal Efficiency with Private Informationrandom arrival of buyers, sellers and/or objectsselling seats for an airplane with random arrival of buyersbidding on ebaybidding for construction projects with uncertain arrival ofnew projectsbidding for links in sponsored search (Google, Yahoo, etc.)initial uncertainty and learning about click-throughprobabilityinitial uncertainty and learning about conversion probabilityleasing resource over timeauction of renewable license, right, capacity over timeweb serving, computational resource (bandwidth, CPU)Dirk Bergemann The Dynamic Pivotal MechanismStatic Efficiency with Private InformationVickrey (1961), Clarke (1971), Groves (1973) (VCG)establish incentive compatibility in dominant strategies inprivate value environmentsagent i internalizes the social objectiveClarke (1971) and Laffont (1977) analyze specific VCGmechanism: pivotal mechanismexternality cost of iutility of Ini when i is absent - utility of Ini when i is presenti internalizes social objective as i pays her externality costmarginal contribution of i = utility of i - externality cost of iDirk Bergemann The Dynamic Pivotal MechanismDynamic Pivotal Mechanismpayoff in Pivot mechanism = marginal contributiondevelop marginal contribution mechanism in intertemporalenvironments with new arrival of information regarding:preferencesagentsallocationsdesign sequence of payments so that each agent receivesflow marginal contribution in every periodDirk Bergemann The Dynamic Pivotal Mechanism...but wait...solve intertemporal problem as a completely contingentplanembed intertemporal problem in a static problem(as in an Arrow Debreu economy) ...... and then appeal to the classic VCG results.but the contingent view fails to account for strategicpossibilities of the agents in the sequential modelDirk Bergemann The Dynamic Pivotal MechanismSequential Incentive and Participation Constraintsinformation arrives over timereport of agent i in period t responds to private informationof agent i, but may also respond to past reports of otheragents (possibly inferred from allocative decisions)truthtelling (generally) fails to be a weakly dominantstrategywith forward looking agents, participation constraint isrequired to be satisfied at every point in time(and not only in the initial period)Dirk Bergemann The Dynamic Pivotal MechanismResultsdynamic pivotal mechanism is socially efficientperiodic ex post: with respect to information in period tsatisfies (periodic) ex post incentive constraintssatisfies (periodic) ex post participation constraintsadding efficient exit condition (weak “online” condition)uniquely identifies dynamic pivotal mechanism:if i doesn’t impact future allocative decisions,then i doesn’t have future monetary transfersDirk Bergemann The Dynamic Pivotal MechanismLiteratureDolan (RAND 1978):priority queuingParkes et al. (2003):delayed VCG without participation or budget balanceconstraintsBergemann & Valimaki (JET 2006):complete information, repeated allocation of single objectover time, first price biddingAthey & Segal (2007):balanced budget rather than participation constraintsDirk Bergemann The Dynamic Pivotal MechanismSchedulingscheduling tasksdiscrete time, infinite horizon: t = 0; 1; ::::common discount factor finite number of agents: i 2 f0; 1; :::; Igeach agent i has a single taskvalue of task for i is:vi> 0quasilinear utility: vi piDirk Bergemann The Dynamic Pivotal MechanismAssignmentvalues are given wlog in descending order:v0> v1>    > vI> 0marginal contribution of task i :difference in welfare with i and without iefficient task assignment policy:policy without i 0 1    i  1 i+1 i+2    I& & &policy with i 0 1    i  1 i i+1 i+2    I"Dirk Bergemann The Dynamic Pivotal MechanismMarginal Contributionpolicy without i 0 1    i  1 i+1 i+2    I& & &policy with i 0 1    i  1 i i+1 i+2    I"insert valuable task i:raise the value of all future tasks: t > imarginal contribution Mi:Mi=IXt=0tvt i1Xt=0tvt+IXt=i+1t1vt!orMi=IXt=it(vt vt+1)  0Dirk Bergemann The Dynamic Pivotal MechanismExternalityfrom marginal contribution to externality pricing:Mi= vi piexternality cost of task i is:pi= vi+1IXt=i+1ti>0z }| {(vt vt+1)task i directly replaces task i + 1; but also:task i raises the value of all future tasksDirk Bergemann The Dynamic Pivotal MechanismIncomplete Informationviis private information to agent i at t = 0incentive compatibility and efficient sorting: when would ilike to win against j versus j + 1:vi vjIXt=jt(j1)(vt vt+1) vi vj+1IXt=j+1tj(vt vt+1)reduces to cost of delay:(1  ) vi (1  ) vj:report thruthful if others report truthful: ex post equilibriumDirk Bergemann The Dynamic Pivotal MechanismGeneral Modelagent i = 1; :::; Itime t = 0; 1:::::common discount factor  2 (0; 1)quasilinear flow utility of agent i in period t :viat; i;t pi;tallocation at2 Amarkovian state t=1;t; :::; I;t2 monetary transfer pi;tprivate (Markovian) signal i;t+1of i is generated byconditional distribution function:i;t+1 Piat; i;tDirk Bergemann The Dynamic Pivotal MechanismDynamic Direct Mechanismagent i reports ri;t2 iin every period tinductively, a history of publicly observable reports:ht=ht1; r1;t; :::; rI;tsocially efficient allocation rule (after all histories ht)a t: Ht! [0; 1]Itransfer (or pricing) rule is given by:pt: Ht! RIDirk Bergemann The Dynamic Pivotal MechanismStrategiesprivate history of agent i:hi;t=i;0; r0; ; :::i;t1; rt1; i;treporting strategy for agent i:ri;t: Hi;t! iexpected discounted payoff for bidder i :E1Xt=0tvia (ht) ; i;t pi;t(ht) :strategy of i solves sequential problem Vi(hi;t) :maxri;t2iEvi;ta (ht) ; i;t pi;t(ht) + Vihi;t+1taking expectation E wrt ri;tDirk Bergemann The Dynamic Pivotal MechanismEquilibriumdenote by hi;t, htn ri;tBayesian incentive compatible if ri;t= i;tsolvesmaxri;t2iEvia ri;t; hi;t; i;t pi;tri;t; hi;t+ Vihi;t+1periodic ex post: with respect to all information in period t(periodic) ex post incentive compatible if ri;t=