以具經濟效益性的分散式組合拍賣機制配置多單位資源

Abstract

資源及任務分配在複雜的系統中是非常重要的議題，而以組合式拍賣為概念的機制是其中一個可有效解決分配問題的方案。然而，在組合式拍賣中找出最佳贏家組合已被證明為無法在多項式時間內解決的問題，故如何設計一個可在多項式時間內執行完畢且能找出近似最佳解的組合式拍賣機制，是本篇論文主要探討的問題。 文章提出一個能有效找出近似最佳解的組合式拍賣機制，並另外提出一個基於賽局理論的分散式方法，讓拍賣中的投標者能自主地決定出合適的贏家組合。最後經由實驗結果確認我們提出的機制相比於舊有的機制，能更有效的求出與最佳解誤差更小的近似最佳解。

Resource or task allocation are important issues in multi-agent systems, and combinatorial auction-based mechanism has been considered an efficient solution to such problems. However, determine the best fit winners and get the optimal solution of an auction is an NP-complete problem. In this thesis, we propose a heuristic mechanism which is able to solve the winner determination problem in polynomial time and find the sub-optimal solution of combinatorial auctions. In order to improve the execution efficiency and avoid the single point of failure, we also propose a game-theoretical decentralized procedure to execute the winner determination problem of auctions. Several experiments have been conducted to show that our mechanisms are more effective in finding the sub-optimal solution of auctions than existing mechanisms.