Market Pricing for Matroid Rank Valuations
Market Pricing for Matroid Rank Valuations
复制标题
Matroid 排名估值的市场定价
DOI：
10.1137/20m1386335
复制
发表时间：
2021
影响因子：
0.8
通讯作者：
Yusuke Kobayashi
中科院分区：
文献类型：
--
作者：
Kristof Berczi;Naonori Kakimura;Yusuke Kobayashi
本文研究了组合市场中通过定价方案实现社会福利最大化的问题。我们认为存在的价格能够实现最佳的社会福利，而没有一个中央打破平局的协调员。在两个买家与拟阵秩估值的情况下，我们给出多项式时间算法，总是找到这样的价格时，其中一个拟阵是一个分区拟阵或两个拟阵是强基有序。这一结果部分回答了Du Mitting和Végh提出的一个问题[私人交流，2017]。我们进一步形式化了Duffetting和Ve 'gh猜想的一个加权变体，并证明了基于Frank关于加权拟阵交的权分裂定理，加权变体可以化为非加权变体.我们还表明，一个类似的减少技术工程M-凹函数，或等价地，总替代功能。
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.
登录
查看更多内容
论组合市场动态定价的力量和局限性
DOI：
--
发表时间：
2020
期刊：
Workshop on Internet and Network Economics
影响因子：
--
作者：
Ben Berger;Alon Eden;M. Feldman
通讯作者：
M. Feldman
最大最小贪婪匹配
DOI：
10.1145/3338506.3340238
发表时间：
2018
期刊：
Proceedings of the 14th Workshop on the Economics of Networks, Systems and Computation
影响因子：
--
作者：
Alon Eden;U. Feige;M. Feldman
通讯作者：
M. Feldman
组合瓦尔拉斯平衡
DOI：
10.1145/2488608.2488617
发表时间：
2013
期刊：
Proceedings of the 22nd ACM Conference on Economics and Computation
影响因子：
--
作者：
M. Feldman;N. Gravin;Brendan Lucier
通讯作者：
Brendan Lucier
论拉丁方的各种猜想与矫直系数的关系
影响因子：
0.8
作者：
Rosa Huang;G. Rota
通讯作者：
G. Rota
DOI：
10.1145/1386790.1386801
发表时间：
2008
期刊：
2010 IEEE 51st Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Liad Blumrosen;Thomas Holenstein
通讯作者：
Thomas Holenstein