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].