Approximate Value by Reordering

There are three major sources of intractability in Equation 1--the alternation of the maximization and expectation operators (allowing decisions to be conditioned on an exponential number of possible sets of holdings), the large number of maximizations (forcing an exponential number of decisions to be considered), and the large number of expectations (resulting in sums over an exponential number of variable settings).

We attack the problem of interleaved operators by moving all but the first of the maximizations inside the expectations, resulting in an expression that approximates the value:

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

Because the choices for bids $r_{i+1}$ through $r_{n-1}$ appear more deeply nested than the bindings for the closing prices $y_i$ through $y_{n-1}$, they cease to be bids altogether, and instead represent decisions as to whether to purchase goods at given prices. Let $G=\mbox{opt}(H,i,Y)$ be a vector representing the optimal number of goods to purchase at the prices specified by the vector $Y$ given the current holdings $H$ starting from auction $i$. Conceptually, this can be computed by evaluating

$$\mbox{opt}(H,i,Y) =\mathop{\mbox{argmax}}_{g_{i}, \ldots, g_{n-1}} (v(G+H)-H \cdot Y).$$ (3)

Thus, Equation 2 can be written:

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

where $H'$ is identical to $H$ except the $i$-th component reflects whether item $i$ is won--$r_i \ge y_i$.

Note that there is a further approximation that can be made by computing the expected prices (as point values) before solving the optimization problem. This approach corresponds to further swapping the expectations towards the core of the equation:

$$\mbox{value-est}(i,H)_{ev} = \max_{r_i} (v(\mbox{opt}(H',i+1,E_{Y})+H')-\mbox{opt}(H',i+1,E_{Y}) \cdot E_{Y})$$ (5)

where $E_{Y} = E[y_{i+1},\ldots,y_{n-1}]$, the vector of expected costs of the goods. In the remainder of the article, we refer to methods that use this further approximation from Equation 5 as expected value approaches for reasons that will be come apparent shortly.

The technique of swapping maximization and expectation operators was previously used by hauskrecht97 hauskrecht97 to generate a bound for solving partially observable Markov decision processes. The decrease of uncertainty when decisions are made makes this approximation an upper bound on the true value of the auction: $\mbox{value-est} \ge \mbox{value}$. The tightness of the approximations in Equations 2 and 5 depends on the true distributions of the expected prices. For example, if the prices were known in advance with certainty, then both approximations are exact.