NDLI: A sufficient condition for truthfulness with single parameter agents

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

Truthful auctions for pricing search keywords

A sufficient condition for truthfulness with single parameter agents

Combinatorial agency

Approximation algorithms and online mechanisms for item pricing

Learning from revealed preference

Optimal pricing with recommender systems

Welfare maximization in congestion games

Implementation with a bounded action space

Non-cooperative multicast and facility location games

Computing the optimal strategy to commit to

Computing pure nash equilibria in graphical games via markov random fields

Nash equilibria in graphical games on trees revisited

Bid expressiveness and clearing algorithms in multiattribute double auctions

(In)Stability properties of limit order dynamics

Incentive-compatible interdomain routing

Efficiency and nash equilibria in a scrip system for P2P networks

Playing games in many possible worlds

Finding equilibria in large sequential games of imperfect information

Multi-attribute coalitional games

The sequential auction problem on eBay: an empirical analysis and a solution

Minimum payments that reward honest reputation feedback

Networks preserving evolutionary equilibria and the power of randomization

Controlling a supply chain agent using value-based decomposition

An analysis of alternative slot auction designs for sponsored search

The dynamics of viral marketing

Random popular matchings

Multi-unit auctions with unknown supply

Scouts, promoters, and connectors: the roles of ratings in nearest neighbor collaborative filtering

An adaptive algorithm for selecting profitable keywords for search-based advertising services

The computational complexity of nash equilibria in concisely represented games

Incentives engineering for structured P2P systems - a feasibility demonstration using economic experiments

B2C e-commerce development in Africa: case study of Botswana

Braess's paradox in large random graphs

Empirical mechanism design: methods, with application to a supply-chain scenario

A privacy-preserving collaborative filtering scheme with two-way communication

Can online reviews reveal a product's true quality?: empirical findings and analytical modeling of Online word-of-mouth communication

A sufficient condition for truthfulness with single parameter agents

Content Provider	ACM Digital Library
Author	Andelman, Nir Mansour, Yishay
Abstract	We consider the task of designing truthful mechanisms for single parameter agents. We prove a general sufficient condition for truthfulness when each agent's valuation function for each possible outcome is a one-dimensional function of its type, continuous everywhere and differentiable almost everywhere. For certain types of natural valuation functions, our condition is also necessary. Our condition extends both the Mirrlees-Spence condition [25, 17], applicable only for differentiable real allocations, and Archer and Tardos' single parameter characterization [4], which assumes an agent's valuation is linear in its type.We demonstrate the simplicity of testing our condition by showing that classical criteria for truthfulness in combinatorial problems such as auctions and machine scheduling can be derived from our condition. In addition, we use our condition to derive results for new single parameter problems, which have not been previously analyzed.We also consider combinatorial problems where the true types of agents affect the valuation of each other, such as in machine scheduling with selfish jobs. In such cases there are only degenerate dominant strategy mechanisms. We show that the same condition can be used to design mechanisms which are ex-post truthful, meaning that the outcome where all agents cooperate and report their true type is a Nash equilibrium. We demonstrate the power of this condition by applying it on the problem of machine scheduling with strategic job owners, previously presented in [5]. We give a constant approximation ratio algorithms for the original problem and to the double setting where both jobs and machines are strategic.
Starting Page	8
Ending Page	17
Page Count	10
File Format	PDF
ISBN	1595932364
DOI	10.1145/1134707.1134709
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2006-06-11
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Algorithmic mechanism design Algorithms Approximation Game theory
Content Type	Text
Resource Type	Article

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

Truthful Approximation Schemes for Single-Parameter Agents

Welfare maximization and truthfulness in mechanism design with ordinal preferences

Truthful Approximation Schemes for Single-Parameter Agents

A sufficient condition for truthfulness with single parameter agents (2006).

Abstract the power of verification for one-parameter agents.

Approaching utopia: strong truthfulness and externality-resistant mechanisms

On the truthfulness and the approximation for scheduling selfish tasks

Black-Box Reductions in Mechanism Design

On the Power of Randomization in Algorithmic Mechanism Design

A sufficient condition for truthfulness with single parameter agents

Similar Documents

Truthful Approximation Schemes for Single-Parameter Agents

Welfare maximization and truthfulness in mechanism design with ordinal preferences

Truthful Approximation Schemes for Single-Parameter Agents

A sufficient condition for truthfulness with single parameter agents (2006).

Abstract the power of verification for one-parameter agents.

Approaching utopia: strong truthfulness and externality-resistant mechanisms

On the truthfulness and the approximation for scheduling selfish tasks

Black-Box Reductions in Mechanism Design

On the Power of Randomization in Algorithmic Mechanism Design

A sufficient condition for truthfulness with single parameter agents