基于数据包络分析的混合多属性第二分值拍卖机制

安庆贤, 鲍 茜, 熊贝贝

(1.中南大学 商学院,湖南 长沙 410083; 2.湖南大学 工商管理学院,湖南 长沙 410082)

0 引言

逆向拍卖作为一种主要拍卖形式广泛应用在采购决策中，可以在信息不对称情况下揭露投标人的私人信息[1]。多属性拍卖作为拍卖的重要组成部分，除价格因素外还考虑了一些非价格因素，比如在工程项目招标过程中，拍卖人不仅考虑价格，还考虑每个投标人针对完成时间、交付质量、投入人力数量等因素的投标。多属性拍卖足以反映现实生活中拍卖交易的复杂性，有利于突出投标人的非价格优势[2]。为了在拍卖中综合考虑物品的多维特性，以往学者提出了分值拍卖来解决这个问题。数据包络分析(data envelopment analysis, DEA)是一种有效的数据驱动型的评价工具，用于评估一组同质决策单元(decisionmakingunit, DMU)的表现[3]。近年来，该方法已经得到广泛的开发并被应用于多输入多输出复杂系统的性能评估[4,5]。从某种程度上来说，DEA十分适合应用于拍卖机制的设计中。首先，在不考虑共谋的情况下，参与拍卖的投标人在某种程度上是独立和同质的，每个投标人都可以视为一个DMU。其次，多属性拍卖往往考虑的不只是价格和质量两种属性，很多情形下会涉及到多个输入输出。第三，DEA对DMU进行效率测度时无需对投入产出进行标准化，这种无量纲测度使得比较投标更容易[6]。最后，DEA可在不事先假定生产边界形式的情况下测量单个DMU的相对效率[7]，非常适合评估投标人的事前相对效率。基于此，本文结合DEA方法设计了混合多属性第二分值拍卖机制。

为了克服传统DEA模型对DMU区分能力不足的问题，以往学者提出了基于规模报酬不变(constant returns to scale, CRS)的超效率DEA模型，从参考集中排除了被评估的DMU，这种想法非常适合设计有效的拍卖机制。Lee等[8]指出在CRS情况下的超效率DEA模型不会出现无可行解的问题。在实际拍卖中，投标人的数量通常足够大，并且拍卖通常向一定范围内具有相似生产规模的公司开放。此外，利用DEA选择最佳供应商时，最好是在参考集中排除被评估的DMU，因为如果被评估的DMU可以影响有效的生产前沿面，那么他将在某种程度上缺乏提高自身表现的动力[9]。因此，本文采用CRS超效率模型来进行多属性拍卖机制的设计。Bogetoft等[9]首次将DEA应用于拍卖机制设计，结合DEA设计了一种新的第二分值拍卖机制。以往将DEA与拍卖相结合的研究较少，而Bogetoft等[9]提出的拍卖机制仅考虑价格和质量属性，应用的DEA模型中只有一个输入。实际上，在将DEA运用于拍卖机制时，很难将单个输入扩展为多个输入，并且推导的定理和性质也难以直接泛化。这是因为拍卖人和投标人往往有不同的偏好，对每种投入赋予的偏好权重不尽相同。本文针对输入几乎没有先验结构且投标人数量足够大的情况，提出了一种新的拍卖机制，在先前有关多属性拍卖研究的基础上将单个投入扩展为多个投入。为了更好地处理拍卖中涉及到的多投入多产出的问题，本文结合多目标规划和逆DEA来确定可以最大化拍卖双方效用的帕累托最优输入，证明了该机制具有的优良性质，并结合应用案例指明了该机制的运行程序及方法。

1 问题描述与模型介绍

1.1 问题描述

图1 拍卖流程

1.2 DEA模型

如前所述，本文采用CRS超效率DEA模型。对于被评价的DMUk，投入导向的CRS超效率模型如下所示，超效率分值被定义为θk*。

minθk

(1)

λj≥0,j≠k

2 拍卖机制设计

2.1 拍卖机制

拍卖人根据模型(1)对每个投标人的投标进行打分，超效率分值代表投标人的相对表现。如果一个投标人可以用更少的投入生产更多的产出，那么他将获得更高的超效率分值，这与多属性拍卖中评分规则的设计相符。将投标人k的投标得分记为Sk，即Sk=S(xk,yk)=θk*，根据每个投标的得分Sk，可以对所有投标人的投标进行排序。

超效率分值可以被视为在排除自身的情况下，求解加权产出与加权投入的比值，那么可以将超效率分值看作性价比，即针对每个投标，求得的超效率分值反映了该投标的性价比。假设拍卖人的目标是最大化性价比，而投标人的目标是最大化性价比的倒数或者最小化性价比。实际上，这种假设是合理的，因为当拍卖人选择最佳竞标者时，能够用最少投入生产最多产出的投标人更受拍卖人青睐，而投标人往往希望拍卖人能设定更高的成本补偿，也就是希望拍卖人能够为中标项目投入更多的钱、预留更长的时间干更少的活。由于投标的分值反映了投标的相对表现，因此不失一般性地，可以认为拍卖人的期望效用是S，而投标人的期望效用是1/S。

基于第二分值拍卖机制的设计思路，在获胜投标人(中标人)的产出保持不变的情况下，超效率分值需要从S(1)降低到S(2)。记拍卖人为中标人设定的目标超效率分值为αk，即αk=S(2)。

考虑以下线性多目标规划问题:

min{l1,l2,…,lm}

(2)

λj≥0,j≠k,li≥0

minα

在应用AUGMECON之前，需要计算每个目标函数的范围。为了获得只包含帕累托最优解的收益表，Mavrotas[11]提出需要对每个目标函数进行字典式优化。第3部分将详细介绍字典式优化的过程。在构建收益表之后，目标函数的范围被划分为几个具有相同间隔的区间，使用每个网格点分别作为ei的值，应用于AUGMECON。

对于模型(2)，如果优化目标函数l1，那么需将其他目标函数作为约束条件。新问题变为:

s.t.-l2-s2=e2

-l3-s3=e3

(4)

…

-lm-sm=em

λj≥0,j≠k,li≥0,si≥0

其中eps是一个足够小的正数(通常位于10-3～10-6的区间内)，si是非负剩余变量。ei来自于收益表，ri是相应目标函数的范围(请参见第3部分中有关如何准确获取ei和ri值的示例)。Mavrotas[11]进一步证明了模型(4)仅产生帕累托有效解，这个有用的命题使拍卖人可以轻松地选择自己偏好的有效预期投入，使得本文提出的混合多属性第二分值拍卖更有实际意义。

2.2 拍卖流程

第二步，拍卖人对所有投标进行排名，并运用模型(1)计算每个投标的超效率分值Sj=S(xj,yj),j∈N。

第三步，得分(超效率分值)最高的投标获胜，即当Sk=S(1)时，选择投标人k作为获胜投标人(中标人)。

在混合多属性拍卖中，投标人提交多属性投标，然后拍卖人通过求解模型(1)为所有投标计算反映其相对生产超效率的得分，并选择具有最高超效率分值的投标人作为中标人，这意味着中标人能够以相对较少的投入生产相对较多的产出，选择最高的超效率分值意味着拍卖人选择了最高的性价比。最后，令αk=S(2)，并根据模型(4)计算的li的值确定中标人的预期投入，即预期投入将是DEA第二分值结果(1+li)xk。

2.3 新拍卖机制的性质

性质1混合多属性第二分值拍卖机制满足激励相容。

性质2混合多属性第二分值拍卖机制满足个人理性。

性质3混合多属性第二分值拍卖机制优于传统第二分值拍卖机制，在吸引投标人的前提下能够最大化拍卖人的利益。

3 应用实例

本章采用一个应用实例来说明上述拍卖机制的运行方式，该实例基于意大利巴里理工大学某设施翻新工程招标数据集，该数据集曾被应用于[12,13]中。

第二步，运用使用模型(1)计算每个投标的超效率分值sj=s(xj,yj),j∈N，并进行排名。表1展示了计算得到的每个投标的超效率分值。

表1 应用实例：投标、超效率分值和排名

第三步，得分最高的投标人获胜。根据表1，由于S23是最高的超效率分值，因此该工程项目被分配给第23号投标人。

第四步，为了计算拍卖人给投标人设定的预期投入，将第23号投标人(中标人)的超效率分值表示为S(1)=1.5954，第10号投标人的超效率分值(排名第二)表示为S(2)=1.1041。那么中标人的预期超效率分值为α(1)=S(2)=1.1041，可以根据模型(2)计算中标人的预期投入。

正如第2.1节所述，可以使用Mavrotas[11]提出的AUGMECON方法来求解模型(2)的帕累托最优解，即根据模型(4)可以计算得到多目标规划问题(2)的帕累托最优解。在应用AUGMECON方法前，需要通过字典式优化来计算每个目标函数的范围。假设对于拍卖人来说价格比完成时间有更高的优先级，即最小化中标人的预期价格更为重要，那么对本实例中两个目标函数的字典式优化是首先优化第一个目标函数(-l1)(优先级更高)，然后在第一个目标函数(-l1)取最优值的约束下，优化第二个目标函数(-l2)。通过字典式优化可以得到如下收益表。

表2 字典式优化计算得出的收益表

4 结论

本文基于多属性商品采购的客观实际情况，利用DEA方法中的超效率模型、逆DEA模型以及改进的多目标规划求解方法，设计了一种混合多属性第二分值逆向拍卖机制。本研究的主要创新性体现在：(1)在以往研究的基础上，新的拍卖机制考虑了包含多个投入和多个产出的投标，纳入了除价格因素外的其他投入因素，考虑了拍卖人和投标人之间的偏好差异，可以极大地扩展每个投标人的投标空间，充分发挥自身的竞标优势；(2)证明了该机制具有个人理性、激励相容性质，每个投标人投标其真实投入，符合有效拍卖机制的要求；(3)我们发现该机制可有效确保拍卖人能够最大化采购商品的性价比，并从帕累托最优解决方案中选择其最偏好的预期资源投入，使得该机制具有一定的应用价值。