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. Excel e.g. if certain requirements are needed for illustrating the output e.g. graphically, but I am uncertain about that. If GAMS (gams.com) 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.
I think computational performance for such problems may have more to do with how the problem is coded rather than the underlying engine. I think MATLAB is supposed to have a relatively faster engine for linear algebra and transform computations, but this won't necessarily translate into faster calculation of optimization problems. It would come down to performance of the specific optimization routine and the quality of the guesses supplied.
Frequently, you have to write the fitness (or error) function yourself, and this is the function that gets evaluated the most. So optimizing this function's performance is where you get payoffs in speed, for example by using pre-computed values or recycling chunks of computed data.
I'm sorry my answer is "well it depends," but that's kind of my experience with heavy computation problems.
Hi,
I searched a lot about game theory and mathematical modelling before. I realized that the best performance for jump library in the Julia software. Julia is so fast and Jump library is so flexible for this kind of analysis. And, it is so easy to use for complex analysis. Have a great one.
https://jump.readthedocs.io/en/latest/
https://www.youtube.com/watch?v=UmMn-N5w-lI
with regard to Salih's reply -- it seems JuMP is a front end programing language that can call many solvers (that is cool) .... but the question is about the solvers.
my reply to that would be I'd be surprised if the problem is actually so computationally intensive that you have to seek better solvers to get it done; I would much rather spend the time in the finesse of the formulation
could you construct your problem from basic MATLAB operations?
Kjell,
Maybe this is too down to earth for your purposes. But have you tried Gambit?
http://gambit.sourceforge.net
Best
Christoph
Kjell,
I recommend Gambit too and some works below to start your search.
http://banach.lse.ac.uk/
Article Computing Equilibria for Two-Person Games
Article Algorithmic Game Theory20081Edited by Noam Nisan, Tim Roughg...
1. Getting this issue settled one way or the other is not so easy. Boris L. Glebov makes a good point that one often has to write the functions etc. oneself, so “well it depends,” except for very simple cases. Salih Tutun’s suggestion of using the fast Julia software is interesting. Morton E. O'Kelly makes a good point that getting better solvers may not always be the best approach, and that one may instead spend time “in the finesse of the formulation.” Well, that brings us back to Boris L. Glebov’s suggestion “well it depends.” Aldo Dall'Osso prefers Mathematica, which perhaps one may as well prefer if one has to write the functions oneself and is trained in Mathematica. Christoph Engel’s and Vsevolod Korepanov’s suggestion of Gambit is of course relevant.
2. Re Mathematica, a Nash package does exist, http://library.wolfram.com/infocenter/MathSource/551 , discussed in this 1993 book edited by Hal Varian http://www.springer.com/us/book/9781475722833 . Mathematica also provides some game theory demonstrations, http://demonstrations.wolfram.com/topic.html?topic=Game%20Theory . One possibly good thing about Mathematica is that old code still works. Mathematica users are offered a package written in 1991 by John Dickaut that still works in Version 11 to find (all) Nash equilibria in 2 x 2 games. Also, if one’s skills extend to RLink, there is an R package GNE that one can access via Mathematica that appears to be a lot more modern.
3. Here’s an approach for solving in GAMS. First, assume an algebraic description of a complementarity problem (CP) whose solutions correspond to the solutions of a game. This is typically the case. For example, there is a well-known formulation of a two-person bimatrix game as a linear complementarity problem (LCP). Similar CPs exist for many other Nash game examples. This is significant because GAMS solves CPs via the PATH solver for CP. With this approach, no need exists to program a solution algorithm (with all its messy details) oneself. When the algebra for the CP has been written, GAMS simply hands this off to PATH for solution. Other MCP solvers also exist in GAMS. Using the MCP (mixed complementarity problem) model type, one can specify the model once and have access to multiple solvers, not just PATH. One typically starts with a trivial model/data size that can be inserted directly into GAMS, but soon one wants to bring in data from other sources. A typical GAMS application involves a model that is separate from the input data, so one can use data utilities we provide to move data between GAMS and other sources (e.g. Matlab, Excel, databases, R, .Net, Java, C++, Python, etc.). This way one can develop a model independently from the data. The same holds for model debugging: often model flaws are exposed during model testing or use, not development. With the right setup, any unusual results can be debugged easily because the data leading to the problematic instance is saved for just such a need. Finally, on the output side (illustrating, etc.): GAMS does provide some charting facilities within the GAMS IDE, but users often have a preferred environment for visualizing results and perhaps some investment in time and capital there too. The GAMS approach is to make it easy to export GAMS results to such environments, using the same data tools mentioned above. So if one has an existing Matlab setup for defining, solving, and illustrating the solution to a Nash problem, an interesting experiment could be to define and solve the same problem in GAMS, then add to that export to Matlab for visualization, then finally add a connection for the input data between Matlab and GAMS. Possibly the divide-and-conquer approach is viable. GAMS may not have an example that does exactly what is described above in its entirety, but one does have independent examples that 1) solve Nash models in GAMS, 2) export results to Matlab, and 3) bring data from Matlab to GAMS. I have heard one user suggesting that GAMS is good for antagonistic games, but not for polymatrix games, which may or may not be correct.
4. If someone has further viewpoints or insights, please let me know.
Can anyone please provide any example of formulating a Nash problem as MCP problem?
- Badges
- Science topic
- Similar topics
- Journal Impact Factor