基于可拓信息的组合拍卖问题的知识表示

钱 巍，冯玉强

QIAN Wei1,2, FENG Yu-qiang1

（1. 哈尔滨工业大学 管理科学与工程系，哈尔滨 150001；2. 东北农业大学 经济管学院信息管理系，哈尔滨 150030）

0 引言

组合拍卖是一种允许竞标者对不同的商品组合进行投标的多物品拍卖机制。商品的组合形式及其复杂的协同价值结构使得组合拍卖比其他形式的拍卖要复杂得多。组合拍卖竞胜者确定问题(WDP) 被证明是一个NP完全问题[1]，所以计算复杂性和拍卖效率之间的矛盾成为阻碍组合拍卖得到广泛应用的瓶颈问题之一。Rothkopf 根据商品的经济特性，提出构建标的一些典型的限制结构如树型结构、集合的势结构和嵌套几何结构等，使组合拍卖的WDP问题可计算[1]。Gottlob G等也提出可以通过分析商品结构来降低组合拍卖WDP的复杂性，并证明了即使商品所构成的树的宽度是3，所构成的WDP也是很难处理的，因此，他们提出了在投标者之间构建限制宽度的超树结构，然后采用根据实例的特点对超树进行分解的方法来解决WDP问题[2]。这些研究在理论上虽然降低了算法复杂度，但是在实际应用中存在一定困难。因此本文基于可拓学的基本理论，充分表达出商品的特有属性，根据商品本身固有性质以及投标者可能进行的投标组合为分析基础，描述商品属性间与投标人投标组合偏好的依赖关系，确定可行的商品组合空间。这样，不但可以降低WDP算法的搜索空间，还可以满足分配过程的激励相容机制，实现资源的有效配置。通过这种对实际中的组合拍卖商品进行形式化表示，并以商品固有知识的内在联系为基础，对逻辑上关联的商品探索其结构，充分表达出组合拍卖的优势，体现商品的替代性和互补性，同时也兼顾考虑投标者的偏好，缩小竞胜标算法的搜索空间，缩短组合拍卖理论与实践间的差距，更有利于解决实际应用中拍卖商品的投标组合问题。

1 组合拍卖问题与可拓理论

1.1 组合拍卖问题描述

组合拍卖是能充分表达出商品的协同价值的一种机制。假设一个拍卖商有n件不同的商品G={g1,g2,……gn}待拍卖，若干个人竞标，每个投标人可以对其中的任意商品组合进行投标，在最极端的情况下，拍卖商将得到2n-1个不同投标。在实际应用中，根据拍卖商品的属性特点，不同商品间具有的替代性和互补性，以及投标人的偏好等，现假设得到m个投标组合方案B={b1,b2,……每个投标组合方案的竞标价格pm。单个投标者的投标组合不能被拆分，要么全部接受，要么拒绝接受。而任何一个商品至少属于一个投标组合。

1.2 可拓学的基本理论

在可拓学中，采用以物元、事元和关系元为基本元的形式化描述体系来表示客观世界的万物以及它们间的关系。这种表示模型即可以描述事物的数量关系，也可以描述事物本身的固有特性。

定义1：物元是描述事物的基本单元，由物N，n个特征c1,c2,……cn及N关于ci(i=1,2……n) 的量值vi(i=1,2……n)构成的有序三元组，表示阵列如下：

定义2：事元用来描述事物间的相互作用，由动词d、动词的n个特征b1,b2,……bn及d关于bi(i=1,2……n)所取得的量值ui(i=1,2……n) 构成的有序三元组，表示阵列如下：

定义3：关系元始描述物元、事元之间的各种各样关系以及这些关系变化间的相互影响、相互作用，由关系词或称关系符s、n个特征a1,a2,……an及N个相应量值wi(i=1,2……n)构成的有序三元组，表示阵列如下：

这些基元都具有可拓性质，包括发散性、可扩性、相关性和蕴含性等。这些性质可以通过可拓分析，分别形成发散树、分合链、相关网和蕴含系等。而且，由于客观世界存在事物的复杂性，为了更好地描述这些事物，也可以使用物元、事元以及关系元的复合形式来表示事物及事物间的相互作用，即可以使用复合元以及相应运算来描述复杂的客观事物。

2 基于可拓信息组合拍卖问题知识表示设计

基元可以对拍卖商品的很多自然信息进行描述，基元的可拓性质可以表达出商品的内在逻辑关系，从而能更好地应用优化技术来解决组合拍卖的实际应用问题。

拍卖商品G={g1,g2,……gn}中的每个商品用物元来表示它的基本属性。如：

其中gi(i=1,2……n) 表示待拍卖的任意一个商品；其特征属性c除了价格和数量以外，其余都是根据不同商品所表达的对应的属性，比如服装类商品，其它特征可以为颜色、尺码、款式等属性，对于电器类商品，其它特征可以为功能、功率、型号等属性；而vi(i=1,2……n)分别表示这些属性ci(i=1,2……n) 所对应的取值范围，也成为c的量域。根据物元的发散规则，可以对这些所表示的商品按照实际需求进行分组归类。即

这种分类即能表达不同类商品的各自属性特征，也可以表达同类商品的同种属性的不同程度特征。根据组合拍卖的要求，设价格p为物元的评价特征，量值p(R)=v，以商品特性范围设定相应的论域v(p)，P为正域，p v(p)，作静态可拓集合 ，关联函数为K(R)=k(p(R))=k(v)。若对商品的要求不仅涉及价格，还涉及到其他属性如颜色(c)、数量(s)等，则这些属性也可以作为评价特征，则相应关联函数发散为

事元可以表示投标人的投标行为，如：

其中hi(i=1,2……j)表示j个投标人中任意一人对所要拍卖的任意商品gi(i=1,2……n)进行投标。根据事元的可组合性质，式(8)可以分解成一个投标人对若干个商品进行投标，也可以分解成一件商品被若干个投标人进行竞标。

关系元表示商品间的协同价值关系及商品间的相互组合关系，分别表示如下：

其中式(9)表示前项gi和后项gj是替代关系，而其他项表示的是这些具有替代关系的商品的其他特征，如替代程度特征的描述，wi表示的是这些其他特征的具体量值大小，如描述替代的程度大小、可替代的范围等。对于商品的互补或者组合关系也类似进行表示。这些关系元也可以表示拍卖商和投标人之间的关系，也可以表示商品的分配关系。根据关系元的蕴含性质，建立需求规则，也能确定各商品间的组合顺序等需求。同理，事元和关系元也可以根据发散规则以及需求目标分别建立相应的静态集合，确定评价特征，建立各自的关联函数。对于以上基元所表示的组合拍卖的命题集，建立基元的可拓集合，若以价格(p)为评价特征，则可以通过所建立相应的关联函数式(10)，考查商品的可行组合情况是否为满意解。

3 结论

我们对组合拍卖中各种要素的这种基于可拓信息的知识表示方法，能够充分表达组合商品的内在固有性质，充分体现组合拍卖的优势。由于许多学者提出根据商品结构解决组合拍卖竞胜标问题，那么以商品实际属性来确定它们的组合结构，则更有利于实际应用。

下一步需要做的工作如下：

1）根据所表达商品属性，充分运用逻辑关系进行优化，并将那些在数学框架下传统意义上的无效信息进行提取，然后采用相应的投标语言进行抽象化描述和表示，使其模型化。

2）结合组合拍卖的实际应用案例，确定商品表达的实际可操作性，并分析确定主要的评价特征，验证所建立的关联函数评价结果的优劣性。

3）根据消费需求性质和消费者的选择约束，以商品表达属性为基础，确定商品组的可分离性及可加性。

4）建立商品的合理及可行性结构，降低组合拍卖竞胜标问题的复杂性，缩小可行解的搜索空间，并实行有效的资源配置。

[1]Rothkopf M H,Aleksandar Pekec,Ronald M. Harstard.Computationally manageable combinational auctions[J].Management Science.1998,44(8)：1131-1147.

[2]Gottlob G,Greco G,On The Complexity of Combinatorial Auctions：Structured Item Graphs and Hypertree Decompositions,Proceedings of the eighth annual conference on electronic commerce,2007.

[3]Leyton-Brown,K.,Shoham,Y.,& Tennenholz,M.An algorithm for multi-unit combinatorial auctions.In Proceedings of the seventeenth international conference on artificial intelligence 2000,56-61.

[4]Andersson,Arne,Mathias Tenhunen and Fredrik Ygge, Integer programming for combinatorial auction winner determination," in Proc.Fourth International Conference on Multi-Agent Systems,2000,39-46.

[5]刘巍,张秀芳.基于可拓信息的知识表示.系统工程理论与实践,1998,1：104-107.

[6]蔡文,杨春燕,何斌.可拓逻辑初步.科学出版社,2004.