What is the value of the auction, that is, the bidder's
expected profit (utility minus cost) for bidding optimally for the
rest of the auction? If a
bidder knows this value, it can make its next bid to be one that
maximizes its expected profit.
The value is a function of the bidder's current holdings
and the current item to bid on, .
It can be
Equation 1 is closely related to the equations defining the value of a finite-horizon partially observable Markov decision process [Papadimitriou TsitsiklisPapadimitriou Tsitsiklis1987] or a stochastic satisfiability expression [Littman, Majercik, PitassiLittman et al.2001]. Like these other problems, the sequential auction problem is computationally intractable for sufficiently general representations of (specifically, linear functions of the holdings are not expressive enough to achieve intractability while arbitrary nonlinear functions are).