We study a model of dynamic combinatorial assignment of indivisible objects without money. We introduce a new solution concept called ``dynamic approximate competitive equilibrium from equal incomes'' (DACEEI), which stipulates that markets must approximately clear in almost all time periods. A naive repeated application of approximate competitive equilibrium from equal incomes (Budish, 2011) does not yield a desirable outcome because the approximation error in market-clearing compounds quickly over time. We therefore develop a new version of the static approximate competitive equilibrium from carefully constructed random budgets which ensures that, in expectation, markets clear exactly. We then use it to design the ``online combinatorial assignment mechanism'' (OCAM) which implements a DACEEI with high probability. The OCAM is (i) group-strategyproof up to one object (ii) envy-free up to one object for almost all agents (iii) approximately market-clearing in almost all periods with high probability when the market is large and arrivals are random. Applications include refugee resettlement, daycare assignment, and airport slot allocation.


翻译:我们研究了一种没有货币的不可分割物品的动态组合分配模型。我们引入了一种名为“来自等收入的动态近似竞争均衡”的新解决方案概念(DACEEI),它规定市场在几乎所有时间段中都必须近似清算。一个天真的重复应用近似等收入竞争均衡(Budish,2011)不能产生理想的结果,因为在市场清算中的近似误差会随着时间迅速复合。因此,我们开发了一种新的静态近似等收入竞争均衡版本,从仔细构造的随机预算开始,确保市场精确清算的预期结果。然后,我们使用它来设计“在线组合分配机制”(OCAM),该机制以高概率实现DACEEI。OCAM是(i)在一个对象上组策略证明的 (ii)使几乎所有代理商在一个对象上没有嫉妒感 (iii)在市场大且抵达是随机的情况下,在几乎所有周期中高概率近似市场清算的。应用包括难民重新安置、日托分配和机场时隙分配。

0
下载
关闭预览

相关内容

【ICDM2022教程】多目标优化与推荐,173页ppt
专知会员服务
44+阅读 · 2022年12月24日
【干货书】金融数学概念和计算方法的导论,290页pdf
专知会员服务
58+阅读 · 2020年11月16日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
“CVPR 2020 接受论文列表 1470篇论文都在这了
RL解决'BipedalWalkerHardcore-v2' (SOTA)
CreateAMind
31+阅读 · 2019年7月17日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
19篇ICML2019论文摘录选读!
专知
28+阅读 · 2019年4月28日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
LibRec 精选:基于LSTM的序列推荐实现(PyTorch)
LibRec智能推荐
50+阅读 · 2018年8月27日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Arxiv
0+阅读 · 2023年5月12日
Arxiv
24+阅读 · 2018年10月24日
A Multi-Objective Deep Reinforcement Learning Framework
VIP会员
相关资讯
“CVPR 2020 接受论文列表 1470篇论文都在这了
RL解决'BipedalWalkerHardcore-v2' (SOTA)
CreateAMind
31+阅读 · 2019年7月17日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
19篇ICML2019论文摘录选读!
专知
28+阅读 · 2019年4月28日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
LibRec 精选:基于LSTM的序列推荐实现(PyTorch)
LibRec智能推荐
50+阅读 · 2018年8月27日
相关基金
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Top
微信扫码咨询专知VIP会员