Minimizing Expectation Plus Variance

M. Mavronicolas, B. Monien, in: Proceedings of the 5th International Symposium on Algorithmic Game Theory (SAGT), 2012, pp. 239–250.

Download
Restricted 597-newtocs_01.pdf 345.83 KB
Conference Paper
Author
Mavronicolas, Marios; Monien, Burkhard
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 [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.
Publishing Year
Proceedings Title
Proceedings of the 5th International Symposium on Algorithmic Game Theory (SAGT)
forms.conference.field.series_title_volume.label
LNCS
Page
239-250
LibreCat-ID
597

Cite this

Mavronicolas M, Monien B. Minimizing Expectation Plus Variance. In: Proceedings of the 5th International Symposium on Algorithmic Game Theory (SAGT). LNCS. ; 2012:239-250. doi:10.1007/978-3-642-33996-7_21
Mavronicolas, M., & Monien, B. (2012). Minimizing Expectation Plus Variance. In Proceedings of the 5th International Symposium on Algorithmic Game Theory (SAGT) (pp. 239–250). https://doi.org/10.1007/978-3-642-33996-7_21
@inproceedings{Mavronicolas_Monien_2012, series={LNCS}, title={Minimizing Expectation Plus Variance}, DOI={10.1007/978-3-642-33996-7_21}, booktitle={Proceedings of the 5th International Symposium on Algorithmic Game Theory (SAGT)}, author={Mavronicolas, Marios and Monien, Burkhard}, year={2012}, pages={239–250}, collection={LNCS} }
Mavronicolas, Marios, and Burkhard Monien. “Minimizing Expectation Plus Variance.” In Proceedings of the 5th International Symposium on Algorithmic Game Theory (SAGT), 239–50. LNCS, 2012. https://doi.org/10.1007/978-3-642-33996-7_21.
M. Mavronicolas and B. Monien, “Minimizing Expectation Plus Variance,” in Proceedings of the 5th International Symposium on Algorithmic Game Theory (SAGT), 2012, pp. 239–250.
Mavronicolas, Marios, and Burkhard Monien. “Minimizing Expectation Plus Variance.” Proceedings of the 5th International Symposium on Algorithmic Game Theory (SAGT), 2012, pp. 239–50, doi:10.1007/978-3-642-33996-7_21.
Main File(s)
File Name
597-newtocs_01.pdf 345.83 KB
Access Level
Restricted Closed Access
Last Uploaded
2018-03-15T08:20:53Z


Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar