ダウンロード数: 35
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
20m1386335.pdf | 379 kB | Adobe PDF | 見る/開く |
タイトル: | Market Pricing for Matroid Rank Valuations |
著者: | Bérczi, Kristóf Kakimura, Naonori Kobayashi, Yusuke https://orcid.org/0000-0001-9478-7307 (unconfirmed) |
著者名の別形: | 小林, 佑輔 |
キーワード: | pricing scheme Walrasian equilibrium gross substitutes valuation matroid rank function 90C27 91B52 |
発行日: | 2021 |
出版者: | Society for Industrial & Applied Mathematics (SIAM) |
誌名: | SIAM Journal on Discrete Mathematics |
巻: | 35 |
号: | 4 |
開始ページ: | 2662 |
終了ページ: | 2678 |
抄録: | In this paper, we study the problem of maximizing social welfare in combinatorial markets through pricing schemes. We consider the existence of prices that are capable of achieving optimal social welfare without a central tie-breaking coordinator. In the case of two buyers with matroid rank valuations, we give polynomial-time algorithms that always find such prices when one of the matroids is a partition matroid or both matroids are strongly base orderable. This result partially answers a question raised by Dütting and Végh [Private communication, 2017]. We further formalize a weighted variant of the conjecture of Dütting and Végh, and show that the weighted variant can be reduced to the unweighted one based on the weight-splitting theorem for weighted matroid intersection by Frank. We also show that a similar reduction technique works for M♮ -concave functions or, equivalently, for gross substitutes functions. |
著作権等: | © 2021, Society for Industrial and Applied Mathematics |
URI: | http://hdl.handle.net/2433/279145 |
DOI(出版社版): | 10.1137/20M1386335 |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。