New algorithm for checking Pareto optimality in bimatrix games

AbstractBimatrix games have had theoretical importance and important applications since the very beginning of game theory to date. Pareto optimal strategy vectors represent a reasonable and frequently applied solution concept (basically in the cooperative approach). Particularly, it often arises whether a non-cooperative solution can be improved in cooperative sense, i.e. it is Pareto optimal or not. However, in concrete cases it may be hard to determine the Pareto optimal strategy vectors or at least check the Pareto optimality of a given strategy vector. In the present paper, the Pareto optimality of the strategy pairs in general n × m ($$n = 2,3, \ldots$$ n = 2 , 3 , … ; $$m = 2,3, \ldots$$ m = 2 , 3 , … ) bimatrix games is studied. First of all an elementary proof is provided for a theorem, which makes the proposed Pareto optimality checking algorithm simpler. Then a nonlinear transform is proposed, which makes the algorithm even more convenient in the important case of 2 × 2 bimatrix games (and for certain other cases). Two numerical examples present the practical applicability of the checking algorithm. The problem of 2 × 2 bimatrix games can be solved even by hand. For larger games, numerous computational tools are available in the practice to apply the checking algorithm in exact or at least approximate way.