| Full text | |
| Author(s): |
Fernandes, Cristina G.
[1]
;
Ferreira, Carlos E.
[1]
;
Miyazawa, Flavio K.
[2]
;
Wakabayashi, Yoshiko
[1]
Total Authors: 4
|
| Affiliation: | [1] Univ Sao Paulo, Inst Math & Stat, Av Prof Almeida Prado, 1280 Butanta, BR-05508070 Sao Paulo - Brazil
[2] Univ Estadual Campinas, Inst Comp, BR-13083970 Campinas, SP - Brazil
Total Affiliations: 2
|
| Document type: | Journal article |
| Source: | INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE; v. 30, n. 3, p. 355-374, APR 2019. |
| Web of Science Citations: | 0 |
| Abstract | |
We consider a game-theoretical problem called selfish 2-dimensional bin packing game, a generalization of the 1-dimensional case already treated in the literature. In this game, the items to be packed are rectangles, and the bins are unit squares. The game starts with a set of items arbitrarily packed in bins. The cost of an item is defined as the ratio between its area and the total occupied area of the respective bin. Each item is a selfish player that wants to minimize its cost. A migration of an item to another bin is allowed only when its cost is decreased. We show that this game always converges to a Nash equilibrium (a stable packing where no single item can decrease its cost by migrating to another bin). We show that the pure price of anarchy of this game is unbounded, so we address the particular case where all items are squares. We show that the pure price of anarchy of the selfish square packing game is at least 2.3634 and at most 2.6875. We also present analogous results for the strong Nash equilibrium (a stable packing where no nonempty set of items can simultaneously migrate to another common bin and decrease the cost of each item in the set). We show that the strong price of anarchy when all items are squares is at least 2.0747 and at most 2.3605. (AU) | |
| FAPESP's process: | 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science |
| Grantee: | Carlos Eduardo Ferreira |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 16/23552-7 - Cutting and Packing Problems: Practical and Theoretical Approaches |
| Grantee: | Rafael Crivellari Saliba Schouery |
| Support Opportunities: | Regular Research Grants |
| FAPESP's process: | 16/01860-1 - Cutting, packing, lot-sizing, scheduling, routing and location problems and their integration in industrial and logistics settings |
| Grantee: | Reinaldo Morabito Neto |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points |
| Grantee: | Flávio Keidi Miyazawa |
| Support Opportunities: | Research Projects - Thematic Grants |