組合せオークションの高速な準最適勝者決定アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
本論文では, 組合せオークションの勝者決定問題について, limited discrepancy探索(LDS)アルゴリズムに基づいた, 近似アルゴリズムの提案を行う.インターネットオークションは電子商取引の重要な一分野である.インターネットを利用することにより, 組合せオークションを含む, 大規模で複雑なオークションの実現が可能となっている.組合せオークションでは, 複数の財を同時に対象とし, 入札者は補完的な選好を表明することができるため, 参加者の効用を増加することができる.しかしながら, その一方で, 最適な勝者を決定することは複雑な制約最適化問題であり, NP完全問題であることが知られている.我々は, A^*アルゴリズムに基づいた既存アルゴリズムにLDSアルゴリズムのアイディアを導入する.LDSの導入により, 探索の労力を良い解が存在する可能性の高い探索範囲に限定することが可能となる.さらに, LDSの探索性能はヒューリスティック関数の値の正確さに比較的影響され難く, 計算コストの高いヒューリスティック関数の再計算を避けることができる.さまざまな問題設定を用いた評価実験により, 従来手法に比べ, LDSは高速に, 最適解に非常に近い準最適解を見つけることができることを示す.
- 2001-09-01
著者
関連論文
- 個人間情報共有システムを用いた情報推薦に関する一考察(テキストマイニング)
- 開放型プロダクションシステムにおけるデータ依存関係の管理
- 組合せオークションの高速な準最適勝者決定アルゴリズム
- 再構成可能なハードウェアを用いた充足可能性問題の解法
- FPGAと論理合成システムを用いた充足可能性問題の解法
- 再構成可能なハードウェアを用いた充足可能性問題の解法
- 再構成可能なハードウェアを用いた充足可能性問題の解法
- 再構成可能なハードウェアを用いた充足可能性問題の解法
- A19 デザインプロセスの外在化 (2) : 議論支援システムの提案
- A18 デザインプロセスの外在化 (1) : 思考の役割のコンセプトモデル
- ユビキタスセンサを用いたライフログの蓄積と利用(セッション2)
- 高密度なセンサネットワークにおけるデータ収集のための階層的クラスタリング手法の提案(企画:「シミュレーションと現実のギャップを埋められるのか?」,モバイルP2P,ユビキタスネットワーク,アドホックネットワーク,センサネットワーク,一般)
- 全米人工知能会議AAAI-94報告
- 会議報告 IJCAI-01
- 多状態コミットメント探索とその評価
- 多状態コミットメント実時間A^*アルゴリズムの性能解析
- 多状態コミットメント探索の性能評価
- ヒューリスティック探索へのn-状態コミットメントの導入
- ヒューリスティック探索への n-状態コミットメントの導入
- 淘汰を用いたマルチエージェント実時間探索の高速化 : 協調探索への競争の導入 ( マルチエージェント)
- マルチエージェント合意形成のための回覧板プロトコル
- 制約充足テクニックを用いた移動体通信の周波数割当問題の解法
- 分散制約充足におけるnogood学習の効果
- 複雑な局所問題に対応する分散制約充足アルゴリズム
- 分散不完全制約充足問題
- 制約充足テクニックを用いた移動体通信の周波数割当問題の解法
- 分散breakout : 反復改善型分散制約充足アルゴリズム(並列処理)
- CSPの新しい展開 : 分散/動的/不完全CSP ( 制約充足問題の基礎と応用)
- ICMAS'95報告
- エージェントの組織による実時間連続問題解決
- ATMSを用いた分散制約充足問題の解法
- Hal R. Varian: Economic Mechanism Design for Computerized Agents, the First Usenix Workshop on Electronic Commercr (1995).
- AAAI-99参加報告
- (1)マルチエージェントシステム(会議報告)
- 座談会 : AIと電子商取引の展望(AIの観点から見た電子商取引の将来像)
- マルチエージェントシステム
- Forbus, K. D. and de Kleer, J. : Building Problem Solvers, MIT Press (1993).
- 分散制約充足の高速化と通信網回線設定への適用
- 分散制約充足の通信網回線設定への適用
- 分散制約充足による分散協調問題解決の定式化とその解法
- サイバーコミュニティ形成支援システムのネットワーク分析による評価
- ネットワーク上のコミュニティ形成を支援するシステム"Community Organizer"の実装と評価実験
- 架空名義表明のメカニズムデザインに対する影響 : インターネットでの集団意思決定に向けて(特集●社会・経済におけるマルチエージェント)
- 不正行為を防ぐ電子商取引メカニズム
- 電子商取引における一般化Vickreyオークションの問題点 : 架空名義入札に対する頑健性
- 新規参入を容易とする頑健な情報財取引メカニズムの提案
- 新規参入を容易とする頑健な情報財取引メカニズムの提案
- 電子商取引における一般化Vickreyオークションの問題点 : 架空名義入札に対する頑健性
- 繰り返しゲームにおいて協調行動を生成する先読み型行動選択方法
- インターネットにおけるコミュニティ形成支援
- インターネットにおけるコミュニティ形成支援
- インターネットオークションの理論と応用(AIの観点から見た電子商取引の将来像)
- 制約充足問題の地形の解析
- 柔軟で動的なエージェントの組織構造を用いた分散制約充足アルゴリズム
- 分散制約充足問題における制約緩和
- 分散探索とその周辺 ( マルチエージェントと協調計算)
- 弱コミットメント戦略を用いた制約充足問題の解法
- 実時間制約充足問題とその解法
- 弱コミットメント戦略を用いた制約充足問題の解法
- コミュニティ支援システムと協調フィルタリングの統合の試み
- サイバーコミュニティのアプリケーションのためのプラットフォームShineの提案
- インターネットにおけるコミュニティ形成支援
- 潜在的なコミュニティを可視化するコミュニティ形成支援システム
- 相手エージェントを考慮した行動戦略の調整
- 組合せオークションの高速な準最適勝者決定アルゴリズム
- ACM EC-00参加報告