  Lately, the problem of designing multi-stage dynamic mechanisms has been
shown to be both theoretically challenging and practically important. In this
paper, we consider the problem of designing revenue optimal dynamic mechanism
for a setting where an auctioneer sells a set of items to a buyer in multiple
stages. At each stage, there could be multiple items for sale but each item can
only appear in one stage. The type of the buyer at each stage is thus a
multi-dimensional vector characterizing the buyer's valuations of the items at
that stage and is assumed to be stage-wise independent.
  In particular, we propose a novel class of mechanisms called bank account
mechanisms. Roughly, a bank account mechanism is no different from any
stage-wise individual mechanism except for an augmented structure called bank
account, a real number for each node that summarizes the history so far. We
first establish that the optimal revenue from any dynamic mechanism in this
setting can be achieved by a bank account mechanism, and we provide a simple
characterization of the set of incentive compatible and ex-post individually
rational bank account mechanisms. Based on these characterizations, we then
investigate the problem of finding the (approximately) optimal bank account
mechanisms. We prove that there exists a simple, randomized bank account
mechanism that approximates optimal revenue up to a constant factor. Our result
is general and can accommodate previous approximation results in single-shot
multi-dimensional mechanism design. Based on the previous mechanism, we further
show that there exists a deterministic bank account mechanism that achieves
constant-factor approximation as well. Finally, we consider the problem of
computing optimal mechanisms when the type space is discrete and provide an
FPTAS via linear and dynamic programming.
