Abstract:

An object is allocated among a number of agents. The optimal allocation depends on the agents' information about their peers, but each agent wants the object for themself. Monetary transfers are unavailable. We study optimal dominant-strategy incentive-compatible (DSIC) mechanisms, and provide a characterization using graph-theoretic techniques. Stochastic mechanisms allow for a significantly more flexible aggregation of reports than deterministic mechanisms: the set of stochastic extreme points of the set of DSIC mechanisms is an order of magnitude larger than the set of deterministic DSIC mechanisms. Further, the problem of determining an optimal deterministic DSIC mechanism is NP-hard. We then make a case for the use of approximately optimal DSIC mechanisms. We present two economically interpretable classes of mechanisms that guarantee a significant fraction of the optimal value and are asymptotically optimal if there are many agents and agents are informationally small.

For further information please contact: erika.somma@unibocconi.it