School choice is the two-sided matching market where students (on one side) are to be matched with schools (on the other side) based on their mutual preferences. The classical algorithm to solve this problem is the celebrated deferred acceptance procedure, proposed by Gale and Shapley. After both sides have revealed their mutual preferences, the algorithm computes an optimal stable matching. Most often in practice, notably when the process is implemented by a national clearinghouse and thousands of schools enter the market, there is a quota on the number of applications that a student can submit: students have to perform a partial revelation of their preferences, based on partial information on the market. We model this situation by drawing each student type from a publicly known distribution and study Nash equilibria of the corresponding Bayesian game. We focus on symmetric equilibria, in which all students play the same strategy. We show existence of these equilibria in the general case, and provide two algorithms to compute such equilibria under additional assumptions, including the case where schools have identical preferences over students.
翻译:学校选择是双向匹配市场,学生(一方)将根据相互偏好与学校(另一方)匹配。解决这一问题的经典算法是Gale和Shapley提出的庆祝推迟录取程序。在双方都暴露了彼此偏好后,算法计算出一种最佳的稳定匹配。在实践上,最经常的情况是这一过程由国家信息交换所实施,数千所学校进入市场,学生可以提交的申请数量有一定的配额:学生必须在市场的部分信息基础上部分披露他们的偏好。我们通过将每个学生类型从众所周知的Bayesian游戏的发行和学习中选取出来来模拟这一情形。我们注重对称平衡,所有学生都使用同样的策略。我们展示了一般情况下存在的这些平衡,并提供两种算法,根据其他假设来计算这种平衡,包括学校对学生有相同偏好的情况。