Abstract

Mechanism design is concerned with decision making involving multiple self-interested participants. Each of the participants holds private information that is relevant to the quality of a decision. A mechanism designer has an objective such as maximising the total utility of the participants (utilitarian) or guaranteeing each participant a certain level of utility (egalitarian). To make the right decision according to the objective, the designer needs to reveal private information of the participants. Truthful revelation is possible with the help of Groves mechanisms that use monetary payments to ensure the participants cannot benefit by misreporting their private information. Until recently, virtually all the attention had been paid to one Groves mechanism called the Vickrey-Clarke-Groves (VCG) mechanism. In the last decade a series of papers started investigating whether there are other Groves mechanisms that are better than VCG for a given scenario and objective.

In this talk I will present general characterisation results along with an approach for choosing the best Groves mechanism for a wide class of scenarios and objectives (including utilitarian and egalitarian). The characterisation links optimality of mechanism’s payments to a geometric condition involving triangulations of hypercubes. When this condition is satisfied, I constructively show existence of an optimal payment function that is piecewise linear. I then use the technique to derive optimal mechanisms for several fundamental scenarios. The technique also provides a unified way to prove a number of results that were previously obtained using different, more complicated techniques.