李鑫，滕可

貴州大學(xué)博學(xué)樓926實(shí)驗(yàn)室

異質(zhì)多物品組合在線拍賣初探

李鑫，滕可

貴州大學(xué)博學(xué)樓926實(shí)驗(yàn)室

近十幾年來(lái)網(wǎng)絡(luò)的興起，原本需要面對(duì)面的拍賣活動(dòng)轉(zhuǎn)移到網(wǎng)絡(luò)。通過(guò)本研究基本假設(shè)，本文建立網(wǎng)上互補(bǔ)異質(zhì)多物品拍賣機(jī)制一般模型?；灸Ｐ蜑橐粋€(gè)最大值目標(biāo)函數(shù)，自變量為競(jìng)買人報(bào)告的其估價(jià)。最后，將設(shè)計(jì)的網(wǎng)上互補(bǔ)異質(zhì)多物品拍賣機(jī)制在拍賣品數(shù)量上具體情況下進(jìn)行了驗(yàn)證，證明了設(shè)計(jì)的拍賣機(jī)制是有應(yīng)用價(jià)值的。

異質(zhì)多物品；組合拍賣；在線拍賣

1.緒論

組合拍賣是拍賣的一種，目標(biāo)為多種商品。具體而言，本文以傳統(tǒng)的單物品拍賣機(jī)制模型為出發(fā)點(diǎn)，遵循Fudenburg和Tirole研究思路，用競(jìng)買者的期望收益來(lái)重述拍賣者的最優(yōu)化問(wèn)題，運(yùn)用包絡(luò)定理，把支付規(guī)則用分配規(guī)則進(jìn)行了表示，使得支付規(guī)則與目標(biāo)函數(shù)無(wú)關(guān)，把目標(biāo)函數(shù)的定義域由原來(lái)的分配規(guī)則和支付規(guī)則簡(jiǎn)化為分配規(guī)則，為后續(xù)的網(wǎng)上互補(bǔ)異質(zhì)多物品拍賣機(jī)制設(shè)計(jì)奠定了基礎(chǔ)。

通過(guò)本研究設(shè)置的基本假設(shè)，本文建立了網(wǎng)上互補(bǔ)異質(zhì)多物品拍賣機(jī)制的一般模型?；灸Ｐ蜑橐粋€(gè)最大值目標(biāo)函數(shù)，自變量為競(jìng)買人報(bào)告的其估價(jià)（類型）。最后，將設(shè)計(jì)的網(wǎng)上互補(bǔ)異質(zhì)多物品拍賣機(jī)制在拍賣物品數(shù)量上情況下進(jìn)行了驗(yàn)證，證明了設(shè)計(jì)的拍賣機(jī)制是有應(yīng)用價(jià)值的。

2.文獻(xiàn)綜述

2.1 拍賣相關(guān)研究

Bierman&Fernandez(1998)認(rèn)為拍賣是一個(gè)買賣雙方針對(duì)特定銷售產(chǎn)品進(jìn)行價(jià)格競(jìng)爭(zhēng)的資源分配制度。拍賣的類型主要可以分成兩大類：一、單邊拍賣(one-side auction)，拍賣的情況為多家買方與一家賣方或者為一家買方與多家賣方；二、雙邊拍賣(twoside auction)，指買賣雙方都有數(shù)位參與者。

綜合國(guó)內(nèi)外對(duì)組合拍賣研究，組合拍賣的競(jìng)勝標(biāo)問(wèn)題作為組合拍賣的核心問(wèn)題，組合拍賣的競(jìng)勝標(biāo)求解為NP-hard問(wèn)題，當(dāng)物品較少的時(shí)候，可以利用近似或者窮舉法求得；當(dāng)物品較多時(shí)，需要通過(guò)一些算法求最優(yōu)解。

2.2 網(wǎng)絡(luò)拍賣相關(guān)研究

近十幾年來(lái)網(wǎng)絡(luò)的興起，原本需要面對(duì)面的拍賣活動(dòng)轉(zhuǎn)移到網(wǎng)絡(luò)上進(jìn)行。網(wǎng)絡(luò)拍賣是一種利用網(wǎng)頁(yè)傳遞商品或服務(wù)的信息，透過(guò)競(jìng)標(biāo)過(guò)程將產(chǎn)品或服務(wù)出售的交易模式(Reck,1997)。網(wǎng)絡(luò)拍賣在拍賣的本質(zhì)不變，但是卻增加了不少效益，可以減少成本主要的活動(dòng)在于(Lee,1996)：

(1)減少搜尋成本：在網(wǎng)絡(luò)拍賣里，買賣雙方不受時(shí)間跟金錢限制，可以隨時(shí)隨地搜尋拍賣活動(dòng)的相關(guān)即時(shí)信息。

(2)減少交易成本：網(wǎng)絡(luò)拍賣另一個(gè)效益在于可以即時(shí)的搓和買賣雙方，買賣雙方可以透過(guò)網(wǎng)絡(luò)進(jìn)行談判、對(duì)交易內(nèi)容進(jìn)行做即時(shí)性的調(diào)整，不用像傳統(tǒng)的拍賣花費(fèi)時(shí)間與成本面對(duì)面的進(jìn)行交易與談判。

本研究根據(jù)拍賣要素對(duì)網(wǎng)絡(luò)拍賣要素進(jìn)行特性分析，分別將拍賣角色和交易平臺(tái)要素作以下論述：

1.拍賣經(jīng)營(yíng)者

拍賣經(jīng)營(yíng)者在傳統(tǒng)拍賣里是中介商的角色，要負(fù)責(zé)的是交易平臺(tái)，即場(chǎng)地的管理，在網(wǎng)絡(luò)拍賣里拍賣經(jīng)營(yíng)者提供的交易平臺(tái)為網(wǎng)絡(luò)。拍賣平臺(tái)即所謂的拍賣網(wǎng)站，拍賣網(wǎng)站又可以分為三種基本型態(tài)(Beam&Segev,1998)：

(1)個(gè)人對(duì)個(gè)人(Consumer to Consumer,C2C)

買賣雙方都是以個(gè)人為主，賣方藉由網(wǎng)絡(luò)拍賣出售二手商品，買方則以比價(jià)的方式試圖買到價(jià)格優(yōu)惠的商品。

(2)企業(yè)對(duì)個(gè)人(Business to Consumer,B2C)

其中文簡(jiǎn)稱為“商對(duì)客”?！吧虒?duì)客”是電子商務(wù)的一種模式，也就是通常說(shuō)的直接面向消費(fèi)者銷售產(chǎn)品和服務(wù)商業(yè)零售模式。

(3)企業(yè)對(duì)企業(yè)(Business to Business,B2B)

指企業(yè)間透過(guò)網(wǎng)絡(luò)進(jìn)行線上拍賣，取代以往用電話、傳真等實(shí)體的方式，以節(jié)省時(shí)間及人力上的浪費(fèi)，可大幅促進(jìn)企業(yè)間的存貨周轉(zhuǎn)率。以世界龍頭拍賣網(wǎng)站eBay為例，1995年基于網(wǎng)絡(luò)背景下成立的C2C eBay拍賣網(wǎng)站在1998年總交易金額便已超過(guò)了10億美元。

2.賣家

透過(guò)網(wǎng)絡(luò)的全球化影響下，賣方可以輕易的將產(chǎn)品藉由網(wǎng)絡(luò)行銷到世界各地，開發(fā)潛在顧客。以eBay拍賣網(wǎng)站為例，以下將eBay刊登時(shí)需要的變項(xiàng)做一整理(Anwar,McMillan,&Zheng,2006;電子灣eBay拍賣網(wǎng)站，2013；Lucking-Reiley et al.,2007)：

(1)起標(biāo)價(jià)：賣方可以選擇商品起標(biāo)的價(jià)格，最低為新臺(tái)幣一元起標(biāo)。

(2)最小出價(jià)：賣家決定每次出價(jià)增額至少要達(dá)到多少的金額。

(3)拍賣時(shí)間：拍賣時(shí)間從開始瀏覽商品到競(jìng)標(biāo)結(jié)束的時(shí)間，分為3天、5天、7天或10天。

(4)秘密保留價(jià)：賣家自己設(shè)定一個(gè)不會(huì)在網(wǎng)頁(yè)上被顯示出來(lái)的價(jià)格，而商品最后結(jié)標(biāo)的價(jià)格要超過(guò)保留價(jià)才會(huì)成交。

(5)直接購(gòu)買價(jià)：賣方可以設(shè)定一個(gè)直接購(gòu)買價(jià)格讓不想等待競(jìng)標(biāo)的買家可以立刻買下該商品。

(6)類別：為刊登商品選擇類別。

(7)說(shuō)明：詳細(xì)的描述商品并包括優(yōu)質(zhì)的圖片、合理的郵資。

在eBay拍賣里，使用者可以在交易中查看的拍賣信息有物品目前的價(jià)格、出價(jià)者號(hào)碼、賣家號(hào)碼、當(dāng)前勝出出價(jià)者；而在交易結(jié)束后，eBay使用者的職責(zé)為買賣雙方聯(lián)絡(luò)、收取付款與寄送物品、留下信用評(píng)價(jià)、上傳郵件追蹤資料、重新刊登物品。

3.異質(zhì)多物品組合拍賣模型

假設(shè)：M=(1,2,…,m)是物品集合。K=(1,2,…,k)是投標(biāo)人集合。S為任意多件物品組合的集合。任何組合si?S，故集合S中有2m-m-1個(gè)元素。對(duì)于投標(biāo)人k的私人報(bào)價(jià)vk(si)≥0，沒有報(bào)價(jià)的取值為0，即vk(si)=0。假設(shè)vk(si)是私人的、獨(dú)立的。若對(duì)于某一個(gè)si∈S，有vl(si)=vk(si) ?k,l∈K成立，我們就按照等概率方式選出一個(gè)競(jìng)勝者。我們令xk(si)=1,si?S代表投標(biāo)人k選擇組合物品si；若投標(biāo)人k沒有選擇組合物品si，則xk(si)=0。

分配：出價(jià)最高的競(jìng)價(jià)人贏得該組合物品。

支付：贏得組合物品的競(jìng)價(jià)人支付vk(si)。

為了解決物品組合劃分的完備性，討論每種物品在數(shù)量上只有一件的情況，構(gòu)建多物品組合拍賣模型。我們給出如下定義：

定義（組合物品的相關(guān)性）：M=(1,2,…,m)是物品集合。S為任意多件物品組合的集合。對(duì)于任意i,j=1,2,…,2m-m-1;i≠j，組合物品，則稱組合物品si和sj是兩兩不相關(guān)的；若，則稱組合物品si和sj是兩兩相關(guān)的。對(duì)于賣家來(lái)說(shuō)要追求收益最大化，則有下面的整數(shù)規(guī)劃模型：

第一個(gè)約束說(shuō)明每競(jìng)標(biāo)人只能競(jìng)選一個(gè)組合物品；第二個(gè)約束說(shuō)明每組組合的物品最多只被一個(gè)競(jìng)標(biāo)人贏得；第三個(gè)約束說(shuō)明贏得的組合物品是兩兩互不相關(guān)的。上述模型的求解我們可以用MATLAB實(shí)現(xiàn)。

多物品拍賣過(guò)程中還應(yīng)該滿足拍賣品的數(shù)量約束。規(guī)則制定者為拍賣者，代理人為競(jìng)買者。

決策向量：R=(r1,…,rl)且ri=(ri,1,…,ri,q)。

其中q為所有可能分配給競(jìng)買者i的拍賣品和拍賣品組合的總數(shù)，ri,j表示競(jìng)買者i得到第j種拍賣品或拍賣品組合的“件數(shù)”。同樣，競(jìng)買者的類型θi也是向量，θi=(θi,1,…,θi,z)表示競(jìng)買者對(duì)不同拍賣品或拍賣品組合愿意支付的最高價(jià)格。

令機(jī)制b表示規(guī)則制定者所制定的機(jī)制，機(jī)制b對(duì)于每個(gè)代理人i定義一個(gè)消息空間Bi，并表明消息的博弈形式μ，其中μ=(μ1,…,μl)是表示在博弈中代理人所發(fā)出的所有消息的向量。因?yàn)轭愋褪撬接行畔?，依賴于θ的y只能根據(jù)代理人發(fā)出的消息來(lái)決定；將機(jī)制b決定分配y表述為函數(shù)yb：B→Y=X×Y。

r=(ri,1,ri,2,…,ri,q)表示競(jìng)買者i被分配拍賣品j(j=1,2,…,q)的數(shù)量。因?yàn)槊糠N拍賣品都是單件的不可分的，在t時(shí)間內(nèi)拍賣機(jī)制應(yīng)滿足的拍賣品數(shù)量約束：

拍賣者設(shè)計(jì)拍賣機(jī)制的問(wèn)題就模型化為：

在上式中，θ=(θ1，…，θn)表示所有競(jìng)買者的估價(jià)向量，c+qht表示拍賣者的總拍賣成本。用競(jìng)買者的期望收益來(lái)重述拍賣者的最優(yōu)化問(wèn)題，以便把分配規(guī)則和支付規(guī)則分開進(jìn)行設(shè)計(jì)。得到如下公式：

通過(guò)支付分配規(guī)則進(jìn)行分析，可得：

競(jìng)買者的偏好類型θi是他的私人信息，但是其概率分布是共同知識(shí)。以上是本研究設(shè)計(jì)的最優(yōu)拍賣機(jī)制，為了得出比較有價(jià)值的結(jié)論，先考慮拍賣網(wǎng)站上只有三種互補(bǔ)性的拍賣品的情況。

4.結(jié)論

綜上所述，本文以傳統(tǒng)的單物品拍賣機(jī)制模型為出發(fā)點(diǎn)，為后續(xù)的網(wǎng)上互補(bǔ)異質(zhì)多物品拍賣機(jī)制設(shè)計(jì)奠定了基礎(chǔ)。通過(guò)本文研究，也證明了設(shè)計(jì)拍賣機(jī)制的應(yīng)用價(jià)值。

[1]Sandholm T.Approaches to winner determination in combinatorial auction[J].Decision Support Systems,2000,28(12)：165-176

[2]Giovannucci A.Computationally manageable combinatorial auctions for supply chain automation[M].Consell Superior d'Investigacions Científiques,Institut d'Investigació en Intel·ligència Artificial, 2008.

[3]Andersson A,Tenhunen M,Ygge F.Integer programming for combinatorial auction winner determination[C].MultiAgent Systems, 2000.Proceedings.Fourth International Conference on.IEEE,2000：39-46.

[4]Van Hoesel S,Müller R.Optimization in electronic markets：examples in combinatorial auctions[J].Netnomics,2001,3(1)：23-33.

[5]陳培友,汪定偉.組合拍賣競(jìng)勝標(biāo)確定問(wèn)題的優(yōu)化方法綜述[J].管理工程學(xué)報(bào),2004,3(18)：74-77.

[6]陳培友,汪定偉.用遺傳算法求解組合拍賣競(jìng)勝標(biāo)[J].東北大學(xué)學(xué)報(bào)(自然科學(xué)版),2003,24,(1)：185-210.

[7]黃河,徐鴻雁,陳劍.多因素采購(gòu)組合拍賣獲勝者確定問(wèn)題研究[J].系統(tǒng)工程理論與實(shí)踐,2008,7(7)：27-33.

[8]傅麗芳,馮玉強(qiáng).基于關(guān)聯(lián)規(guī)則分析的組合拍賣競(jìng)勝標(biāo)決定算法[J].系統(tǒng)管理學(xué)報(bào),2008,10,5(17)：504-508.

[9]Joseph E.Harrington,Jr.哈林頓博弈.北京.中國(guó)人民大學(xué)出版社,2013,4：187-204

[10]Vijay Krishna,Auction Theory.北京.中國(guó)人民大學(xué)出版社, 2010,9.

滕可，單位：貴州大學(xué)博學(xué)樓926實(shí)驗(yàn)室，研究方向：運(yùn)籌學(xué)與控制論。

in recent years,the rise of the network,the original need to face the auction to the network.Through the basic hypothesis of this study,this paper establishes a general model of online complementary heterogeneous multi item auction mechanism.The basic model for a maximum value of the objective function,the independent variables are the bidder valuation report.Finally,the design of online complementary heterogeneous multi item auction mechanism in the number of auction products,the specific circumstances of the verification,it is proved that the design of the auction mechanism is of value.

heterogeneous items；Combinatorial auction model；The secondary market；Online auction

李鑫(1991-),男,碩士,遼寧人，漢族，單位：貴州大學(xué)博學(xué)樓926實(shí)驗(yàn)室；