Mechanism Design for Indivisible Goods Allocation

择校是教育界最热门的话题之一。这意味着给父母选择孩子就读学校的机会。既然不可能把每个学生都分配到她最喜欢的学校，那么学校选择的一个核心问题就是学生分配机制的设计。到目前为止，包括波士顿、剑桥、小石城、圣何塞和西雅图在内的几个城市已经采用了择校计划。虽然这些计划都有自己的协议和指导方针的学生分配，他们都没有一个严格的程序。缺乏严格的程序为操纵提供了机会，并导致对孩子的学校作业不满意的家长提出上诉。本项目引入了一类新的不可分割物品分配问题，该问题模拟了公立学校的选择，提出了一种严格分配学生到学校的机制，并对其进行了分析。该项目还研究了现有租户的住房分配。该模型的主要应用是校园住房，但也有其他应用，如公共住房、办公空间分配和停车位分配。现有的分配机制显示出严重的缺点，包括效率低下。另一种机制可以克服这些缺点。研究了该机构的附加特性，并进行了实验来验证理论结果，将该机构的性能与广泛使用的普通实际机构进行了比较。这两个项目都涉及设计和分析现实生活中不可分割物品分配问题的机制。

School choice is one of the hottest topics in education. It means giving parents the opportunity to choose the schools their children will attend. Since it is not possible to assign each student to her top choice school, a central issue in school choice is the design of a student assignment mechanism. By now several cities including Boston, Cambridge, Little Rock, San Jose, and Seattle have adopted school choice plans. While each of these plans has its protocol and guidelines for the assignment of students, none of them has a rigorous procedure. The lack of rigorous procedures offers opportunities to manipulation and results in appeals by parents who are unsatisfied by the school assignments of their children. This project introduces a new class of indivisible goods allocation problems that model public school choice, proposes a mechanism for rigorously assigning students to schools, and analyzes it. The project also studies the allocation of housing with existing tenants. The main application is on-campus housing, although the model has other applications such as public housing, office space allocation, and parking space allocation. Existing allocation mechanisms are shown to have serious shortcomings including inefficiency. An alternative mechanism is shown to overcome these shortcomings. Additional properties of this mechanism are studied and experiments are conducted to test the theoretical results that compare the performances of this mechanism and a widely used common real-life mechanism. Both of these projects deal with design and analysis of mechanisms for real-life indivisible goods allocation problems.