Optimal bid sequences for multiple-object auctions with unequal budgets

Yuyu Chen, Ming Yang Kao, Hsueh I. Lu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In a multiple-object auction, every bidder tries to win as many objects as possible with a bidding algorithm. This paper studies position-randomized auctions, which form a special class of multiple- object auctions where a bidding algorithm consists of an initial bid se- quence and an algorithm for randomly permuting the sequence. We are especially concerned with situations where some bidders know the bid- ding algorithms of others. For the case of only two bidders, we give an optimal bidding algorithm for the disadvantaged bidder. Our result gene- ralizes previous work by allowing the bidders to have unequal budgets. One might naturally anticipate that the optimal expected numbers of objects won by the bidders would be proportional to their budgets. Sur- prisingly, this is not true. Our new algorithm runs in optimal O(n) time in a straightforward manner. The case with more than two bidders is open.

Original languageEnglish (US)
Title of host publicationAlgorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings
EditorsD.T. Lee, Shang-Hua Teng, Shang-Hua Teng
PublisherSpringer Verlag
Pages84-95
Number of pages12
ISBN (Print)3540412557, 9783540412557
DOIs
StatePublished - 2000
Event11th Annual International Symposium on Algorithms and Computation, ISAAC 2000 - Taipei, Taiwan, Province of China
Duration: Dec 18 2000Dec 20 2000

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1969
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other11th Annual International Symposium on Algorithms and Computation, ISAAC 2000
CountryTaiwan, Province of China
CityTaipei
Period12/18/0012/20/00

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Optimal bid sequences for multiple-object auctions with unequal budgets'. Together they form a unique fingerprint.

  • Cite this

    Chen, Y., Kao, M. Y., & Lu, H. I. (2000). Optimal bid sequences for multiple-object auctions with unequal budgets. In D. T. Lee, S-H. Teng, & S-H. Teng (Eds.), Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings (pp. 84-95). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1969). Springer Verlag. https://doi.org/10.1007/3-540-40996-3_8