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.
Negatively correlated valuations are not uncommon in the literature. For example, consider an instance of the well-known facility location game with two facilities @cite_18 : agents are interested in services from the two facilities, located at the endpoints of a street. Each agent's type is his her location on the street, between the two facilities. The cost (negative utility) to either facility, the same as in @cite_2 , is simply one's distance to that facility, so his overall costs (as well as valuations) sum up to a constant --- the length of the street.
@cite_18 @cite_2
2154843747 2108957189
We consider the problem of locating facilities in a metric space to serve a set of selfish agents. The cost of an agent is the distance between her own location and the nearest facility. The social cost is the total cost of the agents. We are interested in designing strategy-proof mechanisms without payment that have a small approximation ratio for social cost. A mechanism is a (possibly randomized) algorithm which maps the locations reported by the agents to the locations of the facilities. A mechanism is strategy-proof if no agent can benefit from misreporting her location in any configuration. This setting was first studied by Procaccia and Tennenholtz [21]. They focused on the facility game where agents and facilities are located on the real line. studied the mechanisms for the facility games in a general metric space [1]. However, they focused on the games with only one facility. In this paper, we study the two-facility game in a general metric space, which extends both previous models. We first prove an Ω(n) lower bound of the social cost approximation ratio for deterministic strategy-proof mechanisms. Our lower bound even holds for the line metric space. This significantly improves the previous constant lower bounds [21, 17]. Notice that there is a matching linear upper bound in the line metric space [21]. Next, we provide the first randomized strategy-proof mechanism with a constant approximation ratio of 4. Our mechanism works in general metric spaces. For randomized strategy-proof mechanisms, the previous best upper bound is O(n) which works only in the line metric space. The literature on algorithmic mechanism design is mostly concerned with game-theoretic versions of optimization problems to which standard economic money-based mechanisms cannot be applied efficiently. Recent years have seen the design of various truthful approximation mechanisms that rely on payments. In this article, we advocate the reconsideration of highly structured optimization problems in the context of mechanism design. We explicitly argue for the first time that, in such domains, approximation can be leveraged to obtain truthfulness without resorting to payments. This stands in contrast to previous work where payments are almost ubiquitous and (more often than not) approximation is a necessary evil that is required to circumvent computational complexity. We present a case study in approximate mechanism design without money. In our basic setting, agents are located on the real line and the mechanism must select the location of a public facility; the cost of an agent is its distance to the facility. We establish tight upper and lower bounds for the approximation ratio given by strategyproof mechanisms without payments, with respect to both deterministic and randomized mechanisms, under two objective functions: the social cost and the maximum cost. We then extend our results in two natural directions: a domain where two facilities must be located and a domain where each agent controls multiple locations.