MARKET PRICING FOR MATROID RANK VALUATIONS

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

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

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\" utting and V\'egh [Private communication, 2017]. We further formalize a weighted variant of the conjecture of D\" utting and V\'egh, 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\natural -concave functions or, equivalently, for gross substitutes functions.

Original languageEnglish
Pages (from-to)2662-2678
Number of pages17
JournalSIAM Journal on Discrete Mathematics
Volume35
Issue number4
DOIs
Publication statusPublished - 2021

Keywords

  • Walrasian equilibrium
  • gross substitutes valuation
  • matroid rank function
  • pricing scheme

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

Dive into the research topics of 'MARKET PRICING FOR MATROID RANK VALUATIONS'. Together they form a unique fingerprint.

Cite this