著者

松原 繁夫

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.47, no.4, pp.1340-1348, 2006-04-15

被引用文献数

1

---

本論文は動的環境における資源割当て問題を解決するオークションプロトコルを提案する.動的環境においては,資源の価値は不確実性を有する.すなわち,価値はオークションが行われる時点の状況だけでなく,割り当てられた資源が実際に使用される時点の状況に依存する.たとえば,天気が晴れの場合の価値は雨の場合の価値と異なるかもしれない.このような状況を扱う方法の1 つは,事象が生じるたびにオークションを行って,再割当てを行うことである.しかし,再割当ては不効用を生じるかもしれない.さらに,そのようなオークションはつねに均衡戦略が存在するとは限らない.均衡戦略が存在しなければ,どのような結果が得られるか予測できなくなる.この問題を解決するため,我々は新たなプロトコルを提案する.提案プロトコルは,入札者に資源の利用から得られる効用に加えて,再割当てによって生じる費用を申告させる.提案プロトコルでは,入札者の真実申告が均衡となり,期待値のうえで社会的に効率的な割当てが達成できることを証明する.This paper proposes an auction protocol for solving a resource allocation problem in dynamic environments. In such environments, the valuation of resources has uncertainty for each bidder, i.e., this valuation depends on the situation not only at the point when the auction is held but also at the point when the allocated resources are actually used. For example, a bidder's valuation in fine weather may be different from that in rainy weather. A solution for dealing with this problem is to execute auctions whenever an event occurs and then to re-allocate resources. Re-allocating resources, however, may cause disutility. Moreover, it does not always provide an equilibrium strategy because it can be viewed as a sequential auction, which means that we cannot accurately predict what outcome will be obtained. To solve this problem, we propose an auction protocol that allows bidders to declare the cost due to re-allocation and then decides an allocation based on this cost of re-allocation as well as the surplus obtained from the allocated resources themselves in the realized situation. We prove that a bidder's truth telling is in equilibrium and that a socially efficient allocation on expected values is obtained in the proposed protocol.