An Online Multi-unit Auction with Improved Competitive Ratio

Details An Online Multi-unit Auction with Improved Competitive Ratio An Online Multi-unit Auction with Improved Competitive Ratio

2009-01-11

arxiv.org/abs/0901.1427v1

Computer Science

Computer Science and Game Theory

Scientific paper

We improve the best known competitive ratio (from 1/4 to 1/2), for the online multi-unit allocation problem, where the objective is to maximize the single-price revenue. 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 for the same setting: the allocation has to be done online, while the payments can be decided at the end of the day. 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.

Affiliated with

Also associated with

No associations

Rating

An Online Multi-unit Auction with Improved Competitive Ratio does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An Online Multi-unit Auction with Improved Competitive Ratio, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Online Multi-unit Auction with Improved Competitive Ratio will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-258283