Market pricing for matroid rank valuations

K Bérczi, N Kakimura, Y Kobayashi - SIAM Journal on Discrete Mathematics, 2021 - SIAM
SIAM Journal on Discrete Mathematics, 2021SIAM
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 …
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.
Society for Industrial and Applied Mathematics
以上显示的是最相近的搜索结果。 查看全部搜索结果