RUS  ENG
Full version
JOURNALS // Matematicheskaya Teoriya Igr i Ee Prilozheniya // Archive

Mat. Teor. Igr Pril., 2018 Volume 10, Issue 4, Pages 16–29 (Mi mgta225)

On cooperative game in knapsack problem

Sergei I. Dotsenko

National Taras Shevchenko University of Kyiv, Faculty of Computer Science and Cybernetics

Abstract: A knapsack problem with indivisible items as agents is considered. Each agent has certain weight and utility and wants to be in knapsack. Such situation is considered as cooperative game with transferable utility. A characteristic function for such game generalizes bankruptcy problem characteristic function, however, unlike bankruptcy problem case, it is not convex. Nevertheless, it turns out, that the core of such game is not empty. At the end some particular cases are considered. For such cases the Shapley value, $\tau$-value and nucleolus are found in explicit form.

Keywords: knapsack problem, cooperative game, bankruptcy problem, core, Shapley value, nucleolus, $\tau$-value.

UDC: 519.83
BBK: 22.18


 English version:
Automation and Remote Control, 2019, 80:9, 1734–1744


© Steklov Math. Inst. of RAS, 2024