An Optimal Dynamic Programming Model for Algorithm Design in Simultaneous

Byde, Andrew

HP Development Company

关键词: auction;    decision theory;    dynamic programming;    algorithm;   

RP-ID  :  HPL-2001-67

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

In this paper we study algorithms for agents participating in multiple simultaneous auctions for a single private-value good; we use stochastic dynamic programming to derive formal methods for optimal algorithm specification; we study a number of algorithms of complementary complexity and effectiveness, and report preliminary tests on them. The methods and analysis in this paper extend naturally to more complicated scenarios, such as the purchase of multiple complementary goods, although different problem areas bring their own challenges with respect to computational complexity. 15 Pages