BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Mechanism Design without Money via Stable Matching - Ning Chen\, N
 anyang Technical University
DTSTART:20110901T130000Z
DTEND:20110901T140000Z
UID:TALK32678@talks.cam.ac.uk
CONTACT:Microsoft Research Cambridge Talks Admins
DESCRIPTION:Mechanism design without money has a rich history in social ch
 oice literature. Due to the strong impossibility theorem by Gibbard and Sa
 tterthwaite\, exploring domains in which there exist dominant strategy mec
 hanisms is one of the central questions in the field. We propose a general
  framework\, called the generalized packing problem (\\gpp)\, to study the
  mechanism design questions without payment. The \\gpp\\ possesses a rich 
 structure and comprises a number of well-studied models as special cases\,
  including\, e.g.\, matroid\, matching\, knapsack\, independent set\, and 
 the generalized assignment problem.\n\nWe adopt the agenda of approximate 
 mechanism design where the objective is to design a truthful (or strategyp
 roof) mechanism without money that can be implemented in polynomial time a
 nd yields a good approximation to the socially optimal solution. We study 
 several special cases of \\gpp\, and give constant approximation mechanism
 s for matroid\, matching\, knapsack\, and the generalized assignment probl
 em. Our result for generalized assignment problem solves an open problem p
 roposed by Dughmi and Ghosh.\n\nOur main technical contribution is in expl
 oitation of the approaches from stable matching\, which is a fundamental s
 olution concept in the context of matching marketplaces\, in application t
 o mechanism design. Stable matching\, while conceptually simple\, provides
  a set of powerful tools to manage and analyze selfinterested behaviors of
  participating agents. Our mechanism uses a stable matching algorithm as a
  critical component and adopts other approaches like random sampling and o
 nline mechanisms. Our work also\nenriches the stable matching theory with 
 a new knapsack constrained matching model.\n\nJoint work with Nick Gravin 
 and Pinyan Lu
LOCATION:Small public lecture room\, Microsoft Research Ltd\, 7 J J Thomso
 n Avenue (Off Madingley Road)\, Cambridge
END:VEVENT
END:VCALENDAR