Auction ascending-price

In this section, we tie together the mechanism design approach and the competitive equilibrium approach. The basic idea is to construct efficient ascending-price auctions that terminate with the outcome of the VCG mechanism. With this, price-taking behavior is a game-theoretic equilibrium of the auction despite the effect that an agent s bids might have on future price dynamics. The auctions provide a dynamic method to compute a set of competitive equilibrium prices, from which allocative efficiency follows. 

We return to UCE prices in Section 5.1, in the context of an ascending-price combinatorial auction in which agents are interested in bundles of items. The primal-dual analysis is performed with respect to the hierarchy of extended LP formulations described in Section 2.3. 

The implementation complexity of a mechanism considers the complexity of computing the outcome of a mechanism from agent strategies. For example, in a DRM this is the complexity of the problem to compute the outcome from reported agent values. In an indirect mechanism this is the complexity to update the state of the mechanism in response to agent strategies, for example to update the provisional allocation and ask prices in an ascending-price auction. We choose to focus on the issues of implementation complexity in direct mechanisms, which are the mechanisms in which this has received most attention. 

Sushil Bikhchandani and Joseph M Ostroy. Ascending price Vickrey auctions. Games and Economic Behavior, 2002. Forthcoming. 

Olivier Compte and Philippe Jehiel. On the virtues of the ascending price auction New insights in the private value setting. Technical report, CERAS and UCL, 2000. 

David C Parkes. /Bundle An efficient ascending price bundle auction. In Proc. 1st ACM Conf. on Electronic Commerce (EC-99), pages 148-157, 1999. 

David C Parkes and Lyle H Ungar. An ascending-price generalized Vickrey auction. Technical report. Harvard University, 2002. 

This is not to say that alternatives should not be considered, or that either option is necessarily the preferred auction format for every Member State. However the low costs of such formats (e.g. compared with ascending bids) and the fact that Member States can draw on the experiences of securities markets suggest that discriminatory and uniform-price auctions should be thoroughly examined. 

Straightforward MBR bidding is an ex post Nash equilibrium in this case, with each agent choosing to bid in each round for the set of bundles that maximize its payoff given the current prices. This is proved by Ausubel Milgrom [7] in their analysis of the closely-related ascending-proxy auction. 

In the auction of a single object, it has long been known that an open (ascending) auction exists that duplicates the outcomes of the Vickrey auction. This is the English auction, in which the auctioneer continuously raises the price for the object. An agent is to keep his hand raised until the price exceeds... 

Ascending auctions come in two varieties (with hybrids possible). In the first, bidders submit, in each round, prices on various bundles. The auctioneer makes a provisional allocation of the items that depends on the submitted prices. Bidders are allowed to adjust their price offers from the previous rounds and the auction continues. Such auctions come equipped with rules to ensure rapid progress and encourage competition. Ascending auctions of this type seem to be most prevalent in practice. 

In order to understand how to design ascending auctions it is important to identify what properties prices must have in order to produce an allocation that solves CAPl. Such an understanding can be derived from the duality theory of integer programs. 

Other ascending auctions that do not fit neatly into our division between primal-dual and lagrangean have also been proposed. Wurman and Wellman [68] propose an iterative auction that allows bids on subsets but uses anonymous, non-linear prices to direct the auction. Bidders submit bids on bundles and using these bids, an instance of CAPl is formulated and solved. Then, another program is solved to impute prices to the bundles allocated that will satisfy a complementary slackness condition. In the next round, bidders must submit a bid that is at least as large as the imputed price of the bundles. 

---