基于可拓信息的組合拍賣問(wèn)題的知識(shí)表示

錢 巍，馮玉強(qiáng)

QIAN Wei1,2, FENG Yu-qiang1

（1. 哈爾濱工業(yè)大學(xué) 管理科學(xué)與工程系，哈爾濱 150001；2. 東北農(nóng)業(yè)大學(xué) 經(jīng)濟(jì)管學(xué)院信息管理系，哈爾濱 150030）

0 引言

組合拍賣是一種允許競(jìng)標(biāo)者對(duì)不同的商品組合進(jìn)行投標(biāo)的多物品拍賣機(jī)制。商品的組合形式及其復(fù)雜的協(xié)同價(jià)值結(jié)構(gòu)使得組合拍賣比其他形式的拍賣要復(fù)雜得多。組合拍賣競(jìng)勝者確定問(wèn)題(WDP) 被證明是一個(gè)NP完全問(wèn)題[1]，所以計(jì)算復(fù)雜性和拍賣效率之間的矛盾成為阻礙組合拍賣得到廣泛應(yīng)用的瓶頸問(wèn)題之一。Rothkopf 根據(jù)商品的經(jīng)濟(jì)特性，提出構(gòu)建標(biāo)的一些典型的限制結(jié)構(gòu)如樹(shù)型結(jié)構(gòu)、集合的勢(shì)結(jié)構(gòu)和嵌套幾何結(jié)構(gòu)等，使組合拍賣的WDP問(wèn)題可計(jì)算[1]。Gottlob G等也提出可以通過(guò)分析商品結(jié)構(gòu)來(lái)降低組合拍賣WDP的復(fù)雜性，并證明了即使商品所構(gòu)成的樹(shù)的寬度是3，所構(gòu)成的WDP也是很難處理的，因此，他們提出了在投標(biāo)者之間構(gòu)建限制寬度的超樹(shù)結(jié)構(gòu)，然后采用根據(jù)實(shí)例的特點(diǎn)對(duì)超樹(shù)進(jìn)行分解的方法來(lái)解決WDP問(wèn)題[2]。這些研究在理論上雖然降低了算法復(fù)雜度，但是在實(shí)際應(yīng)用中存在一定困難。因此本文基于可拓學(xué)的基本理論，充分表達(dá)出商品的特有屬性，根據(jù)商品本身固有性質(zhì)以及投標(biāo)者可能進(jìn)行的投標(biāo)組合為分析基礎(chǔ)，描述商品屬性間與投標(biāo)人投標(biāo)組合偏好的依賴關(guān)系，確定可行的商品組合空間。這樣，不但可以降低WDP算法的搜索空間，還可以滿足分配過(guò)程的激勵(lì)相容機(jī)制，實(shí)現(xiàn)資源的有效配置。通過(guò)這種對(duì)實(shí)際中的組合拍賣商品進(jìn)行形式化表示，并以商品固有知識(shí)的內(nèi)在聯(lián)系為基礎(chǔ)，對(duì)邏輯上關(guān)聯(lián)的商品探索其結(jié)構(gòu)，充分表達(dá)出組合拍賣的優(yōu)勢(shì)，體現(xiàn)商品的替代性和互補(bǔ)性，同時(shí)也兼顧考慮投標(biāo)者的偏好，縮小競(jìng)勝標(biāo)算法的搜索空間，縮短組合拍賣理論與實(shí)踐間的差距，更有利于解決實(shí)際應(yīng)用中拍賣商品的投標(biāo)組合問(wèn)題。

1 組合拍賣問(wèn)題與可拓理論

1.1 組合拍賣問(wèn)題描述

組合拍賣是能充分表達(dá)出商品的協(xié)同價(jià)值的一種機(jī)制。假設(shè)一個(gè)拍賣商有n件不同的商品G={g1,g2,……gn}待拍賣，若干個(gè)人競(jìng)標(biāo)，每個(gè)投標(biāo)人可以對(duì)其中的任意商品組合進(jìn)行投標(biāo)，在最極端的情況下，拍賣商將得到2n-1個(gè)不同投標(biāo)。在實(shí)際應(yīng)用中，根據(jù)拍賣商品的屬性特點(diǎn)，不同商品間具有的替代性和互補(bǔ)性，以及投標(biāo)人的偏好等，現(xiàn)假設(shè)得到m個(gè)投標(biāo)組合方案B={b1,b2,……每個(gè)投標(biāo)組合方案的競(jìng)標(biāo)價(jià)格pm。單個(gè)投標(biāo)者的投標(biāo)組合不能被拆分，要么全部接受，要么拒絕接受。而任何一個(gè)商品至少屬于一個(gè)投標(biāo)組合。

1.2 可拓學(xué)的基本理論

在可拓學(xué)中，采用以物元、事元和關(guān)系元為基本元的形式化描述體系來(lái)表示客觀世界的萬(wàn)物以及它們間的關(guān)系。這種表示模型即可以描述事物的數(shù)量關(guān)系，也可以描述事物本身的固有特性。

定義1：物元是描述事物的基本單元，由物N，n個(gè)特征c1,c2,……cn及N關(guān)于ci(i=1,2……n) 的量值vi(i=1,2……n)構(gòu)成的有序三元組，表示陣列如下：

定義2：事元用來(lái)描述事物間的相互作用，由動(dòng)詞d、動(dòng)詞的n個(gè)特征b1,b2,……bn及d關(guān)于bi(i=1,2……n)所取得的量值ui(i=1,2……n) 構(gòu)成的有序三元組，表示陣列如下：

定義3：關(guān)系元始描述物元、事元之間的各種各樣關(guān)系以及這些關(guān)系變化間的相互影響、相互作用，由關(guān)系詞或稱關(guān)系符s、n個(gè)特征a1,a2,……an及N個(gè)相應(yīng)量值wi(i=1,2……n)構(gòu)成的有序三元組，表示陣列如下：

這些基元都具有可拓性質(zhì)，包括發(fā)散性、可擴(kuò)性、相關(guān)性和蘊(yùn)含性等。這些性質(zhì)可以通過(guò)可拓分析，分別形成發(fā)散樹(shù)、分合鏈、相關(guān)網(wǎng)和蘊(yùn)含系等。而且，由于客觀世界存在事物的復(fù)雜性，為了更好地描述這些事物，也可以使用物元、事元以及關(guān)系元的復(fù)合形式來(lái)表示事物及事物間的相互作用，即可以使用復(fù)合元以及相應(yīng)運(yùn)算來(lái)描述復(fù)雜的客觀事物。

2 基于可拓信息組合拍賣問(wèn)題知識(shí)表示設(shè)計(jì)

基元可以對(duì)拍賣商品的很多自然信息進(jìn)行描述，基元的可拓性質(zhì)可以表達(dá)出商品的內(nèi)在邏輯關(guān)系，從而能更好地應(yīng)用優(yōu)化技術(shù)來(lái)解決組合拍賣的實(shí)際應(yīng)用問(wèn)題。

拍賣商品G={g1,g2,……gn}中的每個(gè)商品用物元來(lái)表示它的基本屬性。如：

其中g(shù)i(i=1,2……n) 表示待拍賣的任意一個(gè)商品；其特征屬性c除了價(jià)格和數(shù)量以外，其余都是根據(jù)不同商品所表達(dá)的對(duì)應(yīng)的屬性，比如服裝類商品，其它特征可以為顏色、尺碼、款式等屬性，對(duì)于電器類商品，其它特征可以為功能、功率、型號(hào)等屬性；而vi(i=1,2……n)分別表示這些屬性ci(i=1,2……n) 所對(duì)應(yīng)的取值范圍，也成為c的量域。根據(jù)物元的發(fā)散規(guī)則，可以對(duì)這些所表示的商品按照實(shí)際需求進(jìn)行分組歸類。即

這種分類即能表達(dá)不同類商品的各自屬性特征，也可以表達(dá)同類商品的同種屬性的不同程度特征。根據(jù)組合拍賣的要求，設(shè)價(jià)格p為物元的評(píng)價(jià)特征，量值p(R)=v，以商品特性范圍設(shè)定相應(yīng)的論域v(p)，P為正域，p v(p)，作靜態(tài)可拓集合 ，關(guān)聯(lián)函數(shù)為K(R)=k(p(R))=k(v)。若對(duì)商品的要求不僅涉及價(jià)格，還涉及到其他屬性如顏色(c)、數(shù)量(s)等，則這些屬性也可以作為評(píng)價(jià)特征，則相應(yīng)關(guān)聯(lián)函數(shù)發(fā)散為

事元可以表示投標(biāo)人的投標(biāo)行為，如：

其中hi(i=1,2……j)表示j個(gè)投標(biāo)人中任意一人對(duì)所要拍賣的任意商品gi(i=1,2……n)進(jìn)行投標(biāo)。根據(jù)事元的可組合性質(zhì)，式(8)可以分解成一個(gè)投標(biāo)人對(duì)若干個(gè)商品進(jìn)行投標(biāo)，也可以分解成一件商品被若干個(gè)投標(biāo)人進(jìn)行競(jìng)標(biāo)。

關(guān)系元表示商品間的協(xié)同價(jià)值關(guān)系及商品間的相互組合關(guān)系，分別表示如下：

其中式(9)表示前項(xiàng)gi和后項(xiàng)gj是替代關(guān)系，而其他項(xiàng)表示的是這些具有替代關(guān)系的商品的其他特征，如替代程度特征的描述，wi表示的是這些其他特征的具體量值大小，如描述替代的程度大小、可替代的范圍等。對(duì)于商品的互補(bǔ)或者組合關(guān)系也類似進(jìn)行表示。這些關(guān)系元也可以表示拍賣商和投標(biāo)人之間的關(guān)系，也可以表示商品的分配關(guān)系。根據(jù)關(guān)系元的蘊(yùn)含性質(zhì)，建立需求規(guī)則，也能確定各商品間的組合順序等需求。同理，事元和關(guān)系元也可以根據(jù)發(fā)散規(guī)則以及需求目標(biāo)分別建立相應(yīng)的靜態(tài)集合，確定評(píng)價(jià)特征，建立各自的關(guān)聯(lián)函數(shù)。對(duì)于以上基元所表示的組合拍賣的命題集，建立基元的可拓集合，若以價(jià)格(p)為評(píng)價(jià)特征，則可以通過(guò)所建立相應(yīng)的關(guān)聯(lián)函數(shù)式(10)，考查商品的可行組合情況是否為滿意解。

3 結(jié)論

我們對(duì)組合拍賣中各種要素的這種基于可拓信息的知識(shí)表示方法，能夠充分表達(dá)組合商品的內(nèi)在固有性質(zhì)，充分體現(xiàn)組合拍賣的優(yōu)勢(shì)。由于許多學(xué)者提出根據(jù)商品結(jié)構(gòu)解決組合拍賣競(jìng)勝標(biāo)問(wèn)題，那么以商品實(shí)際屬性來(lái)確定它們的組合結(jié)構(gòu)，則更有利于實(shí)際應(yīng)用。

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

1）根據(jù)所表達(dá)商品屬性，充分運(yùn)用邏輯關(guān)系進(jìn)行優(yōu)化，并將那些在數(shù)學(xué)框架下傳統(tǒng)意義上的無(wú)效信息進(jìn)行提取，然后采用相應(yīng)的投標(biāo)語(yǔ)言進(jìn)行抽象化描述和表示，使其模型化。

2）結(jié)合組合拍賣的實(shí)際應(yīng)用案例，確定商品表達(dá)的實(shí)際可操作性，并分析確定主要的評(píng)價(jià)特征，驗(yàn)證所建立的關(guān)聯(lián)函數(shù)評(píng)價(jià)結(jié)果的優(yōu)劣性。

3）根據(jù)消費(fèi)需求性質(zhì)和消費(fèi)者的選擇約束，以商品表達(dá)屬性為基礎(chǔ)，確定商品組的可分離性及可加性。

4）建立商品的合理及可行性結(jié)構(gòu)，降低組合拍賣競(jìng)勝標(biāo)問(wèn)題的復(fù)雜性，縮小可行解的搜索空間，并實(shí)行有效的資源配置。

[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]劉巍,張秀芳.基于可拓信息的知識(shí)表示.系統(tǒng)工程理論與實(shí)踐,1998,1：104-107.

[6]蔡文,楊春燕,何斌.可拓邏輯初步.科學(xué)出版社,2004.