|
3.30 p.m. An Online Multi-unit Auction for Perishable Goods with Unknown Supply Sourav Chakraborty Visiting Faculty CMI, Technion Univ, Israel. 04-09-08 Abstract In auction mechanism design one tries to design auction mechanism in a given setup such that some useful conditions like truthfullness is satisfied. Simple and important mechanisms like second pricing mechanism for auctioning one particular good has been known in the literatrature for few decades. But in the context when the supply of the goods or the bids comes in a online form the subject of auction mechanism design is a very recent subject. In this talk we have for auction multiple copies of a single item, where the copies are coming online. We have no prior knowledge of how many copies of the item will be produced. Each bidder has a utility for one copy of the good, and bids a value at the beginning of the auction. The problem is to design an allocation and pricing scheme such that the auction mechanism is truthfulness and as a new copy comes, either it is allocated to some bidder, who wins the copy, or it is discarded. The prices charged to the winning bidders are determined at the end of the auction, when there are no more copies left. The goal of the auction is to maximize the revenue of the auctioneer. We design an algorithm for the allocation problem that has a competitive ratio of 1/2. Moreover, the competitive ratio of our algorithm tends to 1, as the bid-profile tends to ``smoothen''. This algorithm is used as a subroutine in designing truthful auctions. Earlier, a reduction from the auction design problem to the allocation problem was known only for the unit-demand case. We give a reduction for the general case when the bidders have decreasing marginal utilities. The problem is inspired by sponsored search auctions.
|
