Published July 2008
| public
Book Section - Chapter
Mechanism Design Over Discrete Domains
- Creators
- Mu'alem, Ahuva
- Schapira, Michael
- Other:
- Fortnow, Lance
Abstract
Often, we wish to design incentive-compatible algorithms for settings in which the players' private information is drawn from discrete domains (e.g., integer values). Our main result is identifying discrete settings in which an algorithm can be made incentive-compatible iff the function it computes upholds a simple monotonicity constraint, known as weak-monotonicity. To the best of our knowledge, this is the first such characterization of incentive-compatibility in discrete domains (such characterizations were previously known only for inherently non-discrete domains, e.g., convex domains). We demonstrate the usefulness of this result by showing an application to the TCP-inspired congestion-control problem presented in [20].
Additional Information
© 2008 ACM. Supported by grants from the Israel Science Foundation.Additional details
- Eprint ID
- 72500
- Resolver ID
- CaltechAUTHORS:20161201-133336339
- Isreal Science Foundation
- Created
-
2016-12-02Created from EPrint's datestamp field
- Updated
-
2021-11-11Created from EPrint's last_modified field