next up previous
Next: Approximation via Sampling Up: Simplified Abstraction Previous: Approximate Value by Reordering

Approximate Bidding

Given a vector of costs $Y$, the optimization problem $\mbox{opt}(H,i,Y)$ in Equation 4 is still NP-hard (assuming the representation of the utility function $v(\cdot)$ is sufficiently complex). For many representations of $v(\cdot)$, the optimization problem can be cast as an integer linear program and approximated by using the fractional relaxation instead of the exact optimization problem. This is precisely the approach we have adopted in ATTac [Stone, Littman, Singh, KearnsStone et al.2001].

Peter Stone 2003-09-24