An explicit solution to the multi-level programming problem

The multi-level programming problem is defined as an n-person nonzero-sum game with perfect information in which the players move sequentially. The bi-level linear case is addressed in detail. Solutions are obtained by recasting this problem as a standard mathematical probram and appealing to its implicitly separable structure. The reformulated optimization problem is linear save for a complementarity constraint of the form 〈u, g〉 = 0. This constraint is decomposed in a manner that permits us to achieve separability with very little cost in dimensionality. A general branch and bound algorithm is then applied to obtain solutions. Unlike the conventional mathematical program though, the multi-level program may fail to have a solution even when the decision variables are defined over a compact set. An auxiliary optimization problem is employed to detect such failure. Finally, the general max-min problem is discussed within the bi-level programming framework. Examples are given for a variety of related problems.