Minimizing Expectation Plus Variance

B. Monien, M. Mavronicolas, Theory of Computing Systems 57 (2015) 617–654.

Download
Restricted 398-MEPV14_02.pdf 638.19 KB
Journal Article | English
Author
Monien, Burkhard; Mavronicolas, Marios
Abstract
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 (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-pure RA-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 no RA-equilibrium (whether mixed or pure). As a by-product, the first PLS-completeness result for the computation of RA-equilibria follows.
Publishing Year
Journal Title
Theory of Computing Systems
Volume
57
Issue
3
Page
617-654
LibreCat-ID
398

Cite this

Monien B, Mavronicolas M. Minimizing Expectation Plus Variance. Theory of Computing Systems. 2015;57(3):617-654. doi:10.1007/s00224-014-9542-z
Monien, B., & Mavronicolas, M. (2015). Minimizing Expectation Plus Variance. Theory of Computing Systems, 57(3), 617–654. https://doi.org/10.1007/s00224-014-9542-z
@article{Monien_Mavronicolas_2015, title={Minimizing Expectation Plus Variance}, volume={57}, DOI={10.1007/s00224-014-9542-z}, number={3}, journal={Theory of Computing Systems}, publisher={Springer}, author={Monien, Burkhard and Mavronicolas, Marios}, year={2015}, pages={617–654} }
Monien, Burkhard, and Marios Mavronicolas. “Minimizing Expectation Plus Variance.” Theory of Computing Systems 57, no. 3 (2015): 617–54. https://doi.org/10.1007/s00224-014-9542-z.
B. Monien and M. Mavronicolas, “Minimizing Expectation Plus Variance,” Theory of Computing Systems, vol. 57, no. 3, pp. 617–654, 2015.
Monien, Burkhard, and Marios Mavronicolas. “Minimizing Expectation Plus Variance.” Theory of Computing Systems, vol. 57, no. 3, Springer, 2015, pp. 617–54, doi:10.1007/s00224-014-9542-z.
Main File(s)
File Name
398-MEPV14_02.pdf 638.19 KB
Access Level
Restricted Closed Access
Last Uploaded
2018-03-15T08:22:31Z


Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar