組合せオークションにおける多数入札時での勝者決定の近似解法に関する一考察(モデル/理論,<特集>ソフトウェアエージェントとその応用論文)
スポンサーリンク
概要
- 論文の詳細を見る
本論文では,10,000〜100,000を超えるような多数の入札がある組合せオークションに対して,勝者決定の近似解法を提案し,その特性を評価する.提案アルゴリズムでは,従来手法のLehmannアルゴリズムにおける入札ソート順位の決定因子に着目し,更に山登り法及びシミュレーテッドアニーリング(SA)による解の洗練を行うことで,安定して高い最適性を持った解を得る.入札数が1000程度の場合に,本提案手法では最適解に対して平均して0.997程度の総落札額が得られる解を見つけられることを示す.更に,従来の最適解探索手法と比較して十分に高速に動作し,10,000を超える入札数をもつオークションに対して数秒(入札数10,000)から数分程度(入札数100,000)の実用的な時間で計算が行えることを示す.本近似解法の限界点の一つとして,本近似解法を用いた組合せオークションが一般には真実申告最良とはならないことを,Monotonicityという条件が成り立たないことから示す.一方で,真実申告最良とはならないものの,本近似解法の一部では,解探索の過程におけるランダム性を排除し順序性を保存することで,近似解に対して特定の好ましい性質を満たすことを示す.
- 社団法人電子情報通信学会の論文
- 2007-09-01
著者
-
伊藤 孝行
名古屋工業大学大学院産業戦略工学専攻
-
福田 直樹
静岡大学情報学部
-
福田 直樹
静岡大 情報
-
伊藤 孝行
名古屋工業大学大学院工学研究科産業戦略工学専攻:名古屋工業大学大学情報工学科情報工学類
-
伊藤 孝行
名古屋工業大学大学院産業戦略工学専攻:mitスローン経営大学院集合知研究センター
-
伊藤 孝行
名古屋工業大学
-
伊藤 孝行
名古屋工業大学大学院産業戦略工学専攻 情報工学科:mitスローン経営大学院
関連論文
- Auction Network Trust : 電子商取引ネットワークにおけるユーザ間の関係を利用した評判メカニズム(メカニズムデザイン,ソフトウェアエージェントとその応用論文)
- 複雑な交渉問題における論点間の依存関係を利用した合意形成機構の提案(「社会的インタラクションにおける知」及び一般)
- 電子商取引における関係性を考慮したユーザの信頼性評価(「社会的インタラクションにおける知」及び一般)
- 短時間再割り当てを考慮した組み合わせオークション勝者決定の高速近似手法(オークションとメカニズムデザイン)
- 複数ユニット組合せオークションにおける多数入札時での勝者決定の近似解法について(「社会的インタラクションにおける知」及び一般)
- 計算論的メカニズムデザイン(エージェント)
- ソーシャルレンディングにおけるグループの影響を考慮したベイズ推定による貸出利率決定方法(メカニズムデザインと電子市場(1))
- ソーシャルレンディングにおける借り手が所属するグループの返済履歴を考慮した貸出利率調整メカニズム(「社会的インタラクションにおける知」及び一般)
- 確率推論に基づく位置情報推定システムの実現(モバイルコンピューティング)(次世代移動体通信システム)
- 組み合わせオークションの近似勝者への勝者価格単調性の保証(メカニズムデザインと電子市場(2))
- 組合せオークションにおける多数入札時での勝者決定の近似解法に関する一考察(モデル/理論,ソフトウェアエージェントとその応用論文)
- LF-009 短時間近似が可能な組み合わせオークション勝者決定アルゴリズムの評価(人工知能・ゲーム)
- 6ZF-4 概念辞書を用いたユーザの状況を想定した目的指向衣服推薦システムの実装(テキストマイニングの応用,学生セッション,コンピュータと人間社会)
- 価値を抽出する(編集委員今年の抱負2009:経糸から横糸まで)
- D-8-14 階層型合意形成機構に基づくパーティー会場決定支援システム
- 組織における代替案選択支援の為のエージェント間の階層型合意形成機構
- エージェント間の自動交渉に基づいたコラボレーティブな公共空間設計支援システムの試作
- 複数論点交渉問題における相互依存関係指標およびスケーラブルな交渉メカニズムの提案
- D-8-22 WWWにおける複数インスタンス情報源のためのwrapper生成機構について
- 複数オークション入札支援システム BiddingBot における情報収集エージェントの wrapper 生成機構について
- 2単語間の共起情報と距離情報を考慮した有害文章判別手法の提案
- あうんの呼吸と研究環境(世界のAI,日本のAI〔第13回〕)
- 3V-7 Locally Envy Free均衡に基づくキーワードオークションの安定性に関する考察(マルチエージェント(1),学生セッション,人工知能と認知科学)
- 1V-7 複数のターゲットを対象とする実時間探索における優先ターゲット選択手法の提案(学習・推論,学生セッション,人工知能と認知科学)
- 複数論点交渉問題のための効用空間の絞込みに基づくマルチエージェント交渉手法(モデル/理論,ソフトウェアエージェントとその応用論文)
- F-030 キーワードオークションのLocally Envy-Free均衡に基づく支払額決定機構の提案(F分野:人工知能・ゲーム)
- 相互依存価値モデルに基づく不確定入札を用いた真実申告最良な組合せオークションの設計(分散協調とエージェント)
- 不確定入札に基づく真実申告最良な相互依存価値オークション(分散協調とエージェント)
- 勝つことを意識しているか(世界のAI,日本のAI〔第2回〕)
- 国際交渉エージェント競技会ANAC2010における歩み寄り戦略を基調とする交渉エージェントの開発
- D-5-6 複数単語の共起情報を用いた文書フィルタリング手法の提案(D-5.言語理解とコミュニケーション,一般セッション)
- 重要度分布に基づく大規模グループAHPの提案
- F_012 定性シミュレーションに基づく栄養士養成支援システム(F分野:人工知能・ゲーム)
- WWWに基づいた体験学習支援機構
- 複数論点交渉問題における論点グループに基づくスケーラブルな合意形成手法の提案
- 5Q-5 ユーザビリティを考慮したスタイルを自在に変更可能なWEBコンテンツ作成支援システムの試作(情報アクセス技術,学生セッション,データベースとメディア,情報処理学会創立50周年記念)
- 栄養情報を活用した目的指向料理推薦システムの試作(「社会的インタラクションにおける知」及び一般)
- D-8-8 複数論点交渉問題における論点グループに基づいたスケーラブルな交渉メカニズムの提案(D-8.人工知能と知識処理,一般セッション)
- 複数論点交渉問題におけるエージェントの個人情報の公開に基づいた説得メカニズム(「エージェント基礎」及び一般)
- アプリケーション組み込みに向けた高速組合せオークション実行エンジンの実装(「社会的インタラクションにおける知」及び一般)
- 3R-6 インターネットオークションにおける取引関係を用いた信頼性評価システムの提案(Web応用,学生セッション,データベースとメディア,情報処理学会創立50周年記念)
- エージェント間の自動交渉に基づく公共空間設計支援システムの試作(「社会的インタラクションにおける知」及び一般)
- 2V-8 参加者の持つ情報の違いによる予測市場の振る舞いについて(マルチエージェント(2),学生セッション,人工知能と認知科学,情報処理学会創立50周年記念)
- 複数論点交渉問題におけるエージェントの効用空間の公開範囲に基づく交渉手段の実現(PhDセッション)
- L-065 WisdomAdBalloon : Push型情報配信技術に基づく動的ページ構成システム(L分野:ネットワークコンピューティング)
- 論点クラスタリングと分散GAによる合意可能点の探索について(「社会的インタラクションにおける知」及び一般)
- 国際交渉エージェント競技会ANAC2010における歩み寄り戦略をベースとする自動交渉エージェントの開発(「社会的インタラクションにおける知」及び一般)
- 逐次的リズム音程生成モデルに基づく自動作曲システム
- G-008 反復度に基づく特徴旋律抽出手法の提案(G分野:音声・音楽)
- 2R-8 有害文書判別のための多単語間共起情報辞書の構築とその応用(文書管理,学生セッション,データベースとメディア,情報処理学会創立50周年記念)
- 2R-7 2単語間の共起情報を利用した有害文章判別システム(文書管理,学生セッション,データベースとメディア,情報処理学会創立50周年記念)
- D-13-2 装飾された美しい日本語フォント配信システムの提案(D-13.知能ソフトウェア工学,一般セッション)
- 3N-8 目的指向商品推薦システムのための商品属性値の自動決定手法(メタデータ活用,学生セッション,データベースとメディア)
- 1C-5 美しいフォント高速配信システムの試作と負荷評価(コンテンツ作成支援,一般セッション,データベースとメディア)
- 4U-4 分散GAと論点クラスタを用いたグループ効用最適化手法について(遺伝的アルゴリズム(1),学生セッション,人工知能と認知科学,情報処理学会創立50周年記念)
- グループ効用最適化を目的とした論点クラスタと分散GAを用いた手法の提案
- F_038 コンテンツエージェントモデルに基づくWebページの自動編成システムの試作(F分野:人工知能・ゲーム)
- 3ZA-9 ソーシャルレンディングにおける返済促進のためのインセンティブメカニズム(情報社会を支える技術(2),学生セッション,コンピュータと人間社会)
- 社会を最適化する(編集委員今年の抱負2011)
- 4ZG-7 AHPを用いた大規模グループ意思決定支援システムの試作(協調基盤と意思決定支援,学生セッション,インタフェース,情報処理学会創立50周年記念)
- 2V-7 複雑な交渉問題における論点間の依存関係を利用したマルチエージェント合意形成機構(マルチエージェント(2),学生セッション,人工知能と認知科学,情報処理学会創立50周年記念)
- D-13-1 契約ネットプロトコルに基づいた分散業務分配システムの試作(D-13.知能ソフトウェア工学,一般セッション)
- 2R-8 複数論点交渉問題におけるナッシュ交渉解発見手法の提案(マルチエージェント(2),学生セッション,人工知能と認知科学)
- 分散メディエータに基づく交渉手法におけるパレート最適性の検証(メカニズムデザインと電子市場(2))
- 複数論点交渉問題におけるハイブリッド型セキュア交渉プロトコルの提案(「社会的インタラクションにおける知」及び一般)
- 3V-5 複数論点交渉問題における代表選択交渉メカニズムの代表者選択手法の解析(マルチエージェント(1),学生セッション,人工知能と認知科学)
- F-022 多論点交渉問題におけるエージェントの公開情報の調整に基づく交渉手段(F分野:人工知能・ゲーム)
- 架空名義入札に頑健なオークションプロトコルの計算論的制度設計(セッション1)
- 架空名義入札に頑健なオークションプロトコルの計算論的制度設計
- 定性シミュレーションに基づく環境教育支援システム
- LF-004 組み合わせオークションにおける効用比較に基づいた架空名義入札者発見法の提案(F分野:人工知能・ゲーム)
- 既存 Web ブラウザを利用したオンライン編集可能な Web ページの実現
- 定性シミュレーションに基づく消費者教育支援システムについて
- 評価値つき指名に基づく競争入札プロトコルについて
- 代替財共同購入における買い手の多属性な嗜好に基づいたグループ統合支援機構(人工知能,認知科学)
- 電子共同購入における実時間提携形成支援アルゴリズムについて(「21世紀の知識情報科学に向けて」,及び一般)
- ユーザの考慮する属性を意識した提示文章の更新に基づく対話型商品推薦システムの提案(「社会的インタラクションにおける知」及び一般)
- 3R-5 インターネットオークションにおけるコメント文解析に基づく新しい評価指標とその応用(Web応用,学生セッション,データベースとメディア,情報処理学会創立50周年記念)
- インターネットオークションにおけるコメント文解析による新しい評価指標の提案とその応用
- D-9-18 取引関係に基づくインターネットオークション参加者評価指標の提案(D-9.ライフインテリジェンスとオフィス情報システム,一般セッション)
- 電子商取引における取引情報に基づくユーザ評価手法とその解析(「社会的インタラクションにおける知」及び一般)
- 2T-4 商取引ネットワークにおける不審ユーザ判定モデルの評価と実装(データマイニング,学生セッション,データベースとメディア)
- F-028 ネットオークションでの取引関係の可視化システム(F分野:人工知能・ゲーム)
- Greedyな割当手法に基づくStrategy-proofな組合せオークションプロトコルと公開競上げ式プロトコルへの拡張(分散協調とエージェント)
- 多様な興味を持つ専門家と素人が存在する場合の組み合わせオークション
- 専門家と素人が存在する場合の組合せオークション : 専門家が単一財にのみ専門知識をもつ場合(分散協調とエージェント)
- Gerhard Weiss(編), Multiagent Systems : A Modern Approarch to Distributed Artificial Intelligence, The MIT Press, 1999年, US$60.00, ISBN4-621-05291-8
- 5ZL-3 日常的情報ニーズの即時的共有システムの試作(マーケティング・情報抽出,学生セッション,コンピュータと人間社会,情報処理学会創立50周年記念)
- L-031 ユーザに負担をかけないOSレベルの動的な暗号化と復号化(ネットワーク・セキュリティ,一般論文)
- 5S-2 レシピと材料の関係ネットワークに基づく料理推薦システムの試作(情報推薦(2),学生セッション,データベースとメディア,情報処理学会創立50周年記念)
- 5S-8 不確実な問題空間における先読みに基づく実時間探索手法(認知・推論・探索,学生セッション,人工知能と認知科学)
- 6ZF-3 Webチャット上でのユーザと店員の会話を利用した衣服推薦システムの提案(テキストマイニングの応用,学生セッション,コンピュータと人間社会)
- ユーザの性格を反映したエージェント間の交渉方式とその応用
- 動的重み付き最大制約充足問題に基づくナーススケジューリングシステム : 暫定制約の導入に基づく解の安定性の実現
- D-8-18 多属性な意思決定問題における属性交換に基づくエージェント間の交渉手法とその応用
- 根回しにおける個別交渉戦略に基づいたエージェント間交渉の実現
- 2M-3 効用理論に基づく根回しを導入したエージェント間交渉の実現
- エージェント間の交渉における根回しの実現とその応用
- 分散TMSに基づくマルチエージェントシステムの試作
- 大規模交渉問題における論点グループ数の調整に基づいた自動合意形成機構