Computing Optimal Decision Strategies Using the Infinity Computer: The Case of Non-Archimedean Zero-Sum Games

As is well known, zero-sum games are appropriate instruments for the analysis of several issues across areas including economics, international relations and engineering, among others. In particular, the Nash equilibria of any two-player finite zero-sum game in mixed-strategies can be found solving a proper linear programming problem. This chapter investigates and solves non-Archimedean zero-sum games, i.e., games satisfying the zero-sum property allowing the payoffs to be infinite, finite and infinitesimal. Since any zero-sum game is coupled with a linear programming problem, the search for Nash equilibria of non-Archimedean games requires the optimization of a non-Archimedean linear programming problem whose peculiarity is to have the constraints matrix populated by both infinite and infinitesimal numbers. This fact leads to the implementation of a novel non-Archimedean version of the Simplex algorithm called Gross-Matrix-Simplex. Four numerical experiments served as test cases to verify the effectiveness and correctness of the new algorithm. Moreover, these studies helped in stressing the difference between numerical and symbolic calculations: indeed, the solution output by the Gross-Matrix Simplex is just an approximation of the true Nash equilibrium, but it still satisfies some properties which resemble the idea of a non-Archimedean ε-Nash equilibrium. On the contrary, symbolic tools seem to be able to compute the “exact” solution, a fact which happens only on very simple benchmarks and at the price of its intelligibility. In the general case, nevertheless, they stuck as soon as the problem becomes a little more challenging, ending up to be of little help in practice, such as in real time computations. Some possible applications related to such non-Archimedean zero-sum games are also discussed.