Dósa, György and Kellerer, Hans and Tuza, Zsolt (2019) Using weight decision for decreasing the price of anarchy in selfish bin packing games. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 278 (1). pp. 160-169. ISSN 0377-2217
|
Text
Dosa-Kellerer-Tuza-Using-weight-decision.pdf Download (156kB) | Preview |
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 approximate to 1.4545. Moreover, we give a general lower bound for the price of anarchy which holds for all possible choices of the weights. (C) 2019 Elsevier B.V. All rights reserved.
| Item Type: | Article |
|---|---|
| Additional Information: | Funding Agency and Grant Number: Szechenyi 2020 [EFOP-3.6.1-16-2016-00015]; National Research, Development and Innovation Office - NKFIH [SNN 116095] Funding text: Gyorgy Dosa acknowledges the financial support of Szechenyi 2020 under the EFOP-3.6.1-16-2016-00015. Research of the first and third authors was supported in part by the National Research, Development and Innovation Office - NKFIH under the grant SNN 116095. Department of Mathematics, University of Pannonia, Egyetem u. 10, Veszprém, H-8200, Hungary Institut für Statistik und Operations Research, Universität Graz, Universitätsstraße 15, Graz, 8010, Austria Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, Reáltanoda u. 13–15, Budapest, H-1053, Hungary Department of Computer Science and Systems Technology, University of Pannonia, Egyetem u. 10, Veszprém, H-8200, Hungary Cited By :1 Export Date: 14 January 2020 CODEN: EJORD Correspondence Address: Kellerer, H.; Institut für Statistik und Operations Research, Universität Graz, Universitätsstraße 15, Austria; email: hans.kellerer@uni-graz.at Funding details: EFOP-3.6.1-16-2016-00015 Funding details: Office of Research, Innovation and Economic Development, California State Polytechnic University, Pomona Funding details: Nemzeti Kutatási Fejlesztési és Innovációs Hivatal, SNN 116095 Funding text 1: Gyorgy Dosa acknowledges the financial support of Széchenyi 2020 under the EFOP-3.6.1-16-2016-00015. Research of the first and third authors was supported in part by the National Research, Development and Innovation Office – NKFIH under the grant SNN 116095. |
| Uncontrolled Keywords: | Game theory; MANAGEMENT; Selfish bin packing; |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 16 Jan 2020 12:50 |
| Last Modified: | 16 Jan 2020 12:50 |
| URI: | http://real.mtak.hu/id/eprint/105504 |
Actions (login required)
 |
Edit Item |
