Submodular optimization views on the random assignment problem

• 成果类型: Article
• 署名作者: Fujishige, Satoru; Sano, Yoshio; Zhan, Ping
• 署名单位: Kyoto University; University of Tsukuba
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-018-1310-4
• 发表日期: 2019
• 页码: 485-501
• 关键词: Probabilistic assignment; egalitarianism; allocation; algorithms

摘要

We present a non-pricing allocation scheme of divisible goods to agents with utility functions and submodular constraints on goods. The main contribution of the present paper is that through our non-pricing allocation scheme we reveal the close relation between (1) the recent results in the allocation schemes of the random assignment problem and its extensions with ordinal or lexicographic preferences on goods and (2) the monotone algorithms of fair (egalitarian) allocations with separable utility functions and submodular constraints investigated a few decades ago. The underlying submodularity structure plays a crucial role, so that the probabilistic serial mechanism of Bogomolnaia and Moulin and other related mechanisms can naturally be extended to problems with submodular constraints.