網(wǎng)上組合拍賣機(jī)制設(shè)計(jì)與投標(biāo)模型研究.pdf

1、組合拍賣是一種允許競標(biāo)者對不同商品組合進(jìn)行投標(biāo)的多物品拍賣機(jī)制。理論研究和實(shí)際應(yīng)用都證明當(dāng)商品之間存在互補(bǔ)性或替代性協(xié)同價(jià)值時(shí)，組合拍賣能更好地體現(xiàn)竟標(biāo)者偏好信息，有效避免“暴露”問題，提高資源配置效率，增加社會效益。作為一種有效的商品定價(jià)和資源分配機(jī)制，組合拍賣在B2B等多物品交易商業(yè)模式中有著獨(dú)特的優(yōu)勢，在電子商務(wù)中有著廣闊的應(yīng)用前景。
　　然而，網(wǎng)上組合拍賣的實(shí)現(xiàn)與推廣還面臨許多困難和挑戰(zhàn)。眾多的商品組合形式及其復(fù)雜的協(xié)同價(jià)

2、值結(jié)構(gòu)使得組合拍賣機(jī)制設(shè)計(jì)和投標(biāo)策略都比其它拍賣復(fù)雜的多，其拍賣機(jī)制設(shè)計(jì)中的競勝標(biāo)確定問題(Winner Deterninating Problem—WDP)就是一個(gè)典型的NP完全問題。而網(wǎng)絡(luò)運(yùn)行環(huán)境的特點(diǎn)和要求使得拍賣效率與計(jì)算復(fù)雜性之間的矛盾更加突出，成為阻礙組合拍賣得到廣泛應(yīng)用的瓶頸問題。如何通過合理的機(jī)制設(shè)計(jì)和有效的投標(biāo)決策支持降低拍賣雙方所面臨決策問題的復(fù)雜性和不確定性是增強(qiáng)組合拍賣可行性和適用性、促進(jìn)網(wǎng)上組合拍賣的實(shí)現(xiàn)與應(yīng)用

3、亟待解決的重要問題。
　　針對上述問題，本文以協(xié)調(diào)計(jì)算復(fù)雜性與拍賣運(yùn)行效率之間的內(nèi)在矛盾為根本出發(fā)點(diǎn)，結(jié)合網(wǎng)絡(luò)運(yùn)行環(huán)境的特點(diǎn)和要求，通過拍賣機(jī)制及其WDP算法創(chuàng)新設(shè)計(jì)與投標(biāo)決策支持方法研究，增強(qiáng)組合拍賣的可行性。
　　首先，進(jìn)行網(wǎng)上交互式組合拍賣機(jī)制總體設(shè)計(jì)與分析。本文以機(jī)制設(shè)計(jì)和最優(yōu)拍賣理論為基礎(chǔ)論述了拍賣機(jī)制設(shè)計(jì)基本原則和方法，針對典型的組合拍賣VCG和AkBA各自的優(yōu)點(diǎn)和缺陷,對信息反饋機(jī)制、投標(biāo)規(guī)則等影響拍賣運(yùn)行效率

4、的關(guān)鍵問題進(jìn)行創(chuàng)新設(shè)計(jì)，提出一種新的網(wǎng)上組合拍賣機(jī)制APICA(Ascending Price Iterative Combinatorial Auction)。APICA通過投標(biāo)預(yù)處理和簡單明了的價(jià)格信息反饋機(jī)制有效降低計(jì)算復(fù)雜性，并采用靈活的價(jià)格最小增幅確定方法實(shí)現(xiàn)對拍賣進(jìn)程的動態(tài)調(diào)控，不僅有效地解決了密封投標(biāo)組合拍賣中競標(biāo)者偏好獲取難問題，而且避免了iBundel、AkBA等交互式組合拍賣計(jì)算復(fù)雜性大、信息反饋延遲等弊端，有效緩解

5、了計(jì)算復(fù)雜性與運(yùn)行效率間的矛盾。
　　其次，針對組合拍賣機(jī)制APICA中至關(guān)重要的競勝標(biāo)確定問題進(jìn)行WDP算法設(shè)計(jì)與分析。WDP算法性能是影響組合拍賣運(yùn)行效率的關(guān)鍵因素。本文根據(jù)計(jì)算復(fù)雜性理論分析了WDP問題性質(zhì)和特點(diǎn)，針對拍賣機(jī)制APICA對WDP算法的要求，以現(xiàn)代優(yōu)化方法及算法設(shè)計(jì)理論為基礎(chǔ)充分論證了權(quán)值編碼遺傳算法的優(yōu)良性，并根據(jù)WDP的特點(diǎn)對微觀遺傳策略和遺傳操作進(jìn)行適當(dāng)?shù)母倪M(jìn)和重新設(shè)計(jì)，提出基于權(quán)值編碼的WDP啟發(fā)式算法

6、HA-WCGA。與其他WDP算法不同，HA-WCGA采用先進(jìn)的權(quán)值編碼機(jī)制，具備良好的因果性和遺傳性能，并采用熔合交叉和分層次變異遺傳操作減少了大量計(jì)算。同時(shí)，嵌入基于WDP問題的啟發(fā)式規(guī)則增強(qiáng)算法進(jìn)化能力和求解速度，從而提高了拍賣機(jī)制APICA信息反饋速度和運(yùn)行效率。
　　然后，根據(jù)組合拍賣機(jī)制APICA的投標(biāo)規(guī)則，針對投標(biāo)方所面臨的復(fù)雜決策問題進(jìn)行投標(biāo)策略及投標(biāo)決策支持方法的研究。首先以現(xiàn)實(shí)的網(wǎng)上拍賣投標(biāo)行為特征為基礎(chǔ)構(gòu)建針對

7、不同類型競標(biāo)者的投標(biāo)策略；然后根據(jù)投標(biāo)決策需求設(shè)計(jì)投標(biāo)決策支持Agent(Bidding Support Agent)，使其能夠在偏好信息不完全條件下幫助競標(biāo)者完成商品價(jià)值確定、市場信息反饋及投標(biāo)構(gòu)造等決策支持功能，有效地降低競標(biāo)者決策問題的不確定性和復(fù)雜性。
　　最后，本文通過大量的計(jì)算機(jī)模擬實(shí)驗(yàn)充分論證了組合拍賣機(jī)制APICA的運(yùn)行效率及其WDP算法HA-WCGA的良好性能。以MatLab6.5為編程語言和實(shí)驗(yàn)平臺，分別設(shè)計(jì)并

8、完成兩個(gè)部分共8組模擬實(shí)驗(yàn)。第一部分通過APICA與組合拍賣VCG及AkBA的對比實(shí)驗(yàn)證實(shí)，APICA的拍賣收益明顯高于AKBA，在競標(biāo)者偏好信息不完全條件下實(shí)現(xiàn)與完全信息VCG拍賣相同或非常接近的資源配置效率。進(jìn)而從拍賣收益、分配效率及競標(biāo)者私有信息揭示程度等各方面充分論證了APICA的相對優(yōu)越性。第二部分基于專業(yè)的WDP算法測試數(shù)據(jù)集CAST生成模擬數(shù)據(jù)，通過與其它算法的對比實(shí)驗(yàn)證明，HA-WCGA能夠快速的求出與最優(yōu)解非常接近的解