  In bilevel optimization problems, a leader and a follower make their
decisions in a hierarchy, and both decisions influence each other. Usually one
assumes that both players have full knowledge also of the other player's data.
In a more realistic model, uncertainty can be quantified, e.g., using the
robust optimization approach: We assume that the leader does not know the
follower's objective precisely, but only up to some uncertainty set, and her
aim is to optimize the worst case of the corresponding scenarios. Now the
question arises how the complexity of bilevel optimization changes under the
additional complications of this uncertainty.
  We make a further step towards answering this question by examining an easy
bilevel problem. In the Bilevel Selection Problem (BSP), the leader and the
follower each select some items, while a common number of items to select in
total is given, and each player minimizes the total costs of the selected
items, according to different sets of item costs. We show that the BSP can be
solved in polynomial time and then investigate its robust version. If the item
sets controlled by the players are disjoint, it can still be solved in
polynomial time for several types of uncertainty sets. Otherwise, we show that
the Robust BSP is NP-hard and present a 2-approximation algorithm and exact
exponential-time approaches.
  Furthermore, we investigate variants of the BSP where one or both of the two
players take a continuous decision. One variant leads to an example of a
bilevel optimization problem whose optimum value may not be attained. For the
Robust Continuous BSP, where all variables are continuous, we also develop a
new approach for the setting of discrete uncorrelated uncertainty, which gives
a polynomial-time algorithm for the Robust Continuous BSP and a
pseudopolynomial-time algorithm for the Robust Bilevel Continuous Knapsack
Problem.
