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)在市场大且抵达是随机的情况下,在几乎所有周期中高概率近似市场清算的。应用包括难民重新安置、日托分配和机场时隙分配。