Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Prices of Anarchy of Selfish 2D Bin Packing Games

Texto completo
Autor(es):
Fernandes, Cristina G. [1] ; Ferreira, Carlos E. [1] ; Miyazawa, Flavio K. [2] ; Wakabayashi, Yoshiko [1]
Número total de Autores: 4
Afiliação do(s) autor(es):
[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
Número total de Afiliações: 2
Tipo de documento: Artigo Científico
Fonte: INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE; v. 30, n. 3, p. 355-374, APR 2019.
Citações Web of Science: 0
Resumo

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)

Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
Beneficiário:Carlos Eduardo Ferreira
Linha de fomento: Auxílio à Pesquisa - Temático
Processo FAPESP: 16/23552-7 - Problemas de corte e empacotamento: abordagens práticas e teóricas
Beneficiário:Rafael Crivellari Saliba Schouery
Linha de fomento: Auxílio à Pesquisa - Regular
Processo FAPESP: 16/01860-1 - Problemas de corte, empacotamento, dimensionamento de lotes, programação da produção, roteamento, localização e suas integrações em contextos industriais e logísticos
Beneficiário:Reinaldo Morabito Neto
Linha de fomento: Auxílio à Pesquisa - Temático
Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
Beneficiário:Flávio Keidi Miyazawa
Linha de fomento: Auxílio à Pesquisa - Temático