2023/03/24 by Thành Nguyen, Nguyen, Thành, Alexander Teytelboym +3
Computer Science · Decision Sciences · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #FOS: Economics and business #Game Theory and Applications #Optimization and Search Problems #Theoretical Economics (econ.TH)
paper · pdf · doi:10.48550/arxiv.2303.13967
openalex publication_date 2023/03/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.