Mu'alem, Ahuva and Schapira, Michael (2008) Mechanism Design Over Discrete Domains. In: EC '08 Proceedings of the 9th ACM conference on Electronic commerce. ACM , New York, NY, pp. 31-37. ISBN 978-1-60558-169-9. https://resolver.caltech.edu/CaltechAUTHORS:20161201-133336339
Full text is not posted in this repository. Consult Related URLs below.
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20161201-133336339
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].
| Item Type: | Book Section | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Related URLs: |
| |||||||||
| Additional Information: | © 2008 ACM. Supported by grants from the Israel Science Foundation. | |||||||||
| Funders: |
| |||||||||
| Subject Keywords: | Algorithms, Economics, Theory, Game Theory, Mechanism Design | |||||||||
| Classification Code: | F.m [ Theory of Computation ]: MISCELLANEOUS | |||||||||
| DOI: | 10.1145/1386790.1386797 | |||||||||
| Record Number: | CaltechAUTHORS:20161201-133336339 | |||||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20161201-133336339 | |||||||||
| Official Citation: | Ahuva Mu'alem and Michael Schapira. 2008. Mechanism design over discrete domains. In Proceedings of the 9th ACM conference on Electronic commerce (EC '08). ACM, New York, NY, USA, 31-37. DOI=http://dx.doi.org/10.1145/1386790.1386797 | |||||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||
| ID Code: | 72500 | |||||||||
| Collection: | CaltechAUTHORS | |||||||||
| Deposited By: | INVALID USER | |||||||||
| Deposited On: | 02 Dec 2016 02:30 | |||||||||
| Last Modified: | 11 Nov 2021 05:02 |
Repository Staff Only: item control page
