On complexity of finding strong-weak solutions in bilevel linear programming

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 alpha-strong-weak model, where parameter alpha E [0, 1] controls the leader's level of conservatism. That is, alpha 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 alpha and 1 - alpha, respectively. In this note we show that for any fixed alpha E (0, 1) the problem of finding an optimal alpha-strong-weak solution remains strongly NP-hard, even when both optimal optimistic and pessimistic solutions for the same BLP are known.(c) 2023 Elsevier B.V. All rights reserved.