𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Competitive analysis of incentive compatible on-line auctions

✍ Scribed by Ron Lavi; Noam Nisan

Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
322 KB
Volume
310
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

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 ΓΏrst 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 results, 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 e ciency obtained.

πŸ“œ SIMILAR VOLUMES

The competitive incentives of vertically
The competitive incentives of vertically integrated local exchange carriers: An economic and policy analysis
✍ David S. Sibley; Dennis L. Weisman πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 191 KB πŸ‘ 2 views

The U.S. Congress passed sweeping telecommunications reform legislation in 1996 that will enable the Regional Bell Operating Companies (RBOCs) to enter the interLATA long-distance market once certain conditions are met. This legislation empowers the state public service commissions, the Federal Comm

Competitive On-line Scheduling of Contin
Competitive On-line Scheduling of Continuous-Media Streams
✍ Minos Garofalakis; Yannis Ioannidis; Banu Γ–zden; Avi Silberschatz πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 277 KB

within a small constant factor of log D (i.e., they are provably near-optimal) if r < 1/Klog DL; and (4) we introduce a novel admission control policy that partitions the server bandwidth based on the expected popularities of different request lengths and experimentally demonstrate its benefits comp

Average competitive ratios of on-line sp
Average competitive ratios of on-line spanning trees
✍ Feng Bao; Aohan Mei; Yoshihide Igarashi πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 284 KB

We study the average competitive ratio of on-line spanning trees with the same distribution of points in the Euclidean plane. We show a distribution of n points such that the average competitive ratio of on-line spanning trees by any on-line algorithm cannot be less than 4 In n -f . @ 1997 Elsevier