2016 · 35 citations · 25 references
BusinessDecision SciencesAuction TheoryDecision TheoryOptimizationBidder Valuation ModelsCombinatorial AuctionsPrivate-value AuctionsReserve PricesReserve ValuationRevenue OptimizationAuction AlgorithmsAuctions With Reserve PricesLearning Reserve PricesLearning ValuationsMatroid OptimizationMatroid ValuationsPolynomial-time Approximation SchemeReserve Price Optimization
We study the problem of computing and learning non-anonymous reserve prices to maximize revenue. We first define the {\sc Maximizing Multiple Reserves (MMR)} problem in single-parameter matroid environments, where the input is $m$ valuation profiles v^1,...,v^m, indexed by the same n bidders, and the goal is to compute the vector r of (non-anonymous) reserve prices that maximizes the total revenue obtained on these profiles by the VCG mechanism with reserves r. We prove that the problem is APX-hard, even in the special case of single-item environments, and give a polynomial-time 1/2-approximation algorithm for it in arbitrary matroid environments.
25
Roger B. Myerson · Mathematics of Operations Research · 1981 · 6.1K citations
Simple versus optimal mechanisms
Jason D. Hartline, Tim Roughgarden · 2009 · 330 citations