ダウンロード数: 372
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
3175496.pdf | 935.78 kB | Adobe PDF | 見る/開く |
タイトル: | The Random Assignment Problem with Submodular Constraints on Goods |
著者: | Fujishige, Satoru Sano, Yoshio Zhan, Ping |
著者名の別形: | 藤重, 悟 |
キーワード: | Theory of computation Algorithmic game theory and mechanism design Discrete optimization Random assignment probabilistic serial mechanism ordinal preference matchings polymatroids independent flows submodular optimization weak Nash equilibrium |
発行日: | 22-Jan-2018 |
出版者: | Association for Computing Machinery (ACM) |
誌名: | ACM Transactions on Economics and Computation |
巻: | 6 |
号: | 1 |
論文番号: | 3 |
抄録: | 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 envy-free 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, envy-free, and weakly strategy-proof with respect to the associated stochastic dominance relation. (2)For the multiunit demand and polymatroidal constraint problem, the PS solution is ordinally efficient and envy-free but is not strategy-proof 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. |
著作権等: | © ACM, 2018. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in PUBLICATION, [Volume 6 Issue 1, January 2018, Article No. 3] http://doi.acm.org/10.1145/3175496 この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。 This is not the published version. Please cite only the published version. |
URI: | http://hdl.handle.net/2433/228999 |
DOI(出版社版): | 10.1145/3175496 |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。