Message Boards Message Boards

GROUPS:

Game theory: how Wolfram Language compares?

Posted 2 years ago
4994 Views
|
3 Replies
|
7 Total Likes
|

Does anyone know recent comparisons of software packages such as Mathematica (wolfram.com), GAMS (gams.com), Matlab, etc. for solving e.g. game theory problems? Alternatively, subjective impressions/opinions? The objective is to determine Nash equilibria and various optima for each player. One relevant criterion is speed of execution (minutes, hours, days). A second criterion is ease of programming. Game theoretic problems are so multifarious, despite many common features, that no standardized software seem to have emerged. If that’s correct, each problem has to be programmed individually. Each of multiple players has multiple available strategies and seeks optimal (equilibrium) strategies to maximize his expected utility given that each other player performs the same activity for his strategies. In equilibrium no player has an incentive to deviate unilaterally from his optimal strategies. Such problems usually involve nested DO-loops and IF-tests. One DO-loop is needed for each strategy for each player. One starts with some chosen combination of strategies for each player and determines each player’s expected utility. Next one alters the value for one strategy for one player from some lower limit to some upper limit and determines which value gives the highest expected utility for that player. Thereafter one proceeds to the second strategy for the same player or to the first strategy for player number 2 and chooses the value that gives the highest expected utility for that player. The procedure runs until no further increase in expected utility for each player is possible, or, in some cases, an equilibrium cannot be found and the procedure runs forever. One possible conceptualization of the problem is that each player solves an optimization problem considering the other players as constraints. Thereafter one proceeds to player number 2 and solves that player’s optimization problem considering the other players as constraints. The procedure continues until all players have optimized, and is then repeated since each player’s optimization may lead the other players to prefer to optimize differently. Of course challenges exist, such as multiple equilibria. A common solution method in game theory is backward induction. If the game theoretic problem involves the time dimension, an additional DO-loop is needed. Sometimes bounded rationality can be assumed so that one seeks the optimum for the current or next or next few time periods. Another relevant criterion is illustration e.g. in graphics of the research output. I have used Mathematica since 1995, currently Mathematica 11, and am satisfied with the illustrative capabilities. Possibly, research output from GAMS may sometimes have to be transferred to other software packages such as e.g. Matlab and Excel e.g. if certain requirements are needed for illustrating the output e.g. graphically, but I am uncertain about that. If GAMS compares favorably with Mathematica and/or Matlab e.g. for speed of execution and ease of programming, the illustrative quality may be assigned lower weight. This question has also been posed on Researchgate by me with five replies so far.

3 Replies

One of the good things about Mathematica is that old code still works. There's a package written in 1991 by John Dickaut that still works in Version 11 to find (all) Nash equilibria in 2 x 2 games. I've attached a copy to this post.

Here's an illustration of the package in use finding all the Nash equilbria of a 5 x 5 2-player game. The game is expressed in strategic (normal) form as a 5x5x2 matrix.

    game={{{10, 14}, {0, 12}, {12, 7}, {16, 10}, {11, 11}}, {{1, 7}, {14, 
       19}, {5, 19}, {13, 15}, {13, 12}}, {{10, 18}, {7, 3}, {17, 
       16}, {18, 20}, {9, 6}}, {{6, 3}, {20, 19}, {20, 13}, {17, 15}, {13,
        4}}, {{18, 12}, {10, 10}, {20, 12}, {10, 11}, {6, 8}}};
Quiet[Nash[game]]

Now, I am confident there have been a few developments in efficiently finding Nash Equilibria, particularly in larger or n-player games since 1991, but if you wanted to get started, you do not have to reinvent the wheel. Also, if your skills extend to RLink, there is an R package GNE that you can access via Mathematica that appears to be a lot more modern.

Here's the link to the Nash package: Microeconomic Analysis

There's a book edited by Hal Varian Economic and Financial Modeling with Mathematica that discusses the package.

Also FWIW, I did some work about 15 years ago in "Foggy Game Theory" in which the assumption that a player can always "see" all of its moves is relaxed and the visible strategies available to a player depend on the current state of the game.

Attachments:

There are also examples in Game Theory section of Demonstrations. I know at least of a few folks here, such as @Valeriu Ungureanu and @Michael Stern who are familiar with the field and research, - perhaps they will comment.

Unfortunately, it's look like the situation is still the same described by Kjell, I don't know software good enough for determining game solutions, inclusive Nash equilibrium solutions. I have tried to use some years ago GAMS, but it was good for antagonistic games, not for polymatrix ones.

The package written in 1991 by John Dickaut still works with some warnings. It doesn't specify all equilibra, but only the ones I named reference equilibria. In the example presented there, it gives all three solutions.

enter image description here

But, what must the user know in the following example, obtained from precedent one by modifying a single element?

enter image description here

The set of all equilibria consists of one distinct (isolated) point and one interval. Such type of situations appears in more complicated form when the the number of strategies is greater... For example, for three person 2x2x2 gamed the set of all equilibria may consists of surfaces defined by nonlinear forms.

To generate pictures above, I have used the demonstration "Nash Equilibrium Sets in Dyadic Bimatrix Mixed-Strategy Games".

The problem of computing a Nash equilibrium in two-player game is PPAD-complete

(PPAD is an abbreviation for Polynomial Parity Argument for Directed graphs, see:

Papadimitriou, C. H., On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence, Journal of Computer and System Sciences, No. 48(3), 1994, pp. 498–-532.

Daskalakis, C., Goldberg, P.W., and Papadimitriou, C.H. The complexity of computing a Nash equilibrium, Communications of the ACM, 52(2), 2009, pp. 89–-97.).

Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract