The communication complexity of private value single-item auctions
AbstractIn this paper we present a new auction, the bisection auction, that can be used for the sale of a single indivisible object. We discuss the issue concerning the information revelation requirement of this auction and the associated amount of data that needs to be transmitted. We show that in the truthtelling equilibrium the bisection auction is economical in its demand for information on the valuations of the players. It requires the players to transmit less information bits to the auctioneer than the Vickrey and English auctions. In particular, we prove that for integer valuations uniformly distributed on the interval [0,L) the bisection auction of n players requires in expectation transmission of at most 2n + log L information bits by the players. Compared with the corresponding number in the Vickrey auction which is n log L, and in the English auction which is on average at least (1/3) nL, the bisection auction turns out to be the best performer.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by Maastricht University in its series Open Access publications from Maastricht University with number urn:nbn:nl:ui:27-12147.
Date of creation: 2006
Date of revision:
Publication status: Published in Operations research letters (2006) v.34, p.491-498
Contact details of provider:
Web page: http://www.maastrichtuniversity.nl/web/Home.htm
Other versions of this item:
- Grigorieva,Elena & Herings,Jean-Jacques & Müller,Rudolf & Vermeulen,Dries, 2004. "The communication complexity of private value single item auctions," Research Memoranda 052, Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization.
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Grigorieva, Elena & Herings, P. Jean-Jacques & Muller, Rudolf & Vermeulen, Dries, 2007.
"The private value single item bisection auction,"
Open Access publications from Maastricht University
urn:nbn:nl:ui:27-12149, Maastricht University.
- Engelbrecht-Wiggans, R. & Kahn, C.M., 1990.
"Protecting the Wnner: Second-price Versus Oral Auctions,"
University of Chicago - Economics Research Center
90-8, Chicago - Economics Research Center.
- Engelbrecht-Wiggans, Richard & Kahn, Charles M., 1991. "Protecting the winner : Second-price versus oral auctions," Economics Letters, Elsevier, vol. 35(3), pages 243-248, March.
- Kagel, John H & Harstad, Ronald M & Levin, Dan, 1987. "Information Impact and Allocation Rules in Auctions with Affiliated Private Values: A Laboratory Study," Econometrica, Econometric Society, vol. 55(6), pages 1275-1304, November.
- Groves, Theodore, 1973. "Incentives in Teams," Econometrica, Econometric Society, vol. 41(4), pages 617-31, July.
- Rothkopf, Michael H. & Harstad, Ronald M., 1994. "On the role of discrete bid levels in oral auctions," European Journal of Operational Research, Elsevier, vol. 74(3), pages 572-581, May.
- Rothkopf, Michael H & Teisberg, Thomas J & Kahn, Edward P, 1990. "Why Are Vickrey Auctions Rare?," Journal of Political Economy, University of Chicago Press, vol. 98(1), pages 94-109, February.
- Green, Jerry & Laffont, Jean-Jacques, 1977. "Characterization of Satisfactory Mechanisms for the Revelation of Preferences for Public Goods," Econometrica, Econometric Society, vol. 45(2), pages 427-38, March.
- Grigorieva Elena & Herings P. Jean-Jacques & Müller Rudolf & Vermeulen Dries, 2009.
"Fraction auctions: the tradeoff between effciency and running time,"
045, Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization.
- Grigorieva, Elena & Jean-Jacques Herings, P. & Müller, Rudolf & Vermeulen, Dries, 2012. "Fraction auctions: The tradeoff between efficiency and running time," European Journal of Operational Research, Elsevier, vol. 220(2), pages 577-587.
- Katerina Sherstyuk, 2011. "Complexity and bidder behavior in iterative auctions," Economics Bulletin, AccessEcon, vol. 31(4), pages 2769-2776.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (J.Odekerken).
If references are entirely missing, you can add them using this form.