NDLI: Truth revelation in approximately efficient combinatorial auctions

Content Provider	ACM Digital Library
Author	Lehmann, Daniel Oallaghan, Liadan Ita Shoham, Yoav
Copyright Year	2002
Abstract	Some important classical mechanisms considered in Microeconomics and Game Theory require the solution of a difficult optimization problem. This is true of mechanisms for combinatorial auctions, which have in recent years assumed practical importance, and in particular of the gold standard for combinatorial auctions, the Generalized Vickrey Auction (GVA). Traditional analysis of these mechanisms---in particular, their truth revelation properties---assumes that the optimization problems are solved precisely. In reality, these optimization problems can usually be solved only in an approximate fashion. We investigate the impact on such mechanisms of replacing exact solutions by approximate ones. Specifically, we look at a particular greedy optimization method. We show that the GVA payment scheme does not provide for a truth revealing mechanism. We introduce another scheme that does guarantee truthfulness for a restricted class of players. We demonstrate the latter property by identifying natural properties for combinatorial auctions and showing that, for our restricted class of players, they imply that truthful strategies are dominant. Those properties have applicability beyond the specific auction studied.
Starting Page	577
Ending Page	602
Page Count	26
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/585265.585266
Journal	Journal of the ACM (JACM)
Volume Number	49
Issue Number	5
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2002-09-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Combinatorial auctions Computational complexity Mechanism design
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Bayesian Combinatorial Auctions

Optimal Mechanisms for Combinatorial Auctions and Combinatorial Public Projects via Convex Rounding

Single-value combinatorial auctions and algorithmic implementation in undominated strategies

Impossibility Results for Truthful Combinatorial Auctions with Submodular Valuations

Truth revelation in approximately efficient combinatorial auctions (1999).

Truth revelation in approximately efficient combinatorial auctions

Truthful and Near-Optimal Mechanism Design via Linear Programming

Efficient Exercising of Switching Elements in Combinatorial Nets

Computational Complexity and Probability Constructions

Truth revelation in approximately efficient combinatorial auctions

Similar Documents

Bayesian Combinatorial Auctions

Optimal Mechanisms for Combinatorial Auctions and Combinatorial Public Projects via Convex Rounding

Single-value combinatorial auctions and algorithmic implementation in undominated strategies

Impossibility Results for Truthful Combinatorial Auctions with Submodular Valuations

Truth revelation in approximately efficient combinatorial auctions (1999).

Truth revelation in approximately efficient combinatorial auctions

Truthful and Near-Optimal Mechanism Design via Linear Programming

Efficient Exercising of Switching Elements in Combinatorial Nets

Computational Complexity and Probability Constructions

Truth revelation in approximately efficient combinatorial auctions