University of Cambridge > Talks.cam > Microsoft Research Cambridge, public talks > Frugality in set-system auctions

Frugality in set-system auctions

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

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

Edith Elkind, Nanyang Technological University, Singapore

In set-system auctions, there is a task that can be completed by several overlapping teams of selfish agents, and the center`s goal is to hire one of these teams and pay as little as possible. Examples of this setting include shortest path auctions, minimum spanning tree auctions, and vertex cover auctions. From the seller`s perspective, an interesting parameter in this setting in the {\em frugality ratio} of a mechanism. Informally, the ``frugality ratio`` is the ratio of the total payment of a mechanism to a desired payment bound. The ratio captures the extent to which the mechanism overpays, relative to perceived fair cost. In this talk, I will discuss several alternative definitions of frugality ratio, and recent lower and upper bounds on frugality ratio for various classes of set systems.

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

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2019 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity