The complexity of equilibria for risk-modeling valuations

Following the direction pioneered by Fiat and Papadimitriou in their 2010 paper [12], 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 of expectation  EE and a risk valuation  RR of their costs; RR 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-equilibrium, no player could unilaterally reduce her cost.Say that VV has the Weak-Equilibrium-for-Expectation property if all strategies supported in a player's best-response   mixed strategy incur the same conditional expectation of her cost. We introduce EE-strict concavity   and observe that every EE-strictly concave valuation has the Weak-Equilibrium-for-Expectation property. We focus on a broad class of valuations shown to have the Weak-Equilibrium-for-Expectation property, which we exploit to prove two main complexity results, the first of their kind, for the two simplest cases of the problem:
• Two strategies: Deciding the existence of a VV-equilibrium is strongly NPNP-hard for the restricted class of player-specific scheduling games on two ordered links [22], when choosing RR as (1)VarVar (variance), or (2)SDSD (standard deviation), or (3) a concave linear sum of even moments of small order.
• Two players: Deciding the existence of a VV-equilibrium is strongly NPNP-hard when choosing RR as (1)γ⋅Varγ⋅Var, or (2)γ⋅SDγ⋅SD, where γ>0γ>0 is the risk-coefficient,   or choosing VV as (3) a convex combination of E+γ⋅VarE+γ⋅Var and the concave ν-valuation  ν−1(E(ν(⋅)))ν−1(E(ν(⋅))), where ν(x)=xrν(x)=xr, with r≥2r≥2. This is a concrete consequence of a general strong NPNP-hardness result that only needs the Weak-Equilibrium-for-Expectation   property and a few additional properties for VV; its proof involves a reduction with a single parameter, which can be chosen efficiently so that each valuation satisfies the additional properties.