The Complexity of Equilibria for Risk-Modeling Valuations

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 $\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 could unilaterally reduce her cost. Say that $\mathsf{V}$ 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 $\mathsf{E}$-strict concavity and observe that every $\mathsf{E}$-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: games with two strategies, or games with two players. For each case, we show that deciding the existence of a $\mathsf{V}$-equilibrium is strongly $\mathcal{NP}$-hard for certain choices of significant valuations (including variance and standard deviation).

49 pages