A Caltech Library Service

Mechanism Design Over Discrete Domains

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.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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:
URLURL TypeDescription
Additional Information:© 2008 ACM. Supported by grants from the Israel Science Foundation.
Funding AgencyGrant Number
Isreal Science FoundationUNSPECIFIED
Subject Keywords:Algorithms, Economics, Theory, Game Theory, Mechanism Design
Classification Code:F.m [ Theory of Computation ]: MISCELLANEOUS
Record Number:CaltechAUTHORS:20161201-133336339
Persistent URL:
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=
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:72500
Deposited On:02 Dec 2016 02:30
Last Modified:11 Nov 2021 05:02

Repository Staff Only: item control page