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.
@cite_7 considers a setting where the bidders valuations are positively correlated between the items and are both weakly increasing with respect to a one-dimensional type. Levin shows that, under regularity condition, this case can be solved using Myerson's very method. Our work can be seen as a complement of Levin's setting to the negative correlation setting.
@cite_7
1966404657
Abstract This paper considers the optimal selling mechanism for complementary items. When buyers are perfectly symmetric, the optimal procedure is to bundle the items and run a standard auction. In general, however, bundling the items is not necessarily desirable, and the standard auctions do not maximize revenue. Moreover, the optimal auction allocation may not be socially efficient since the auction must discriminate against bidders who have strong incentives to misrepresent their true preferences. Journal of Economic Literature Classification Number: D44.