
The Random Assignment Problem with Submodular Constraints on GoodsThe Random Assignment Problem with Submodular Constraints on Goods 
"/Fujishige, Satoru/"Fujishige, Satoru ,
"/Sano, Yoshio/"Sano, Yoshio ,
"/Zhan, Ping/"Zhan, Ping
6
(
1
)
20180122 , Association for Computing Machinery (ACM)
ISSN:21678375
内容記述
Problems of allocating indivisible goods to agents in an efficient and fair manner without money have long been investigated in literature. The random assignment problem is one of them, where we are given a fixed feasible (available) set of indivisible goods and a profile of ordinal preferences over the goods, one for each agent. Then, using lotteries, we determine an assignment of goods to agents in a randomized way. A seminal paper of Bogomolnaia and Moulin (2001) shows a probabilistic serial (PS) mechanism to give an ordinally efficient and envyfree solution to the assignment problem. In this article, we consider an extension of the random assignment problem to submodular constraints on goods. We show that the approach of the PS mechanism by Bogomolnaia and Moulin is powerful enough to solve the random assignment problem with submodular (matroidal and polymatroidal) constraints. Under the agents’ ordinal preferences over goods we show the following: (1) The obtained PS solution for the problem with unit demands and matroidal constraints is ordinally efficient, envyfree, and weakly strategyproof with respect to the associated stochastic dominance relation. (2)For the multiunit demand and polymatroidal constraint problem, the PS solution is ordinally efficient and envyfree but is not strategyproof in general. However, we show that under a mild condition (that is likely to be satisfied in practice) the PS solution is a weak Nash equilibrium.
本文を読む
http://repository.kulib.kyotou.ac.jp/dspace/bitstream/2433/228999/1/3175496.pdf