The complexity of equilibria for risk-modeling valuations

DOI10.1016/J.TCS.2016.04.013zbMATH Open1339.91005arXiv1510.08980OpenAlexW2963496271MaRDI QIDQ284585FDOQ284585

Burkhard Monien, Marios Mavronicolas

Publication date: 18 May 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: 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 $mathsfV=mathsfE+mathsfR$ of expectation $mathsfE$ and a risk valuation $mathsfR$ of their costs; $mathsfR$ 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 $mathsfV$-equilibrium, no player could unilaterally reduce her cost. Say that $mathsfV$ 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 $mathsfE$-strict concavity and observe that every $mathsfE$-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 $mathsfV$-equilibrium is strongly $mathcalNP$-hard for certain choices of significant valuations (including variance and standard deviation).

Full work available at URL: https://arxiv.org/abs/1510.08980

Recommendations

• $$\mathcal {NP}$$-Hardness of Equilibria in Case of Risk-Averse Players
• Minimizing expectation plus variance
• Minimizing expectation plus variance
• The complexity of \((\mathsf{E}+\mathsf{Var})\)-equilibria, \(\mathsf{ESR}\)-equilibria, and \(\mathsf{SuperE}\)-equilibria for 2-players games with few cost values
• Conditional value-at-risk: structure and complexity of equilibria

zbMATH Keywords

complexityequilibrium computationrisk-valuationstrong NP-completenessweak-equilibrium-for-expectation

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Noncooperative games (91A10)

Cites Work

• Non-cooperative games
• Equilibrium points in n -person games
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Efficiency Analysis of Choices Involving Risk
• Correlated Equilibrium as an Expression of Bayesian Rationality
• Fixed-point and Minimax Theorems in Locally Convex Topological Linear Spaces
• A Social Equilibrium Existence Theorem*
• Exposition of a New Theory on the Measurement of Risk
• New complexity results about Nash equilibria
• Existence and dynamic consistency of Nash equilibrium with non-expected utility preferences
• On the complexity of the parity argument and other inefficient proofs of existence
• Congestion games with player-specific payoff functions
• Markowitz revisited: mean-variance models in financial portfolio analysis
• When the players are not expectation maximizers
• Optimal Financial Portfolios
• Equilibrium without independence
• Minimizing expectation plus variance

Cited In (8)

• The complexity of \((\mathsf{E}+\mathsf{Var})\)-equilibria, \(\mathsf{ESR}\)-equilibria, and \(\mathsf{SuperE}\)-equilibria for 2-players games with few cost values
• $$\mathcal {NP}$$-Hardness of Equilibria in Case of Risk-Averse Players
• An intensity-based approach for equity modeling
• When the players are not expectation maximizers
• Lipschitz continuity and approximate equilibria
• (In)existence of equilibria for 2-player, 2-value games with semistrictly quasiconcave cost functions
• Conditional value-at-risk: structure and complexity of equilibria
• The complexity of computational problems about Nash equilibria in symmetric win-lose games

This page was built for publication: The complexity of equilibria for risk-modeling valuations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q284585)