×

A Stackelberg knapsack game with weight control. (English) Zbl 1443.91085

Summary: We address a bilevel knapsack problem where a set of items with weights and profits is given. One player, the leader, may control the weights of a given subset of items. The second player, the follower, outputs the actual solution of the resulting knapsack instance, maximizing the overall profit. The leader receives as payoff the weights from those items of its associated subset that were included in the solution chosen by the follower.
We analyze the leader’s payoff maximization problem for three different solution strategies of the follower and discuss the complexity of the corresponding problems. In particular, we show that, when the follower adopts a greedy strategy, setting the optimal weight values is \(\mathcal{NP}\)-hard. Also, it is \(\mathcal{NP}\)-hard to provide a solution within a constant factor of the best possible solution. However, a MIP-formulation can be given. Moreover, the truncated greedy strategy allows an easy answer for the revision of weights. For the additional case, in which the follower faces a continuous (linear relaxation) version of the above problems, the optimal strategies can be fully characterized and computed in polynomial time.

MSC:

91A65 Hierarchical games (including Stackelberg games)
91A05 2-person games
91A68 Algorithmic game theory and complexity

Software:

Knapsack
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Akçay, Y.; Li, H.; Xu, S. H., Greedy algorithm for the general multidimensional knapsack problem, Ann. Oper. Res., 150, 17-29 (2007) · Zbl 1144.90466
[2] Ben-Ayed, O., Bilevel linear programming, Comput. Oper. Res., 20, 5, 485-501 (1993) · Zbl 0783.90068
[3] Briest, P.; Hoefer, M.; Gualà, L.; Ventre, C., On Stackelberg pricing with computationally bounded consumers, Networks, 60, 1, 31-44 (2012) · Zbl 1251.91032
[4] Briest, P.; Hoefer, M.; Krysta, P., Stackelberg network pricing games, Algorithmica, 62, 733-753 (2012) · Zbl 1237.91012
[5] Caprara, A.; Carvalho, M.; Lodi, A.; Woeginger, G. J., A study on the computational complexity of the bilevel knapsack problem, SIAM J. Optim., 24, 2, 823-838 (2014) · Zbl 1297.90134
[6] Caprara, A.; Carvalho, M.; Lodi, A.; Woeginger, G. J., Bilevel knapsack with interdiction constraints, INFORMS J. Comput., 28, 2, 319-333 (2016) · Zbl 1343.90075
[7] Chen, L.; Zhang, G., Approximation algorithms for a bi-level knapsack problem, Theor. Comput. Sci., 497, 1-12 (2013) · Zbl 1351.90139
[8] Darmann, A.; Nicosia, G.; Pferschy, U.; Schauer, J., The subset sum game, Eur. J. Oper. Res., 233, 3, 539-549 (2014) · Zbl 1339.91069
[9] Della Croce, F.; Scatamacchia, R., Lower bounds and a new exact approach for the bilevel knapsack with interdiction constraints, (Proceedings of IPCO 2019. Proceedings of IPCO 2019, Lecture Notes in Computer Science, vol. 11480 (2019), Springer), 155-167 · Zbl 1436.90119
[10] Ensthaler, L.; Giebe, T., Bayesian optimal knapsack procurement, Eur. J. Oper. Res., 234, 3, 774-779 (2014) · Zbl 1304.91048
[11] Hansen, P.; Jaumard, B.; Savard, G., New branch-and-bound rules for linear bilevel programming, SIAM J. Sci. Stat. Comput., 5, 13, 1194-1217 (1992) · Zbl 0760.65063
[12] Jeroslow, R. G., The polynomial hierarchy and a simple model for competitive analysis, Math. Program., 32, 2, 146-164 (1985) · Zbl 0588.90053
[13] Julstrom, B. A., Greedy, genetic, and greedy genetic algorithms for the quadratic knapsack problem, (Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation. Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation, GECCO ’05 (2005)), 607-614
[14] Kellerer, H.; Pferschy, U.; Pisinger, D., Knapsack Problems (2004), Springer · Zbl 1103.90003
[15] Labbé, M.; Violin, A., Bilevel programming and price setting problems, 4OR, 11, 1, 1-30 (2013) · Zbl 1259.90112
[16] Marini, C.; Nicosia, G.; Pacifici, A.; Pferschy, U., Strategies in competing subset selection, Ann. Oper. Res., 207, 1, 181-200 (2013) · Zbl 1272.91017
[17] Nicosia, G.; Pacifici, A.; Pferschy, U., Competitive subset selection with two agents, Discrete Appl. Math., 159, 16, 1865-1877 (2011) · Zbl 1227.90042
[18] Nicosia, G.; Pacifici, A.; Pferschy, U., Price of fairness for allocating a bounded resource, Eur. J. Oper. Res., 257, 933-943 (2017) · Zbl 1394.91252
[19] Pferschy, U.; Nicosia, G.; Pacifici, A., On a Stackelberg subset sum game, Electron. Notes Discrete Math., 69, 133-140 (2018), extended version available as
[20] U. Pferschy, G. Nicosia, A. Pacifici, J. Schauer, On the Stackelberg knapsack game, submitted for publication, 2019. · Zbl 1443.91085
[21] Pisinger, D., Core problems in knapsack algorithms, Oper. Res., 47, 4, 570-575 (1999), code available at · Zbl 0979.90091
[22] Qiu, X.; Kern, W., Improved approximation algorithms for a bilevel knapsack problem, Theor. Comput. Sci., 595, 120-129 (2015) · Zbl 1328.68306
[23] von Stackelberg, H., Marktform und Gleichgewicht (1934), Verlag von Julius Springer · Zbl 1405.91003
[24] Wang, Z.; Xing, W.; Fang, S.-C., Two-group knapsack game, Theor. Comput. Sci., 411, 7-9, 1094-1103 (2010) · Zbl 1225.91026
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.