Search for Locally Optimal Strategies in a Linear Game Problem with Favorable Situations

A linear game problem for two players is considered. The two players alternately choosetheir strategies from their respective sets. First, player 1 chooses his/her strategy, then player 2,knowing the strategy of player 1, does the same. The set of strategies of player 2 depends on thestrategy of player 1. The goal of player 1 is to choose a strategy to maximize a convex andpiecewise linear function (the minimum function of the strategy of player 2). The goal of player 2is to minimize the linear function. An algorithm is proposed that allows constructing strategies inthis problem, as well as strategies in the dual problem, that satisfy necessary “higher-order”optimality conditions. This algorithm uses a formula for the increment of the objective function inthe dual problem. Theorems that assert the finiteness of the proposed algorithm and itsmodification are proved. An example illustrating the operation of the algorithm is given. Theresults of a numerical experiment on the construction of strategies that satisfy the necessary“higher-order” optimality conditions in problems whose elements were generated by a randomnumber generator are also presented. Based on the results of the numerical experiment, we canconclude that with the proposed algorithm, it is often possible to switch from one locally optimalstrategy of player 1 to another one increasing the objective function.