Minimizing Expectation Plus Variance
Date
2015Author
Mavronicolas, MariosMonien, Burkhard
ISSN
1432-4350Source
Theory of Computing SystemsVolume
57Issue
3Pages
617-654Google Scholar check
Keyword(s):
Metadata
Show full item recordAbstract
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 PLS-completeness result for the computation of RA-equilibria follows. © 2014, Springer Science+Business Media New York.