English

运筹学学报 ›› 2023, Vol. 27 ›› Issue (4): 166-174.doi: 10.15960/j.cnki.issn.1007-6093.2023.04.009

•   • 上一篇    

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

张莹1, 敬新奇2, 王长军2,*()   

  1. 1. 北京电子科技学院, 北京 100070
    2. 中国科学院数学与系统科学研究院, 北京 100190
  • 收稿日期:2023-04-28 出版日期:2023-12-15 发布日期:2023-12-07
  • 通讯作者: 王长军 E-mail:wcj@amss.ac.cn
  • 作者简介:王长军, E-mail: wcj@amss.ac.cn
  • 基金资助:
    国家自然科学基金(11971046);北京市自然科学基金(Z220001)

A conjecture of optimal pricing for two matroids

Ying ZHANG1, Xinqi JING2, Changjun WANG2,*()   

  1. 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:2023-04-28 Online:2023-12-15 Published:2023-12-07
  • Contact: Changjun WANG E-mail:wcj@amss.ac.cn

RichHTML

4

PDF

156

摘要：

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

关键词: 拟阵, 定价方案, 拟阵基, 完美匹配

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

中图分类号: