Cooperative and axiomatic approaches to the knapsack allocation problem

Arribillaga, Pablo and Bergantiños, Gustavo (2019): Cooperative and axiomatic approaches to the knapsack allocation problem.

Abstract

In the knapsack problem a group of agents want to fill a knapsack with several goods. Two issues should be considered. Firstly, to decide optimally the goods selected for the knapsack, which has been studied in many papers. Secondly, to divide the total revenue among the agents, which has been studied in few papers (including this one). We assign to each knapsack problem several cooperative games. For some of them we prove that the core is non-empty. Later, we follow the axiomatic approach. We propose two rules. The first one is based on the optimal solution of the knapsack problem. The second one is the Shapley value of the so called optimistic game. We offer axiomatic characterizations of both rules.

• Item Type: MPRA Paper
• Language: English
• Keywords: Knapsack problem; axiomatic; cooperative games
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C71 - Cooperative Games

References

G. Bergantiños, S. Lorenzo-Freire (2008). A characterization of optimistic weighted Shapley rules in minimum cost spanning tree problems. Economic Theory 35: 523-538.

G. Bergantiños, J.J. Vidal-Puga (2007a). A fair rule in minimum cost spanning tree problems. Journal of Economic Theory 137: 326-352.

G. Bergantiños, J.J. Vidal-Puga (2007b). The optimistic TU game in minimum cost spanning tree problems. International Journal of Game Theory 36: 223-239.

C.G. Bird (1976). On cost allocation for a spanning tree: A game theoretic approach. Networks 6: 335-350.

A. Bogomolnaia, H. Moulin (2010). Sharing a minimal cost spanning tree: Beyond the Folk solution. Games and Economic Behavior 69: 238-248.

P. Borm, H. Hamers, R. Hendrickx (2001). Operations research games: A survey. TOP 9: 139-216.

K.M. Bretthauer, B. Shetty (2002). The nonlinear knapsack problem -- algorithms and applications. European Journal of Operational Research 138: 459-472

A. Darmann, C. Klamler (2014). Knapsack cost sharing. Review of Economic Design 18: 219-241.

B. Dutta, A. Kar (2004). Cost monotonicity, consistency and minimum cost spanning tree games. Games and Economic Behavior 48: 223-248.

J.L. Hougaard, H. Moulin (2018). Sharing the cost of risky projects. Economic Theory 65 (3): 663-679.

A. Kar (2002). Axiomatization of the Shapley value on minimum cost spanning tree games. Games and Economic Behavior 38: 265-277.

H. Kellerer, U. Pferschy, D. Pisinger (2004) Knapsack problems. Springer, Berlin.

S. Martello, D. Psinger, P. Toth (2000). New trends in exact algorithms for the 0-1 knapsack problem. European Journal of Operational Research 123: 325-332.

J.D. Moreno-Ternero, A. Villar (2004). The Talmud rule and the securement of agents' awards. Mathematical Social Sciences 47: 245-257.

R. Myerson (1980). Conference structures and fair allocation rules. International Journal of Game Theory 9: 169-182.

J. Nash (1950). The Bargaining Problem. Econometrica 18: 155--162.

B. O'Neill (1982). A problem of rights arbitration from the Talmud. Mathematical Social Sciences 2: 345-371.

D. Pisinger, P. Toth (1998). Knapsack problems. Handbook of Combinatorial Optimization (Volume 1) Springer pp. 299-428.

L.S. Shapley (1953) A value for n-person games. In: Kuhn HW, Tucker AW (eds.) Contributions to the Theory of Games II. Princeton University Press, Princeton NJ, pp. 307-317.

W. Thomson (2003). Axiomatic and game-theoretic analysis of bankruptcy and taxation problems: a survey. Mathematical Social Sciences 45: 249-297.

W. Thomson (2015). Axiomatic and game-theoretic analysis of bankruptcy and taxation problems: An update. Mathematical Social Sciences 74: 41-59.

S. Tijs, R. Branzei, S. Moretti, H. Norde (2006). Obligation rules for minimum cost spanning tree situations and their monotonicity properties. European Journal of Operational Research 175: 121-134.

C. Trudeau (2012). A new stable and more responsive solution for minimum cost spanning tree problems. Games and Economic Behavior 75: 402-412.