NP-hardness of equilibria in case of risk-averse players
Date
2018Author
Mavronicolas, MariosMonien, Burkhard
ISBN
978-3-319-98355-4Publisher
Springer International PublishingPlace of publication
ChamSource
Adventures Between Lower Bounds and Higher Altitudes: Essays Dedicated to Juraj Hromkovič on the Occasion of His 60th BirthdayPages
409-422Google Scholar check
Metadata
Show full item recordAbstract
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.