| Presentation | 2005-04-18 Truthful Auctions with Limited Ranges of Bids Daisuke SUMITA, Takashi HORIYAMA, Kazuo IWAMA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | truthful auctions / algorithms / competitive ratios / limited ranges of bids |
| Paper # | COMP2005-6 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2005/4/11(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Truthful Auctions with Limited Ranges of Bids |
| Sub Title (in English) | |
| Keyword(1) | truthful auctions |
| Keyword(2) | algorithms |
| Keyword(3) | competitive ratios |
| Keyword(4) | limited ranges of bids |
| 1st Author's Name | Daisuke SUMITA |
| 1st Author's Affiliation | Graduate School of Informatics, Kyoto University() |
| 2nd Author's Name | Takashi HORIYAMA |
| 2nd Author's Affiliation | Graduate School of Informatics, Kyoto University |
| 3rd Author's Name | Kazuo IWAMA |
| 3rd Author's Affiliation | Graduate School of Informatics, Kyoto University |
| Date | 2005-04-18 |
| Paper # | COMP2005-6 |
| Volume (vol) | vol.105 |
| Number (no) | 7 |
| Page | pp.pp.- |
| #Pages | 9 |
| Date of Issue | |