caa a22 4500 606166939 CHVBK 20210128100700.0 cr unu---uuuuu 210128e20150401xx s 000 0 eng 10.1007/s10665-014-9742-1 doi (NATIONALLICENCE)springer-10.1007/s10665-014-9742-1 Wong Kelvin School of Computer Science and Software Engineering, The University of Western Australia, 35 Stirling Highway, 6000, Crawley, WA, Australia aut Bridging game theory and the knapsack problem: a theoretical formulation [Elektronische Daten] [Kelvin Wong] This paper presents an approach to solving the knapsack problem in which the solution can be derived based on a treatment of the classical bargaining problem. In spatial game theory, all the players form an $$n$$ n -polyhedron in space, and the bargaining set of items is positioned such that the geometrical distance of each item from every player reference vertex point is inversely proportional to its utility to the player. The game-theoretical-based distance of an item to a player is defined as the ratio of the geometrical distance referenced from the player's vertex position to the sum of distances from all the $$n$$ n -player vertices of the polyhedron, and its game moment is derived from the product of utility and this distance. Pareto optimality can then be achieved by balancing the effective game-moment contributions from $$n$$ n -player subsets of items at equilibrium. The Pareto-optimal solution is defined such that for a given set of consolidated items, further addition of items to the knapsack will result in diminishing returns in their payoffs or profits attained together with the corresponding unwanted increases in constraints or burdens to cause destabilization of this equilibrium. This game-theoretical approach is employed by having the game player entities work cooperatively to maximize profit and minimize burdens in order to arrive at a solution and is the first spatial game representation of the knapsack problem. Springer Science+Business Media Dordrecht, 2015 Game theory nationallicence Knapsack problem nationallicence Non-zero-sum game nationallicence Pareto-optimal solution nationallicence Optimization nationallicence Journal of Engineering Mathematics Springer Netherlands 91/1(2015-04-01), 177-192 0022-0833 91:1<177 2015 91 10665 https://doi.org/10.1007/s10665-014-9742-1 text/html Onlinezugriff via DOI BK010053 XK010053 XK010000 Metadata rights reserved Springer special CC-BY-NC licence nationallicence 1 research-article jats NATIONALLICENCE NATIONALLICENCE NL-springer NATIONALLICENCE 856 40 https://doi.org/10.1007/s10665-014-9742-1 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Wong Kelvin School of Computer Science and Software Engineering, The University of Western Australia, 35 Stirling Highway, 6000, Crawley, WA, Australia aut NATIONALLICENCE 773 0- Journal of Engineering Mathematics Springer Netherlands 91/1(2015-04-01), 177-192 0022-0833 91:1<177 2015 91 10665