A General Bin Packing Game: Interest Taken into Account
  • Metaadatok
Tartalom: http://real.mtak.hu/89931/
Archívum: REAL
Gyűjtemény: Status = Published
Subject = Q Science / természettudomány: QA Mathematics / matematika: QA72 Algebra / algebra
Subject = Q Science / természettudomány: QA Mathematics / matematika
Type = Article
Cím:
A General Bin Packing Game: Interest Taken into Account
Létrehozó:
Wang, Zhenbo
Han, Xin
Dósa, György
Tuza, Zsolt
Kiadó:
Springer
Dátum:
2018
Téma:
QA Mathematics / matematika
QA72 Algebra / algebra
Tartalmi leírás:
In this paper we study a general 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 Nash Equilibrium (NE) always exists. However the Price of Anarchy (PoA) may be very large, therefore we consider several special cases and give bounds for PoA. We present some results for the asymmetric case, too. Moreover we introduce a new metric, called the Price of Harmony (PoH for short), which we think is more accurate to describe the quality of an NE in the new model.
Nyelv:
angol
Típus:
Article
PeerReviewed
info:eu-repo/semantics/article
Formátum:
text
Azonosító:
Wang, Zhenbo and Han, Xin and Dósa, György and Tuza, Zsolt (2018) A General Bin Packing Game: Interest Taken into Account. ALGORITHMICA, 80 (5). pp. 1534-1555. ISSN 0178-4617
Kapcsolat:
MTMT:3280347 10.1007/s00453-017-0361-x