Market pricing for matroid rank valuations

Kristóf Bérczi, Naonori Kakimura, Yusuke Kobayashi

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish
Title of host publication31st International Symposium on Algorithms and Computation, ISAAC 2020
EditorsYixin Cao, Siu-Wing Cheng, Minming Li
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Number of pages3525
ISBN (Electronic)9783959771733
Publication statusPublished - 2020 Dec
Event31st International Symposium on Algorithms and Computation, ISAAC 2020 - Virtual, Hong Kong, China
Duration: 2020 Dec 142020 Dec 18

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference31st International Symposium on Algorithms and Computation, ISAAC 2020
CityVirtual, Hong Kong


  • Gross substitutes valuations
  • Matroid rank functions
  • Pricing schemes
  • Walrasian equilibrium

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Market pricing for matroid rank valuations'. Together they form a unique fingerprint.

Cite this