Optimal Dynamic Auctions are Virtual Welfare Maximizers
Abstract
We are interested in the setting where a seller sells sequentially
arriving items, one per period, via a dynamic auction.
At the beginning of each period, each buyer draws a private
valuation for the item to be sold in that period and this valuation
is independent across buyers and periods. The auction
can be dynamic in the sense that the auction at period
t can be conditional on the bids in that period and all previous
periods, subject to certain appropriately defined incentive
compatible and individually rational conditions. Perhaps
not surprisingly, the revenue optimal dynamic auctions are
computationally hard to find and existing literatures that aim
to approximate the optimal auctions are all based on solving
complex dynamic programs. It remains largely open on the
structural interpretability of the optimal dynamic auctions.
In this paper, we show that any optimal dynamic auction is
a virtual welfare maximizer subject to some monotone allocation
constraints. In particular, the explicit definition of
the virtual value function above arises naturally from the
primal-dual analysis by relaxing the monotone constraints.
We further develop an ironing technique that gets rid of the
monotone allocation constraints. Quite different from Myerson’s
ironing approach, our technique is more technically involved
due to the interdependence of the virtual value functions
across buyers. We nevertheless show that ironing can be
done approximately and efficiently, which in turn leads to a
Fully Polynomial Time Approximation Scheme of the optimal
dynamic auction.
arriving items, one per period, via a dynamic auction.
At the beginning of each period, each buyer draws a private
valuation for the item to be sold in that period and this valuation
is independent across buyers and periods. The auction
can be dynamic in the sense that the auction at period
t can be conditional on the bids in that period and all previous
periods, subject to certain appropriately defined incentive
compatible and individually rational conditions. Perhaps
not surprisingly, the revenue optimal dynamic auctions are
computationally hard to find and existing literatures that aim
to approximate the optimal auctions are all based on solving
complex dynamic programs. It remains largely open on the
structural interpretability of the optimal dynamic auctions.
In this paper, we show that any optimal dynamic auction is
a virtual welfare maximizer subject to some monotone allocation
constraints. In particular, the explicit definition of
the virtual value function above arises naturally from the
primal-dual analysis by relaxing the monotone constraints.
We further develop an ironing technique that gets rid of the
monotone allocation constraints. Quite different from Myerson’s
ironing approach, our technique is more technically involved
due to the interdependence of the virtual value functions
across buyers. We nevertheless show that ironing can be
done approximately and efficiently, which in turn leads to a
Fully Polynomial Time Approximation Scheme of the optimal
dynamic auction.
Research Areas
