Tight bounds for the price of anarchy and stability in sequential transportation games

Autor(es)

da Silva, Francisco J. M. ; Miyazawa, Flavio K. ; Romero, Ieremies V. F. ; Schouery, Rafael C. S.

• Tipo de documento: Artigo Científico
• Fonte: JOURNAL OF COMBINATORIAL OPTIMIZATION; v. 46, n. 2, p. 20-pg., 2023-09-01.

Resumo

In this paper, we analyze a transportation game first introduced by Fotakis, Gourves, and Monnot in 2017, where players want to be transported to a common destination as quickly as possible and, to achieve this goal, they have to choose one of the available buses. We introduce a sequential version of this game and provide bounds for the Sequential Price of Stability and the Sequential Price of Anarchy in both metric and non-metric instances, considering three social cost functions: the total traveled distance by all buses, the maximum distance traveled by a bus, and the sum of the distances traveled by all players (a new social cost function that we introduce). Finally, we analyze the Price of Stability and the Price of Anarchy for this new function in simultaneous transportation games. (AU)

• Processo FAPESP: 17/05223-9 - Análise teórica de problemas de transporte sob a perspectiva da teoria dos jogos
• Beneficiário: Francisco Jhonatas Melo da Silva
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• 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
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• 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
• Modalidade de apoio: Auxílio à Pesquisa - Temático