Informatics Seminar (Perspective in Informatics 4B) 2011 - 2012
December 22 (Thu), 14:45 - 16:15
- Place:
Lecture Hall 1, Faculty of Engineering Bldg. No.10, Main Campus
- Title:
Mechanism Design without Money via Stable Matching
- Speaker:
Chen Ning (Nanyang Technological University)
- Abstract:
Mechanism design without money has a rich history in social choice literature. Due to the strong impossibility
theorem by Gibbard and Satterthwaite, exploring domains in which there exist dominant strategy mechanisms
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.
We adopt the agenda of approximate mechanism design where the objective is to design a truthful (or
strategyproof) mechanism without money that can be implemented in polynomial time and yields a good
approximation to the socially optimal solution. We study several special cases of \gpp, and give constant
approximation mechanisms for matroid, matching, knapsack, and the generalized assignment problem. Our
result for generalized assignment problem solves an open problem proposed by Dughmi and Ghosh.
Our main technical contribution is in exploitation of the approaches from stable matching, which is a
fundamental solution concept in the context of matching marketplaces, in application to 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 online mechanisms. Our work also
enriches the stable matching theory with a new knapsack constrained matching model.
Joint work with Nick Gravin and Pinyan Lu
Kyoto University
> Graduate School of Informatics
> International Courses
> Informatics Seminar