集合竞价问题研究

集合竞价问题研究

刘新明,罗超

刘新明；罗超（井冈山大学信息科学与传媒学院，吉安343009）

摘要：20世纪中期以来，随着纳什均衡理论的提出和发展，博弈论（gametheory）逐渐成为一门新兴的科学，它涉及了经济学、管理学、计算机科学、社会学等各个领域，对社会的发展起了极大的推动作用。本文侧重在博弈论中一些具体问题的优化算法的实现与比较，以及其在高性能平台下的并行度和改进情况的分析和研究。

关键词：集合竞价；电子商务；博弈论；全排列穷举算法

中图分类号：TP3-0文献标识码：A文章编号：1006-4311（2010）10-0154-01

0引言

集合竞价在电子商务中起着重要的作用，它的主要特点是能降低投资风险，提高拍卖效率。传统拍卖大多采取非集合竞价方式，如第一价格密封拍卖(first-pricesealed-bidauction)，则竞胜标确定是一件十分容易的事情，只需将“标的”相同的最高价格的标分别挑出即可。如果有ɑ个标，m个待拍项目，则只需用O（ɑm）这么长时间。但是这种竞标方式风险大、效率低，往往难以达到预期的效果。相比传统方式，集合竞价有着良好的实际效果，但在同样条件下，集合竞价竞胜标确定要复杂得多，集合竞价的算法复杂度是指数级，属于NP问题。

1．1问题定义假设M为待拍项目的集合,任意投标人i可以对M中的单项或其项目的组合S∈M投标，标价为bi（S）。集合竞价的基本问题就是求解mɑx∑bi（si）（∪si=M）从而确定最优的竞胜标。

1．2预处理由于在问题求解的初期阶段，会遇到很多冗余标，影响算法运行效率，而这些冗余标能在线性时间内得到去除，故先对所有的标进行预处理能一定程度的提高算法运行速度。

预处理1：对“标的”相同的单一标，只保留其最高价格的标，即有

b（S）=mɑxbi（S）

i∈bidders

预处理2：对“标的”相同的组合标，只保留其最高价格的组合标。这样，其它的标可视为因无“竞争力”而被遗弃掉。

显然，预处理1先是淘汰掉“显性”的无竞争力的标；预处理2则是淘汰掉“隐性”的无竞争力的标,这种标具有一定的欺骗性。

本文所述的标均是经过上述处理后剩下的“标的”不同的标，共n个。

1．3模型设计根据问题的定义和预处理过程，我们给出集合竞价问题的基本模型：

T（M）=max∑b（s）

X∈AS∈X

模型说明：①模型以极大化拍卖商收益为目标，目的是求得最后的竞胜标；②X为一个可行解，即每个项目至多可以分配给一个标；③A为可行解空间，A中的可行解满足两个条件：a）彼此不相交b）所有可行解的并集为整个空间M。

从上面的模型中可以看出，集合竞价问题是一个组合问题。看似容易，但求解却是十分复杂的计算问题，是一个NP难题（NPhardproblem）。

2集合竞价问题算法设计——全排列穷举法

2．1传统算法简介Sandholm首先讨论了用穷举法的思想来对问题进行求解。他指出了该问题可行分配方案(即可行解)的精确数为∑Z（m，q）。这里的Z（m，q）表示将m个项目分配给q个。竞买人的分配方案数，是众所周知的第二类斯特林数，具有如下递推关系：

Z（m，q）=qZ（m-1，q）+Z（m-1，q-1）

其中：Z（m，m）=Z（m，1）=1。

Sandholm根据上面的递推关系证明了可行的分配方案总数为O（m^m）。除非待拍卖的项目数（m<12左右）非常小，否则无法实现对全部的可行解空间进行搜索。

Rothdopf等提出了用动态规划法来对问题求解。算法的求解步数介于O（2^m）和O（3^m）之间，算法搜索的步数只与待拍卖项目数m有关，而与经过预处理后得到的标数n无关。动态规划法仍然不能求得待拍卖项目数（m>20）时问题的最优解。

本文采用的是数字全排列的穷举方法，设计思路清晰，方法直观，缺点是运算复杂度较高O（n！），只能解决n<12时的情况。

2．2全排列穷举法的算法思想注意到，精确算法的本质是要以某种方式遍历整个搜索空间，随后比较其竞标总额的大小，从而确定最优的竞胜标。而先前的各种算法的目的只是尽可能优化的遍历整个搜索空间，而其本质还是穷举。

算法思想：本文所用的全排列穷举法的主要思想是先求出给定的n个标的一个n－全排列，搜索空间内可能出现的所有情况就是n！个搜索序列，把这些序列存储在一个n!*n的数组中，然后在调用创建竞胜标的函数createBid时运用这个数组，从而得到竞胜标。

2．3全排列穷举算法的具体设计过程

设问题的规模为n,则问题的设计过程如下：

（1）建立一个用于计算n全排列的类range，该类中的主要成员包括Result、InsertBid、Bridge、Factorial、GetResult。（2）计算全排列的思想：利用逆序数的一一对应性，逐个求出所有全排列，求出了所有的排列以后，在main函数调用createBid函数，根据每个排列，创造一个标的，存储在一个二维数组中；（3）createBid函数的设计思想：①设置存放标的数组t，t的初始值为空，位置指针指在队头位置；②从对应序列的第一个元素开始，如果和t没有相交，把该标的存放在t中，而t的队尾指针后移一格。③当遍历完一个排列的所有元素后，一次搜索算法结束。④t中的元素个数应为n。⑤计算每次搜索得到的标的的标价总和，存放在数组t_pay中。

2.4当所有的空间都搜索完毕后，去t_pay中最打的元素，其对应的标的就是竞胜标，t_pay[i]的值就是最佳竞价。

3全排列穷举算法的复杂度及优缺点

该算法主要的运算开销在求n的全排列，所以算法的复杂度为O（n！）。该算法简洁明了、易于实现，且覆盖整个搜索空间，故不会出错；但是，正是由于搜索空间较打，该算法存在着存储空间较大，算法复杂度较高，不能用于较大的n等缺点。