Exact Value

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 $H$ and the current item to bid on, $i$. It can be expressed as

$$\mbox{value}(i,H) = \max_{r_i} E_{y_i} \max_{r_{i+1}} E_{y_{i+1}} \ldots \max_{r_{n-1}} E_{y_{n-1}} (v(G+H)- G \cdot Y),$$ (1)

where the components of $G$ are the new holdings as a result of additional winnings $g_j \equiv r_j \ge y_j$. Note that $H$ only has non-zero entries for items that have already been sold ( $\forall j \geq i, H_j = 0$) and $G$ only has non-zero entries for items that have yet to be sold ( $\forall j < i, G_j = 0$). Note also that $G$ and $Y$ are fully specified when the $g_j$ and $y_j$ variables (for $j \geq i$) are bound sequentially by the expectation and maximization operators. The idea here is that the bids $r_i$ through $r_{n-1}$ are chosen to maximize value in the context of the possible closing prices $y_j$.

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 $v(\cdot)$ (specifically, linear functions of the holdings are not expressive enough to achieve intractability while arbitrary nonlinear functions are).