NDLI: Single-value combinatorial auctions and algorithmic implementation in undominated strategies

Content Provider	ACM Digital Library
Author	Babaioff, Moshe Lavi, Ron Pavlov, Elan
Copyright Year	2009
Abstract	In this article, we are interested in general techniques for designing mechanisms that approximate the social welfare in the presence of selfish rational behavior. We demonstrate our results in the setting of Combinatorial Auctions (CA). Our first result is a general deterministic technique to decouple the algorithmic allocation problem from the strategic aspects, by a procedure that converts any $\textit{algorithm}$ to a dominant-strategy ascending $\textit{mechanism}.$ This technique works for any single value domain, in which each agent has the same value for each desired outcome, and this value is the only private information. In particular, for “single-value CAs”, where each player desires any one of several different bundles but has the same value for each of them, our technique converts any approximation algorithm to a dominant strategy mechanism that almost preserves the original approximation ratio. Our second result provides the first computationally efficient deterministic mechanism for the case of single-value multi-minded bidders (with private value and private desired bundles). The mechanism achieves an approximation to the social welfare which is close to the best possible in polynomial time (unless P=NP). This mechanism is an algorithmic implementation in undominated strategies, a notion that we define and justify, and is of independent interest.
Starting Page	1
Ending Page	32
Page Count	32
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/1462153.1462157
Journal	Journal of the ACM (JACM)
Volume Number	56
Issue Number	1
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2009-02-03
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Combinatorial auctions Incentives Mechanism design Undominated strategies
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

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

Bayesian Combinatorial Auctions

Truth revelation in approximately efficient combinatorial auctions

Single-value combinatorial auctions and algorithmic implementation in undominated strategies (2011)

Single-value combinatorial auctions and implementation in undominated strategies

Truthful Mechanisms with Implicit Payment Computation

Empirical hardness models: Methodology and a case study on combinatorial auctions

The Synthesis of Algorithmic Systems

Impossibility Results for Truthful Combinatorial Auctions with Submodular Valuations

Single-value combinatorial auctions and algorithmic implementation in undominated strategies

Similar Documents

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

Bayesian Combinatorial Auctions

Truth revelation in approximately efficient combinatorial auctions

Single-value combinatorial auctions and algorithmic implementation in undominated strategies (2011)

Single-value combinatorial auctions and implementation in undominated strategies

Truthful Mechanisms with Implicit Payment Computation

Empirical hardness models: Methodology and a case study on combinatorial auctions

The Synthesis of Algorithmic Systems

Impossibility Results for Truthful Combinatorial Auctions with Submodular Valuations

Single-value combinatorial auctions and algorithmic implementation in undominated strategies