We consider Stackelberg pricing games, which are also known as bilevel pricing problems, or combinatorial price-setting problems. This family of problems consists of games between two players: the leader and the follower. There is a market that is partitioned into two parts: the part of the leader and the part of the leader’s competitors. The leader controls one part of the market and can freely set the prices for products. By contrast, the prices of the competitors' products are fixed and known in advance. The follower, then, needs to solve a combinatorial optimization problem in order to satisfy their own demands, while comparing the leader’s offers to the offers of the competitors. Therefore, the leader has to hit the intricate balance of making an attractive offer to the follower, while at the same time ensuring that their own profit is maximized. Pferschy, Nicosia, Pacifici, and Schauer considered the Stackelberg pricing game where the follower solves a knapsack problem. They raised the question whether this problem is complete for the second level of the polynomial hierarchy, i.e., Σ^p₂-complete. The same conjecture was also made by Böhnlein, Schaudt, and Schauer. In this paper, we positively settle this conjecture. Moreover, we show that this result holds actually in a much broader context: The Stackelberg pricing game is Σ^p₂-complete for over 50 underlying problems whose decision versions are NP-complete, including most classics such as TSP, vertex cover, clique, subset sum, etc. This result falls in line of recent meta-theorems about higher complexity in the polynomial hierarchy by Grüne and Wulf.

ABSTRACT We introduce a new bilevel version of the classic shortest path problem and completely characterize its computational complexity with respect to several problem variants. In our problem, the leader and the follower each control a subset of the edges of a graph and together aim at building a path between two given vertices, while each of the two players minimizes the cost of the resulting path according to their own cost function. We investigate both directed and undirected graphs, as well as the special case of directed acyclic graphs. Moreover, we distinguish two versions of the follower's problem: Either they have to complete the edge set selected by the leader such that the joint solution is exactly a path or they have to complete the edge set selected by the leader such that the joint solution is a superset of a path. In general, the bilevel problem turns out to be much harder in the former case: We show that the follower's problem is already NP‐hard here and that the leader's problem is even hard for the second level of the polynomial hierarchy, while both problems are one level easier in the latter case. Interestingly, for directed acyclic graphs, this difference turns around, as we give a polynomial‐time algorithm for the first version of the bilevel problem, but it stays NP‐hard in the second case. Finally, we consider restrictions that render the problem tractable. We prove that, for a constant number of leader's edges, one of our problem variants is actually equivalent to the shortest‐‐cycle problem, which is a known combinatorial problem with partially unresolved complexity status. In particular, our problem admits a polynomial‐time randomized algorithm that can be derandomized if and only if the shortest‐‐cycle problem admits a deterministic polynomial‐time algorithm.

Abstract We consider a bilevel continuous knapsack problem where the leader controls the capacity of the knapsack and the follower chooses an optimal packing according to his own profits, which may differ from those of the leader. To this bilevel problem, we add uncertainty in a natural way, assuming that the leader does not have full knowledge about the follower’s problem. More precisely, adopting the robust optimization approach and assuming that the follower’s profits belong to a given uncertainty set, our aim is to compute a solution that optimizes the worst-case follower’s reaction from the leader’s perspective. By investigating the complexity of this problem with respect to different types of uncertainty sets, we make first steps towards better understanding the combination of bilevel optimization and robust combinatorial optimization. We show that the problem can be solved in polynomial time for both discrete and interval uncertainty, but that the same problem becomes NP-hard when each coefficient can independently assume only a finite number of values. In particular, this demonstrates that replacing uncertainty sets by their convex hulls may change the problem significantly, in contrast to the situation in classical single-level robust optimization. For general polytopal uncertainty, the problem again turns out to be NP-hard, and the same is true for ellipsoidal uncertainty even in the uncorrelated case. All presented hardness results already apply to the evaluation of the leader’s objective function.

Abstract We consider the bilevel minimum spanning tree (BMST) problem where the leader and the follower choose a spanning tree together, according to different objective functions. We show that this problem is NP‐hard, even in the special case where the follower only controls a matching. Moreover, we give some evidence that BMST might even remain hard in case the follower controls only few edges. On the positive side, we present a ‐approximation algorithm for BMST, where is the number of vertices. Moreover, we show that 2‐approximating BMST is fixed‐parameter tractable and that, in case of uniform costs on leader's edges, even solving BMST exactly is fixed‐parameter tractable. We finally consider bottleneck variants of BMST and settle the complexity landscape of all combinations of sum or bottleneck objective functions for the leader and follower, for the optimistic as well as the pessimistic setting.