BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Frugality in set-system auctions - Speaker to be confirmed
DTSTART:20100819T130000Z
DTEND:20100819T140000Z
UID:TALK25865@talks.cam.ac.uk
CONTACT:Microsoft Research Cambridge Talks Admins
DESCRIPTION: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 thi
 s setting include shortest path auctions\, minimum spanning tree auctions\
 , and vertex cover auctions. From the seller`s perspective\, an interestin
 g 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 w
 hich the mechanism overpays\, relative to perceived fair cost. In this tal
 k\, I will discuss several alternative definitions of frugality ratio\, an
 d recent lower and upper bounds on frugality ratio for various classes of 
 set systems.
LOCATION:Small public lecture room\, Microsoft Research Ltd\, 7 J J Thomso
 n Avenue (Off Madingley Road)\, Cambridge
END:VEVENT
END:VCALENDAR