基于可拓信息的組合拍賣問題的知識表示

錢 巍，馮玉強

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.