Solving a bilevel linear program when the inner decision maker controls few variables

This paper presents an algorithm that always finds an optimum of a Bilevel Linear Program (BLP) problem if one exists. Moreover, if the inner decision maker does not control too many variables the algorithm is efficient. In particular, if the number of variables controlled by the inner decision maker can be considered to be constant, then the algorithm is a polynomial time algorithm. The algorithm is also well suited to parallel implementation.