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

作者：张莹; 敬新奇; 王长军^*

来源：运筹学学报, 2023, 27(04): 166-174.

DOI：10.15960/j.cnki.issn.1007-6093.2023.04.009

• 拟阵
• 定价方案
• 拟阵基
• 完美匹配

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

• 单位
  中国科学院数学与系统科学研究院; 北京电子科技学院