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 @math of expectation @math and a risk valuation @math of their costs; @math 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 @math -equilibrium, no player could unilaterally reduce her cost. Say that @math 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 @math -strict concavity and observe that every @math -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 @math -equilibrium is strongly @math -hard for certain choices of significant valuations (including variance and standard deviation).
@cite_7: Much of Game Theory, including the Nash equilibrium concept, is based on the assumption that players are expectation maximizers. It is known that if players are risk averse, games may no longer have Nash equilibria ([11,6]. We show that 1. Under risk aversion (convex risk valuations), and for almost all games, there are no mixed Nash equilibria, and thus either there is a pure equilibrium or there are no equilibria at all, and, 2. For a variety of important valuations other than expectation, it is NP-complete to determine if games between such players have a Nash equilibrium.
Fiat and Papadimitriou [Section 2] FP10 coined a notion termed as strict concavity, denoted here as @math -strict concavity, which is similar to but different than @math -strict concavity. It turns out that their difference is essential since @math is not @math -strictly concave while it is @math -strictly concave. See the Appendix for the definition of @math -strict concavity and a proof that @math is not @math -strictly concave. In fact, no concrete example of an @math -strictly concave valuation was given in @cite_7 . Fiat and Papadimitriou [Theorem 3 & Observation 4] FP10 proved the sparsity of mixed @math -equilibria, when @math is @math -strictly concave: games with a mixed @math -equilibrium have measure @math . The sparsity of mixed @math -equilibria follows from [Theorem 1] BKS10 where it is established that @math is a Mean-Variance Preference Function [Claim 1] BKS10 . See for the definition of Mean-Variance Preference Functions and their relation to this work. Contrary to their sparsity, this work establishes that deciding the existence of mixed @math -equilibria is strongly @math -hard (Theorems and ).