Optimality conditions for a bilevel matroid problem

In bilevel programming there are two decision makers, the leader and the follower, who act in a hierarchy. In this paper we deal with a weighted matroid problem where each of the decision makers has a different set of weights. The independent set of the matroid that is chosen by the follower determines the payoff to both the leader and the follower according to their different weights. The leader can increase his payoff by changing the weights of the follower, thus influencing the follower’s decision, but he has to pay a penalty for this. We want to find an optimum strategy for the leader. This is a bilevel programming problem with continuous variables in the upper level and a parametric weighted matroid problem in the lower level. We analyze the structure of the lower level problem. We use this structure to develop local optimality criteria for the bilevel problem that can be verified in polynomial time.