臺灣博碩士論文加值系統

資源分配問題是將有限的資源或工作分配給需要的使用者以滿足系統的需求。此問題可用拍賣機制來解決，而組合拍賣機制為每位投標者可以對複數項資源來進行投標。組合拍賣機制需設計如何決定贏家與付款，前者為拍賣者該如何決定得標者以最大化拍賣者的利潤，後者為得標者該付出多少標金給予拍賣者。本篇論文著重在如何決定贏家使得拍賣者獲得最大利潤。過往的研究存在尺度性不佳、標金無法真實反應出投標者對資源的估價以及在拍賣者的總利潤上有改善的空間的缺點。與以往的決定機制研究不同，我們將著重在衝突數對於贏家機制的影響，提出了BOCN、BRAC、PLOBOCN三種不同的贏家決定機制的集中式演算法，並且確保投標者提出的標金會真實反映其對於資源的估價。本篇論文也利用賽局理論，提出了非同步與同步兩種分散式演算法，並且確保能夠達到收斂。在最後的實驗數據中，在本篇論文的實驗設定下，本篇論文提出的三種方法皆能夠使拍賣者的總收益增加，並且分散式與集中式演算法之間效能的並無太大差距，同時分散式演算法存在較快的收斂速度。

Resource allocation problem is to allocate limited resources to users so as to meet the system’s requirements. A potential solution to this problem is via auction mechanism. Combinatorial auction mechanism allows bidders to bid multiple items with a single bid. The design of a combination auction mechanism involves two tasks: how to determine winners and how to determine payments. The former is to decide the set of winners in a combinatorial auction to maximize the auctioneer's revenue. The latter is to determine the payments of winners. Previous mechanisms have some shortcomings like poor scalability, bid not faithfully reflecting the bidder’s valuation of resources, and to-be-improved auctioneer’s revenue. This paper focuses on winner determination that maximizes auctioneer’s revenue. Unlike previous studies, we utilization called conflict number and propose three different winner determination methods, namely, BOCN, BRAC, and PLOBOCN, together with a centralized algorithm. We ensure that bidders would place bids that faithfully reflect the bidder’s valuation of resources. This paper also uses game theory to develop synchronous and asynchronous distributed algorithms, and ensures the convergence of these algorithms. Our experimental results show that, compared with prior work, the proposed methods effectively increase total revenue of auctioneer. We also compared the performance between centralized and distributed algorithms. The results show no significant performance gap. The convergence time is low in distributed algorithms.

致謝 ii
摘要 iii
ABSTRACT iv
圖目錄 vii
表目錄 x
第一章 簡介 1
第二章 背景知識與相關研究 5
2.1拍賣機制與組合拍賣機制 5
2.1.1單一拍賣機制 5
2.1.2組合拍賣機制與性質 6
2.2賽局理論 7
2.2.1 賽局的定義 8
2.2.2 賽局的均衡 8
2.3組合拍賣贏家決定問題 9
2.3.1相關研究 10
2.3.2真實資訊 12
2.3.3付款機制 15
第三章 分散式組合拍賣問題 17
3.1組合拍賣贏家決定問題 17
3.1.1系統設定 17
3.2集中式贏家決定演算法設計與性質 18
3.2.1 集中式演算法 18
3.2.2優先(preference)函式 20
3.2.3真實資訊的證明 22
3.3非同步分散式贏家決定演算法 23
3.3.1賽局基本設定 23
3.3.2利益函式 24
3.3.3賽局運作範例 25
3.3.4賽局的實作 27
3.3.5集中式與分散式演算法間的差異 29
3.3.6分散式付款機制 29
3.4同步分散式贏家決定演算法 31
3.4.1非同步與同步分散式演算法間的差異與問題 31
3.4.2同時決策賽局運作範例 32
3.4.3同步分散式贏家決定演算法 33
第四章 模擬實驗與結果 35
4.1實驗設定 35
4.2集中式演算法實驗數據 36
4.2.1標金與資源組合數量無關的投標設定 36
4.2.2標金與資源組合數量有關的投標設定 41
4.3非同步分散式演算法數據 45
4.3.1標金與資源組合數量無關的投標設定 45
4.3.2標金與資源組合數量有關的投標設定 50
4.4同步分散式演算法數據 54
4.4.1標金與資源組合數量無關的投標設定 54
4.4.2標金與資源組合數量有關的投標設定 59
第五章 結論 64
參考文獻 65

[AP01]L. M. Ausubel and P. Milgrom,“Ascending auctions with package bidding,”Frontiers of Theoretical Economics, vol. 1, no. 1,pp. 1-42,Feb. 2002.

[AUS06] L. M. Ausubel,“An efficient dynamic auction for heterogeneous Commodities,” American Economic Review, vol. 96, no. 3, pp. 602-629, June 2006.

[ACS+04] A. AuYoung, B. Chun, A. Snoeren, A. Vahdat, “Resource allocation in federateddistributed computing infrastructures,” in: Proc. 1st Workshop on Operating
System and Architectural Support for the Ondemand IT Infrastructure, OASIS
2004, Boston, USA, Oct. 2004.

[CBH09]H.-L. Choi, L. Brunet, and J. P. How, “Consensus-based decentralized auctions for robust task allocation,” IEEE Transactions on Robotics, vol. 25, no. 4, pp. 912–926, 2009.

[CLA71] E. H.Clarke, “Multipart pricing of public goods,” Public Choice, vol.11,pp. 17–33,1971.

[FLS99] Y. Fujishima, K. L. Brown, and Y. Shoham, “Taming the computational complexity of combinatorial auctions: Optimal and approximate approaches,” in Proceedings of IJCAI’99,Stockholm,Sweden, July 1999

[GH07]J. K.Goeree and C. A. Holt, “Hierarchical package bidding: a paper & pencil combinatorial auction,” Caltech Working Paper,2007.

[GRO73] T.Groves, “Incentives in teams,” Econometrica,vol. 41, pp. 617–631, 1973.

[HR97] M.M. Halldorsson, and J. Radhakrishnan, “Greed is good: Approximating independent sets in sparse and bounded-degree graphs,” Algorithmica, 18(1), pp. 145–163, 1997.

[LOS02] D. Lehmann, L. O‘Callaghan, and Y. Shoham,“Truth revelation in approximately efficient combinatorial auctions,” Journal of the ACM, 49 (5),pp. 577–602,2002.

[NIS00] N. Nisan, “Bidding and allocation in combinatorial auctions,” Proc. ACM Conf. on Electronic Commerce (EC-00), pp. 1–12, 2000.

[PU00] D. C.Parkesand L. Ungar, “Iterative combinatorial auctions: theory and practice,” Proc. 17th National Conf. on Artificial Intelligence, pp.74–81, 2000.

[RPH98] M. H. Rothkopf, R. A. Pekec, and M. Harstad, “Computationally manageable combinatorial auctions,” Management Science 44, pp. 1131–1147, 1998.

[VAR95] H. R. Varian, “Economic mechanism design for computerized agents,” in Proc. USENIX Workshop on Electronic Commerce, July 1995.

[Vic61]W. Vickrey, “Counterspeculation, auctions, and competitive sealed tenders,” Journal of Finance, vol. 16, pp. 8-37, Mar 1961.

[VV03] Sven de Vries and Rakesh V. Vohra, “Combinatorial auctions: A survey,” INFORMS J. Comput, vol. 15, pp. 284–309, 2003.

[WWW+01] M. P. Wellman, W. E. Walsh, P. R. Wurman, and J. K. MacKie-Mason, “Auction protocols for decentralized scheduling,” Gamesand Economic Behavior, vol. 35, pp. 271-303, 2001

[WEL93] M. P. Wellman, “A market-oriented programming environment and its application to distributed multicommodity flow problems,” Journal of Artificial Intelligence Research, vol. 1, pp. 1-23, 1993.

[YHT16] L.-H. Yen, J.-Y. Huang, and V. Turau, “Designing self-stabilizing systems using game theory,” ACM Trans. on Autonomous and Adaptive Systems, in press.

[ZN01] E. Zurel and N. Nisan, “An efficient approximate allocation algorithm for combinatorial auctions,” in: Proc. 3rd ACM Conf. on Electronic Commerce, pp. 125–136, 2001.