Optimal bid sequences for multiple-object auctions with unequal budgets

Yuyu Chen; Ming Yang Kao; Hsueh I. Lu

doi:10.1007/3-540-40996-3_8

Optimal bid sequences for multiple-object auctions with unequal budgets

Yuyu Chen, Ming Yang Kao, Hsueh I. Lu

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings
Editors	D.T. Lee, Shang-Hua Teng, Shang-Hua Teng
Publisher	Springer Verlag
Pages	84-95
Number of pages	12
ISBN (Print)	3540412557, 9783540412557
DOIs	https://doi.org/10.1007/3-540-40996-3_8
State	Published - 2000
Event	11th Annual International Symposium on Algorithms and Computation, ISAAC 2000 - Taipei, Taiwan, Province of China Duration: Dec 18 2000 → Dec 20 2000

Publication series

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

Other

Other	11th Annual International Symposium on Algorithms and Computation, ISAAC 2000
Country/Territory	Taiwan, Province of China
City	Taipei
Period	12/18/00 → 12/20/00

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-40996-3_8

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

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.}",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2000.; 11th Annual International Symposium on Algorithms and Computation, ISAAC 2000 ; Conference date: 18-12-2000 Through 20-12-2000",

year = "2000",

doi = "10.1007/3-540-40996-3_8",

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",

}

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. https://doi.org/10.1007/3-540-40996-3_8

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 proceeding › Conference 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.

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2000.

PY - 2000

Y1 - 2000

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

U2 - 10.1007/3-540-40996-3_8

DO - 10.1007/3-540-40996-3_8

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

PB - Springer Verlag

T2 - 11th Annual International Symposium on Algorithms and Computation, ISAAC 2000

Y2 - 18 December 2000 through 20 December 2000

ER -

Chen Y, Kao MY, Lu HI. Optimal bid sequences for multiple-object auctions with unequal budgets. In Lee DT, Teng SH, Teng SH, 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)). doi: 10.1007/3-540-40996-3_8

Optimal bid sequences for multiple-object auctions with unequal budgets

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this