A Dynamic Programming Model for Determining Bidding Strategies in Sequential Auctions: Quasi-linear Utility and Budget Constraints
Hiromitsu Hattori, Makoto Yokoo, Yuko Sakurai, Toramatsu Shintani
In this paper, we develop a new method for finding an optimal biddingstrategy in sequential auctions, using a dynamic programming technique. Theexisting method assumes that the utility of a user is represented in anadditive form. Thus, the remaining endowment of money must be explicitlyrepresented in each state, and the calculation of the optimal biddingstrategy becomes time-consuming when the initial endowment of money mbecomes large.In this paper, we develop a new problem formalization that avoids explicitlyrepresenting the remaining endowment, by assuming the utility of a user canbe represented in a quasi-linear form, and representing the payment as astate-transition cost. Experimental evaluations show that we can obtainmore than an m-fold speed-up in the computation time. Furthermore, we havedeveloped a method for obtaining a semi-optimal bidding strategy underbudget constraints, and have experimentally confirmed the efficacy of thismethod.
PDF Link: /papers/01/p211-hattori.pdf
AUTHOR = "Hiromitsu Hattori
and Makoto Yokoo and Yuko Sakurai and Toramatsu Shintani",
TITLE = "A Dynamic Programming Model for Determining Bidding Strategies in Sequential Auctions: Quasi-linear Utility and Budget Constraints",
BOOKTITLE = "Proceedings of the Seventeenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-01)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "2001",
PAGES = "211--218"