![[Search]](/static/images/search.gif){kind=small}
![[A-Z Index]](/static/images/az.gif){kind=small}
![[Contact]](/static/images/contact.gif){kind=small}
![[University of Cambridge]](/static/images/identifier2.gif){kind=small}
![[Talks.cam]](/static/images/talkslogosmall.gif)
Speaker to be confirmed
Thursday 19 August 2010, 14:00-15:00
Frugality in set-system auctions
- đ¤ Speaker: Speaker to be confirmed
- đ Date & Time: Thursday 19 August 2010, 14:00 - 15:00
- đ Venue: Small public lecture room, Microsoft Research Ltd, 7 J J Thomson Avenue (Off Madingley Road), Cambridge
Abstract
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.
Series This talk is part of the Microsoft Research Cambridge, public talks series.
Included in Lists
- All Talks (aka the CURE list)
- bld31
- Cambridge Centre for Data-Driven Discovery (C2D3)
- Cambridge talks
- Chris Davis' list
- Guy Emerson's list
- Interested Talks
- Microsoft Research Cambridge, public talks
- ndk22's list
- ob366-ai4er
- Optics for the Cloud
- personal list
- PMRFPS's
- rp587
- School of Technology
- Small public lecture room, Microsoft Research Ltd, 7 J J Thomson Avenue (Off Madingley Road), Cambridge
- Trust & Technology Initiative - interesting events
- yk449
Note: Ex-directory lists are not shown.