ダウンロード数: 234
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
s10107-018-1310-4.pdf | 131.55 kB | Adobe PDF | 見る/開く |
タイトル: | Submodular optimization views on the random assignment problem |
著者: | Fujishige, Satoru Sano, Yoshio Zhan, Ping |
著者名の別形: | 藤重, 悟 |
キーワード: | Random assignment problem Submodular optimization Independent flows Submodular flows Non-pricing allocation Probabilistic serial mechanism |
発行日: | Nov-2019 |
出版者: | Springer Berlin Heidelberg |
誌名: | Mathematical Programming |
巻: | 178 |
号: | 1-2 |
開始ページ: | 485 |
終了ページ: | 501 |
抄録: | 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. |
著作権等: | This is a post-peer-review, pre-copyedit version of an article published in [insert journal title]. The final authenticated version is available online at: https://doi.org/10.1007/s10107-018-1310-4. The full-text file will be made open to the public on 21 June 2019 in accordance with publisher's 'Terms and Conditions for Self-Archiving'. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。 This is not the published version. Please cite only the published version. |
URI: | http://hdl.handle.net/2433/232502 |
DOI(出版社版): | 10.1007/s10107-018-1310-4 |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。