Abstract
This paper characterizes the family of truthful double-sided auctions. Despite the importance of double-sided auctions to market design, to date no characterization of truthful double-sided auctions was made. This paper characterizes truthful mechanisms for double-sided auctions by generalizing Roberts’ classic result [18], to show that truthful double-sided auctions must ”almost” be affine maximizers.
Our main result of characterizing double-sided auctions required the creation of a new set of tools, reductions that preserve economic properties. This paper utilizes two such reductions; a truth-preserving reduction and a non-affine preserving reduction. The truth-preserving reduction is used to reduce the double-sided auction to a special case of a combinatorial auction to make use of the impossibility result proved in [11]. Intuitively, our proof shows that truthful double-sided auctions are as hard to design as truthful combinatorial auctions.
Two important concepts are developed in addition to the main result. First, the form of reduction used in this paper is of independent interest as it provides a means for comparing mechanism design problems by design difficulty. Second, we define the notion of extension of payments; which given a set of payments for some players finds payments for the remaining players. The extension payments maintain the truthful and affine maximization properties.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Archer, A., Tardos, E.: Truthful Mechanisms for one-parameter agents. In: Proceeding of 42th FOCS 2001 (2001)
Bartal, Y., Gonen, R., LaMura, P.: Negotiation-Range Mechanisms:Exploring the Limits of Truthful Efficient Markets. In: Proceeding of 5th EC 2004 (2004)
Bartal, Y., Gonen, R., Nisan, N.: Incentive Compatible Multi-Unit Combinatorial Auctions. In: Proc. of TARK 2003, pp. 72–87 (June 2003)
Clarke, E.H.: Multipart Pricing of Public Goods. journal Public Choice 2, 17–33 (1971)
Dobzinski, S., Nisan, N., Schapira, M.: Truthful Randomized Mechanisms for Combinatorial Auctions. In: Proceeding of 38th STOC 2006 (2006)
Feige, U., Goldwasser, S., Lovasz, L., Safra, S., Szegedy, M.: Interactive Proofs and the Hardness of Approximating Cliques. Journal of the ACM 43, 268–292 (1996)
Gonen, M., Gonen, R., Pavlov, E.: Characterizing Truthful Market Design. http://www.cs.huji.ac.il/~rgonen or http://www.cs.huji.ac.il/~rgonen
Gonen, R., Lehmann, D.: Optimal Solutions for Multi-Unit Combinatorial Auctions: Branch and Bound Heuristics. In: Proc. of EC 2000, pp. 13–20 (October 2000)
Groves, T.: Incentives in teams. journal Econometrica 41, 617–631 (1973)
Lehmann, D., O’Callaghan, L.I., Shoham, Y.: Truth Revelation in Approximately Efficient Combinatorial Auctions. Journal of ACM 49(5), 577–602 (2002)
Lavi, R., Mu’alem, A., Nisan, N.: Towards a Characterization of Truthful Combinatorial Auctions. In: Proceeding of 44th FOCS 2003 (2003)
McAfee, R.: A Dominant Strategy Double Auction. Journal of economic Theory 56, 434–450 (1992)
Moulin, H.: The Strategy of Social Choice. North-Holland, Amsterdam (1983)
Mu’alem, A., Nisan, N.: Truthful Approximation Mechanisms for Restricted Combinatorial Auctions. In: Proceeding of AAAI 2002 (2002)
Nisan, N.: Algorithms for Selfish Agents. In: Meinel, C., Tison, S. (eds.) STACS 99. LNCS, vol. 1563, Springer, Heidelberg (1999)
Nisan, N., Ronen, A.: Computationally Feasible VCG mechanisms. In: Proceeding of 2nd EC 2000 and Journal of Games and Economic Behavior, 35, 166-196 (2001)
Papadimitriou, C.: Algorithms, Games, and the Internet. In: Proceeding of 33rd STOC 2001 (2001)
Roberts, K.: The Characterization of Implementable Choice Rules. In: Laffont, J.-J. (ed.) Aggregation and Revelation Of Preferences. Papers presented at the first European Summer Workshop of the Econometric Society, North-Holland, Amsterdam (1979)
Satterthwaite, M.: Strategy-Proofness and Arrow’s Conditions: Existence and Correspondence Theorem for Voting Procedures and social Welfare Functions. Journal of Economic Theory 10, 187–217 (1975)
Vickrey, W.: Counterspeculation, Auctions and Competitive Sealed Tenders. Journal of Finance 16, 8–37 (1961)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gonen, M., Gonen, R., Pavlov, E. (2007). Characterizing Truthful Market Design. In: Deng, X., Graham, F.C. (eds) Internet and Network Economics. WINE 2007. Lecture Notes in Computer Science, vol 4858. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77105-0_65
Download citation
DOI: https://doi.org/10.1007/978-3-540-77105-0_65
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-77104-3
Online ISBN: 978-3-540-77105-0
eBook Packages: Computer ScienceComputer Science (R0)