NDLI: Approximate Mechanism Design without Money

Please wait, while we are loading the content...

Approximate Mechanism Design without Money

Content Provider	ACM Digital Library
Author	Procaccia, Ariel D. Tennenholtz, Moshe
Copyright Year	2013
Abstract	The literature on algorithmic mechanism design is mostly concerned with game-theoretic versions of optimization problems to which standard economic money-based mechanisms cannot be applied efficiently. Recent years have seen the design of various truthful approximation mechanisms that rely on payments. In this article, we advocate the reconsideration of highly structured optimization problems in the context of mechanism design. We explicitly argue for the first time that, in such domains, approximation can be leveraged to obtain truthfulness without resorting to payments. This stands in contrast to previous work where payments are almost ubiquitous and (more often than not) approximation is a necessary evil that is required to circumvent computational complexity. We present a case study in approximate mechanism design without money. In our basic setting, agents are located on the real line and the mechanism must select the location of a public facility; the cost of an agent is its distance to the facility. We establish tight upper and lower bounds for the approximation ratio given by strategyproof mechanisms without payments, with respect to both deterministic and randomized mechanisms, under two objective functions: the social cost and the maximum cost. We then extend our results in two natural directions: a domain where two facilities must be located and a domain where each agent controls multiple locations.
Starting Page	1
Ending Page	26
Page Count	26
File Format	PDF
ISSN	21678375
e-ISSN	21678383
DOI	10.1145/2542174.2542175
Volume Number	1
Issue Number	4
Journal	ACM Transactions on Economics and Computation (TEAC)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-12-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Approximation Mechanism design
Content Type	Text
Resource Type	Article
Subject	Economics and Econometrics Marketing Computational Mathematics Statistics and Probability Computer Science

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

Mechanism Design with Strategic Mediators

Local Computation Mechanism Design

Selling in Exclusive Markets: Some Observations on Prior-Free Mechanism Design

Payment Rules through Discriminant-Based Classifiers

Privacy Auctions for Recommender Systems

Optimal Contest Design for Simple Agents

On Random Sampling Auctions for Digital Goods

Display Advertising Auctions with Arbitrage

Truthfulness Flooded Domains and the Power of Verification for Mechanism Design

Approximate Mechanism Design without Money

Similar Documents

Mechanism Design with Strategic Mediators

Local Computation Mechanism Design

Selling in Exclusive Markets: Some Observations on Prior-Free Mechanism Design

Payment Rules through Discriminant-Based Classifiers

Privacy Auctions for Recommender Systems

Optimal Contest Design for Simple Agents

On Random Sampling Auctions for Digital Goods

Display Advertising Auctions with Arbitrage

Truthfulness Flooded Domains and the Power of Verification for Mechanism Design

Approximate Mechanism Design without Money