Optimal Bid Sequences for Multiple-Object Auctions with Unequal Budgets.
Journal
Algorithms and Computation, 11th International Conference, ISAAC 2000, Taipei, Taiwan, December 18-20, 2000, Proceedings
Pages
84-95
Date Issued
2000
Author(s)
Chen, Yuyu
Kao, Ming-Yang
HSUEH-I LU
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.
Type
conference paper