English

运筹学学报 >

2023 , Vol. 27 >Issue 4: 166 - 174

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2023.04.009

 

一个双拟阵下的最优定价存在性猜想

展开
  • 1. 北京电子科技学院, 北京 100070
    2. 中国科学院数学与系统科学研究院, 北京 100190
王长军, E-mail: wcj@amss.ac.cn

收稿日期: 2023-04-28

  网络出版日期: 2023-12-07

基金资助

国家自然科学基金(11971046);北京市自然科学基金(Z220001)

收起

A conjecture of optimal pricing for two matroids

Expand
  • 1. Beijing Electronic Science and Technology Institute, Beijing 100070, China
    2. Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China

Received date: 2023-04-28

  Online published: 2023-12-07

Fold

摘要

本文研究了一个双拟阵结构下的最优定价存在性猜想。该猜想是关于如何在组合市场中给物品定价以实现配置的社会效益最大化而衍生出的一个问题。给定两个定义在共同的离散元素基础集上的拟阵, 而元素基础集存在一个不相交二划分(称为理想基划分对), 使得两个划分子集各为其中一个拟阵下的基。该猜想认为存在一个关于所有元素的定价函数, 使得任取某个拟阵中的一个最小费用基, 剩余元素集仍构成另一个拟阵的基。我们利用二部图上的完美匹配等, 证明了当理想基划分对的个数不超过2时, 存在价格函数使得猜想成立, 同时我们还给出了可快速实现的定价方法。

关键词： 拟阵; 定价方案; 拟阵基; 完美匹配

本文引用格式

张莹, 敬新奇, 王长军 . 一个双拟阵下的最优定价存在性猜想[J]. 运筹学学报, 2023 , 27(4) : 166 -174 . DOI: 10.15960/j.cnki.issn.1007-6093.2023.04.009

Abstract

In this paper, we study a conjecture of optimal pricing for two matroids, which arises from the problem of maximizing social welfare in combinatorial markets through pricing schemes. Given two matroids with a common ground set of items, there exists a disjoint partition of the ground set such that each subset is a base of one corresponding matroid (called ideal base-partition). The conjecture believes that there exists a price function on the items such that, if we pick any one of the cheapest bases of one matroid from the ground set, then the remaining items still constitute a base of the other matroid. By using perfect matchings on bipartite graphs, we prove that if the ground set admits at most two ideal base-partitions, then the conjecture is true and we can give the price vector efficiently.

Key words： matroid; pricing scheme; matroid bases; perfect matching

参考文献

1 Vickrey W . Counterspeculation, auctions, and competitive sealed tenders[J]. The Journal of Finance, 1961, 16 (1): 8- 37.
2 Clarke E H . Multipart pricing of public goods[J]. Public Choice, 1971, 11 (1): 17- 33.
3 Groves T . Incentives in teams[J]. Econometrica: Journal of the Econometric Society, 1973, 41 (4): 617- 631.
4 Nisan N , Segal I . The communication requirements of efficient allocations and supporting prices[J]. Journal of Economic Theory, 2006, 129 (1): 192- 224.
5 Walras L . éléments d'économie politique pure: ou, Théorie de la richesse sociale[M]. Lausanne: F. Rouge, 1900.
6 Kelso Jr A S , Crawford V P . Job matching, coalition formation, and gross substitutes[J]. Econometrica: Journal of the Econometric Society, 1982, 50 (6): 1483- 1504.
7 Cohen-Addad V, Eden A, Feldman M, et al. The invisible hand of dynamic market pricing [C]//Proceedings of the Seventeenth ACM Conference on Economics and Computation (EC), 2016: 383-400.
8 Berger B, Eden A, Feldman M. On the power and limits of dynamic pricing in combinatorial markets [C]//Proceedings of the Sixteenth International Conference on Web and Internet Economics (WINE), Lecture Notes in Computer Science, 12495, Springer International Publishing, 2020: 206-219.
9 Bérczi K , Kakimura N , Kobayashi Y . Market pricing for matroid rank valuations[J]. SIAM Journal on Discrete Mathematics, 2021, 35 (4): 2662- 2678.
10 Gul F , Stacchetti E . Walrasian equilibrium with gross substitutes[J]. Journal of Economic Theory, 1999, 87 (1): 95- 124.
11 Hsu J , Morgenstern J , Rogers R , et al. Do prices coordinate markets?[J]. ACM Sigecom Exchanges, 2016, 15 (1): 84- 88.
12 Feldman M , Gravin N , Lucier B . Combinatorial Walrasian Equilibrium[J]. SIAM Journal on Computing, 2016, 45 (1): 29- 48.
13 Blumrosen L, Holenstein T. Posted prices vs. negotiations: an asymptotic analysis [C]//Proceedings of the Ninth ACM Conference on Electronic Commerce (EC), 2008: 49-49.
14 Chawla S, Hartline J D, Malec D L, et al. Multi-parameter mechanism design and sequential posted pricing [C]//Proceedings of the Forty-second ACM Symposium on Theory of Computing (STOC), 2010: 311-320.
15 Feldman M, Gravin N, Lucier B. Combinatorial auctions via posted prices [C]//Proceedings of the Twenty-sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Society for Industrial and Applied Mathematics, 2014: 123-135.
16 Chawla S, Miller J B, Teng Y. Pricing for online resource allocation: Intervals and paths [C]//Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Society for Industrial and Applied Mathematics, 2019: 1962-1981.
17 Whitney H . On the abstract properties of linear dependence[J]. American Journal of Mathematics, 1935, 57 (3): 509- 533.
18 Nishimura H , Kuroda S . A Lost Mathematician, Takeo Nakasawa: The Forgotten Father of Matroid Theory[M]. Basel: Birkh?user Basel, 2009.
19 Brualdi R A . Comments on bases in dependence structures[J]. Bulletin of the Australian Mathematical Society, 1969, 1 (2): 161- 167.
20 Schrijver A . Combinatorial Optimization: Polyhedra and Efficiency[M]. Berlin: Springer, 2003.
Options
文章导航

/

〈 〉