Frugality in set-system auctions

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

• Speaker to be confirmed
• Thursday 19 August 2010, 14:00-15:00
• Small public lecture room, Microsoft Research Ltd, 7 J J Thomson Avenue (Off Madingley Road), Cambridge.

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.

This talk is included in these lists:

• All Talks (aka the CURE list)
• 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
• Small public lecture room, Microsoft Research Ltd, 7 J J Thomson Avenue (Off Madingley Road), Cambridge
• Trust & Technology Initiative - interesting events
• bld31
• ndk22's list
• ob366-ai4er
• personal list
• rp587

Note that ex-directory lists are not shown.