Cette page appartient aux archives web de l'EPFL et n'est plus tenue à jour.
This page belongs to EPFL's web archive and is no longer updated.

Lossless abstraction of imperfect information games

Please comment on the following paper before class on April 4. It is available from the course webpage.

 

A. Gilpin and T. Sandholm, 2007, Lossless abstraction of imperfect information games, Journal of the ACM, Vol 54(5).

Posted by Katherine Skirving Larson on Tuesday 27 March 2012 at 14:09
Comments
This paper introduces a transformation that maps large extensive forms of games into smaller ones, without loosing possibility of recalculating original Nash equilibrium from the one found in the smaller extensive forms. These observations are restricted to specific type of games called games with ordered signals. With the assumptions that there is a structure connecting the player actions and the chance action, and that there is a common ordering of signals, authors were able to define ordered game isomorphism together with ordered game isomorphic abstraction transformation, and show that these abstractions are equilibrium preserving. In other words, the Nash equilibrium found in the transformed game can be mapped into the Nash equilibrium of the original game. Moreover, abstraction of the original game contains less nodes, so finding Nash equilibrium is easier. This fact led the authors to construct GameShrink algorithm which finds ordered game isomorphisms and applies the associated ordered game isomorphic abstraction transformations. After the simplified isomorphic game form is obtained, one can search for Nash equilibrium, but now the search process operates on smaller number of nodes. Complexity of GameShrink algorithm is O(n^2) where n is the number of nodes in the signal tree, structure that is usually drastically smaller that the game tree. Authors used Rhode Island Hold'em poker to experimentally verify their implications and show that for this type of game the number of nodes is substantially reduced when abstractions are applied. Regardless of the improvement, one should be aware that the model works only for restricted type of games, and that some abstractions are not exploited, such as transpositions and symmetries.
Posted by Goran Radanovic on Monday 2 April 2012 at 23:37
The problem that has been addressed in this paper is finding equilibrium in large extensive games. The proposed solution is to use an isomorphism transformation to shrink the game to a smaller size and deal with a smaller game. This isomorphism transformation is not changing the Nash equilibrium point. The authors introduce an algorithm called "game shrink" in which they apply the isomorphism transformation exhaustively. Its complexity is O(N*N), where N is the number of nodes in a in signal tree. The paper takes a class of games, which is called games with ordered signals. This class of games refers to sequential games in which agents know about the action of all the other agents in every round, but there are some private signals that the agents might not get them. The method is not applicable for all extensive form games because finding the transformation is possible only for games in which agents can see the actions of others and there is a common ordering signal. The method is improved by introducing an approximation for the transformation by taking into account the coarseness of abstraction. In addition, the method does not take into account the levels of abstractions coming by transpositions or symmetries.
Posted by Laleh Makarem on Tuesday 3 April 2012 at 17:14
The authors start by defining a class of extensive games with imperfect information called games with ordered signals that models the transmission of public and private signals to the players in the game rounds. The definition is showcased by modeling "Rhode Island Hold'em" as such a game. Then, information filters are defined. These are maps that modify the signals given to the players (this has no effect on the game's underlying action space). It is then shown that applying that a certain transformation (called ordered game isomorphic abstraction transformation) on information filters preserves the game's Nash equilibria. This is the crux of designing an algorithm to reduce the game tree size while preserving equilibria. The authors proceed to show that their technique does not generalize to models with some crucial assumptions weakened. Finally a dynamic programming algorithm (GameShrink) is described to apply the transformations to reduce the game tree size (and subsequently calculate NE) and analyzed to run in time O(n^2 alpha(n^2, n)) where n is the game tree size and alpha is the inverse Ackerman function. The paper is concluded by a brief discussion about getting a tradeoff between runtime and the accuracy of the theoretical guarantees on the preservation of the optimal strategies. It is also mentioned briefly that the algorithm presented is used to reduce the game "Rhode Island Hold'em", allowing for a solution for the optimal strategy, setting the record for the largest solved game of that kind.
Posted by Abdallah Alaaeldin Abdelaziz Elguindy on Tuesday 3 April 2012 at 17:25
This paper address the problem with finding an equilibrium of imperfect information games in extensive form. The solution proposed is to abstract the games to their isomorphic structure. A polynomial time algorithm to perform the abstraction is also provided. The solution proposed works only for a game with ordered signal (an example on the cases where the technique does not work also has been provided), however it is claimed that this class of game represents a lot of games with strategic situations out there.

Then, the authors show how to compute the equilibrium. The idea is to compute the equilibrium in the abstracted game which later can be transform into the equilibrium in the original game. This is because the size of the abstracted game is much smaller in most cases, hence computing equilibrium become more feasible: less time, less space, and possibly computing equilibrium for a game that originally was infeasible to compute.

The idea is great. Even though the approach only works for a specific type of game, but this open a lot more possibilities to compute equilibrium (or any kind of analytics task) for large-size games by transforming their representation (inline with the spirit of AGG), compute the equilibrium on the transformed representation and presents the corresponding equilibrium in the original game.
Posted by Tri Kurniawan Wijaya on Wednesday 4 April 2012 at 9:15