3
$\begingroup$

Computing equilibria in games and the complexity thereof is imho still quite a young field in which a lot of work still is to be done (especially the former).

GAMUT (2004) is a very nice "suite of game generators designated for testing game-theoretic algorithms".

An example (2005) of a complexity result is that in normal form games, deciding if there exists a pure Nash equilibrium is a NP-complete problem. There are other types of equilibria each with their complexity results in different types of games.

An example (2014) of an (exact) method that solves said decision problem is a mixed 0-1 linear program.

So we have:

  • Problem(s) that are considered hard.
  • Instance generators (GAMUT)
  • Algorithms to solve said problems.

By hard I mean (most likely) not solveable in polynomial time.

Yet, to the best of my knowledge, no benchmarks have been created for any problem in Game Theory. I think, however, benchmarks could prove very interesting to compare algorithm results in future research.

How would one go about creating benchmarks? What is a good benchmark and what are good problem instances to benchmark? If someone decides to create a benchmark for some problem in some field, how is this process approached?

Examples of benchmarks: Graph coloring, Steiner Trees, equilibria in games (coming soon?), ...

$\endgroup$
7
  • $\begingroup$ @Auberon: Are you aware that it is known to be PPAD-complete to compute a Nash equilibrium of a bimatrix game and PSPACE-hard to compute any of the solutions found by the Lemke-Howson algorithm? In terms of hard problem instances, these are not easy to come by (we simply don't have good generic hard classes of games), but for some more recent experimental results since GAMUT, see our SEA 2015 or AAMAS 2016 papers. $\endgroup$ Commented Mar 29, 2016 at 21:34
  • $\begingroup$ @Auberon: cont., Beyond the results in experimental papers like above, I don't know any standalone benchmarks; if you are interested to create some and would like to discuss feel free to email me.. $\endgroup$ Commented Mar 29, 2016 at 21:42
  • $\begingroup$ @RahulSavani Thank you for the references, I will be sure (!) to read them through. I'm aware of the complexities of equilibria in games and algorithms. I'm also aware of complexities when games grow to n-player games e.g. The NP-complete problem I mentioned in my post or optimizing over correlated equilibria. These last two are ones I'm particularly interested in as I'm focussing my bachelor's dissertation on them. $\endgroup$
    – Auberon
    Commented Mar 29, 2016 at 21:58
  • $\begingroup$ @Auberon: Actually there are NP-completeness for a bunch of decision problems associated with TWO player games (see Gilboa and Zemel 1989 and Conitzer and Sandholm 2005). The AAMAS 2006 paper is about n-player polymatrix games. The problem with general $n$-player games is that the input size itself is exponential (even a two action $n$-player game requires $n.2^n$ payoffs! As well as polymatrix games you may want to look at other graphical games, and anonymous games. $\endgroup$ Commented Mar 29, 2016 at 22:13
  • $\begingroup$ @Auberon: cont., BTW, while a correlated equilibrium can be computed efficiently via an easy reduction to LP when a game is given in strategic-form, it is a non-trivial result that it can also be done efficiently when the game is given succinctly (see Papadimitriou and Roughgarden 2008). $\endgroup$ Commented Mar 29, 2016 at 22:16

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.