網上組合拍賣機制設計與投標模型研究.pdf

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

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

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

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

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

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

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

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