Concave game

In game theory, a concave game is a generalization of the normal-form game defined by Rosen. ^[1] 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 m_i pure actions. The set of strategies available to each player is the set of lotteries over the pure actions, which is a simplex in R^mi.

• In a concave game, the set of strategies available to each player may be any convex set in R^mi.

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 R^m (where m:=m₁+...+m_n). 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 ^[2] ).

3. In a normal-form game, the utility function of each player i (denoted u_i - 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 u_i 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 x₁,...,x_i-1,x_i+1,...,x_n, or using the shorthand notation x_-i. Fix some two possible strategies for player i; denote them by x_i, y_i, such that both (x_i,x_-i) and (y_i,x_-i) are in S. Choose some value t in [0,1]. Note that, since S is convex, every convex combination of x_i, y_i is in S too; particularly, (1-t)*x_i+t*y_i is in S. The concavity requirement is that u_i[(1-t)*x_i+t*y_i] ≥ (1-t)*u_i(x_i) + t*u_i(y_i).

Existence of equilibrium

If the above conditions hold (that is, the space S of possible strategy profiles is convex, and each payoff function u_i is continuous in all strategies and of all players concave in the strategy of player i), then an equilibrium exists. ^{[1] : Thm.1} The proof uses the Kakutani fixed-point theorem.

Uniqueness of equilibrium

Rosen also proved that, under certain technical conditions which include strict concavity, the equilibrium is unique. The conditions are explained below.

Assume that the space S of allowed strategy profiles is defined by some k functions (representing constraints), that is, ${\displaystyle S=\{x\in \mathbb {R} ^{m}|h_{1}(x)\geq 0,\ldots ,h_{k}(x)\geq 0\}}$. In a normal-form game, the constraint functions are linear functions defining the simpices of the players; in a concave game, the h_j can be any concave function of x. For the uniqueness proof, it is also required that each h_j has continuous first derivatives at any x in S.

Assume also that, for each player i, the utility function u_i has continuous first derivatives at the components of x_i (that is, each player's utility is continuously differentiable in the player's own strategy).

For any fixed positive vector r>0 in Rⁿ, define the r-weighted-sum of the players' payoffs:

${\displaystyle f(x,r):=r\cdot u(x)=\sum _{i=1}^{n}r_{i}\cdot u_{i}(x)}$.

Define the pseudogradient of f:

${\displaystyle g(x,r):=[r_{1}\cdot \bigtriangledown _{1}u_{1}(x),\ldots ,r_{n}\cdot \bigtriangledown _{n}u_{n}(x)]}$

where ${\displaystyle \bigtriangledown _{i}u_{i}(x)}$ is the gradient of u_i with respect to the x_i components. So ${\displaystyle \bigtriangledown _{i}u_{i}(x)}$ is a vector in R^mi and g(x,r) is a vector in R^m.

We say that f is diagonally-strictly-concave at r if for every x,y in S: ${\displaystyle (y-x)\cdot g(x,r)+(x-y)\cdot g(y,r)>0}$

• For orthogonal constraint sets, if there exists some r>0 for which f is diagonally-strictly-concave at r, then the concave game has a unique equilibrium. ^{[1] : Thm.2}
• For coupled constraint sets, if there exists a convex subset Q of R^m such that, for every r in Q, f is diagonally-strictly-concave at r, then for each r in Q, the game has a unique r-normalized equilibrium (an equilibrium where the Lagrange multipliers have the same proportion as r). ^{[1] : Thm.3}

A sufficient condition for f being diagonally-strictly-concave at r is that the symmetric matrix G(x,r)+G^T(x,r) is negative definite. ^{[1] : Thm.5} See the paper for an example for bimatrix games.

Convergence to equilibrium

Consider a dynamic model of a concave game in which each player changes his strategy such that the strategy-profile remains in S, and subject to that, his utility increases. Each player i changes his strategy at rate r_i in the direction of the gradient defining the maximum utility increase subject to the constraints. This results in a set of n differential equations. For any concave game and any staring point in S, this set of differential equations has a continuous solution x(t) that remains in S for all t>0. ^{[1] : Thm.7}

If, in addition, the matrix G(x,r)+G^T(x,r) is negative definite for all x in S, then the solution x(t) converges to an equilibrium point as t approaches infinity. ^{[1] : Thm.8}

If, in addition, the matrix G(x,r)+G^T(x,r) is negative definite for all x in S, then the solution x(t) converges to the unique r-normalized equilibrium point. ^{[1] : Thm.9}

Correlated equilibrium

Takashi Ui ^[3] 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. ^[4]

Computation of equilibrium

Based on the above results, it is possible to compute equilibrium points for concave games using gradient methods for convex optimization. ^[1]

Theory

Papadimitriou, Vlatakis-Gkaragkounis and Zampetakis ^[5] 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 ^[6] presented gradient method s for solving two-player zero-sum game s with non-linear utilities.

Krawczyk and Uryasev ^[7] 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 equiilbrium. 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 ^[8] 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 ^[9] 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

Flam and Ruzcynzki ^[10] 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: ${\displaystyle L(r,x,y):=\sum _{i=1}^{n}r_{i}\cdot u_{i}(x)-u_{i}(y_{i},x_{-i})}$.

For such convex-concave games, they present two algorithms for finding equilibria, both using partial regularization s and relaxed subgradient projections. They prove that these algorithms converge.

See also

• Nash equilibrium computation
• Fictitious play
• Best response dynamics
• Saddle-point method - a method for finding max-min points.

References

1. Rosen, J. B. (1965). "Existence and Uniqueness of Equilibrium Points for Concave N-Person Games". Econometrica. 33 (3): 520–534. doi:10.2307/1911749. hdl: 2060/19650010164 . ISSN   0012-9682. JSTOR   1911749.
2. Debreu, Gerard (October 1952). "A Social Equilibrium Existence Theorem*". Proceedings of the National Academy of Sciences. 38 (10): 886–893. Bibcode:1952PNAS...38..886D. doi: 10.1073/pnas.38.10.886 . PMC   1063675 . PMID   16589195.
3. Ui, Takashi (2008-04-01). "Correlated equilibrium and concave games". International Journal of Game Theory. 37 (1): 1–13. doi:10.1007/s00182-007-0098-x. ISSN   1432-1270.
4. Neyman, Abraham (1997-06-01). "Correlated equilibrium and potential games". International Journal of Game Theory. 26 (2): 223–227. doi:10.1007/BF01295851. ISSN   1432-1270.
5. Papadimitriou, Christos H.; Vlatakis-Gkaragkounis, Emmanouil-Vasileios; Zampetakis, Manolis (2022). "The Computational Complexity of Multi-player Concave Games and Kakutani Fixed Points". arXiv: 2207.07557 [cs.CC].
6. Arrow, Kenneth; Hurwicz, Leonid (April 1957). "Gradient Methods for Constrained Maxima". Operations Research. 5 (2): 258–265. doi:10.1287/opre.5.2.258. ISSN   0030-364X.
7. Krawczyk, Jacek B.; Uryasev, Stanislav (2000-01-01). "Relaxation algorithms to find Nash equilibria with economic applications". Environmental Modeling & Assessment. 5 (1): 63–73. Bibcode:2000EMdAs...5...63K. doi:10.1023/A:1019097208499. ISSN   1573-2967.
8. Krawczyk, Jacek (2007-04-01). "Numerical solutions to coupled-constraint (or generalised Nash) equilibrium problems". Computational Management Science. 4 (2): 183–204. doi:10.1007/s10287-006-0033-9. ISSN   1619-6988.
9. Chernov, A. V. (2019-05-01). "On Some Approaches to Find Nash Equilibrium in Concave Games". Automation and Remote Control. 80 (5): 964–988. doi:10.1134/S0005117919050138. ISSN   1608-3032.
10. Flåm, S. D.; Ruszczyński, A. (March 2008). "Finding normalized equilibrium in convex-concave games". International Game Theory Review. 10 (1): 37–51. doi:10.1142/S0219198908001765. ISSN   0219-1989.