Minimizing Expectation Plus Variance
Mavronicolas, Marios
Monien, Burkhard
ddc:040
We consider strategic games in which each player seeks a mixed strategy to minimize her cost evaluated by a concave valuation V (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 [15, 16], 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 impact of such valuations on the existence, structure and complexity of mixed equilibria? We address this fundamental question for a particular concave valuation: expectation plus variance, 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 equilibrium properties.- 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. Using examples, we provide the first demonstration that going from E to RA may as well create new mixed (RA-)equilibria.- A purification technique to transform a player-specific scheduling game on identical links into a player-specific scheduling game so that all non-pure RA-equilibria are eliminated while new pure equilibria cannot be created; so, a particular game on two identical links yields one with no RA-equilibrium. As a by-product, the first-completeness result for the computation of RA-equilibria follows.
2012
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
https://ris.uni-paderborn.de/record/597
Mavronicolas M, Monien B. Minimizing Expectation Plus Variance. In: <i>Proceedings of the 5th International Symposium on Algorithmic Game Theory (SAGT)</i>. LNCS. ; 2012:239-250. doi:<a href="https://doi.org/10.1007/978-3-642-33996-7_21">10.1007/978-3-642-33996-7_21</a>
info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-642-33996-7_21
info:eu-repo/semantics/closedAccess