 Using weight decision for decreasing the price of anarchy in selfish bin packing gamesGyorgy Dosa, Hans Kellerer and Zsolt Tuza European Journal of Operational Research, 2019, vol. 278, issue 1, 160-169 Abstract: A selfish bin packing game is a variant of the classical bin packing problem in a game theoretic setting. In our model the items have not only a size but also a nonnegative weight. Each item plays the role of a selfish agent, and any agent/item pays some cost for being in a bin. The cost of a bin is 1, and this cost is shared among the items being in the bin, proportionally to their weight. A packing of the items into bins is called a Nash equilibrium if no item can decrease its cost by moving to another bin. In this paper we present two different settings for the weights which provide better values for the price of anarchy (PoA) than previous settings investigated so far. The improved PoA is not bigger than 16/11 ≈ 1.4545. Moreover, we give a general lower bound for the price of anarchy which holds for all possible choices of the weights. Keywords: Game theory; Selfish bin packing; Price of anarchy (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:278:y:2019:i:1:p:160-169 DOI: 10.1016/j.ejor.2019.04.026 Access Statistics for this article European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati More articles in European Journal of Operational Research from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.