The sequential price of anarchy for affine congestion games with few players

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

This paper determines the sequential price of anarchy for Rosenthal congestion games with affine cost functions and few players. We show that for two players, the sequential price of anarchy equals 1.5, and for three players it equals approximately 2.13. While the case with two players is analyzed analytically, the tight bound for three players is based on the explicit computation of a worst-case instance using linear programming. The basis for both results are combinatorial arguments to show that finite worst-case instances exist.
Original language English 133-139 7 Operations research letters 47 2 https://doi.org/10.1016/j.orl.2019.01.008 Published - Mar 2019

Fingerprint

Congestion Games
Price of Anarchy
Cost functions
Linear programming
Combinatorial argument
Affine Function
Approximately equal
Cost Function
Price of anarchy
Congestion games
Cost function

Cite this

@article{f50264ec24ab470196d2a8073e27c4b6,
title = "The sequential price of anarchy for affine congestion games with few players",
abstract = "This paper determines the sequential price of anarchy for Rosenthal congestion games with affine cost functions and few players. We show that for two players, the sequential price of anarchy equals 1.5, and for three players it equals approximately 2.13. While the case with two players is analyzed analytically, the tight bound for three players is based on the explicit computation of a worst-case instance using linear programming. The basis for both results are combinatorial arguments to show that finite worst-case instances exist.",
author = "{de Jong}, Jasper and Uetz, {Marc Jochen}",
year = "2019",
month = "3",
doi = "https://doi.org/10.1016/j.orl.2019.01.008",
language = "English",
volume = "47",
pages = "133--139",
journal = "Operations research letters",
issn = "0167-6377",
publisher = "Elsevier",
number = "2",

}

In: Operations research letters, Vol. 47, No. 2, 03.2019, p. 133-139.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - The sequential price of anarchy for affine congestion games with few players

AU - de Jong, Jasper

AU - Uetz, Marc Jochen

PY - 2019/3

Y1 - 2019/3

N2 - This paper determines the sequential price of anarchy for Rosenthal congestion games with affine cost functions and few players. We show that for two players, the sequential price of anarchy equals 1.5, and for three players it equals approximately 2.13. While the case with two players is analyzed analytically, the tight bound for three players is based on the explicit computation of a worst-case instance using linear programming. The basis for both results are combinatorial arguments to show that finite worst-case instances exist.

AB - This paper determines the sequential price of anarchy for Rosenthal congestion games with affine cost functions and few players. We show that for two players, the sequential price of anarchy equals 1.5, and for three players it equals approximately 2.13. While the case with two players is analyzed analytically, the tight bound for three players is based on the explicit computation of a worst-case instance using linear programming. The basis for both results are combinatorial arguments to show that finite worst-case instances exist.

U2 - https://doi.org/10.1016/j.orl.2019.01.008

DO - https://doi.org/10.1016/j.orl.2019.01.008

M3 - Article

VL - 47

SP - 133

EP - 139

JO - Operations research letters

JF - Operations research letters

SN - 0167-6377

IS - 2

ER -