Non-Archimedean zero-sum games
Autor: | Marco Cococcioni, Lorenzo Fiaschi, Luca Lambertini |
---|---|
Přispěvatelé: | Cococcioni M., Fiaschi L., Lambertini L. |
Rok vydání: | 2021 |
Předmět: |
Computer Science::Computer Science and Game Theory
Correctness Linear programming Infinitesimal media_common.quotation_subject Zero-Sum Matrix Games Infinity Computer 010103 numerical & computational mathematics 01 natural sciences symbols.namesake Game Theory Simplex algorithm Applied mathematics Linear Programming 0101 mathematics Representation (mathematics) Mathematics media_common Applied Mathematics TheoryofComputation_GENERAL Infinity 010101 applied mathematics Computational Mathematics Zero-sum game Game Theory Zero-Sum Matrix Games Linear Programming Non-Archimedean Analysis Grossone Methodology Infinity Computer Nash equilibrium Non-Archimedean analysi symbols Non-Archimedean Analysis Grossone Methodology |
Zdroj: | Journal of Computational and Applied Mathematics. 393:113483 |
ISSN: | 0377-0427 |
DOI: | 10.1016/j.cam.2021.113483 |
Popis: | Zero-sum games are a well known class of game theoretic models, which are widely used in several economics and engineering applications. It is known that any two-player finite zero-sum game in mixed-strategies can be solved, i.e., one of its Nash equilibria can be found solving a linear programming problem associated to it. The idea of this work is to propose and solve zero-sum games which involve infinite and infinitesimal payoffs too, that is non-Archimedean payoffs. Since to find a Nash equilibrium a non-Archimedean linear programming problem needs to be solved, we implement and extend a more powerful version of an already existing non-Archimedean Simplex algorithm, namely the Gross-Simplex one. In particular, the new algorithm, called Gross-Matrix-Simplex, is able to handle the constraint matrix A when it is made of non-Archimedean quantities. To test the correctness and the efficiency of the Gross-Matrix-Simplex algorithm, we provide four numerical experiments, which have been run on an Infinity Computer simulator. Furthermore, we stressed the difference between numerical and symbolic calculations, characterizing the solutions that an algorithm is able to output running over a finite-precision machine. In particular, we showed that the numerical solutions are particular approximations of the true Nash equilibrium which satisfy some properties which make them interestingly close to the concept of an non-Archimedean e -Nash equilibrium. Finally, we also discuss several examples based on well known models related to economics, politics and engineering, where a non-Archimedean zero-sum model appears to be a reasonable, powerful and flexible representation. |
Databáze: | OpenAIRE |
Externí odkaz: |