Pricing semi-cooperation in unstable linear–linear bilevel programs via strictly convex tie-breaking and stability contracts

Abstract

Abstract When the follower problem in a bilevel program admits multiple optimal solutions, the leader’s outcome depends on how ties are resolved. This yields the classical optimistic/pessimistic ambiguity and makes the model unstable (ill-posed) from a predictive viewpoint. We study linear–linear bilevel programs without additional upper-level coupling constraints involving the follower variables and propose a stabilization mechanism that preserves the follower’s linear objective as a primary criterion, while resolving ties within the follower optimal set through a strictly convex quadratic rule. This tie-break selects a unique follower reaction and can be anchored to implement any prescribed follower optimum (e.g., a leader-favorable one). We then interpret stabilization as a semi-cooperation contract: in the presence of a (possibly unknown) secondary preference used by the follower to break ties, the leader may need to compensate the follower to accept the leader-chosen tie-break. We define the price of semi-cooperation as the minimal transfer ensuring acceptance, and we derive explicit formulas and robust bounds under preference uncertainty. A computational illustration highlights stabilization and pricing behavior on randomly generated instances.