In this paper, we present the first approximation algorithms for the problem of designing revenue optimal Bayesian incentive compatible auctions when there are multiple (heterogeneous) items and when bidders can have arbitrary demand and budget constraints. Our mechanisms are surprisingly simple: We show that a sequential all-pay mechanism is a 4 approximation to the revenue of the optimal ex-interim truthful mechanism with discrete correlated type space for each bidder. We also show that a sequential posted price mechanism is a O(1) approximation to the revenue of the optimal ex-post truthful mechanism when the type space of each bidder is a product distribution that satisfies the standard hazard rate condition. We further show a logarithmic approximation when the hazard rate condition is removed, and complete the picture by showing that achieving a sub-logarithmic approximation, even for regular distributions and one bidder, requires pricing bundles of items. Our results are based on formulating novel LP relaxations for these problems, and developing generic rounding schemes from first principles. We believe this approach will be useful in other Bayesian mechanism design contexts.
Finally, several researchers have considered the behavior specific types of auctions, for instance, auctions that are sequential by item and second price within each item @cite_21 @cite_4 , and ascending price auctions @cite_25 @cite_26 . The goal here is to analyze the improvement in revenue (or social welfare) by optimal sequencing, or to study incentive compatibility of commonly used ascending price mechanisms. However, analyzing the performance of sequential or ascending price auctions is difficult in general, and there is little known in terms of optimal mechanisms (or even approximately optimal mechanisms) in these settings.
@cite_21 @cite_4 @cite_25 @cite_26
1594189438 2102636809 1498123810
We study sequential auctions for private value objects and unit-demand bidders using second-price sealed-bid rules. We analyze this scenario from the seller's perspective and consider several approaches to increasing the total revenue. We derive the equilibrium bidding strategies for each individual auction.We then study the problem of selecting an optimal agenda, i.e., a revenue-maximizing ordering of the auctions. We describe an efficient algorithm that finds an optimal agenda in the important special case when the revenue of each auction is guaranteed to be strictly positive. We also show that the seller can increase his revenue by canceling one or more auctions, even if the number of bidders exceeds the number of objects for sale, and analyze the bidders' behavior and the seller's profit for different cancellation rules. March 2002 A family of ascending package auction models is introduced in which bidders may determine their own packages on which to bid. In the proxy auction (revelation game) versions, the outcome is a point in the core of the exchange economy for the reported preferences. When payoffs are linear in money and goods are substitutes, sincere reporting constitutes a Nash equilibrium and the outcome coincides with the Vickrey auction outcome. Even when goods are not substitutes, ascending proxy auction equilibria lie in the core with respect to the true preferences. Compared to the Vickrey auction, the proxy auctions generate higher equilibrium revenues, are less vulnerable to collusion, can handle budget constraints much more robustly, and may provide better ex ante investment incentives. Working Papers Index We study the impact of potentially binding liquidity constraints on the level of competition in a version of the simultaneous ascending bid auctions. We show that the possibility, even if arbitrarily small, of binding budget constraints can reduce competition significantly, because bidders can ‘pretend’ to be constrained, even if they are not. This effect can be significant: for many distributions of the bidders’ values, all unconstrained bidders behave as if they were liquidity constrained, even as the probability that bidders are budget constrained goes to zero. The possibility of budget constraints therefore requires special attention to the details of the auction. JEL classification number: D44 [H]