Optimal Payments in Dominant-Strategy Mechanisms

Add to your list(s) Download to your calendar using vCal

• Victor Naraditskiy, University of Southampton
• Thursday 14 March 2013, 10:00-11:00
• Auditorium, Microsoft Research Ltd, 21 Station Road, Cambridge, CB1 2FB.

If you have a question about this talk, please contact Microsoft Research Cambridge Talks Admins.

This event may be recorded and made available internally or externally via http://research.microsoft.com. Microsoft will own the copyright of any recordings made. If you do not wish to have your image/voice recorded please consider this before attending

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.

This talk is part of the Microsoft Research Cambridge, public talks series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Auditorium, Microsoft Research Ltd, 21 Station Road, Cambridge, CB1 2FB
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge talks
• Chris Davis' list
• Guy Emerson's list
• Interested Talks
• Microsoft Research Cambridge, public talks
• Optics for the Cloud
• PMRFPS's
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• ndk22's list
• ob366-ai4er
• personal list
• rp587

Note that ex-directory lists are not shown.