考虑属性关联的两阶段获胜者确定模型

杨 娜，廖貅武，雷宏振

(1.陕西师范大学国际商学院，陕西 西安 710119；2.西安交通大学管理学院，过程控制与效率工程教育部重点实验室，陕西 西安 710049)

1 引言

逆向拍卖是一种由买方发起并主导，多个卖方参与竞价的拍卖机制。实践表明，企业采用这种方式采购产品和服务不仅可以提升采购效率，还能大幅度降低采购成本。近年来，逆向拍卖日益成为一种重要的采购解决方案。它与正向拍卖最主要的区别在于其多属性特征。例如，在运输服务采购中，托运商不仅根据运输价格来选择承运人，还需考虑及时性、设备的合适性以及业务的熟悉程度等其他因素。这种多属性特征引出了一个关键的研究问题——获胜者确定问题(winner determination problem, WDP)，即如何综合多个属性评价投标人的报价。

目前主要的研究思路是采用评分函数进行打分。Bichler和Kalagnanam[1]以标准的加性价值函数为评分规则，研究了多单位采购情形下的获胜者确定问题，建立了混合整数规划模型筛选获胜者。Kameshwaran等[2]在此基础上，将存在交易约束以及投标人成本函数具有批量折扣特点的单一产品大规模采购下的报价评价问题归结为一个混合整数优化问题，提出采用目标规划技术进行求解。Cheng Chibin[3]将密封多属性逆向拍卖机制下买方的获胜者确定问题归结为一个多属性决策问题，并使用TOPSIS方法对投标人的报价进行评价。Ray等[4,5]使用了拟线性评分函数，研究了中标者实际交付与承诺报价不一致情形下的获胜者确定问题。王明喜等[6]基于加权和评分函数，提出了一种赢者决策方案，并给出了风险中性者和风险规避者的均衡投标策略。在这些以评分函数为基础的研究中，Pham等[7]指出加性效用函数是目前最为普遍使用的评分函数。该函数必须以属性相互偏好独立为前提，这在现实中很难满足。

针对这一不足，已有一些学者进行了改进。Talluri等[8]基于数据包络分析思想提出了一个考虑属性之间相互关联的价值函数。但该函数只能反映部分属性之间的交互关系，具有一定的局限性。呼大永等[9]采用数据包络分析中的C2R模型确定最终获胜供应商，在解决传统指标体系评价方法中假设属性不相关以及人为设定权重等不足方面做出了有益尝试。Huang Min等[10]考虑到拍卖属性之间的冲突性，引入了BOCR框架，并在其中嵌入前景理论刻画拍卖人的风险规避行为。所提出的PT-BOCR方法首先采用Choquet积分得到下层的评价值，再使用CCSD方法求解上层模型的权重，最后综合二者得到总评价值。刘卫锋等[11]还提出了一种Heronian平均算子来刻画属性间的相互作用。在多准则决策领域，除了这些模型和方法，可反映属性间交互关系的偏好函数还有两类：一类是带惩罚和奖励的一般加性效用函数[12, 13]；另一类是模糊积分，其中建立在k-可加模糊测度上的Choquet积分最为常用。Choquet被广泛应用于管理领域的现实问题[14-16]。这一类型的偏好函数在应用上的最大困难是参数值的获得。虽然文献中提出了一些方法，如Marichal熵方法[17]、菱形成对比较法[18]以及序关系分析法与施密特正交马田系统相结合的方法[19]，但这些方法过于强调理论推演，计算过程复杂，不适合应用于多属性逆向拍卖的现实问题。

文献中有一类研究涉及到拍卖人的偏好揭示。它们大都强调了揭示拍卖人偏好并构造恰当的评分函数的重要性[1, 20]。最新的多属性在线逆向拍卖的综述性文章[7]还专门将偏好揭示列为一项重要的研究内容。于红岩和刘仲英[21]通过设定多属性的期望值和保留值作为投标参考点，提出了一种基于拍卖方偏好揭示的多属性网上拍卖模型。Karakaya和Köksalan[22]在多轮次的多属性拍卖框架下提出了一种交互式决策方法，从拍卖人的历史偏好信息中间接地估计其偏好函数。拍卖过程中不断将新的偏好信息加入偏好约束集，从而进一步精确对偏好函数的估计。Yang Na等[23]进一步扩展了这一研究，设计了交互式偏好引出框架，并提出了相应的偏好揭示方法。这些方法都为获得拍卖人的偏好函数进而确定获胜者提出了新的思路。

本文将从拍卖人偏好揭示的角度构造Choquet积分形式的评分函数。在获胜者确定方法的选择上，文献中有一些学者研究了两阶段拍卖机制[24]，这种方式有利于降低拍卖的复杂性并易于被拍卖人所接受，受到这些研究的启发，本文采用一种两阶段的方法确定获胜者。这一方法首先考虑所有与拍卖人主观偏好一致的参数值筛选可能获胜报价，再以与整体评价结果最为接近的报价排序为依据确定稳健获胜报价。该方法的理论贡献主要反映在：以模糊测度和模糊积分表达拍卖人评价属性之间的关联性，避免了属性相互偏好独立的强假设，扩展了现有研究；以所有与主观偏好相一致的参数集表示拍卖人的评分函数，避免人为选择的随意性；侧重分析拍卖人更关注的潜在获胜报价，避免分析大量不可能获胜报价的偏好关系，提升了评价效率；提出了选择稳健获胜报价的规则。

2 问题的提出

多属性逆向拍卖中，拍卖人的评价属性集记为G={g1,g2,…,gn}，其中gi表示第i个属性。考虑到属性之间的关联性，引入模糊测度和模糊积分表示拍卖人的偏好。相关的基本知识[25]介绍如下：

定义1：P(G)表示G的幂集，如果集函数μ:P(G)→[0,1]满足以下非负有界性条件和单调性条件：

(a-1)μ(Ø)=0，μ(G)=1；

(a-2)∀A,B∈P(G)，A⊆B，有μ(A)≤μ(B)，

则称μ是G上的模糊测度。

对每个属性集A⊆G，μ(A)可理解为A的权重或重要程度。

定义2：模糊测度μ可由其默比乌斯变换唯一地表示为：

(1)

其中，集函数m(B)反映出忽略任意gi∉B与gj∈B之间的关联时，集合B中属性之间的关联程度。任意集函数m：p(G)→不一定对应一个模糊测度的默比乌斯变换形式。根据条件(a-1)、(a-2)以及式(1)，以下两个条件保证了m(·)能唯一地确定集合G上的一个模糊测度：

定义3: 如果一个模糊测度μ的默比乌斯变换满足：对任意A⊆G，若|A|>k，有m(A)=0，并存在A⊆G，|A|=k，使得m(A)≠0，则该模糊测度被称为k-可加模糊测度。

k-可加模糊测度可表示任意复杂度的模糊测度。k值越大，模型表现力越强，但参数越多。由于现实拍卖问题中三个及三个以上的属性之间的关联并不多见，本文为简化建模，采用定义在2-可加模糊测度上的Choquet积分作为拍卖人的评分函数。该积分由默比乌斯变换表示为[26]：

(2)

其中，b表示投标人的报价，gi(b)表示该报价在属性gi上的评价值。

图1 多轮次拍卖流程

3 两阶段获胜者确定模型

3.1 定义与偏好信息一致的评分函数

关联程度大于gk和gl之间的关联程度。

根据拍卖人所提供的偏好信息可推测得到2-可加模糊测度的参数值。如果由这些估计值所确定的偏好关系与拍卖人的主观判断相吻合，称这样的2-可加模糊测度与偏好信息相一致。这样，所有一致的2-可加模糊测度可由以下约束所定义：

(3)

其中，前三个不等式约束分别表示在拍卖人给出的三种形式的报价比较信息下报价得分所应满足的条件。δ是拍卖人的无差异阈值，δ≥0。若两个报价得分值之差低于该阈值，拍卖人不能区分它们的优劣。反之，若拍卖人明确给出优于关系，则得分值之差必然超过该阈值。因此，ε1取略大于δ的数。第四个不等式反映的是属于较强偏好强度类的两个报价的得分差值也较大。属性权重满足第五个约束式，其中Iμ({gi})表示单个属性gi的相对重要程度。属性集A(A⊆G)中各属性之间的关联程度用I(A)表示。由于文中只考虑属性两两关联，当|A|>2时，I(A)=0。第六至第八个约束式分别表示当属性之间存在互补性、替代性和相互独立时关联系数需满足的条件，其中ε2是较小的正数，目的在于保证严格不等式成立。第九个约束式对应属性关联程度比较信息。以上各式中的Cμ(·)和I(·)可由集函数m(·)表示。根据Grabisch对关联系数的定义及该系数与默比乌斯变换的关系[27]，单个属性的相对重要程度以及属性两两关联系数分别表示为：

(4)

I({gi,gj})=m({gi,gj}),∀{gi,gj}⊆G

(5)

3.2 获胜者选择分析

3.2.1 可能获胜报价

根据这一定义，建立如下的线性规划模型LP1确定备选获胜报价集。

LP1(bi):Maxyi

(6)

定理1如果bi∉Wt-1，必有bi∉Wt。

推论1：如果bi∉Wt，则对任意k>t，bi∉Wk。

该定理表明这种确定获胜者的方式保证了在某一轮不可能获胜的报价也不可能在以后各轮中获胜。因此，每一轮筛选可能获胜者时只需考虑上一轮的潜在获胜报价和本轮的新报价，即Wt⊆(Wt-1∪Bt)。

3.2.2 稳健获胜报价

当存在多个可能获胜报价时，进一步对这些报价进行分析，选择其中的稳健获胜者推荐给拍卖人。稳健获胜报价是这样的一个报价：该报价为获胜者时其他的可能获胜报价也排在尽可能靠前的位置；当存在多个这样的报价使得其他可能获胜报价排序最靠前时，选择其中使得所有可能获胜报价与不可能获胜报价得分总差值最大的报价。图2以一个示例说明了挑选稳健获胜者的思路。该例中，报价集合中共有5个报价，其中b2、b3和b5为可能获胜报价。当b2为获胜者时，其他两个可能获胜报价b3和b5分别排在第4位和第2位；当b3为获胜者时，b2和b5分别排在第3位和第2位；当b5为获胜者时，b2和b3可能排在第2、3位，也可能排在第3、4位。可见，b3和b5为获胜者时可保证其他可能获胜报价排在最靠前的位置(即依次排在第2、3位)。接下来，再考虑二者分别为获胜者时所有可能获胜报价与不可能获胜报价之间的整体得分差异。在示例数据下，b5为获胜者时得分总差值更大，因此选择b5为稳健获胜者。在这一规则下，使稳健获胜报价得分最高的评分函数的评价结果与所有一致的评分函数的评价结果最为接近。在所有可能获胜报价都有最好的评价时，稳健获胜报价为最优中的最优。

图2 稳健获胜报价选择示意图

根据这一思路，建立如下的混合整数规划MIP2挑选稳健获胜者。

bj∈BWt

(7)

(8)

(9)

3.3 获胜者确定方法的基本步骤

通过上述分析，文中确定获胜者的基本步骤概括如下。

步骤1：拍卖初始时刻(t=0)，拍卖人提出评价属性集，以及能反映自身偏好的参考报价信息和相应偏好信息；

步骤2：根据3.1节中的方法确定与拍卖人偏好一致的2-可加模糊测度集；

步骤3：检查拍卖结束条件是否已满足。若已满足，输出当前获胜者为最终获胜者，拍卖结束；若未满足，拍卖进入下一轮(t=t+1)；

步骤4：投标人进行投标；

步骤5：利用模型LP1确定本轮的备选获胜报价集Wt；

4 算例分析

4.1 仿真实验

某企业因业务需求要采购一批台式机用于日常办公。其采购部门拟通过一个网上拍卖项目采购这批商用台式机。根据企业的现实应用需求，该部门(即拍卖人)将以四个指标(即属性)评价供应商(即投标人)提供的台式机，分别是：价格(g1)、处理器性能(g2)、内存容量(g3)和硬盘容量(g4)。拍卖活动正式开始之前，他们考察了市场上部分商用台式机产品(即参考报价，如表1所示)，并向拍卖网站提交了一些关于这些台式机的评价信息(即偏好信息, 如表2所示)表达其采购偏好，期望拍卖网站根据这些信息筛选出符合其要求的报价。

表1 参考报价信息

注：产品信息来自太平洋电脑网产品报价频道

表2 采购部门提交的偏好信息

u1(3599)+u2(i34170)+u3(4G)+u4(1000G)>u1(5499)+u2(i74770)+u3(4G)+u4(1000G)

(10)

同时，根据r6≻r1，有：

u1(10499)+u2(i74770)+u3(2G)+u4(500G)>u1(3599)+u2(i34170)+u3(2G)+u4(500G)

(11)

由(10)得到：

u1(3599)+u2(i34170)>u1(5499)

+u2(i74770)

(12)

而由(11)得到：

u1(3599)+u2(i34170)

+u2(i74770)

(13)

根据边际价值函数u1(·)的单调非递增性质，即价格越高拍卖人的边际效用越低，有：

u1(10499)≤u1(5499)

(14)

因此不等式(12)和(13)明显地不一致，这表明拍卖人的偏好信息违反了偏好独立假设，传统的加性效用函数失效。

本例采用Choquet积分表达采购部门的偏好。首先对初始偏好信息进行预处理。以权威IT产品评测机构Pconline发布的处理器横向测评结果为依据，采取3Dmake Vantage得分值作为处理器性能的评价值。再根据目前太平洋电脑网所有商用台式机产品在各属性上的取值范围，将参考报价各指标值转换到[0,100]统一标度上，0表示该指标上的最差得分，100表示最好得分。

以下采用仿真实验进行分析。可能对计算结果有影响的因素主要包括每次拍卖的轮数和每轮的报价数目，为方便表述，分别记为r和b。首先设定每一次采购进行3轮(即r=3)，每一轮参与竞价的报价数目10个(即b=10)。随机生成各报价在各属性上的评价值。重复进行100次拍卖(即重复计算100次)，可能获胜报价的比例如图3所示。单次运算中最多有36.67%的报价可能获胜，最少仅有13.33%，100次运算的平均值为21.93%。控制每一轮参与竞价的报价数目不变(b=10)，拍卖轮数由1轮增加到10轮，每种实验设置仍重复执行100次，平均可能获胜报价比例如图4所示。如图，可能获胜报价的比例基本上与拍卖轮数无关。在每轮报价数目为10的规模下，可能获胜报价所占的比例在22.14%左右。

图3 可能获胜报价比例

图4 不同拍卖轮数下平均可能获胜报价比例

控制每一次拍卖的轮数为3轮(r=3)，每一轮参与竞价的报价数目发生变化时，运算执行100次的平均可能获胜报价比例如图5所示。如图，可能获胜报价的比例将随着报价个数的增加而递减。当报价数目为3时，平均有52.44%的报价为可能获胜报价，但当报价数目增加到12个，可能获胜报价比例降低至18.58%。这与拍卖实践中的已有经验一致，当报价增多时，意味着供应商之间的竞争增强，将导致具有相对领先优势的报价减少。从图中还可以看到，这种递减趋势在报价数目持续增多时减缓，报价数目分别为10、11和12时，平均的可能获胜报价比例分别为21.93%、20.12%和18.58%。

图5 不同报价个数下平均可能获胜报价比例

综上，尽管可能获胜报价的比例会随着报价数目的变化而变化，但整体上，实验表明大量的报价为不可能获胜报价。即便在每一轮仅有3个报价的情形下，仍有超过45%的报价不可能获胜，且随着报价数目的增多，不可能获胜报价的比例持续增加，当一轮报价增加到10个时，不可能获胜报价高达80%。这说明本文提出的获胜者确定方法在第一阶段筛选出可能获胜报价非常必要，而且参与竞价的供应商越多，本文的方法越适用。

4.2 方法比较

设置一次拍卖进行3轮(r=3)，且保持相同的初始偏好信息、相同的随机报价信息和相同的反馈信息。报价数目在b=3到b=12之间变动时，两种方法在“可识别比例”和“未知报价比例”两个指标上的变化情况如表3所示。其中，“可识别比例”指的是在所有100次运算中，TSA可识别出由ROR方法确定的被占优报价的平均比例。从表中可以看到，由ROR两两比较所确定出的必然被占优报价100%地被TSA方法识别为不可能获胜报价，表明了TSA方法的有效性。此外，ROR方法的两两比较分析还可能产生一类“未知报价”，即既不必然优于其他报价、也不必然被其他报价占优的报价，这类报价无法确定其是否可能获胜。如表3所示，当一轮中参与竞价的报价数目较少时，未知报价的平均比例较高。因此，整体来说，在计算效果上TSA略优于ROR。

表3 不同报价数目下TSA的可识别比例和ROR的未知报价比例

为比较两种方法的计算效率，首先设置报价个数b=10，每次拍卖由1轮增加到10轮时，分别运算100次，两种方法平均每一轮的运行时间如图6所示。设置拍卖轮数r=3，报价数目由3个增加到12个时，同样执行运算100次，平均每一轮的运行时间如图7所示。可以看到，在r和b变化时，两种方法的运行时间变化呈现相似的规律。首先，TSA和ROR方法的平均运行时间都随着r和b的增加而增大。这是因为，当拍卖轮数增加时，各轮要处理的反馈信息增多；当报价数目增多时，每一轮的计算量增加。虽然两种方法都呈现出递增趋势，但在相同的问题规模下，TSA花费的时间代价总是比ROR小。尤其是当拍卖轮数和报价数目较大时，TSA在计算效率上的优势更为明显。

图6 拍卖轮数变化时平均每轮运行时间

图7 报价数目变化时平均每轮运行时间

综上，无论是在计算效果还是计算效率上，本文方法均优于Angilella等的方法。通过仿真实验，表明了本文方法更适用于拍卖轮数较多、报价规模较大的拍卖项目。

5 结语

多属性逆向拍卖日益广泛地应用在采购活动中，其中的关键问题是获胜者确定问题。目前主要的方法是采用评分函数进行打分，但是现有研究假设属性不相关，具有局限性。本文根据模糊测度和模糊积分理论，提出了一种考虑属性两两关联的获胜者确定方法。由于参数值众多且拍卖人难以直接提供，文中从拍卖人提供的偏好信息中推测Choquet积分形式的评分函数。与偏好信息一致的评分函数可能不唯一，不同的评分函数可能导致不同的决策结果，因此文中考虑了所有一致的评分函数集确定获胜者。首先根据拍卖人的主观偏好定义了与其一致的2-可加模糊测度集，其次根据该评分函数集合挑选出备选获胜报价集，最后以与所有一致评分函数的评价结果最为接近的报价排序为依据，选出得分最高者作为稳健获胜报价推荐给拍卖人。拍卖人确认最终获胜者，产生的反馈信息进入下一轮的偏好信息集，进一步精确方法的推荐结果。

经过随机数据验证，拍卖中不可能获胜报价的比例远高于可能获胜报价比例，且随着供应商竞价增多呈增长趋势，因此在第一阶段筛选出少量的可能获胜报价非常重要。与Angilella等提出的方法进行比较发现，文中方法可将全部的必然被占优报价识别为不可能获胜报价，且Angilella等的方法总会存在一小部分的报价无法确知其是否可能获胜，因此在计算效果上本文方法略优。从运算效率上，在相同的问题规模下文中方法花费的时间更短，且随着拍卖轮数和报价数目的增多，该方法的优势更为明显。