Concave game
Concave game
In game-theory, a concave game is a generalization of the normal-form-game defined by Rosen. He extended the theorem on existence of a nash-equilibrium, which John Nash originally proved for normal-form games, to concave games.
From normal-form games to concave games We will describe the generalization step by step.
1. In a normal-form game, each player i can choose one of mi pure actions. The set of strategies available to each player is the set of lotteries over the pure actions, which is a simplex in Rmi.
- In a concave game, the set of strategies available to each player may be any convex set in Rmi.
2. In a normal-form game, the set of strategies available to each player is independent of the strategies chosen by other players. This means that the set of all possible strategy profiles (denoted S) is a Cartesian product of the sets of strategies available to the players (in other words, the constraints on each player's choices are orthogonal).
- In a concave game, the set of strategy profiles may be any convex set in Rm (where m:=m1+...+mn). This means that the constraints on each player's choice are coupled - each player's available strategies may depend on what other players choose (such "coupled constraints" were also studied earlier by Debreu).
3. In a normal-form game, the utility function of each player i (denoted ui - a real-valued function on S) is a linear function in each of its components, for any fixed value of the other components (for each agent j, given any choice of strategies by the other agents, the payoff of agent i is a linear function in the probabilities by which agent j chooses his pure actions).
- In a concave game, each ui can be any continuous function that is concave in the strategy of agent i.
- To state this property more explicitly, fix some strategies for all players except i; denote them by x1,...,xi-1,xi+1,...,xn, or using the shorthand notation x-i. Fix some two possible strategies for player i; denote them by xi, yi, such that both (xi,x-i) and (yi,x-i) are in S. Choose some value t in [0,1]. Note that, since S is convex, every convex combination of xi, yi is in S too; particularly, (1-t)xi*+*tyi is in S. The concavity requirement is that ui[(1-*t*)**xi*+*t***yi*] ≥ (1-t)ui*(*xi*) + *tui(yi).
Existence of equilibrium If the above conditions hold (that is, the space S of possible strategy profiles is convex, and each payoff function ui is continuous in all strategies and of all players concave in the strategy of player i), then an equilibrium exists. shows that the same condition that guarantees uniqueness of a Nash equilibrium also guarantees uniqueness of a correlated-equilibrium. Moreover, an even weaker condition guarantees the uniqueness of a correlated equilibrium - a generalization of a condition proved by abraham-neyman.
Computation of equilibrium Based on the above results, it is possible to compute equilibrium points for concave games using gradient methods for convex optimization. prove that computing an equilibrium in a concave game is PPAD-complete. In fact, they prove that the problem is in PPAD even for general concave games, and it is PPAD-hard even in the special case of strongly-concave utilities that can be expressed as multivariate polynomials of a constant degree with axis-aligned box constraints.
Practice Arrow and Hurwicz presented gradient methods for solving two-player zero-sum-games with non-linear utilities.
Krawczyk and Uryasev studied infinite games with nonlinear utilities and coupled constraints. Starting from an existing Relaxation method, they improved it by adding steepest-descent step-size control and other improvements, and proved that it indeed converges to an equilibrium. They tested their algorithm numerically on several applications, such as pollution of a river basin, and showed that it converges quickly on a wide range of parameters.
Krawczyk explains numerical methods converging to an equilibrium, focusing on the case of coupled constraints. He presents several application examples using a Matlab suite called NIRA.
Chernov presents two numerical search approaches for computing equilibrium points, that have guaranteed convergence without additional requirements on the objective functions: (1) using the Hooke-Jeeves method for residual function minimization (2) an intermediate between the relaxation algorithm and the Hooke-Jeeves method of configurations. Convergence is proved for one-dimensional sets of players strategies. The approaches are tested using numerical experiments.
Variants Flåm and Ruszczyński define a convex-concave game. This is a game in which the space S of strategy profiles is convex, as in Rosen's definition. But instead of requiring smoothness and other conditions on g(x,r), they allow non-smooth data, and only require that the following function is convex in x and concave in y: <math>L(r,x,y) := \sum_{i=1}^n r_i\cdot u_i(x) - u_i(y_i, x_{-i})</math>.
For such convex-concave games, they present two algorithms for finding equilibria, both using partial regularizations and relaxed subgradient projections. They prove that these algorithms converge.