The complexity of equilibria for risk-modeling valuations

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.