Truth-telling Online Auctions of Network Resources
Baruch Awerbuch, John Hopkins

Abstract:
Online auctions of network resources involves auctioneer who controls network bandwidth and bidders who offer bids for bandwidth (or other resource) necessary to accomplish their objectives, such as for example establishing virtual circuits between certain sources and destinations. The bids arrive in an online manner, and auctioneer's decisions must be made without knowing the future bids. Additional complication is that bidders may not be telling the truth on what they are willing to pay.

Yet, the auctioneer can still optimize its own revenue, on all instances, as well "force" the bidders to be truthful. Specifically, auctioneer's profit is within a logarithmic factor from the offline prescient solution that knows true values of all the current and future bidders. Logarithmic gap is inherent for any online resource allocation.

Host: Avrim Blum