Indexed by:会议论文

Date of Publication:2015-08-04

Included Journals:EI、CPCI-S、Scopus

Volume:9198

Page Number:57-69

Abstract:In this paper we study a game problem, called bin packing game with an interest matrix, which is a generalization of all the currently known bin packing games. In this game, there are some items with positive sizes and identical bins with unit capacity as in the classical bin packing problem; additionally we are given an interest matrix with rational entries, whose element a(ij) stands for how much item i likes item j. The payoff of item i is the sum of aij over all items j in the same bin with item i, and each item wants to stay in a bin where it can fit and its payoff is maximized. We find that if the matrix is symmetric, a pure Nash Equilibrium always exists. However the PoA (Price of Anarchy) may be very large, therefore we consider several special cases and give bounds for PoA in them. We present some results for the asymmetric case, too.