Shahar Dobzinski
Noam Nisan
ABSTRACT
We exhibit incentive compatible multi-unit auctions that are not affine maximizers (i.e., are not of the VCG family) and yet approximate the social welfare to within a factor of 1+ε. For the case of two-item two-bidder auctions we show that these auctions, termed Triage auctions, are the only scalable ones that give an approximation factor better than 2. "Scalable" means that the allocation does not depend on the units in which the valuations are measured. We deduce from this that any scalable computationally-efficient incentive-compatible auction for m items and n ≥ 2 bidders cannot approximate the social welfare to within a factor better than 2. This is in contrast to arbitrarily good approximations that can be reached under computational constraints alone, and in contrast to the existence of incentive-compatible mechanisms that achieve the optimal allocation.
- Aaron Archer and Éva Tardos. Truthful mechanisms for one-parameter agents. In FOCS'01. Google Scholar
Digital Library
- Itai Ashlagi, Shahar Dobzinski, and Ron Lavi. An optimal lower bound for anonymous scheduling mechanisms. In EC'09. Google ScholarDigital Library
- Yair Bartal, Rica Gonen, and Noam Nisan. Incentive compatible multi unit combinatorial auctions. In TARK'03. Google ScholarDigital Library
- Sushil Bikhchandani, Shurojit Chatterji, Ron Lavi, Ahuva Mu'alem, Noam Nisan, and Arunava Sen. Weak monotonicity characterizes deterministic dominant-strategy implementation. Econometrica, 74(4):1109--1132, July 2006.Google ScholarCross Ref
- Patrick Briest, Piotr Krysta, and Berthold Vöcking. Approximation techniques for utilitarian mechanism design. In STOC'05. Google ScholarDigital Library
- Dave Buchfuhrer, Shaddin Dughmi, Hu Fu, Robert Kleinberg, Elchanan Mossel, Christos Papadimitriou, Michael Schapira, Yaron Singer, and Chris Umans. Inapproximability for vcg-based combinatorial auctions. In SODA'10. Google ScholarDigital Library
- George Christodoulou, Elias Koutsoupias, and Angelina Vidali. A lower bound for scheduling mechanisms. In SODA'07. Google ScholarDigital Library
- George Christodoulou and Annamária Kovács. A deterministic truthful PTAS for scheduling related machines. In SODA'10. Google ScholarDigital Library
- Peerapong Dhangwatnotai, Shahar Dobzinski, Shaddin Dughmi, and Tim Roughgarden. Truthful approximation schemes for single-parameter agents. In FOCS'08. Google ScholarDigital Library
- Shahar Dobzinski. An impossibility result for truthful combinatorial auctions with submodular valuations. In STOC'11. Google ScholarDigital Library
- Shahar Dobzinski. Two randomized mechanisms for combinatorial auctions. In APPROX'07. Google ScholarDigital Library
- Shahar Dobzinski and Shaddin Dughmi. On the power of randomization in algorithmic mechanism design. In FOCS'09. Google ScholarDigital Library
- Shahar Dobzinski and Noam Nisan. Limitations of vcg-based mechanisms. Preliminary version in STOC'07. Google ScholarDigital Library
- Shahar Dobzinski and Noam Nisan. Mechanisms for multi-unit auctions. In EC'07. Google ScholarDigital Library
- Shahar Dobzinski, Noam Nisan, and Michael Schapira. Approximation algorithms for combinatorial auctions with complement-free bidders. In STOC'05. Google ScholarDigital Library
- Shahar Dobzinski, Noam Nisan, and Michael Schapira. Truthful randomized mechanisms for combinatorial auctions. In STOC'06. Google ScholarDigital Library
- Shahar Dobzinski and Mukund Sundararajan. On characterizations of truthful mechanisms for combinatorial auctions and scheduling. In EC'08. Google ScholarDigital Library
- Uriel Feige. On maximizing welfare where the utility functions are subadditive. In STOC'06. Google ScholarDigital Library
- J. Green and J.J. Laffont. Characterization of satisfactory mechanism for the revelation of preferences for public goods. Econometrica, pages 427--438, 1977.Google ScholarCross Ref
- Ron Holzman, Noa Kfir-Dahav, Dov Monderer, and Moshe Tennenholtz. Bundling equilibrium in combinatrial auctions. Games and Economic Behavior, 47:104--123, 2004.Google ScholarCross Ref
- Elias Koutsoupias and Angelina Vidali. A lower bound of 1+phi for truthful scheduling mechanisms. In MFCS'07. Google ScholarDigital Library
- Ron Lavi, Ahuva Mu'alem, and Noam Nisan. Towards a characterization of truthful combinatorial auctions. In FOCS'03. Google ScholarDigital Library
- Ron Lavi and Chaitanya Swamy. Truthful and near-optimal mechanism design via linear programming. In FOCS'05. Google ScholarDigital Library
- Daniel Lehmann, Liadan Ita O'Callaghan, and Yoav Shoham. Truth revelation in approximately efficient combinatorial auctions. In JACM 49(5), pages 577--602, Sept. 2002. Google ScholarDigital Library
- Ahuva Mu'alem and Noam Nisan. Truthful approximation mechanisms for restricted combinatorial auctions. In AAAI'02. Google ScholarDigital Library
- Noam Nisan. 2007. Introduction to Mechanism Design (for Computer Scientists). In "Algorithmic Game Theory", N. Nisan, T. Roughgarden, E. Tardos and V. Vazirani, editors.Google Scholar
- Noam Nisan and Amir Ronen. Algorithmic mechanism design. In STOC'99.Google Scholar
- Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani. Algorithmic Game Theory. Cambridge University Press, New York, NY, USA, 2007. Google ScholarDigital Library
- Christos Papadimitriou, Michael Schapira, and Yaron Singer. On the hardness of being truthful. In FOCS'08. Google ScholarDigital Library
- Kevin Roberts. The characterization of implementable choice rules. In Jean-Jacques Laffont, editor, Aggregation and Revelation of Preferences. Papers presented at the first European Summer Workshop of the Economic Society, pages 321--349. North-Holland, 1979.Google Scholar
- Michael E. Saks and Lan Yu. Weak monotonicity suffices for truthfulness on convex domains. In EC'05. Google ScholarDigital Library
- W. Vickrey. Counterspeculation, auctions and competitive sealed tenders. Journal of Finance, pages 8--37, 1961.Google ScholarCross Ref
Index Terms
- Multi-unit auctions: beyond roberts
Recommendations
Mechanisms for multi-unit auctions
EC '07: Proceedings of the 8th ACM conference on Electronic commerceWe present an incentive-compatible polynomial-time approximation scheme for multi-unit auctions with general k-minded playervaluations. The mechanism fully optimizes over an appropriately chosen sub-range of possible allocations and then uses VCG ...
Walrasian pricing in multi-unit auctions
AbstractMulti-unit auctions are a paradigmatic model of resource allocation, where a seller brings multiple units of a good to a set of buyers equipped with monetary budgets. It is well known that Walrasian equilibria do not always exist in ...
Highlights- We consider multi-unit auctions with budgets and design a best possible envy-free and prior-free mechanism.
What Format for Multi-Unit Multiple-Bid Auctions?
This paper uses computational experiments where bidders learn over nonlinear bidding strategies to compare outcomes for alternative pricing format for multi-unit multiple-bid auctions. Multi-unit multiple-bid auctions, in which bidders are allowed to ...
Comments