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. In each of these cases, one can consider computing an exact NE or an epsilon-approximate NE:

  • In an exact NE, no player can gain by deviating;
  • In an epsilon-approximate NE, no player can gain more than epsilon by deviating. The utilities are normalized to [0,1], so this is actually a multiplicative approximation: the gain cannot be more than epsilon times the highest utility.
This article is issued from Wikipedia. The text is available under Creative Commons Attribution-Share Alike 4.0 unless otherwise noted. Additional terms may apply for the media files.