Years and Authors of Summarized Original Work
-
2005; Briest, Krysta, Vöcking
Problem Definition
This problem deals with the design of efficiently computable incentive compatible, or truthful, mechanisms for combinatorial optimization problems with selfish one-parameter agents and a single seller. The focus is on approximation algorithms for NP-hard mechanism design problems. These algorithms need to satisfy certain monotonicity properties to ensure truthfulness.
A one parameter agent is an agent who as her private data has some resource as well as a valuation, i.e., the maximum amount of money she is willing to pay for this resource. Sometimes, however, the resource is assumed to be known to the mechanism. The scenario where a single seller offers these resources to the agents is primarily considered. Typically, the seller aims at maximizing the social welfare or her revenue. The work by Briest, Krysta and Vöcking [6] will mostly be considered, but also other existing models and...
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
Notes
- 1.
In the case of unknown single-minded bidders, the bidders have as private data not only their valuations (as in the case of known single-minded bidders) but also the sets they demand.
Recommended Reading
Andelman N, Mansour Y (2006) A sufficient condition for truthfulness with single parameter agents. In: Proceedings of the 8th ACM conference on electronic commerce (EC), Ann Arbor, June 2006
Archer A, Papadimitriou CH, Talwar K, Tardos E (2003) An approximate truthful mechanism for combinatorial auctions with single parameter agents. In: Proceedings of the 14th annual ACM–SIAM symposium on discrete algorithms (SODA), Baltimore, pp 205–214
Awerbuch B, Azar Y, Meyerson A (2003) Reducing truth-telling online mechanisms to online optimization. In: Proceedings of the 35th annual ACM symposium on theory of computing (STOC), San Diego
Azar Y, Gamzu I, Gutner S (2007) Truthful unsplittable flow for large capacity networks. In: Proceedings of the 19th annual ACM symposium on parallelism in algorithms and architectures (SPAA), pp 320–329
Bartal Y, Gonen R, Nisan N (2003) Incentive compatible multi unit combinatorial auctions. In: Proceedings of the 9th conference on theoretical aspects of rationality and knowledge (TARK), ACM Press, pp 72–87. http://doi.acm.org/10.1145/846241.846250
Briest P, Krysta P, Vöcking B (2005) Approximation techniques for utilitarian mechanism design. In: Proceedings of the 37th annual ACM symposium on theory of computing (STOC), pp 39–48
Fiat A, Goldberg AV, Hartline JD, Karlin AR (2002) Competitive generalized auctions. In: Proceedings of the 34th annual ACM symposium on theory of computing (STOC), pp 72–81
Goldberg AV, Hartline JD, Wright A (2001) Competitive auctions and digital goods. In: Proceedings of the 12th annual ACM–SIAM symposium on discrete algorithms (SODA), pp 735–744
Krysta P (2005) Greedy approximation via duality for packing, combinatorial auctions and routing. In: Proceedings of the 30th international conference on mathematical foundations of computer science (MFCS). Lecture notes in computer science, vol 3618, pp 615–627
Lehmann DJ, O'Callaghan LI, Shoham Y (1999) Truth revelation in approximately efficient combinatorial auctions. In: Proceedings of the 1st ACM conference on electronic commerce (EC), pp 96–102
Mu'alem A, Nisan N (2002) Truthful approximation mechanisms for restricted combinatorial auctions. In: Proceedings of the 18th national conference on artificial intelligence. AAAI, pp 379–384
Myerson RB (1981) Optimal auction design. Math Oper Res 6:58–73
Ronen A (2001) On approximating optimal auctions (extended abstract). In: Proceedings of the 3rd ACM conference on electronic commerce (EC), pp 11–17
Ronen A, Saberi A (2002) On the hardness of optimal auctions. In: Proceedings of the 43rd annual IEEE symposium on foundations of computer science (FOCS), pp 396–405
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer Science+Business Media New York
About this entry
Cite this entry
Krysta, P., Vöcking, B. (2016). Utilitarian Mechanism Design for Single-Minded Agents. In: Kao, MY. (eds) Encyclopedia of Algorithms. Springer, New York, NY. https://doi.org/10.1007/978-1-4939-2864-4_454
Download citation
DOI: https://doi.org/10.1007/978-1-4939-2864-4_454
Published:
Publisher Name: Springer, New York, NY
Print ISBN: 978-1-4939-2863-7
Online ISBN: 978-1-4939-2864-4
eBook Packages: Computer ScienceReference Module Computer Science and Engineering