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
StatePublished - Jan 1 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

Fingerprint

Auctions
Unequal
Bidding
Object
Genes
Directly proportional
Generalise

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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.
Chen, Yuyu ; Kao, Ming Yang ; Lu, Hsueh I. / Optimal bid sequences for multiple-object auctions with unequal budgets. Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings. editor / D.T. Lee ; Shang-Hua Teng ; Shang-Hua Teng. Springer Verlag, 2000. pp. 84-95 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{002fa0781211428f9b997434a8292ed4,
title = "Optimal bid sequences for multiple-object auctions with unequal budgets",
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.",
author = "Yuyu Chen and Kao, {Ming Yang} and Lu, {Hsueh I.}",
year = "2000",
month = "1",
day = "1",
language = "English (US)",
isbn = "3540412557",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "84--95",
editor = "D.T. Lee and Shang-Hua Teng and Shang-Hua Teng",
booktitle = "Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings",
address = "Germany",

}

Chen, Y, Kao, MY & Lu, HI 2000, Optimal bid sequences for multiple-object auctions with unequal budgets. in DT Lee, S-H Teng & S-H Teng (eds), Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1969, Springer Verlag, pp. 84-95, 11th Annual International Symposium on Algorithms and Computation, ISAAC 2000, Taipei, Taiwan, Province of China, 12/18/00.

Optimal bid sequences for multiple-object auctions with unequal budgets. / Chen, Yuyu; Kao, Ming Yang; Lu, Hsueh I.

Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings. ed. / D.T. Lee; Shang-Hua Teng; Shang-Hua Teng. Springer Verlag, 2000. p. 84-95 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1969).

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

TY - GEN

T1 - Optimal bid sequences for multiple-object auctions with unequal budgets

AU - Chen, Yuyu

AU - Kao, Ming Yang

AU - Lu, Hsueh I.

PY - 2000/1/1

Y1 - 2000/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84949759446&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84949759446&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84949759446

SN - 3540412557

SN - 9783540412557

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 84

EP - 95

BT - Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings

A2 - Lee, D.T.

A2 - Teng, Shang-Hua

A2 - Teng, Shang-Hua

PB - Springer Verlag

ER -

Chen Y, Kao MY, Lu HI. Optimal bid sequences for multiple-object auctions with unequal budgets. In Lee DT, Teng S-H, Teng S-H, editors, Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings. Springer Verlag. 2000. p. 84-95. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).