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_14: We consider strategic games in which each player seeks a mixed strategy to minimize her cost evaluated by a concave valuationV (mapping probability distributions to reals); such valuations are used to model risk. In contrast to games with expectation-optimizer players where mixed equilibria always exist (Nash 1950; Nash Ann. Math. 54, 286---295, 1951), a mixed equilibrium for such games, called a V-equilibrium, may fail to exist, even though pure equilibria (if any) transfer over. What is the exact impact of such valuations on the existence, structure and complexity of mixed equilibria? We address this fundamental question in the context of expectation plus variance, a particular concave valuation denoted as RA, which stands for risk-averse; so, variance enters as a measure of risk and it is used as an additive adjustment to expectation. We obtain the following results about RA-equilibria: A collection of general structural properties of RA-equilibria connecting to (i)E-equilibria and Var-equilibria, which correspond to the expectation and variance valuations E and Var, respectively, and to (ii) other weaker or incomparable properties such as Weak Equilibrium and Strong Equilibrium. Some of these structural properties imply quantitative constraints on the existence of mixed RA-equilibria.A second collection of (i) existence, (ii) equivalence and separation (with respect to E-equilibria), and (iii) characterization results for RA-equilibria in the new class of player-specific scheduling games. We provide suitable examples with a mixed RA-equilibrium that is not an E-equilibrium and vice versa.A purification technique to transform a player-specific scheduling game on two identical links into a player-specific scheduling game on two links so that all non-pureRA-equilibria are eliminated while no new pure equilibria are created; so, a particular player-specific scheduling game on two identical links with no pure equilibrium yields a player-specific scheduling game with noRA-equilibrium (whether mixed or pure). As a by-product, the first ?????-completeness result for the computation of RA-equilibria follows.
@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.
@cite_17: 
While bringing concave valuations from Actuarial Risk Theory @cite_17 into play, our framework encompasses general classes of @math -valuations, assuming the Risk-Positivity property, that also enjoy the Weak-Equilibrium-for-Expectation property, and a few additional properties. The @math -equilibria on which @cite_7 @cite_14 focused are a special case of our general framework.