基于数据包络分析的混合多属性第二分值拍卖机制_安庆贤.pdf

第 卷 第 期运筹与 管理，年 月 收稿日期：基金项目：国家自然科学基金资助项目（，）作者简介：安庆贤（），男，安徽蚌埠人，教授，博士生导师，研究方向：博弈论与拍卖理论，数据包络分析等；鲍茜（），女，湖北黄冈人，硕士研究生，研究方向：数据包络分析，拍卖理论等；熊贝贝（），通讯作者，女，安徽滁州人，副教授，硕士生导师，研究方向：评价理论与方法等。基于数据包络分析的混合多属性第二分值拍卖机制安庆贤，鲍 茜，熊贝贝（中南大学 商学院，湖南 长沙；湖南大学 工商管理学院，湖南 长沙）摘 要：多属性拍卖在传统价格拍卖的基础上纳入了价格和质量多个属性，已广泛应用于许多领域。本文针对输入几乎没有先验结构且投标人数量足够大的情况，在以往有关多属性拍卖研究的基础上将单个投入扩展为多个投入，将物品的多个属性（价格、完成时间、劳动力数量、质量等因素）合理划分为投入或产出，设计了运行有效的基于数据包络分析的多属性第二分值拍卖机制。与其他方法相比，数据包络分析方法可以有效解决多投入多产出问题，结合多目标规划方法，可以帮助采购方在最大化自身利益的同时，找到整体表现更好的供应商。该机制满足个人理性和激励相容，与传统第二分值拍卖机制相比，在吸引投标人的前提下能够最大化拍卖人的利益。关键词：多属性拍卖；数据包络分析；第二分值拍卖；信息不对称；激励相容中图分类号：文章标识码：文章编号：（）：，（，；，）：，（，），：；引言逆向拍卖作为一种主要拍卖形式广泛应用在采购决策中，可以在信息不对称情况下揭露投标人的私人信息。多属性拍卖作为拍卖的重要组成部分，除价格因素外还考虑了一些非价格因素，比如在工程项目招标过程中，拍卖人不仅考虑价格，还考虑每个投标人针对完成时间、交付质量、投入人力数量等因素的投标。多属性拍卖足以反映现实生活中拍卖交易的复杂性，有利于突出投标人的非价格优势。为了在拍卖中综合考虑物品的多维特性，以往学者提出了分值拍卖来解决这个问题。数 据 包 络 分 析（，）是一种有效的数据驱动型的评价工具，用于评估 一 组 同 质 决 策 单 元（，）的表现。近年来，该方法已经得到广泛的开发并被应用于多输入多输出复杂系统的性能评估，。从某种程度上来说，十分适合应用于拍卖机制的设计中。首先，在不考虑共谋的情况下，参与拍卖的投标人在某种程度上是独立和同质的，每个投标人都可以视为一个。其次，多属性拍卖往往考虑的不只是价格和质量两种属性，很多情形下会涉及到多个输入输出。第三，对 进行效率测度时无需对投入产出进行标准化，这种无量纲测度使得比较投标更容易。最后，可在不事先假定生产边界形式的情况下测量单个 的相对效率，非常适合评估投标人的事前相对效率。基于此，本文结合 方法设计了混合多属性第二分值拍卖机制。为了克服传统 模型对 区分能力不足的问题，以往学者提出了基于规模报酬不变（，）的超效率 模型，从参考集中排除了被评估的，这种想法非常适合设计有效的拍卖机制。等指出在 情况下的超效率 模型不会出现无可行解的问题。在实际拍卖中，投标人的数量通常足够大，并且拍卖通常向一定范围内具有相似生产规模的公司开放。此外，利用 选择最佳供应商时，最好是在参考集中排除被评估的，因为如果被评估的 可以影响有效的生产前沿面，那么他将在某种程度上缺乏提高自身表现的动力。因此，本文采用 超效率模型来进行多属性拍卖机制的设计。等首次将 应用于拍卖机制设计，结合 设计了一种新的第二分值拍卖机制。以往将 与拍卖相结合的研究较少，而 等提出的拍卖机制仅考虑价格和质量属性，应用的 模型中只有一个输入。实际上，在将 运用于拍卖机制时，很难将单个输入扩展为多个输入，并且推导的定理和性质也难以直接泛化。这是因为拍卖人和投标人往往有不同的偏好，对每种投入赋予的偏好权重不尽相同。本文针对输入几乎没有先验结构且投标人数量足够大的情况，提出了一种新的拍卖机制，在先前有关多属性拍卖研究的基础上将单个投入扩展为多个投入。为了更好地处理拍卖中涉及到的多投入多产出的问题，本文结合多目标规划和逆 来确定可以最大化拍卖双方效用的帕累托最优输入，证明了该机制具有的优良性质，并结合应用案例指明了该机制的运行程序及方法。问题描述与模型介绍 问题描述假设风险中立的拍卖人正在从多个投标人中寻求一个合适的供应商，以便将项目（或服务）分配给（）个风险中立的投标人中的一个，。也就是说，多个投标人需要根据拍卖人的招标要求进行投标，然后拍卖人选择一个可以使其自身效用最大化的供应商，并设定激励相容目标。假设投标人 根据招标要求提供的投标由一个 维的输入向量 和一个 维的输出向量 组成，用（，）来表示投标人 能利用至少 的投入生产 的产出。假设产出 可以被验证，即投标人承诺的产出可以被强制执行。例如，拍卖人可以对投标人的投标产出和实际产出之间的偏差实行严厉的惩罚。这样的假设具有一定的合理性，因为产出水平代表了可观察到的投标人的生产能力，拍卖人可以通过监测确定投标人是否按真实产出投标，投标的产出也可以通过惩罚等手段被强制执行。这意味着投标人将始终投标其实际产出，并且我们主要关注事前私人信息的逆向选择问题，而不考虑道德风险问题。产出为 的投标人的实际投入是 ，令 （，）为所有投标人的实际投入向量，这些实际投入通常是投标人的私人信息且不能被第三方验证。机制设计的目标是使投标人按照其真实投入进行投标，即应满足 。拍卖人根据提交的投标来确定中标人以及合同中的预期投入。令 表示拍卖人与中标供应商 约定的预期投入（最终确定后在采购合同中达成一致意见，未必与中标人的投标一致）。该机制更侧重于逆向选择问题的研究（图）。图 拍卖流程 模型 模型的生产可能集为（，）运 筹 与 管 理 年第 卷利用 生产，的估计是根据最小外推原理构造的：是包含（，）（）的集合 的最小子集。在实际的拍卖案例中，尤其是在物流领域，拍卖人需要在时间维度上设置提前期，并在价格维度上设置额外的奖励。这种设置形式将为投标人带来利润空间和时间余量，从而激励投标人对他们的实际投入进行投标。这意味着应该在输出固定的情形下考虑输入的变化，因此采用投入导向的 模型较为合适。如前所述，本文采用 超效率 模型。对于被评价的，投入导向的 超效率模型如下所示，超效率分值被定义为。，（），拍卖机制设计 拍卖机制拍卖人根据模型（）对每个投标人的投标进行打分，超效率分值代表投标人的相对表现。如果一个投标人可以用更少的投入生产更多的产出，那么他将获得更高的超效率分值，这与多属性拍卖中评分规则的设计相符。将投标人 的投标得分记为，即 （，），根据每个投标的得分，可以对所有投标人的投标进行排序。超效率分值可以被视为在排除自身的情况下，求解加权产出与加权投入的比值，那么可以将超效率分值看作性价比，即针对每个投标，求得的超效率分值反映了该投标的性价比。假设拍卖人的目标是最大化性价比，而投标人的目标是最大化性价比的倒数或者最小化性价比。实际上，这种假设是合理的，因为当拍卖人选择最佳竞标者时，能够用最少投入生产最多产出的投标人更受拍卖人青睐，而投标人往往希望拍卖人能设定更高的成本补偿，也就是希望拍卖人能够为中标项目投入更多的钱、预留更长的时间干更少的活。由于投标的分值反映了投标的相对表现，因此不失一般性地，可以认为拍卖人的期望效用是，而投标人的期望效用是。基于第二分值拍卖机制的设计思路，在获胜投标人（中标人）的产出保持不变的情况下，超效率分值需要从（）降低到（）。记拍卖人为中标人设定的目标超效率分值为，即 （）。问题在于确定拍卖人为中标人设定的目标投入，由于超效率分值降低，目标投入应该至少有一种投入有所增加，考虑每种投入分别以不同的比例增加的情形。为了更具体地表达这个问题，假设中标人 的投入从 增加到（），其中向量 且（至少一种投入增加），那么 （，）（）（），（）（），（）（）。考虑以下线性多目标规划问题：，（），（），定理 令，为模型（）的帕累托最优解，那么以下模型的最优值是：（），（），根据定理，如果在产出保持不变的情况下将投入增加到（），则投标人 的超效率分值将降低到（）。因此，为了确定目标投入的值，我们只需要求解多目标规划问题（）。本文采用提出的 约束方法（）确定多目标规划问题的帕累托最优解。的核心思想是选定一个目标函数作为优化对象，其他的目标函数加入适当的松弛或剩余变量作为约束。在应用 之前，需要计算每个目标函数的范围。为了获得只包含帕累托最优解的收益表，提出需要对每个目标函数进行字典式优化。第 部分将详细介绍字典式优化的过程。在构建收益表之后，目标函数的范围被划分为几个具有相同间隔的区间，使用每个网格点分别作为 的值，应用于。对于模型（），如果优化目标函数，那么需将其他目标函数作为约束条件。新问题变为：第 期 安庆贤，等：基于数据包络分析的混合多属性第二分值拍卖机制 （）（）（），其中 是一个足够小的正数（通常位于的区间内），是非负剩余变量。来自于收益表，是相应目标函数的范围（请参见第 部分中有关如何准确获取 和 值的示例）。进一步证明了模型（）仅产生帕累托有效解，这个有用的命题使拍卖人可以轻松地选择自己偏好的有效预期投入，使得本文提出的混合多属性第二分值拍卖更有实际意义。拍卖流程第一步，拍卖人向所有投标人宣布评估标准，然后将所有标准划分为投入和产出。投标人提交投入产出投标（，），。第二步，拍卖人对所有投标进行排名，并运用模型（）计算每个投标的超效率分值 （，），。第三步，得分（超效率分值）最高的投标获胜，即当 （）时，选择投标人 作为获胜投标人（中标人）。第四步，拍卖人为中标人 设定预期投入（或资源）：（，）（）。其中 是根据模型（）计算的拍卖人最偏好的帕累托最优解。拍卖人与获胜投标人签订合同，拍卖结束。在混合多属性拍卖中，投标人提交多属性投标，然后拍卖人通过求解模型（）为所有投标计算反映其相对生产超效率的得分，并选择具有最高超效率分值的投标人作为中标人，这意味着中标人能够以相对较少的投入生产相对较多的产出，选择最高的超效率分值意味着拍卖人选择了最高的性价比。最后，令 （），并根据模型（）计算的 的值确定中标人的预期投入，即预期投入将是 第二分值结果（）。新拍卖机制的性质性质 混合多属性第二分值拍卖机制满足激励相容。性质 混合多属性第二分值拍卖机制满足个人理性。性质 混合多属性第二分值拍卖机制优于传统第二分值拍卖机制，在吸引投标人的前提下能够最大化拍卖人的利益。应用实例本章采用一个应用实例来说明上述拍卖机制的运行方式，该实例基于意大利巴里理工大学某设施翻新工程招标数据集，该数据集曾被应用于，中。第一步，在投标人数量为 的情况下，拍卖人宣布，每个投标（表）均根据投标书中定义的四个标准进行评估。这四个标准包括：价格（以 为单位）、计划工作的执行时间（以周为单位）、工程完工后免费维修时间（以月为单位）以及工程质量（由拍卖人采用 标度进行打分，分值越高代表工程质量越好）。在应用超效率 模型计算投标得分之前，这四个标准需要先划分为投入和产出。投入因素被认为是用于执行工程项目投入的资源，而产出因素则与最终交付的质量有关。在此实例中，为了简单和合理起见，将这四个标准分为两个投入和两个产出（请参见表）。将第 个投标定义为（，）（，）。第二步，运用使用模型（）计算每个投标的超效率分值 （，），并进行排名。表 展示了计算得到的每个投标的超效率分值。表 应用实例：投标、超效率分值和排名投标人价格 完成时间周保修期月工程质量超效率分值 排名投标人 价格 完成时间周保修期月工程质量超效率分值 排名运 筹 与 管 理 年第 卷 第三步，得分最高的投标人获胜。根据表，由于 是最高的超效率分值，因此该工程项目被分配给第 号投标人。第四步，为了计算拍卖人给投标人设定的预期投入，将第 号投标人（中标人）的超效率分值表示为（），第 号投标人的超效率分值（排名第二）表示为（）。那么中标人的预期超效率分值为（）（），可以根据模型（）计算中标人的预期投入。正如第 节所述，可以使用 提出的 方法来求解模型（）的帕累托最优解，即根据模型（）可以计算得到多目标规划问题（