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 equal-cost mechanisms with monitoring.
Joint work with Dimitris Fotakis and Carmine Ventre.
29/11/2018