论文标题
Matroid排名估值的市场定价
Market Pricing for Matroid Rank Valuations
论文作者
论文摘要
在本文中，我们研究了通过定价方案在组合市场中最大化社会福利的问题。我们认为存在能够实现最佳社会福利的价格的存在，而无需中央冠军协调员。对于两个具有排名估值的买家，我们会提供多项式时间算法，这些算法总是在一个简单的分区矩阵或两个矩形的基本订购时总是找到这样的价格。该结果部分回答了Düetting和Végh在2017年提出的一个问题。我们进一步正式化了Düetting和Végh的猜想的加权变体，并表明可以将加权变体降低到根据弗兰克（Frank）加权的Matroid相互作用的重量分解定理，将加权变体缩小为未级别的变体。我们还表明，类似的还原技术适用于M $ {}^\ natural $ -concave函数，或等效地，总替代功能。
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 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${}^\natural$-concave functions, or equivalently, gross substitutes functions.
