An Online Multi-unit Auction with Improved Competitive Ratio

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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.

Keywords

Computer Science and Game Theory, Computational Complexity, Discrete Mathematics, Data Structures and Algorithms

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/215501

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0901.1427
 http://arxiv.org/abs/0901.1427

Collections

arXiv