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

Francisco J. M. da Silva (), Flávio K. Miyazawa, Ieremies V. F. Romero and Rafael C. S. Schouery
Additional contact information
Francisco J. M. da Silva: University of Campinas
Flávio K. Miyazawa: University of Campinas
Ieremies V. F. Romero: University of Campinas
Rafael C. S. Schouery: University of Campinas

Journal of Combinatorial Optimization, 2023, vol. 46, issue 2, No 1, 20 pages

Abstract: Abstract In this paper, we analyze a transportation game first introduced by Fotakis, Gourvès, 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.

Keywords: Transportation; Sequential games; Subgame perfect equilibrium; Price of Anarchy; Price of stability (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-023-01073-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:46:y:2023:i:2:d:10.1007_s10878-023-01073-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-023-01073-y

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().