Multi-Player Game Approach to Solving Multi-Entity Problems

Abstract

Many real-world problems involve the allocation of limited resources to competing consumers with dissimilar objective functions. Current techniques that handle such problems usually examine the problem domain as a whole in order to find a solution that maximizes a single overall performance metric (commonly expressed as a weighted sum of the utility of all consumers and some global measures). For example, stochastic search techniques such as Simulated Annealing and Genetic Algorithm all generally use this single-metric approach. There are some drawbacks to this modeling scheme. Firstly, a solution that achieves a high score based on this single performance metric may not be good in the practical sense. For instance, such a solution may involve alienating one or two consumers while favoring others greatly. In real life, the alienated consumers may not take such treatment kindly. Secondly, such techniques fail to take advantage of the natural division of the problem domain into the subsets belonging to the different consumers. The items within these subsets generally contain some sort of interrelation, especially in real-life instances. Therefore, it may be better to tailor the allocation strategies to each subset. Thirdly, the problem may be too large to solve as a whole, but becomes more manageable if divided into smaller subproblems. In an ideal setting, multi-entity problems should be solved by sitting all the consumers together and negotiating the allocation of resources in a fair and diplomatic manner. Such a model can be thought of as a multi-player competitive cum collaborative game, where each consumer is a player in the game. It is competitive since each player seeks primarily to maximize his own utility; it is collaborative since all consumers must take the feasibility and quality of the overall solution into account. This research examines this Multi-Player Game Approach (MPGA).