  We study a bilevel optimization problem which is a zero-sum Stackelberg game.
In this problem, there are two players, a leader and a follower, who pick items
from a common set. Both the leader and the follower have their own
(multi-dimensional) budgets, respectively. Each item is associated with a
profit, which is the same to the leader and the follower, and will consume the
leader's (follower's) budget if it is selected by the leader (follower). The
leader and the follower will select items in a sequential way: First, the
leader selects items within the leader's budget. Then the follower selects
items from the remaining items within the follower's budget. The goal of the
leader is to minimize the maximum profit that the follower can obtain. Let
$s_A$ and $s_B$ be the dimension of the leader's and follower's budget,
respectively. A special case of our problem is the bilevel knapsack problem
studied by Caprara et al. [SIAM Journal on Optimization, 2014], where
$s_A=s_B=1$. We consider the general problem and obtain an
$(s_B+\epsilon)$-approximation algorithm when $s_A$ and $s_B$ are both
constant. In particular, if $s_B=1$, our algorithm implies a PTAS for the
bilevel knapsack problem, which is the first O(1)-approximation algorithm. We
also complement our result by showing that there does not exist any
$(4/3-\epsilon)$-approximation algorithm even if $s_A=1$ and $s_B=2$. We also
consider a variant of our problem with resource augmentation when $s_A$ and
$s_B$ are both part of the input. We obtain an O(1)-approximation algorithm
with O(1)-resource augmentation, that is, we give an algorithm that returns a
solution which exceeds the given leader's budget by O(1) times, and the
objective value achieved by the solution is O(1) times the optimal objective
value that respects the leader's budget.
