Nash equilibrium computation

Nash equilibrium (NE) computation is a class of computational problems in the intersection of game theory and computer science. The input to this problem is a normal-form game, usually represented as a list of payoff matrices. The required output is a Nash equilibrium of the game.

NE computation can be broadly divided into computing mixed-strategy NE vs computing pure-strategy NE.

Mixed-strategy equilibria

Summarize

Perspective

When mixed strategies are allowed, every game has a Nash equilibrium. This was proved by John Nash in 1950^[1] using the Kakutani fixed-point theorem, and later in 1951^[2] using the Brouwer fixed-point theorem. For games with a small number of actions per player, a NE can be computed manually by solving a set of equations. However, when the number of actions per player grows, the number of possible strategy vectors grows exponentially, and the computation becomes computationally hard.

Non-polynomial-time algorithms

There are various algorithms that work well in practice, but do not guarantee termination in polynomial time. One of the most famous such algorithms is the Lemke–Howson algorithm.^[3]

Porter, Nudelman and Shoham^[4] present an algorithm based on simple search heuristics, that performs well in practice on a large variety of games. They use the GAMUT testbed for testing the performance of their algorithm.

Lipton, Markakis and Mehta^[5] presented a Quasi-polynomial time algorithm for computing an approximate NE. It takes time $n^{\log n}$ , where n is the number of possible actions per player. They do it by proving the existence of an approximate NE strategies with support logarithmic in n, and proving that the payoffs to all players in any exact NE can be ε-approximated by such an approximate NE. They also prove that, if the payoff matrices have constant rank, then an exact NE can be found in polytime.

Computational hardness

Daskalakis, Goldberg and Papadimitriou^[6] proved that finding a NE is PPAD-complete in games with four or more players; later, Chen and Deng^[7] extended the result even for two-player games (bimatrix games). Under standard complexity assumptions, these hardness results imply that no polynomial-time algorithm is expected for general equilibrium computation.

Computing a Nash equilibrium is PPAD-complete even for win-lose bimartix games, that is, two-player games in which the payoff of each player is either 0 or 1.^{[citation needed]}

Etessami and Yannakkis^[8] (who defined the complexity class FIXP) proved that computing an exact or approximate NE for 3 or more players is FIXP-complete. They also show that computing an approximate NE with any approximation factor smaller than 1/2 is at least as hard as the square-root sum problem, as well as a more general arithmetic circuit decision problem.

Approximation algorithms

Tsaknakis and Spirakis^[9] presented a polytime algorithm that finds an 0.3393-approximate NE for a bimatrix game. Their algorithm minimizes a certain function, representing the distance from NE, using gradient descent. The procedure converges in polynomial time to local optima which are 0.3393-approximate NE.

Deligkas, Fearnley, Savani and Spirakis^[10] extend the descent techniques to polymatrix games, attaining an (0.5+δ)-approximate NE in time polynomial in the input size and 1/δ. For general n-player games, the approximation ratio increases with n (e.g. it is 0.6022 for n=3 and 0.7153 for n=4).

Approximation hardness

The PPAD-completeness results in ^[6]^[7] in fact show that computing an ε-approximate NE is PPAD-complete, if ε is exponentially small (smaller than 2^-m, where m is the number of actions per player).

Chen Deng and Teng^[11] proved PPAD-hardness even for ε that is polynomially small. In other words, they proved that no algorithm with runtime polynomial in n and 1/ε can compute an ε-approximate Nash equilibrium in a two-player game with n actions per player, unless PPAD ≤ P. In particular, this means that there is probably no FPTAS for NE.

Aviad Rubinstein^[12] showed that finding an ε-approximate Nash equilibrium is PPAD-complete even for a simple class of games: graphical games of degree three, in which each agent has only two actions; and even when ε is a constant. In particular, there is no PTAS for NE in general games (He also proved inapproximability for other related problems, such as: Bayesian Nash equilibrium in a two-player game, relative ε-Nash equilibrium in a two-player game, market equilibrium in a non-monotone market as well as approximate competitive equilibrium from equal incomes).

Later, Rubinstein^[13] proved that, assuming the Exponential time hypothesis for PPAD, there exists a positive constant ε such that computing ε-approximate NE in a two-player game with n actions per player requires quasi-polynomial time, as in the ^[5] algorithm.

Smoothed complexity

Smoothed analysis has been used to prove that many problems that are computationally-hard in the worst case, are in fact "almost always" easy, that is, if a problem is perturbed randomly, then the perturbed problem is easy. Interestingly, this is not the case for the problem of computing a NE. In particular:

Chen, Deng and Teng^[11] proved that no algorithm for computing NE in a two-player game has smoothed complexity polynomial in n and 1/s, where s is the input perturbation size, unless PPAD ≤ RP. In particular, the smoothed complexity of the Lemke-Howson algorithm is probably not polynomial.
Boodaghians, Brakensiek, Hopkins and Rubinstein^[14] prove that computing NE in a 2-player game is PPAD-hard (under randomized reductions) even when smoothing with noise of constant magnitude.

Irrationality of outcomes

All two-player games with rational payoff matrices always have only NE with rational probabilities. However, there are three-player games with rational payoff matrices, in which every NE requires irrational probabilities, which cannot be output accurately in finite time. An example was already shown by Nash^[2]^: 293: it is a simplified variant of Poker for three players, with a unique NE in which all probabilities are linear functions of sqrt(321), which is an irrational number. Another example can be found in ^[15]^{: Proposition 3}: it is a three-player game where each player has only two possible actions "0" and "1". There is a unique NE in which all players choose "0" with proabilities that are linear functions of sqrt(409).

Datta^[16] shows that every real algebraic variety is isomorphic to the set of totally mixed Nash equilibria of some three-person game, and also to the set of totally mixed Nash equilibria of an n-person game in which each player has two actions. This means that, in each of these classes, there are games whose probabilities require roots of any real polynomial.^{[clarification needed]}

Orzech and Rinard^[17] show that, for any n ≥ 4, there is an n-player game where all payoffs are in {0,1,2}, with a unique NE in which all the probabilities are irradical numbers (algebraic numbers that cannot be expressed with m-th roots for any integer m).

Two-Player Zero-Sum Games

Two-player zero-sum games represent the most fundamental class with polynomial-time equilibrium computation. In these games, one player's gain equals the other's loss, creating a pure conflict scenario. The key insight is that NE in zero-sum games correspond to minimax strategies, which can be computed via linear programming. For a zero-sum game with payoff matrix A for the row player, the minimax theorem of John von Neumann establishes that the game value can be computed by solving dual linear programs.^[18] Since linear programming can be solved in polynomial time using interior-point methods or the ellipsoid algorithm, NE can be computed in time polynomial in the size of the payoff matrices.

Anonymous games

In an anonymous game, the payoff of each player depends only on his own strategy and on the number of players taking every strategy, but not on their identity. Anonymous games admit efficient computation of approximate NE. In particular:

Daskalakis and Papadimitriou^[19] presented polytime approximation algorithms for games with many players but few strategies (s strategies per player). Their algorithm computes a $s^{2}L$ -approximate pure NE, where L is the Lipschitz constant of the utility functions. They also show a PTAS for mixed NE when s=2. In a later work,^[20] they prove that approximate mixed NE in anonymous games can be computed in polytime to any desired accuracy, if the number of strategies is a constant (i.e., there is a PTAS). Moreover, if the utility functions are Lipschitz continuous, one can compute in polytime an approximate pure NE, whose quality depends on the number of strategies and the Lipschitz constant. If the game has two strategies, there always exists an approximate NE in which either only a small number of players randomize, or of those who do, they all randomize the same way.
Cheng, Diakonikolas and Stewart^[21] present other algorithms for finding approximate mixed NE in anonymous games, where the strategies of the players are "simple": each player plays one strategy with probability 1—δ, for some small δ, and plays uniformly at random with probability δ.
In contrast, Chen Durfee and Orfanou^[22] prove that, if the approximation parameter is exponentially small in the number of players, then the problem is PPAD-complete when there are at least 7 strategies.

Graphical Games

Graphical games represent strategic interactions using graphs where each player's payoff depends only on neighbors' actions, enabling algorithms that exploit sparsity.

In general, computing NE on graphical games is still PPAD-hard, even if the graph degree is at most 3 and each player has only 2 actions.^[23] However, when the graph is a tree with a bounded degree, more efficient algorithms are possible.

Kearns, Littman and Singh^[24] presented a dynamic programming algorithm for computing all NE of a tree-graphical game (with two actions per player); its run-time is exponential, but it allows to compute approximate NE in polynomial time. The algorithm requires only messages between neighboring nodes, and thus can be implemented in a distributed fashion.

They then proposed a modification that can find a single NE in polytime. However, Elkind, Goldberg and Goldberg^[23] showed that the modification is incorrect (does not always find a NE). Based on their ideas, they proposed a new algorithm that computes all NE in quadratic time for a path graph, and in polynomial time for a general graph of degree at most 2. For general trees, the run-time of this algorithm is exponential even when the tree has bounded degree and its pathwidth is 2, but the same is true for any algorithm of the same kind. Finding a NE for a degree-3 graphical game with constant pathwidth and 2 actions per player is PPAD-complete.

Bramoulle, Kranton and D'Amours^[25] study graphical games in which the best response function of each player is a linear function of the actions of his neighbors. They prove that the Nash equiibrium depends only on a single parameter of the graph: the smallest eigenvalue of the matrix representing the graph. Hence, it can be computed efficiently.^{[clarification needed]}

Win-Lose Games

Win-lose games are games in which all payoffs are either 0 or 1.

Codenotti, Leoncini and Resta^[26] presented a linear-time algorithm for win-lose bimatrix games where the number of winning positions per strategy of each of the players is at most two.
Liu, Li and Deng^[27] showed that, for polymatrix games, approximating a Nash equilibrium with polynomial precision is PPAD-hard, even for sparse win-lose games.

Bounded-rank bimatrix games

Rank-1 bimatrix games have payoff matrices that can be written as outer products of vectors. Adsul, Garg, Mehta and Sohoni^[28] presented a polytime algorithm for exact NE. They also presented an algorithm to enumerate all the NE of a rank-1 game.\

Bounded rank bimatrix games: Lipton, Markakis and Mehta^[5] prove that, for two players, if the payoff matrices have constant rank, then an exact NE can be found in polytime.

Auction Games

Auctions with dominant strategies (e.g. second-price auction and some special cases of combinatorial auctions^[29]) clearly have pure-strategy NE that can be computed efficiently. But even for first-price auctions, which do not have dominant strategies, it is often possible to compute NE directly, by direct computation using knowledge of agents' distributions. For example,^[30] when all n buyers have uniform valuations on [0,1], the equilibrium bidding function is: b(v) = (n-1)v/n.

Remove ads

Pure-strategy equilibria

Summarize

Perspective

A pure-strategy Nash equilibrium (PNE) is not guaranteed to exist in general games, though there are special classes of games in which a PNE always exists.

Deciding existence

Gottlob, Greco and Sarcello^[31] prove that, even in very restrictive settings, deciding the existence of a PNE is NP-hard. Deciding the existence of a strong Nash equilibrium is even harder: it is Σ^P₂-complete.

However, when the utility function for each player depends only on the actions of a logarithmically small number of other players (that is, the dependency graph of the game has a small degree), then finding a PNE can be done in polytime. For graphical games, these problems are LOGCFL-complete.^[32]

Anonymous games

Daskalakis and Papadimitriou^[19]^[20] proved that anonymous games with Lipschitz continuous utility functions and at most s strategies always contain an $s^{2}L$ -approximate PNE, where L is the Lipschitz constant of the utility functions; such a PNE can compute in polytime.

Graphical games

Gottlob, Greco and Sarcello^[31] present algorithms for graphical games where the graphs with bounded treewidth. They show that a PNE can be found in polynomial time using tree decomposition techniques. The algorithm's complexity is exponential in the treewidth but polynomial in the game size.

Potential games and Congestion games

Potential games always have a PNE. Potential games satisfy the Finite Improvement Property: every sequence of unilateral beneficial deviations terminates at a Nash equilibrium.^[33] This immediately gives a simple algorithm: start with any strategy profile; while some player can improve their payoff by switching strategies - let that player switch to a better strategy; return the final strategy profile (guaranteed to be a Nash equilibrium). However, this algorithm might go through exponentially many different states before it converges.

Fabrikant, Papadimitriou and Talwar^[34] studied the special case of congestion games (which are equivalent to exact potential games). They proved that:

PNE can be found in polytime in the special case of symmetric network congestion games. Such a game is represented by a directed graph with two nodes marked as "source" and "target". The set of actions available to each player is the set of paths from the source to the target. For each edge, there is a delay which is a function of the number of players who use it. The payoff to each player is minus the total delay on his chosen path. In this special case, a PNE can be computed in polynomial time by maximizing the potential, through reduction to min-cost flow.
In contrast, for asymmetric network congestion games (which are network congestion games in which each player has a different source and a different target), computing a PNE is PLS-complete. The same holds for non-network congestion games (games in which all agents have the same set of strategies, but it is not the set of paths in any graph), whether symmetric or not. The proof implies that there are examples of such games in which some improvement paths are exponentially long. It also implies that the problem of finding a PNE reachable from a given input state is PSPACE-complete.
The class of ordinal potential games is even larger than the class of congestion games: every problem in the class PLS can be presented as an ordinal potential game, where the set of PNE coincides with the set of local optima.

They also study the case of nonatomic congestion games. Computing a PNE in a nonatomic congestion game can be rephrased as a convex optimization problem, and thus can be approximated in wealky-polynomial time (e.g. by the ellipsoid method). Fabrikant, Papadimitriou and Talwar^[34] presented a strongly-polytime algorithm for finding a PNE in the special case of nonatomic network congestion games. In this special case there is a graph G; for each type i there are two nodes s_i and t_i from G; and the set of strategies available to type i is the set of all paths from s_i to t_i. If the utility functions of all players are Lipschitz continuous with constant L, then their algorithm computes an e-approximate PNE in strongly-polynomial time - polynomial in n, L and 1/e.

Ackermann, Roglin and Vocking^[35] prove that, if the strategy space of each player consists of the bases of a matroid over the set of resources, then all best-response sequences converge in polynomial number of steps, and the matroid property is essential for guaranteeing polynomial-time convergence. They also present a simpler technique for hardness proofs; using this technique, they prove that computing a PNE in (asymmetric) network congestion games is PLS-complete for directed and undirected networks, even if all delay functions are linear.

Chien and Sinclair^[36] study an "ε-greedy dynamics" in which, at each step, some player plays a move that decreases its cost by at least a factor of (1+ε). They prove that, in symmetric congestion games, when the delay functions satisfy some technical condition they call "bounded-jump", this ε-greedy dynamics converges to an ε-approximate PNE in a number of steps polynomial in the number of players and 1/ε. This result holds for various update policies and sequences, as long as they satisfy the weak condition that each player has an opportunity to play eventually. The result holds even when a constant number of resources have arbitrary cost functions.

Skopalik and Vocking^[37] prove that, in general congestion games, even computing an ε-approximate PNE, for any polynomial-time computable ε, is PLS-complete. Their reduction also implies that computing an ε-approximate equilibrium reachable from a given initial state is PSPACE-complete. They also present asymmetric congestion with the bounded-jump condition in which, for some states, every ε-greedy sequence might have exponential length.

Caragiannis, Fanelli, Gravin and Skopalik^[38] study general congestion games (possibly asymmetric). They present an algorithm that computes a constant-factor approximation PNE. In particular:

With linear delay functions, the approximation ratio is 2+ε, and the runtime is polynomial in the number of players, the number of resources, and 1/ε.
When delay functions are degree-d polynomials, the approximation ratio is d^O(d).

Their algorithm identifies a short sequence of best-response moves, that leads to an approximate equilibrium. They also show that, for congestion games with more general delay functions (not bounded-degree polynomial), attaining any polynomial approximation of PNE is PLS-complete.

Even-Dar, Kesselman and Mansour^[39] analyze a job scheduling setting where each job is a player. Each job is mapped to a machine. The cost of each job is determined by the load on that machine (all jobs mapped to the same machine have the same cost). Each job in turn moves to a machine that decreases or minimizes its cost (that is, plays a better response or a best response). They study how much steps are required for the system to converge to a Nash equilibrium. They study scheduling on Identical machines, uniform machines and unrelated machines; they also study various policies regarding the sequence of jobs that are allowed to make an improving move. Their upper bound for the most general case (unrelated machines, general real weights) is $\min \left([O({\frac {n}{Km}}+1)]^{Km},m^{n}\right)$ , where m is the number of machines, n the number of jobs, and K the number of different weights. On the other extreme, for the case of identical machines, there are policies that converge in at most n steps, or in O(n²) steps.

Fabrikant, Jaggard and Schapira^[40] study weakly-acyclic games - a generalization of potential games in which, from any starting state, there is a sequence of better-response moves that leads to a PNE, so that natural distributed dynamics cannot enter "inescapable oscillations".

Generalized congestion games

A weighted CG is a congestion game in which each player may have a different weight, and the delay of a resource is the sum of weights of the players using the resource. A player-specific-cost CG is a congestion game in which each player has a different delay function. Both these generalized CGs do not necessarily have a potential, and do not necessarily have a PNE.

Dunkel and Schulz^[41] prove that deciding whether a given network weighted CG has a PNE is strongly NP-hard. This is true even if the flow is splittable (i.e., each player may split his flow among different routes). If the flow is unsplittable, the problem is strongly NP-hard even for a fixed number of players.

Milchtaich^[42] proves that deciding whether a given network CG has a PNE is NP-hard even in the following cases:

Weighted network CG with two players with the same delay functions; all players are allowed to use all paths; all delay functions are nonnegative.
Unweighted network CG with two players with different delay functions; all delay functions are nonnegative.

The proof is by reduction from the directed edge-disjoint paths problem.^[43]

Fotakis, Kontogiannis and Spirakis^[44] present an algorithm that, in any weighted network CG with linear delay functions, finds a PNE in pseudo-polynomial time (polynomial in the number of players n and the sum of players' weights W). Their algorithm is a greedy best-response algorithm: players enter the game in descending order of their weight, and choose a best-response to existing players' strategies.

Panagopoulou and Spirakis^[45] show empirical evidence that the algorithm of Fotakis, Kontogiannis and Spirakis in fact runs in time polynomial in n and log W. They also propose an initial strategy-vector that dramatically speeds this algorithm.

Caragiannis, Fanelli, Gravin and Skopalik^[46] present an algorithm that computes a constant-factor approximation PNE in weighted CGs. In particular:

With linear delay functions, the approximation ratio is ${\frac {3+{\sqrt {5}}}{2}}+O(\epsilon )$ , and the runtime is polynomial in the number of playres, the number of resources, and 1/ε.
When delay functions are degree-d polynomials, the approximation ratio is $d^{2d+o(d)}$ .

To prove their results, they show that, although weighted CGs may not have a potential function, every weighted CG can be approximated by a certain potential game. This lets them show that every weighted CG has a (d!)-approximate PNE. Their algorithm identifies a short sequence of best-response moves, that leads to such an approximate PNE.

Local effect games

Dunkel and Schulz^[41] study an extension of CG in which the cost of a player taking an action depends on the number of players choosing either the same action, or a "related" action. They call it a local effect game (LEG). Their results are:

Deciding whether a bidirectional LEG admits a PNE is NP-complete.
Finding a PNE in a bidirectional LEG with linear structure is PLS-complete.

Submodular games

A finite game is called submodular if (a) the set of feasible joint decisions is a sublattice; (b) the cost function of each player is submodular and has antitone differences. Topkis^[47] proves, using fixed-point arguments, that some submodular games always have a PNE. Two algorithms, corresponding to fictitious play in dynamic games, generate sequences of feasible joint decisions converging monotonically to a PNE.

Concave Games

Concave games (where each player's payoff function is concave in their own strategy) admit efficient computation via convex optimization techniques.^[48]

Remove ads

Correlated equilibria

Correlated equilibria are, in general, computationally easier to find.

Hart and Mas-Collel^[49] present a dynamic called ‘regret-matching’, in which players depart from their current play with probabilities proportional to regret for not having used other strategies previously. These dynamics converge with probability 1 to the set of correlated equilibria.

Papadimitriou and Roughgarden^[50] studied the computational problem of finding a correlated equilibrium (CE). They presented a polytiime algorithm for finding a CE in various multiplayer games, such as graphical games, symmetric (anonymous) games, polymatrix games, congestion games, scheduling games and local effect games.

They also studied the problem of optimizing a linear function of the set of CE. For this problem, they give a polytime algorithm for two cases: symmetric games, and graphical games of bounded treewidth; and prove NP-hardness for the other classes of games.

Repeated games

In a repeated game, the strategy of each player is a finite-state machine. Gilboa^[51] studies the following problem: given a game and the FSM-s of some n-1 players, find a best response FSM for the n-th player. The problem is polytime solvable when n is fixed, but computationally hard when n is part of the input.

Littman and Stone^[52] present a polytime algorithm computing NE for an average-payoff repeated game between two players. Their algorithm relies on the folk theorem. It computes finite-state equilibrium strategies which can be succinctly represented.

Remove ads

Concave games

A concave game is a generalization of a normal-form game in which the space of strategy profiles can be an arbitrary convex set (rather than just a Cartesian product of simplices).

Papadimitriou, Vlatakis-Gkaragkounis and Zampetakis^[55] 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.

Chernov^[56] presents some numeric approaches, related to convex optimization, for computing an equilibrium

Remove ads

Recent developments and modern approaches

Summarize

Perspective

Machine learning methods

Deep learning approaches have emerged as promising techniques for large-scale equilibrium computation. Li, Long and Deng^[57] introduce the Deep Iterative Nash Equilibrium Solver (DINES), that integrates deep learning into iterative algorithms, achieving polynomial time complexity by leveraging query-based access to utility functions rather than requiring full utility matrices.

Reinforcement learning approaches enabled advances in Nash equilibrium computation. Zhang, Wang, Cui, Zhou, Kakade and Du^[58] introduce Preference-Based Multi-Agent Reinforcement Learning (PbMARL), which addresses Nash equilibrium identification from preference-only offline datasets. They show that single-policy coverage—sufficient for single-agent reinforcement learning—is inadequate for multi-agent settings, requiring unilateral dataset coverage conditions.

Generative adversarial networks

Generative Adversarial Networks (GANs) are a tool for training models for image identification, by modeling this as a game between the identifier and an adversary. Heusel, Ramsauer, Unterthiner, Nessler and Hochreiter^[59] introduce a Two Time-Scale Update Rule (TTUR). Using the theory of stochastic approximation, they prove that it converges to a local Nash equilibrium of the GAN training game.

Blockchain systems

Reynouard, Laraki and Gorelkina^[60] apply Nash equilibrium analysis to Blockchain systems through BAR Nash Equilibrium (BARNE) - equilibrium among Byzantine, Altruistic, and Rational agents. This framework addresses the verifier's dilemma in cryptocurrency systems, demonstrating how fines and forced errors can reestablish honest behavior as globally stable equilibria.

Remove ads

Software and practical implementations

Summarize

Perspective

Computational tools

Gambit is the primary comprehensive software package for game theory computations, supporting both extensive-form and strategic-form games.^[61] Version 16.0 includes implementations of the Lemke-Howson algorithm, simplicial subdivision methods, and quantal response equilibrium computation, with both GUI and command-line interfaces plus Python integration.

Specialized tools include Game Theory Explorer (GTE) for web-based small game analysis, and various research implementations focusing on specific algorithms. Integration with modern deep learning frameworks (PyTorch, TensorFlow) enables scalable implementations and GPU acceleration for large-scale problems.

Scalability challenges

Computational scaling presents the primary practical limitation, with exponential growth in complexity as games increase in size. Current approaches handle small-to-medium games (up to roughly 100×100 strategies) through approximation algorithms, while larger games require heuristic methods.

Numerical stability issues arise from degenerate linear systems and floating-point precision limitations in equilibrium computation. Rational arithmetic implementations provide exact computation but at significant computational cost, making ε-equilibria the practical standard for providing robustness to numerical errors.

Remove ads

References

Loading content...

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads

Nash equilibrium computation

Mixed-strategy equilibria

Non-polynomial-time algorithms

Computational hardness

Approximation algorithms

Approximation hardness

Smoothed complexity

Irrationality of outcomes

Two-Player Zero-Sum Games

Anonymous games

Graphical Games

Win-Lose Games

Bounded-rank bimatrix games

Auction Games

Pure-strategy equilibria

Deciding existence

Anonymous games

Graphical games

Potential games and Congestion games

Generalized congestion games

Local effect games

Submodular games

Concave Games

Correlated equilibria

Repeated games

Related computational problems

Concave games

Recent developments and modern approaches

Machine learning methods

Generative adversarial networks

Blockchain systems

Software and practical implementations

Computational tools

Scalability challenges

Further reading

See also

References

Wikiwand - on