A linear max—min problem

This work considers a two person max—min problem in which the maximizing player moves first and the minimizing player has perfect information of the outcome of this move.

Abstract

We consider a two person max—min problem in which the maximizing player moves first and the minimizing player has perfect information of the outcome of this move. The move of the maximizing player influences not only the objective function but also the constraints of the minimizing player. The joint constraints as well as the objective function are assumed to be linear. For this problem it is shown that the familiar inequality min max ⩾ max min is reversed due to the influence of the joint constraints. The problem is characterized as a nonconvex program and a method of solution based on the branch and bound philosophy is given. A small example is presented to illlustrate the algorithm.