2015 | OriginalPaper | Buchkapitel
Bin Packing Game with an Interest Matrix
verfasst von : Zhenbo Wang, Xin Han, György Dósa, Zsolt Tuza
Erschienen in: Computing and Combinatorics
Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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}$$
a
i
j
stands for how much item
i
likes item
j
. The payoff of item
i
is the sum of
$$a_{ij}$$
a
i
j
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.