Determining bidding strategies in sequential auctions: quasi-linear utility and budget constraints

ABSTRACT

In this paper, we develop a new method for finding an optimal bidding strategy in sequential auctions, using a dynamic programming technique. The existing method assumes the utility of a user is represented in an additive form. Thus, the remaining endowment of money must be explicitly represented in each state. On the other hand, our method assumes the utility of a user can be represented in a quasi-linear form, and representing the payment as a state-transition cost. Accordingly, we can obtain more than an $m$-fold speed-up in the computation time, where $m$ is the initial endowment of money. Furthermore, we have developed a method for obtaining a semi-optimal bidding strategy under budget constraints.

REFERENCES

• 1: Craig Boutilier , Moisés Goldszmidt , Bikash Sabata, Sequential Auctions for the Allocation of Resources with Complementarities, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.527-523, July 31-August 06, 1999
• 2: A.Mas-Colell, M. D.Whinston, and J. R.Green. Microeconomic Theory. Oxford University Press, 1995.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Dynamic programming

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Design, Measurement, Performance, Theory