Efficient Decompositions of Games: Computing Nash equilibria in bimatrix games is one of the core problems in Algorithmic Game Theory. As it is known to be PPAD-complete [1], it is considered unlikely that polynomial-time algorithms exist. Practical experience also hints that many larger games take prohibitively long to solve (e.g., see here). In [2], for an unrelated purpose products of games were defined. It is easy to see that factoring of games can be done in polynomial time, so it is conceivable that such decompositions can be utilized to reduce (average) computation time. The aim of the project is to implement decompositions of products and sums (another type of operation) of games in strategic form, and to evaluate the usefulness of such decompositions in praxis. As benchmark, and to solve the reduced games, one might use Gambit or similar tools. Potentially, also some theoretical analysis of the decompositions can be included in the project, e.g. to calculate the fraction of games permitting decompositions into smaller parts. Prior knowledge of Algorithmic Game Theory is not required, the needed concepts can easily be picked up in a few days. The first two chapters of [3] would more than suffice. If Gambit is chosen as a tool, then the programming language needs to admit interaction with C++, but otherwise there are no restrictions on the language used (besides the obvious, e.g. no whitespace). This project has been completed by Xiang Jiang. |
[1] C. Papadimitriou: The Complexity of Finding Nash Equilibria, in [3].
[2] Arno Pauly: How Discontinuous is Computing Nash Equilibria? (Extended Abstract); in A. Bauer et al., "6th Int'l Conf. on Computability and Complexity in Analysis", 2009. [3] N. Nisan et. al.: Algorithmic Game Theory, Cambridge University Press, 2007. |