Conditional Value-at-Risk: Structure and Complexity of Equilibria

Conditional Value-at-Risk, denoted as \({\mathsf {CVaR}}_{\alpha }\), is becoming the prevailing measure of risk over two paramount economic domains: the insurance domain and the financial domain; \(\alpha \in (0,1)\) is the confidence level. In this work, we study the strategic equilibria for an economic system modeled as a game, where risk-averse players seek to minimize the Conditional Value-at-Risk of their costs. Concretely, in a \({\mathsf {CVaR}}_{\alpha }\)-equilibrium, the mixed strategy of each player is a best-response. We establish two significant properties of \({\mathsf {CVaR}}_{\alpha }\) at equilibrium: (1) The Optimal-Value property: For any best-response of a player, each mixed strategy in the support gives the same cost to the player. This follows directly from the concavity of \({\mathsf {CVaR}}_{\alpha }\) in the involved probabilities, which we establish. (2) The Crawford property: For every \(\alpha \), there is a 2-player game with no \({\mathsf {CVaR}}_{\alpha }\)-equilibrium. The property is established using the Optimal-Value property and a new functional property of \({\mathsf {CVaR}}_{\alpha }\), called Weak-Equilibrium-for-\({\mathsf {VaR}}_{\alpha }\), we establish. On top of these properties, we show, as one of our two main results, that deciding the existence of a \({\mathsf {CVaR}}_{\alpha }\)-equilibrium is strongly \({\mathcal {NP}}\)-hard even for 2-player games. As our other main result, we show the strong \({\mathcal {NP}}\)-hardness of deciding the existence of a \({\mathsf {V}}\)-equilibrium, over 2-player games, for any valuation \({\mathsf {V}}\) with the Optimal-Value and the Crawford properties. This result has a rich potential since we prove that the very significant and broad class of strictly quasiconcave valuations has the Optimal-Value property.