Submodular optimization views on the random assignment problem

Abstract

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 rôle, so that the probabilistic serial mechanism of Bogomolnaia and Moulin and other related mechanisms can naturally be extended to problems with submodular constraints.