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.
The Bayesian setting is widely studied in the economics literature @cite_21 @cite_26 @cite_10 @cite_27 @cite_18 @cite_22 @cite_0 @cite_20 @cite_5 . In this setting, the optimal (either BIC or DSIC) mechanism can always be computed by encoding the incentive compatibility constraints in an integer program and maximizing expected revenue. However, the number of variables (and constraints) in this IP is exponential in the number of bidders, there being variables for the allocations and prices for each scenario of revealed types. Therefore, the key difficulty in the Bayesian mechanism design case is computational : Can the optimal (or approximately optimal) auction be efficiently computed and implemented?
@cite_18 @cite_26 @cite_22 @cite_21 @cite_0 @cite_27 @cite_5 @cite_10 @cite_20
1498123810 1594643704 2739947352 2035239570 2133387873
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] We consider a dynamic auction problem motivated by the traditional single-leg, multi-period revenue management problem. A seller with C units to sell faces potential buyers with unit demand who arrive and depart over the course of T time periods. The time at which a buyer arrives, her value for a unit as well as the time by which she must make the purchase are private information. In this environment, we derive the revenue maximizing Bayesian incentive compatible selling mechanism. This paper finds an optimal mechanism for selling an indivisible good to consumers who may be budget-constrained. Unlike the case where buyers are not budget constrained, a single posted price is not typically optimal. An optimal mechanism generally consists of a continuum of lotteries indexed by the probability of comsumption and the entry fee. We show that all-pay auctions dominate first-price sealed-bid auctions when bidders face budget constraints. This ranking is explained by the fact that budget constraints bind less frequently in the all-pay auctions, which leads to more aggressive bidding in that format. Abstract Using a model of substitutable goods I determine generic conditions on tastes which guarantee that fixed prices are not optimal: the fully optimal tariff includes lotteries. That is, a profit maximising seller would employ a haggling strategy. We show that the fully optimal selling strategy in a class of cases requires a seller to not allow themselves to focus on one good but to remain haggling over more than one good . This throws new light on the selling strategies used in diverse industries. These insights are used to provide a counter-example to the no lotteries result of McAfee and McMillan (J. Econ. Theory 46 (1988) 335).