\(\mathcal {NP}\)-Hardness of Equilibria in Case of Risk-Averse Players

We study the complexity of deciding the existence of mixed equilibria for minimization games where players use valuations other than expectation to evaluate their costs. We consider risk-averse players seeking to minimize the sum \({\mathsf {V}} = {\mathsf {E}} + {\mathsf {R}}\) of expectation \({\mathsf {E}}\) and a risk valuation \({\mathsf {R}}\) of their costs; \({\mathsf {R}}\) is non-negative and vanishes exactly when the cost incurred to a player is constant over all choices of strategies by the other players. In a \({\mathsf {V}}\)-equilibrium, no player can unilaterally reduce her cost.