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


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
Number of pages12
ISBN (Print)3540412557, 9783540412557
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)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other11th Annual International Symposium on Algorithms and Computation, ISAAC 2000
Country/TerritoryTaiwan, Province of China

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


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

Cite this