| 講演名 | 2005-04-18 入札額の範囲が制限された正直なオークション 角田 大輔, 堀山 貴史, 岩間 一雄, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 1回入札, 秘密入札(入札額が他人には分からない入札)の正直なオークション(truthful auction)を扱う. 正直なオークションでは, 正直に入札すること, すなわち自分にとっての真の利用価値を自分の入札値とすることで, 最良の利得を得ることが保証される. 正直なオークションを実現するアルゴリズムの性能評価には競合比が用いられ, これまでに下界が2.42であることが知られている. また, COREアルゴリズムが提案されており, 競合比3.39を達成している. 本報告では, 入札額の最大値と最小値の比が高々γ倍以内である時に, 競合比lnγ+1を達成するオークションアルゴリズムを提案する. 最初に, 基本となるアルゴリズムとして, 他の入札者の最低入札額を提示額とする最低入札額オークションを示す. このアルゴリズムを拡張することで, 最低入札額またはその定数倍の複数の提示額をもつオークションを提案する. 提示額の種類を増化させることで競合比は改善され, 確率分布により提示額を決定することで競合比lnγ+1を達成する. |
| 抄録(英) | We study a class of single-round, sealed-bid truthful auctions. In truthful auctions, truth-telling, i.e, revealing their true utility value as their bid, maximizes their profit. The current lower bound on the competitive ratio of truthful auctions is 2.42, and the upper bound is 3.39 that is achieved by the Goldberg and Hartline's CORE algorithm. In this paper, we limite the range of bid-values : The ratio between the maximum and the minimum bid-values is at most γ (γ > 1, constant). Under this situation, by utilizing the minimum bid-values of other bidders, we can achieve the competitive ration lnγ + 1, which gives better results than the conventional algorithms when γ ≦ 10.9. |
| キーワード(和) | 正直なオークション / アルゴリズム / 競合比 / 入札額の範囲 |
| キーワード(英) | truthful auctions / algorithms / competitive ratios / limited ranges of bids |
| 資料番号 | COMP2005-6 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2005/4/11(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 入札額の範囲が制限された正直なオークション |
| サブタイトル（和） | |
| タイトル（英） | Truthful Auctions with Limited Ranges of Bids |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 正直なオークション / truthful auctions |
| キーワード(2)（和/英） | アルゴリズム / algorithms |
| キーワード(3)（和/英） | 競合比 / competitive ratios |
| キーワード(4)（和/英） | 入札額の範囲 / limited ranges of bids |
| 第 1 著者 氏名（和/英） | 角田 大輔 / Daisuke SUMITA |
| 第 1 著者 所属（和/英） | 京都大学大学院 情報学研究科 Graduate School of Informatics, Kyoto University |
| 第 2 著者 氏名（和/英） | 堀山 貴史 / Takashi HORIYAMA |
| 第 2 著者 所属（和/英） | 京都大学大学院 情報学研究科 Graduate School of Informatics, Kyoto University |
| 第 3 著者 氏名（和/英） | 岩間 一雄 / Kazuo IWAMA |
| 第 3 著者 所属（和/英） | 京都大学大学院 情報学研究科 Graduate School of Informatics, Kyoto University |
| 発表年月日 | 2005-04-18 |
| 資料番号 | COMP2005-6 |
| 巻番号（vol） | vol.105 |
| 号番号（no） | 7 |
| ページ範囲 | pp.- |
| ページ数 | 9 |
| 発行日 | |