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 NP-hard. Also, it is 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. (C) 2019 Elsevier B.V. All rights reserved.

Pferschy, U., Nicosia, G., Pacifici, A. (2019). A Stackelberg knapsack game with weight control. THEORETICAL COMPUTER SCIENCE, 799, 149-159 [10.1016/j.tcs.2019.10.007].

A Stackelberg knapsack game with weight control

Pacifici A.
2019-01-01

Abstract

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 NP-hard. Also, it is 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. (C) 2019 Elsevier B.V. All rights reserved.
2019
Pubblicato
Rilevanza internazionale
Articolo
Esperti anonimi
Settore MAT/09 - RICERCA OPERATIVA
Settore ING-INF/05 - SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI
Settore INF/01 - INFORMATICA
English
Knapsack problem; Stackelberg game; Bilevel optimization
https://www.sciencedirect.com/science/article/pii/S0304397519306309
Pferschy, U., Nicosia, G., Pacifici, A. (2019). A Stackelberg knapsack game with weight control. THEORETICAL COMPUTER SCIENCE, 799, 149-159 [10.1016/j.tcs.2019.10.007].
Pferschy, U; Nicosia, G; Pacifici, A
Articolo su rivista
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0304397519306309-main.pdf

solo utenti autorizzati

Descrizione: Articolo pubblicato
Licenza: Copyright dell'editore
Dimensione 377.14 kB
Formato Adobe PDF
377.14 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/242020
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 15
  • ???jsp.display-item.citation.isi??? 11
social impact