  We consider an infinite horizon dynamic mechanism design problem with
interdependent valuations. In this setting the type of each agent is assumed to
be evolving according 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 truthful 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 mechanism which is efficient, `strict' ex-post incentive compatible and
ex-post individually rational in a setting with interdependent values and
Markovian type evolution.
