NP-hardness of equilibria in case of risk-averse players

Abstract

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 V=E+RV=E+R{\mathsf {V}} = {\mathsf {E}} + {\mathsf {R}} of expectation EE{\mathsf {E}} and a risk valuation RR{\mathsf {R}} of their costs

RR{\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 VV{\mathsf {V}}-equilibrium, no player can unilaterally reduce her cost.The results presented in this paper show that the question whether a 2-player game with such risk-modeling valuations VV{\mathsf {V}} has a VV{\mathsf {V}}-equilibrium is strongly NPNP{\mathcal {NP}}-hard under very mild assumptions. We only have to ask that the valuation functions are strictly quasiconcave or that they fulfill the Weak-Equilibrium-for-Expectation property and that additionally some 2-strategy game has no VV{\mathsf {V}}-equilibrium. These conditions are fulfilled for the functions from Markowitz’s Mean-Variance approach like E+Var,E+SDE+Var,E+SD{\mathsf {E}} + {\mathsf {Var}}, {\mathsf {E}} + {\mathsf {SD}} and the Sharpe Ration, and also for Conditional Value-at-Risk, recently very popular for modeling volatile economic circumstances.