Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published June 2008 | public
Journal Article

Characterizing Truthfulness In Discrete Domains

Abstract

Algorithmic mechanism design [9; 10] focuses on the design of algorithms that aim to achieve global objectives in settings in which the "input" is provided by self-interested strategic players2. This necessitates the design of algorithms that are incentive-compatible (a.k.a. truthful 3) in the sense that players are incentivized via payments to behave as instructed. The most natural approach to designing incentive-compatible algorithms is coming up with an algorithm and an explicit payment scheme that guarantees its incentive-compatibility. However, finding appropriate payments is often a difficult, setting-specific, task, which is mostly achievable for very simple types of algorithms.

Additional Information

© 2008 ACM. Supported by grants from the Israel Science Foundation.

Additional details

Created:
August 19, 2023
Modified:
October 23, 2023