予定表 -詳細情報-
| 件名 | WS 小島武仁氏 |
| 開始日時 | 2009年 12月 21日 (月曜日) 16時30分 (GMT+09:00) |
| 終了日時 | 2009年 12月 21日 (月曜日) 18時00分 (GMT+09:00) |
| 場所 | 現代政治経済研究所会議室 |
| 詳細 | 【報告者】小島武仁（Stanford University, Assistant Professor） 【タイトル】"Implementing Random Assignments: A Generalization of the Birkhoff-von Neumann Theorem" 【場所】 現代政治経済研究所会議室 【概要】 小島武仁氏はゲーム理論、マーケットデザインを専門とする若手研究者であり、近年、多数の論文を国際査読付き著名学術雑誌に掲載している（American Economic Review, Econometrica, Journal of Economic Theory, International Journal of Game Theory, Games and Economic Behaviorなど）。今回は以下に挙げる、同氏の割り当て問題についての最新研究結果を報告していただく。これはGLOPE２の本プロジェクトの研究とも関連が深い。 概要：The literature on random mechanisms often describes outcomes incompletely as ``random assignments'' - expressing the probabilities that individual items are assigned to different agents - and the joint constraints that a feasible assignment must satisfy. We provide a necessary and sufficient condition (the ``bihierarchy'' condition) for the set of constraints to have the property that if the random assignment satisfies the constraints in expectation, then it is a randomization over pure assignments that each satisfy the constraints. The sets of constraints generalize those allowed by the celebrated Birkhoff-von Neumann theorem. We also provide a random algorithm to implement any such random assignment. Several applications are described, including (i) single-unit random assignment, such as school choice; (ii) multi-unit random assignment, such as course allocation and fair division; and (iii) two-sided matching problems, such as the scheduling of inter-league sports matchups. The same method also finds applications beyond economics, generalizing previous results on the minimize makespan problem in the computer science literature. |
| カテゴリー | ワークショップ・セミナー |
