On the Stackelberg knapsack game

In this work we consider a bilevel knapsack problem, in which one player, the follower, decides on the optimal utilization of a bounded resource. The second player, the leader, can offer incentives, or shared profits, so that the follower chooses options attractive also for the leader. Formally, each of the two players is associated with a subset of the knapsack items. The leader may offer profits for its items as incentives to the follower, before the follower selects a subset of all items in order to maximize its overall profit. The leader receives as pay-off only the profits from those of its items that are included by the follower in the overall knapsack solution. 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 analyze the problem for the case in which the follower solves the resulting knapsack problem to optimality and obtain a number of strong complexity results. Then we invoke a common assumption of the literature, namely that the follower’s computing power is bounded. Under this condition, we study several natural Greedy-type heuristics applied by the follower. The solution structure and complexity of the resulting problems are investigated and solution strategies are derived, in particular an Integer Linear Programming (ILP) model, but also pseudopolynomial and polynomial algorithms, when possible.