We consider a bi-level knapsack problem, where two players, the leader and the follower, are each associated with a subset of the items. The leader may offer profits for its items to the follower, before the follower selects a subset of all items in order to utilize a bounded resource in the best possible way, i.e. trying to maximize the overall profit.

The leader receives as pay-off only the profits from those items of its associated subset that were included in the overall solution chosen by the follower. This pay-off is then reduced by the profits offered to the follower. The resulting setting is a Stackelberg strategic game. The leader has to resolve the trade-off between offering high profits as incentives to the follower and offering low profits to gain high pay-offs.

We analyse the problem for the case where the follower solves the resulting knapsack problem to optimality, and obtain a number of strong complexity results. Then we invoke a typical assumption of the literature that the follower’s computation power is bounded. Under this condition, we study three natural Greedy-type heuristics applied by the follower. The solution structures and complexities of the resulting problems are investigated and solution strategies are derived, in particular an ILP model, but also (pseudo)polynomial algorithms, when possible.

Joint work with Gaia Nicosia, Andrea Pacifici and Joachim Schauer