Efficient Auctions with Identity-Dependent Negative Externalities

摘要: We investigate a class of single-item multi-supply auctions (including digital goods with unlimited supply) bidders who have identity-based negative externalities. In such an auction, each bidder has set competitors. Her private valuation from winning item decreases the number her Negative externalities are prevalent in many applications, which auctioned play role future interactions among auction's participants, as patent licensing and sponsored search auctions. However, development is stymied by computational difficulty underlying welfare maximization allocation problem; even without consideration truthfulness, problem social general competition relations NP-hard hard to approximate within constant factor (unless P=NP). this work, we design polynomial time strategy-proof mechanisms under different restrictions on graph structure. Our results can be summarized follows. (1) When only one competitor, propose truthful maximizing mechanism. (2) (1 + e )-approximation mechanism when planar. (3) give two ar- bitrary relations, approximation ratio (n/ log n) [(d 1)/3], respectively, where d maximum degree "undirected" graph.