## The complexity of equilibria for risk-modeling valuations

##### Date

2016##### Author

Mavronicolas, MariosMonien, Burkhard

##### Source

Theoretical Computer Science##### Volume

634##### Pages

67-96Google Scholar check

##### Keyword(s):

##### Metadata

Show full item record##### Abstract

Following the direction pioneered by Fiat and Papadimitriou in their 2010 paper [12], 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 V=. E+. R of expectation E and a risk valuation R of their costs R 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 V-equilibrium, no player could unilaterally reduce her cost.Say that V 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 E-strict concavity and observe that every E-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:. •Two strategies: Deciding the existence of a V-equilibrium is strongly NP-hard for the restricted class of player-specific scheduling games on two ordered links [22], when choosing R as (1) Var (variance), or (2) SD (standard deviation), or (3) a concave linear sum of even moments of small order.•Two players: Deciding the existence of a V-equilibrium is strongly NP-hard when choosing R as (1) γVar, or (2) γSD, where γ>0 is the risk-coefficient, or choosing V as (3) a convex combination of E+γVar and the concave ν-valuation ν-1(E(ν)), where ν(x)=xr, with r≥2. This is a concrete consequence of a general strong NP-hardness result that only needs the Weak-Equilibrium-for-Expectation property and a few additional properties for V its proof involves a reduction with a single parameter, which can be chosen efficiently so that each valuation satisfies the additional properties. © 2016 Elsevier B.V.