The estimate of the convergence rate of the iterative method for solving combinatorial optimization problems of the gaming type

Combinatorial optimization problems of the gaming type in which combinatorial restrictions are imposed on the strategies of the players are an important class of combinatorial optimization problems. For solving this class of problems iterative methods were previously developed such as game-playing and those similar to the method of Brown - Robinson in matrix games . These methods are implemented in software. Numerical experiments conducted on it show that the iterative algorithm is convergent. It’s also proved through theoretical study of convergence. The purpose of this publication is to define the a priori estimate of the convergence rate of the iterative method for solving combinatorial optimization problems of the gaming type with restrictions and permutations on the strategy of one player, as well as to spread this estimate on problems of the same class with other combinatorial restrictions. Using the developed software implementation, the theoretical estimate of the convergence rate of the method was compared to the results obtained experimentally. According to the results, the theoretical estimate of the rate of convergence was confirmed experimentally. In particular, the problems with a square matrix of order $A$ that is equal to 10, it was found that the rate of convergence does not exceed its theoretical estimate at the 5th iteration already. This article examines the proof of convergence, the estimate of the convergence rate of the iterative method for solving combinatorial optimization problems with restrictions and permutations that are imposed on the strategies of one player. Since combinatorial restrictions on strategies of players can be represented as different combinatorial sets, we carried out a synthesis of the estimate of the convergence rate of iterative methods for solving combinatorial optimization problems of the gaming type with different types of combinatorial restrictions.