On the Stackelberg knapsack game

Ulrich Pferschy, Gaia Nicosia, Andrea Pacifici and Joachim Schauer

European Journal of Operational Research, 2021, vol. 291, issue 1, 18-31

Abstract: 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.

Keywords: Complexity theory; Knapsack problem; Stackelberg game; Bilevel optimization (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221720307931
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:291:y:2021:i:1:p:18-31

DOI: 10.1016/j.ejor.2020.09.007

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().