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).
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 ).
@cite_7
2179146913
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.