Given a vector of costs , the optimization problem in Equation 4 is still NP-hard (assuming the representation of the utility function is sufficiently complex). For many representations of , 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