On approximating optimal auctions

摘要: We study the following problem: A seller wishes to sell an item a group of self-interested agents. Each agent i has privately known valuation vi for object. Given distribution on these valuations, our goal is construct auction that maximizes seller's expected revenue (optimal auction). The must be incentive compatible and satisfy individual rationality. present simple generic guarantees at least half optimal revenue. generalize this result in several directions, particular, case multiple copies with unit demand. Our requires ability learn (or compute) polynomial time conditional maximal valuation, given valuations other show some sense essential. Finally we suggest generalization argue it will generate which close reasonable distributions. In particular under independence assumption