An efficient ascending auction for private valuations

Known dynamic implementations of the Vickrey-Clarke-Groves mechanism in general private-value auction settings utilize non-linear (not additively-separable over goods) and non-anonymous (bidder-specific) prices. The need for non-linear and non-anonymous prices - a complication that is often difficult to implement in practice - arises from limiting attention to elicitation processes based on demand queries (i.e., asking bidders to report their demands at posted prices). In this paper, we relax this restriction and allow the auctioneer to supplement demand queries with marginal value queries (i.e., requests to report value differences between pairs of commodity bundles) as needed. This added flexibility enables an iterative ascending auction design that achieves efficiency despite using linear and anonymous prices.