Content deleted Content added
Line 12:
In case where each player's utility function depends only on one other player, the maximal degree of the graph is 1, and the game can be described as <math>n</math> functions (tables) of size <math>m^{2}</math>. So, the total size of the input will be <math>nm^{2}</math>.
==Nash
Finding Nash equilibrium in a game takes exponential time in the size of the representation. If the graphical representation of the game is a tree, we can find the equilibrium in polynomial time. In the general case, where the maximal degree of a node is 3 or more, the problem is [[NP-complete]].
| |||