Group:Student Seminar
Title: Some Results Related to Truthful Mechanism without Money
Speaker: Jialin Zhang Tsinghua university
Time: 2010-05-06 16:00-2010-05-06 17:00
Venue: FIT1-222

Abstract:

In many settings in the game theory, it is impossible to design truthful mechanism without money, for example, one item auction in which valuation can be any positive real number. However, sometimes, monetary transfers are not feasible, either because of ethical or legal issues, or because of practical issues with collecting payments. Typically, in these setting, the private information is the valuation function of the players. Recently, people think about a new model of game: the valuation function is the public information, and the private one is the "structure". They obtain some interesting mechanisms which are truthful without the help of money. I will mention the results about generalized assignment problem and mainly discuss the results of a new problem motivated by kidney exchanges.

In this game, each player privately holds disjoint sets of vertices. We seek a mechanism to maximize the number of matching. Each player wants to maximize the number of its own vertices that match. Players can choose to hide (not report) some of its vertices, and then privately match the hidden vertices with any of its own vertices that go unmatched by the mechanism. The authors prove that no deterministic mechanism can provide an approximation ratio better than 2, and provide a mechanism with unbounded approximation ratio :( The gap in randomized setting is small (lower bound: 4/3, upper bound: 2). There are a lot of interesting open problems left in their paper.

Reference:

1. Truthful Assignment without Money (EC 2010)

2. Mix and Match (EC 2010)




Short Bio: