Dynamic Mechanism Design with Interdependent Valuations
Swaprava Nath, Onno Zoeter, Yadati Narahari, Chris Dance
We consider an infinite horizon dynamic mechanism design problem with interdepen-
dent valuations. In this setting the type of each agent is assumed to be evolving ac-
cording to a first order Markov process and is independent of the types of other agents.
However, the valuation of an agent can depend on the types of other agents, which
makes the problem fall into an interdependent valuation setting. Designing truth-
ful mechanisms in this setting is non-trivial in view of an impossibility result which
says that for interdependent valuations, any efficient and ex-post incentive compatible
mechanism must be a constant mechanism, even in a static setting. Mezzetti (2004)
circumvents this problem by splitting the decisions of allocation and payment into two
stages. However, Mezzetti’s result is limited to a static setting and moreover in the
second stage of that mechanism, agents are weakly indifferent about reporting their
valuations truthfully. This paper provides a first attempt at designing a dynamic mech-
anism which is efficient, strict ex-post incentive compatible and ex-post individually rational in a setting with interdependent values and Markovian type evolution.