Authors: Kelvin Kian Loong Wong
Publish Date: 2015/01/27
Volume: 91, Issue: 1, Pages: 177-192
Abstract
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 npolyhedron 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 gametheoreticalbased 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 nplayer 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 gamemoment contributions from nplayer subsets of items at equilibrium The Paretooptimal 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 gametheoretical 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 problemThe author wishes to acknowledge the assistance of Paul Bourke at iVEC and the use of advanced computing resources located at the University of Western Australia to generate full permutation solution sets for validation of the spatial game theory examples
Keywords: