We study a class of single-round, sealed-bid auctions for a set of identical items. We adopt the worst case competitive framework defined by [6,3] that compares the profit of an auction to that of an optimal single price sale to at least two bidders. In this framework, we give a lower bound of 2.42 (an improvement from the bound of 2 given in ) on the competitive ratio of any truthful auction, one where each bidders best strategy is to declare the true maximum value an item is worth to them. This result contrasts with the 3.39 competitive ratio of the best known truthful auction .
|Original language||English (US)|
|Number of pages||12|
|Journal||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|State||Published - Dec 1 2004|
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Science(all)