ダウンロード数: 35
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
20m1386335.pdf | 379 kB | Adobe PDF | 見る/開く |
完全メタデータレコード
DCフィールド | 値 | 言語 |
---|---|---|
dc.contributor.author | Bérczi, Kristóf | en |
dc.contributor.author | Kakimura, Naonori | en |
dc.contributor.author | Kobayashi, Yusuke | en |
dc.contributor.alternative | 小林, 佑輔 | ja |
dc.date.accessioned | 2023-02-07T09:00:54Z | - |
dc.date.available | 2023-02-07T09:00:54Z | - |
dc.date.issued | 2021 | - |
dc.identifier.uri | http://hdl.handle.net/2433/279145 | - |
dc.description.abstract | 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. | en |
dc.language.iso | eng | - |
dc.publisher | Society for Industrial & Applied Mathematics (SIAM) | en |
dc.rights | © 2021, Society for Industrial and Applied Mathematics | en |
dc.subject | pricing scheme | en |
dc.subject | Walrasian equilibrium | en |
dc.subject | gross substitutes valuation | en |
dc.subject | matroid rank function | en |
dc.subject | 90C27 | en |
dc.subject | 91B52 | en |
dc.title | Market Pricing for Matroid Rank Valuations | en |
dc.type | journal article | - |
dc.type.niitype | Journal Article | - |
dc.identifier.jtitle | SIAM Journal on Discrete Mathematics | en |
dc.identifier.volume | 35 | - |
dc.identifier.issue | 4 | - |
dc.identifier.spage | 2662 | - |
dc.identifier.epage | 2678 | - |
dc.relation.doi | 10.1137/20M1386335 | - |
dc.textversion | publisher | - |
dcterms.accessRights | open access | - |
datacite.awardNumber | 17K00028 | - |
datacite.awardNumber | 18H05291 | - |
datacite.awardNumber | 20H05795 | - |
datacite.awardNumber | 21H03397 | - |
datacite.awardNumber | 19H05485 | - |
datacite.awardNumber | 20K11692 | - |
datacite.awardNumber.uri | https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-17K00028/ | - |
datacite.awardNumber.uri | https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18H05291/ | - |
datacite.awardNumber.uri | https://kaken.nii.ac.jp/grant/KAKENHI-PLANNED-20H05795/ | - |
datacite.awardNumber.uri | https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-21H03397/ | - |
datacite.awardNumber.uri | https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20K20417/ | - |
datacite.awardNumber.uri | https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20K11692/ | - |
dc.identifier.pissn | 0895-4801 | - |
dc.identifier.eissn | 1095-7146 | - |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.awardTitle | 組合せ最適化理論を用いたネットワーク解析手法の設計 | ja |
jpcoar.awardTitle | 巨大グラフとビッグデータ解析の基礎基盤:理論研究と高速アルゴリズム開発 | ja |
jpcoar.awardTitle | 数学アプローチによる組合せ遷移の展開:活用事例を手がかりとして新解法へ | ja |
jpcoar.awardTitle | 不確実性をもつ組合せ最適化モデルに対する理論基盤の構築 | ja |
jpcoar.awardTitle | 走行税課金による道路インフラ維持管理 --EV化と車両認証のデジタル時代を迎えて-- | ja |
jpcoar.awardTitle | 組合せ最適化における多面体手法の高度化 | ja |
出現コレクション: | 学術雑誌掲載論文等 |
![](/dspace/image/articlelinker.gif)
このリポジトリに保管されているアイテムはすべて著作権により保護されています。