Preference-Based Characterizations of Truthfulness and the Limited Expressiveness of Order-Based Domains

Abstract

An important direction in computational mechanism design is to characterize the space of choice functions that can be truthfully implemented. For this, one must carefully describe the class of preferences in a domain. For unrestricted preferences the domain is well-characterized, and small. Moreover, recent work [Lavi et al., 2003] has allowed for “order-based” preferences but found essentially the same (negative) characterization. However, most interesting domains have preferences that are still more structured than those allowed in the orderbased model. We highlight this issue in our paper, through many examples, thus demonstrating the limited applicability of this result. We propose extensions to the model of order-based domains to capture new preference structure, and conjecture that more positive characterizations for truthfulness are possible. We also advocate, in proposing a research direction for sufficient conditions for truthfulness, that attention be restricted to natural (critical-value based) payment functions.