2004 | OriginalPaper | Buchkapitel
Truthful Mechanisms for Generalized Utilitarian Problems
verfasst von : G. Melideo, P. Penna, G. Proietti, R. Wattenhofer, P. Widmayer
Erschienen in: Exploring New Frontiers of Theoretical Informatics
Verlag: Springer US
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper we investigate extensions of the well-known Vickrey-Clarke-Groves (VCG)mechanisms to problems whose objective function is not utilitarian and whose agents’ utilities are not quasi-linear. We provide a generalization of utilitarian problems,termed consistent problems, and prove that every consistent problem admits a truthful mechanism. These mechanisms,termed VCG-consistent (VCGc) mechanisms,can be seen as a natural extension of VCG mechanisms for utilitarian problems.We then investigate extensions/restrictions of consistent problems. This yields three classes of problems for which (i) VCGc mechanisms are the only truthful mechanisms, (ii) no truthful VCGc mechanism exists, and (iii) no truthful mechanism exists, respectively. Showing that a given problem is in one of these three classes is straightforward, thus yielding a simple way to see whether VCGc mechanisms are appropriate or not.Finally, we apply our results to a number of basic non-utilitarian problems.