Abstract
We consider bilevel linear programs (BLPs) that model hierarchical decision-making settings with two independent decision-makers (DMs), referred to as a leader (an upper-level DM) and a follower (a lower-level DM). BLPs are strongly NP-hard. In general, the follower's rational reaction (i.e., a set that contains optimal solutions of the lower-level problem for a given leader's decision) is not a singleton. If we assume that, for a given leader's decision, the follower always selects a solution from the rational reaction set that is most (least) favorable to the leader, then we obtain the optimistic (pessimistic) model. It is known that the optimistic (pessimistic) model remains NP-hard even if an optimal pessimistic (optimistic) solution of the same BLP is known. One interesting generalization of these two approaches studied in the related literature is to consider the so-called α-strong-weak model, where parameter controls the leader's level of conservatism. That is, α provides the probability of the follower's “cooperation” in a sense that, the lower-level's rational decisions that are most and least favorable to the leader are picked with probabilities α and , respectively. In this note we show that for any fixed the problem of finding an optimal α-strong-weak solution remains strongly NP-hard, even when both optimal optimistic and pessimistic solutions for the same BLP are known.
Lagos, Tomás