2012 | OriginalPaper | Buchkapitel
Mechanisms and Impossibilities for Truthful, Envy-Free Allocations
verfasst von : Michal Feldman, John Lai
Erschienen in: Algorithmic Game Theory
Verlag: Springer Berlin Heidelberg
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
We study mechanisms for combinatorial auctions that are simultaneously incentive compatible (IC), envy free (EF) and efficient in settings with
capacitated
valuations — a subclass of subadditive valuations introduced by Cohen et al. [4]. Capacitated agents have valuations which are additive up to a publicly known capacity. The main result of Cohen et al. [4] is the assertion that the Vickrey-Clarke-Groves mechanism with Clarke pivot payments is EF (and clearly IC and efficient) in the case of homogeneous capacities. The main open problem raised by Cohen et al. [4] is whether the existence result extends beyond homogeneous capacities. We resolve the open problem, establishing that no mechanism exists that is simultaneously IC, EF and efficient for capacitated agents with heterogeneous capacities. In addition, we establish the existence of IC, EF, and efficient mechanisms in the special cases of capacitated agents with heterogeneous capacities, where (i) there are only two items; or (ii) the individual item values are binary. Finally, we show that the last existence result does not extend to the stronger notion of
Walrasian
mechanisms, i.e. mechanisms whose allocation and payments correspond to a Walrasian equilibrium.