逐次型オークションの入札戦略決定手法:準線形効用と予算制約の導入

服部 宏充  横尾 真  櫻井 祐子  新谷 虎松  

誌名
電子情報通信学会論文誌 D   Vol.J85-D1   No.10   pp.974-984
発行日: 2002/10/01
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 論文
専門分野: 分散協調とエージェント
キーワード: 
逐次型オークション,  準線形効用,  予算制約,  入札戦略,  

本文: PDF(567.2KB)
>>論文を購入


あらまし: 
インターネットオークションに関する研究が盛んである.これまでに,オークションの一形式である逐次型オークションにおいて,動的計画法を用いて最適な入札戦略を求める手法が提案されている.しかし従来の手法では,入札を行うエージェントの効用が一般的な加法的な形式であることを仮定しており,入札の途中での所持金の額を,動的計画法で考慮する状態中に表現する必要があった.このため,初期状態での所持金の額 m が大きくなった場合に,考慮すべき状態数が非常に大きくなるという問題点があった.本論文では,エージェントの効用が,加法的な形式の一種である準線形と呼ばれる形式であると仮定することで,状態数を効用が加法的な形式の場合の 1/m に削減し,動的計画法を用いて最適戦略が得られることを示す.また,実験的評価により,m 倍以上の処理時間の高速化が得られることを示す.一方,エージェントの効用が準線形であると仮定した場合,予算制約を表現することが不可能となる.本論文では,準線形の効用を仮定して得られた戦略を修正し,予算制約が存在する場合の準最適戦略を高速に得る方法を提案し,実験的評価により提案手法の有効性を示す.