文章基本信息
- 标题：Market Pricing for Matroid Rank Valuations
- 本地全文：下载
- 作者：Bérczi, Kristóf ; Naonori Kakimura ; Yusuke Kobayashi 等
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2020
- 卷号：181
- 页码：1-15
- DOI：10.4230/LIPIcs.ISAAC.2020.39
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：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 to achieve 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 simple partition matroid or both matroids are strongly base orderable. This result partially answers a question raised by Düetting and Végh in 2017. We further formalize a weighted variant of the conjecture of Düetting 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.
- 关键词：Pricing schemes; Walrasian equilibrium; gross substitutes valuations; matroid rank functions
