TY - GEN
T1 - Market pricing for matroid rank valuations
AU - Bérczi, Kristóf
AU - Kakimura, Naonori
AU - Kobayashi, Yusuke
N1 - Funding Information:
Funding This work was supported by the Research Institute for Mathematical Sciences, an International Joint Usage/Research Center located in Kyoto University. Kristóf Bérczi: Supported by the János Bolyai Research Fellowship of the Hungarian Academy of Sciences, by the ÚNKP-19-4 New National Excellence Program of the Ministry for Innovation and Technology, and by projects no. NKFI-128673 and TKP2020-NKA-06 (National Challenges Subprogramme, “Application Domain Specific Highly Reliable IT Solutions”) provided by the National Research, Development and Innovation Fund of Hungary. Naonori Kakimura: Supported by JSPS KAKENHI grant numbers JP17K00028 and JP18H05291, Japan. Yusuke Kobayashi: Supported by JSPS, KAKENHI grant numbers JP18H05291, JP19H05485, and JP20K11692, Japan.
Publisher Copyright:
© Kristóf Bérczi, Naonori Kakimura, and Yusuke Kobayashi.
PY - 2020/12
Y1 - 2020/12
N2 - 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.
AB - 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.
KW - Gross substitutes valuations
KW - Matroid rank functions
KW - Pricing schemes
KW - Walrasian equilibrium
UR - http://www.scopus.com/inward/record.url?scp=85100930697&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85100930697&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ISAAC.2020.39
DO - 10.4230/LIPIcs.ISAAC.2020.39
M3 - Conference contribution
AN - SCOPUS:85100930697
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 391
EP - 3915
BT - 31st International Symposium on Algorithms and Computation, ISAAC 2020
A2 - Cao, Yixin
A2 - Cheng, Siu-Wing
A2 - Li, Minming
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 31st International Symposium on Algorithms and Computation, ISAAC 2020
Y2 - 14 December 2020 through 18 December 2020
ER -