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游戏的发行和学习中选取出来来模拟这一情形。我们注重对称平衡,所有学生都使用同样的策略。我们展示了一般情况下存在的这些平衡,并提供两种算法,根据其他假设来计算这种平衡,包括学校对学生有相同偏好的情况。

0
下载
关闭预览

相关内容

《计算机信息》杂志发表高质量的论文,扩大了运筹学和计算的范围,寻求有关理论、方法、实验、系统和应用方面的原创研究论文、新颖的调查和教程论文,以及描述新的和有用的软件工具的论文。官网链接:https://pubsonline.informs.org/journal/ijoc
数据科学导论,54页ppt,Introduction to Data Science
专知会员服务
38+阅读 · 2020年7月27日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
75+阅读 · 2020年7月26日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
104+阅读 · 2020年5月15日
因果图,Causal Graphs,52页ppt
专知会员服务
238+阅读 · 2020年4月19日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
24+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
人工智能 | NIPS 2019等国际会议信息8条
Call4Papers
7+阅读 · 2019年3月21日
大数据 | 顶级SCI期刊专刊/国际会议信息7条
Call4Papers
10+阅读 · 2018年12月29日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
15+阅读 · 2018年12月24日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Arxiv
0+阅读 · 2021年11月10日
Arxiv
0+阅读 · 2021年11月9日
Arxiv
4+阅读 · 2021年10月19日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
24+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
人工智能 | NIPS 2019等国际会议信息8条
Call4Papers
7+阅读 · 2019年3月21日
大数据 | 顶级SCI期刊专刊/国际会议信息7条
Call4Papers
10+阅读 · 2018年12月29日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
15+阅读 · 2018年12月24日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Top
微信扫码咨询专知VIP会员