Competitive analysis of incentive compatible on-line auctions

Publisher Website
Google Scholar
Abstract
This paper studies auctions in a setting where the di.erent bidders arrive at di.erent times and the auction mechanism is required to make decisions about each bid as it is received. Such settings occur in computerized auctions of computational resources as well as in other settings. We call such auctions, on-line auctions. We 3rst characterize exactly on-line auctions that are incentive compatible, i.e. where rational bidders are always motivated to bid their true valuation. We then embark on a competitive worst-case analysis of incentive compatible on-line auctions. We obtain several re- sults, the cleanest of which is an incentive compatible on-line auction for a large number of identical items. This auction has an optimal competitive ratio, both in terms of seller's revenue and in terms of the total social e6ciency obtained. c 2003 Elsevier B.V. All rights reserved.

This publication has 10 references indexed in Scilit: