Equal-Cost Mechanism Design with Monitoring

2^nd May 2018, 13:00
Piotr Krysta
University of Liverpool

Abstract

We consider the question of whether the transfers of truthful mechanisms can be defined in a way to make the cost of every agent equal. We want to marry this natural notion of equal-cost fairness with truthfulness. Given the known limitations of the Vickrey-Clarke-Groves (VCG) mechanism, which can be cast as a truthful equal-cost mechanism, we focus on monitoring – a paradigm wherein the designer can force overbidding agents to pay the reported bid. In this context, we show how and when approximation, of both optimisation and money burning objective functions, can be reconciled with this combination of fairness and truthfulness. We study within this paradigm three broad classes of optimisation problems: makespan machine scheduling, bottleneck network design and binary covering problems with social cost minimisation. For each of these classes we provide close upper and lower bounds on the approximation guarantees of truthful mechanisms.

Joint work with Dimitris Fotakis and Carmine Ventre.