We consider the problem of designing revenue-optimal auctions for selling two items and bidders' valuations are independent among bidders but negatively correlated among items. In this paper, we obtain the closed-form optimal auction for this setting, by directly addressing the two difficulties above. In particular, the first difficulty is that when pointwise maximizing virtual surplus under multi-dimensional feasibility (i.e., the Border feasibility), (1) neither the optimal interim allocation is trivially monotone in the virtual value, (2) nor the virtual value is monotone in the bidder's type. As a result, the optimal interim allocations resulting from virtual surplus maximization no longer guarantees BIC. To address (1), we prove a generalization of Border's theorem and show that optimal interim allocation is indeed monotone in the virtual value. To address (2), we adapt Myerson's ironing procedure to this setting by redefining the (ironed) virtual value as a function of the lowest utility point. The second difficulty, perhaps a more challenging one, is that the lowest utility type in general is no longer at the endpoints of the type interval. To address this difficulty, we show by construction that there exist an allocation rule and an induced lowest utility type such that they form a solution of the virtual surplus maximization and in the meanwhile guarantees IIR. In the single bidder case, the optimal auction consists of a randomized bundle menu and a deterministic bundle menu; while in the multiple bidder case, the optimal auction is a randomization between two extreme mechanisms. The optimal solutions of our setting can be implemented by a Bayesian IC and IR auction, however, perhaps surprisingly, the revenue of this auction cannot be achieved by any (dominant-strategy) IC and IR auction.
At a higher level, our work is within the agenda of multidimensional revenue maximization. In particular, our work is in the direction of exactly optimal mechanism design @cite_14 @cite_10 @cite_27 @cite_1 , orthogonal to those aiming for approximate optimality @cite_8 @cite_4 @cite_23 @cite_25 @cite_24 @cite_11 .
@cite_14 @cite_4 @cite_8 @cite_1 @cite_24 @cite_27 @cite_23 @cite_10 @cite_25 @cite_11
2275043201 203000141 2118442327 2133106342 2088970293 2038821244 2169604085 1718157382 1495768673
Optimal mechanisms have been provided in quite general multi-item settings [ 2012b, as long as each bidder's type distribution is given explicitly by listing every type in the support along with its associated probability. In the implicit setting, e.g. when the bidders have additive valuations with independent and or continuous values for the items, these results do not apply, and it was recently shown that exact revenue optimization is intractable, even when there is only one bidder [ 2013]. Even for item distributions with special structure, optimal mechanisms have been surprisingly rare [Manelli and Vincent 2006] and the problem is challenging even in the two-item case [Hart and Nisan 2012]. In this paper, we provide a framework for designing optimal mechanisms using optimal transport theory and duality theory. We instantiate our framework to obtain conditions under which only pricing the grand bundle is optimal in multi-item settings (complementing the work of [Manelli and Vincent 2006]), as well as to characterize optimal two-item mechanisms. We use our results to derive closed-form descriptions of the optimal mechanism in several two-item settings, exhibiting also a setting where a continuum of lotteries is necessary for revenue optimization but a closed-form representation of the mechanism can still be found efficiently using our framework. The VCG mechanism is the gold standard for combinatorial auctions (CAs), and it maximizes social welfare. In contrast, the revenue-maximizing (aka optimal) CA is unknown, and designing one is NP-hard. Therefore, research on optimal CAs has progressed into special settings. Notably, Levin [1997] derived the optimal CA for complements when each agent's private type is one-dimensional. (This does not fall inside the well-studied "single-parameter environment".) We introduce a new research avenue for increasing revenue where we poke holes in the allocation space--based on the bids--and then use a welfare-maximizing allocation rule within the remaining allocation set. In this paper, the first step down this avenue, we introduce a new form of "reserve pricing" into CAs. We show that Levin's optimal revenue can be 2-approximated by using "monopoly reserve prices" to curtail the allocation set, followed by welfare-maximizing allocation and Levin's payment rule. A key lemma of potential independent interest is that the expected revenue from any truthful allocation-monotonic mechanism equals the expected virtual valuation; this generalizes Myerson's lemma [1981] from the single-parameter environment. Our mechanism is close to the gold standard and thus easier to adopt than Levin's. It also requires less information about the prior over the bidders' types, and is always more efficient. Finally, we show that the optimal revenue can be 6- approximated even if the "reserve pricing" is required to be symmetric across bidders. The monopolist's theory of optimal single-item auctions for agents with independent private values can be summarized by two statements. The first is from Myerson [8]: the optimal auction is Vickrey with a reserve price. The second is from Bulow and Klemperer [1]: it is better to recruit one more bidder and run the Vickrey auction than to run the optimal auction. These results hold for single-item auctions under the assumption that the agents' valuations are independently and identically drawn from a distribution that satisfies a natural (and prevalent) regularity condition. These fundamental guarantees for the Vickrey auction fail to hold in general single-parameter agent mechanism design problems. We give precise (and weak) conditions under which approximate analogs of these two results hold, thereby demonstrating that simple mechanisms remain almost optimal in quite general single-parameter agent settings. Optimal mechanisms for agents with multi-dimensional preferences are generally complex. This complexity makes them challenging to solve for and impractical to run. In a typical mechanism design approach, a model is posited and then the optimal mechanism is designed for the model. Successful mechanism design gives mechanisms that one could at least imagine running. By this measure, multi-dimensional mechanism design has had only limited success. In this paper we take the opposite approach, which we term reverse mechanism design. We start by hypothesizing the optimality of a particular form of mechanism that is simple and reasonable to run, then we solve for sufficient conditions for the mechanism to be optimal (among all mechanisms). This paper has two main contributions. The first is in codifying the method of virtual values from single-dimensional auction theory and extending it to agents with multidimensional preferences. The second is in applying this method to two paradigmatic classes of multi-dimensional preferences. The first class is unit-demand preferences (e.g., a homebuyer who wishes to buy at most one house); for this class we give sufficient conditions under which posting a uniform price for each item is optimal. This result generalizes one of [2013] for a consumer with values uniform on interval [0; 1], and contrasts with an example of Thanassoulis [2004] for a consumer with values uniform on interval [5; 6] where uniform pricing is not optimal. The second class is additive preferences, for this class we give sufficient conditions under which posting a price for the grand bundle is optimal. This result generalizes a recent result of Hart and Nisan [2012] and relates to work of Armstrong [1999]. Similarly to an approach of [2013], these results for single-agent pricing problems can be generalized naturally to multi-agent auction problems. Abstract Consider the revenue-maximizing problem in which a single seller wants to sell k different items to a single buyer, who has independently distributed values for the items with additive valuation. The case was completely resolved by Myerson’s classical work in 1981, whereas for larger k the problem has been the subject of much research efforts ever since. Recently, Hart and Nisan analyzed two simple mechanisms: selling the items separately, or selling them as a single bundle. They showed that selling separately guarantees at least a fraction of the optimal revenue; and for identically distributed items, bundling yields at least a fraction of the optimal revenue. In this paper, we prove that selling separately guarantees at least fraction of the optimal revenue, whereas for identically distributed items, bundling yields at least a constant fraction of the optimal revenue. These bounds are tight (up to a constant factor), settling the open questions raised by Hart and Nisan. The results are valid for arbitrary probability distributions without restrictions. Our results also have implications on other interesting issues, such as monotonicity and randomization of selling mechanisms. We solve the optimal multi-dimensional mechanism design problem when either the number of bidders is a constant or the number of items is a constant. In the first setting, we need that the values of each bidder for the items are i.i.d., but allow different distributions for each bidder. In the second setting, we allow the values of each bidder for the items to be arbitrarily correlated, but assume that the bidders are i.i.d. For all e > 0, we obtain an efficient additive e-approximation, when the value distributions are bounded, or a multiplicative (1--e)-approximation when the value distributions are unbounded, but satisfy the Monotone Hazard Rate condition. When there is a single bidder, we generalize these results to independent but not necessarily identically distributed value distributions, and to independent regular distributions. Myerson's classic result provides a full description of how a seller can maximize revenue when selling a single item. We address the question of revenue maximization in the simplest possible multi-item setting: two items and a single buyer who has independently distributed values for the items, and an additive valuation. In general, the revenue achievable from selling two independent items may be strictly higher than the sum of the revenues obtainable by selling each of them separately. In fact, the structure of optimal (i.e., revenue-maximizing) mechanisms for two items even in this simple setting is not understood. In this paper we obtain approximate revenue optimization results using two simple auctions: that of selling the items separately, and that of selling them as a single bundle. Our main results (which are of a "direct sum" variety, and apply to any distributions) are as follows. Selling the items separately guarantees at least half the revenue of the optimal auction; for identically distributed items, this becomes at least 73 of the optimal revenue. For the case of k > 2 items, we show that selling separately guarantees at least a c log2(k) fraction of the optimal revenue; for identically distributed items, the bundling auction yields at least a c log(k) fraction of the optimal revenue. Revenue maximization in multi-item settings is notoriously elusive. This paper studies a class of two-item auctions which we call a mixed-bundling auction with reserve prices (MBARP). It calls VCG on an enlarged set of agents by adding the seller---who has reserve valuations for each bundle of items---and a fake agent who receives nothing nor has valuations for any item or bundle, but has a valuation for pure bundling allocations, i.e., allocations where the two items are allocated to a single agent. This is a strict subclass of several known classes of auctions, including the affine maximizer auction (AMA), λ-aution, and the virtual valuations combinatorial auction (VVCA). As we show, a striking feature of MBARP is that its revenue can be represented in a simple closed form as a function of the parameters. Thus, we can solve first-order conditions on the parameters and obtain the optimal MBARP. The optimal MBARP yields significantly higher revenue than prior auctions for which the revenue-maximizing parameters could be solved for in closed form: separate Myerson auctions, pure-bundling Myerson auction, VCG, and mixed-bundling auction without reserve prices. Its revenue even exceeds that obtained via simulation within broader classes: VVCA and AMA. In this paper, we introduce a novel approach for reducing the k-item n-bidder auction with additive valuation to k-item 1-bidder auctions. This approach, called the Best-Guess reduction, can be applied to address several central questions in optimal revenue auction theory such as the relative strength of simple versus complex mechanisms, the power of randomization, and Bayesian versus dominant-strategy implementations. First, when the items have independent valuation distributions, we present a deterministic mechanism called Deterministic Best-Guess that yields at least a constant fraction of the optimal revenue by any randomized mechanism. This also gives the first simple mechanism that achieves constant fraction optimal revenue for such multi-buyer multi-item auctions. Second, if all the nk valuation random variables are independent, the optimal revenue achievable in dominant strategy incentive compatibility (DSIC) is shown to be at least a constant fraction of that achievable in Bayesian incentive compatibility (BIC). Third, when all the nk values are identically distributed according to a common one-dimensional distribution F, the optimal revenue is shown to be expressible in the closed form Θ(k(r + ∫0mr(1 − F(x)n)dx)) where r = supx≥0 x(1 − F(x)n) and m = lk nr; this revenue is achievable by a simple mechanism called 2nd-Price Bundling. All our results apply to arbitrary distributions, regular or irregular.