如何优化组合拍卖？

拍卖理论被广泛应用于各种组合优化问题。由于多物品拍卖与指派问题（assignment problem）之间的等价性，Bertsekas（1990）为指派问题开发了所谓的拍卖算法（auction algorithm）。之后，Bertsekas（1992）进一步拓展了拍卖算法，将其应用到网络流问题（network flow problem），如最短路径问题、最小价格流问题、运输问题等。

从拍卖机制设计的角度来说，拍卖人希望寻找效用最大化的拍卖品分配方案。基于拍卖人的不同效用函数，组合拍卖可以界定为两类典型的优化问题。一是胜者决定问题（winner determination problem，WDP），一是组合分配问题（combinatorial allocation problem，CAP）。前者希望最大化拍卖人的期望收益，后者希望最大化拍卖品分配的社会效益。

Rothkopf等（1998）研究了单一单位组合拍卖（single-unit combinatorial auction，SUCA）问题，其中每个拍卖品（bidding object）都只有一个单位物品，因此只能出售给一名竞买人（bidder）。记所有拍卖品的集合为G，其中包含m项不可分割的拍卖品，每项拍卖品只有一个单位。一共有N个竞买人，第i个竞买人的投标（bid）可定义为一个元组（b，Pi，b），其中b⊆G为拍卖品组合，Pi，b为竞买人i愿意为b支付的费用。对于拍卖人（auctioneer）来说，可定义如下的决策变量：

拍卖人所面临的胜者决定问题（WDP）可描述为（Abrache et al.，2007；De Vries and Vohra，2003）：

其中，δj，b为判别函数：

式（11.3）限定每项拍卖品最多分配给一位竞买人；式（11.4）限定每位竞买人最多提出一个拍卖品组合；式（11.5）定义决策域。WDP的目标函数（11.2）为拍卖人收益最大化。WDP是一个NP-complete问题（Rothkopf et al.，1998），甚至于难以求得次优解（Sandholm，2002）。

如果定义竞买人i对拍卖品组合b⊆G的偏好（preference）为vi（b），则拍卖人所面临的组合分配问题（CAP）可描述为（Abrache et al.，2007）：

可见，对于单一单位组合拍卖（SUCA）来说，WDP和CAP具有一样的约束条件，唯一区别就是目标函数。而目标函数恰恰反映了两种不同的拍卖机制设计思想。(www.xing528.com)

式（11.2）至（11.5）定义了SUCA的胜者决定问题。对于多单位组合拍卖（multi-unit combinatorial auctin，MUCA）的胜者决定问题，还需要进行拓展。假设拍卖品j的供应量为Mj。将竞买人i的投标定义为b=（{ab，j}j∈G，Pb），其中ab，j为拍卖品组合中包含的物品j的单位数量，Pb是竞买人的报价。称所有竞买人的投标构成的集合为B，并定义如下的决策变量：

则MUCA的胜者决定问题可描述为（Abrache et al.，2007）：

式（11.13）限定任何拍卖品最终的出售量不能超过其供应量；式（11.14）定义决策域。目标函数（11.12）仍然是拍卖人的收益最大化。MUCA的WDP等价于一个多维背包问题（multidimensional knapsack problem），并已经发展出一些精确算法和搜索算法（Abrache et al.，2007）。

以上的组合拍卖问题并不必须限制在一轮竞拍中结束（Pekečand Rothkopf，2003）。迭代拍卖（iterative auction）允许竞买人在多轮拍卖过程中改变投标。不断调整的投标事实上成为一种信息披露机制。此时，拍卖人的定价策略就极为重要。对单物品拍卖而言，定价比较容易。但是，对于组合拍卖来说，定价就成为很艰巨的挑战（Xia et al.，2004）。

上述三种组合拍卖问题是现有文献中最常见的问题，在实践中也得到较多的应用。许多优化问题都可以转化为上述组合拍卖问题，从而通过拍卖机制设计加以实现和解决。例如，Graves等（1993）将组合拍卖机制应用于选课系统。学生通过信息系统选择课程模块，而非单门课程，学生也可以在选课过程中调整他们的选项。学生完成选课之后，信息系统根据学生的投标分配教室与教师。Rassenti等（1982）设计了应用于机场的密封组合拍卖机制，用于在航空公司之间分配机场跑道。Kutanoglu和Wu（1999）应用组合拍卖机制解决作业车间调度问题（job shop scheduling problem，JSP）。应瑛、寿涌毅（2009）采用组合拍卖方式进行多项目调度以实现项目加强拖期最小化。不过，由于组合拍卖问题是NP-hard问题，在网络带宽分配这样实时性要求比较高的场合，目前尚不能得到很好的应用（Dramitinos et al.，2007）。

表11.1总结了组合拍卖与上述应用之间的对应关系。在这些应用中，由一名（虚拟的）拍卖人负责调整拍卖品的价格，而竞买人则根据自身的约束与偏好，结合当前拍卖品定价，选择合适的一组拍卖品进行投标。显然，在组合拍卖与多项目调度之间也可以建立类似的对应关系，如表11.1最后一行所示。

表11.1　组合拍卖及其应用