On some numerical experiments on symmetric games

Author: Koba Gelashvili
Keywords: Symmetric Game, Linear Programming
Annotation:

In its 80 years of existence, the field of linear programming becamed the most powerful tool in theoretical computer science for algorithm design. Nowadays, LP effectively solves integer programming, graph theory and other problems and is a widely used technique for designing approximation algorithms for complex tasks. Besides, for many computational problems, proofs of efficient algorithm existence are LP based. Linear programming has several equivalent formulations. We are experimenting with symmetric games. In this case it is possible using penalty functions together with general-purpose unconstrained minimimization solvers like l-bfgs (see [1]) of modified heavy ball (see [2]), yet get algorithm, competetive to open source or comercial LP-solvers. In this approach, the main problem lies in constraints of the sign of variables and we have two-stage solution to this problem. Consider this issue roughly but in some details.

Lecture files:

ზოგიერთი რიცხვითი ექსპერიმენტი სიმეტრიულ თამაშებზე [ka]
On some numerical experiments on symmetric games [en]