BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Frugal Procurement Auction Design - Mahyar Salek\, University of S
 outhern California
DTSTART:20110303T100000Z
DTEND:20110303T110000Z
UID:TALK30051@talks.cam.ac.uk
CONTACT:Microsoft Research Cambridge Talks Admins
DESCRIPTION:Suppose we want to hire a team of selfish agents to perform a 
 task via auction. Each agent is assumed to have a private cost if being hi
 red. Moreover\, only certain combination of agents are feasible which are 
 expressed in a set system. For instance\, in the well-studied case of path
  auctions\, each agent are edges of a graph\, and we are trying to buy an 
 s-t path. A natural goal for us (the auctioneer) is to seek a mechanism to
  pay 'the least'.\n\nIn this talk\, I will present optimal truthful mechan
 isms in three classes of set systems: Vertex Covers\, k-Flows (generalizat
 ion of path) and Cuts. For Vertex Covers\, we achieve optimal mechanisms u
 sing spectral techniques. Our mechanism first scales each bid by a multipl
 ier derived from the dominant eigenvector of a certain matrix related to t
 he adjacency matrix and then runs VCG. \n\nAdditionally\, we use Vertex Co
 vers mechanism as a primitive and propose a methodology to obtain 'frugal'
  mechanisms for a given set system by pruning it down to a Vertex Cover in
 stance. We show the power of our methodology by achieving optimal mechanis
 ms for flows and cuts.
LOCATION:Small lecture theatre\, Microsoft Research Ltd\, 7 J J Thomson Av
 enue (Off Madingley Road)\, Cambridge
END:VEVENT
END:VCALENDAR