Tight inefficiency bounds for perception-parameterized affine congestion games

Pieter Kleer, Guido Schäfer

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

We introduce a new model of congestion games that captures several extensions of the classical congestion game introduced by Rosenthal in 1973. The idea here is to parameterize both the perceived cost of each player and the social cost function of the system designer. Intuitively, each player perceives the load induced by the other players by an extent of ρ≥0, while the system designer estimates that each player perceives the load of all others by an extent of σ≥0. For specific choices of ρ and σ we obtain extensions such as altruistic player behavior, risk sensitive players and the imposition of taxes on the resources. We derive tight bounds on the price of anarchy and the price of stability for a large range of parameters. Our bounds provide a complete picture of the inefficiency of equilibria for these games. As a result, we obtain tight bounds on the price of anarchy and the price of stability for the above mentioned extensions. Our results also reveal how one should “design” the cost functions of the players in order to reduce the price of anarchy. Somewhat counterintuitively, if each player cares about all other players to the extent of ρ=0.625 (instead of 1 in the standard setting) the price of anarchy reduces from 2.5 to 2.155 and this is best possible.

LanguageEnglish
Pages65-87
Number of pages23
JournalTheoretical Computer Science
Volume754
DOIs
Publication statusPublished - 6 Jan 2019

Fingerprint

Congestion Games
Price of Anarchy
Cost functions
Taxation
Cost Function
Parameterise
Tax
Costs
Game
Resources
Perception
Estimate
Range of data

Keywords

  • Altruistic games
  • Congestion games
  • Inefficiency of equilibria
  • Price of anarchy
  • Price of stability
  • Risk-averse players
  • Universal taxes

Cite this

@article{c73fe3ae9f0c4b058be45c4c0df65a17,
title = "Tight inefficiency bounds for perception-parameterized affine congestion games",
abstract = "We introduce a new model of congestion games that captures several extensions of the classical congestion game introduced by Rosenthal in 1973. The idea here is to parameterize both the perceived cost of each player and the social cost function of the system designer. Intuitively, each player perceives the load induced by the other players by an extent of ρ≥0, while the system designer estimates that each player perceives the load of all others by an extent of σ≥0. For specific choices of ρ and σ we obtain extensions such as altruistic player behavior, risk sensitive players and the imposition of taxes on the resources. We derive tight bounds on the price of anarchy and the price of stability for a large range of parameters. Our bounds provide a complete picture of the inefficiency of equilibria for these games. As a result, we obtain tight bounds on the price of anarchy and the price of stability for the above mentioned extensions. Our results also reveal how one should “design” the cost functions of the players in order to reduce the price of anarchy. Somewhat counterintuitively, if each player cares about all other players to the extent of ρ=0.625 (instead of 1 in the standard setting) the price of anarchy reduces from 2.5 to 2.155 and this is best possible.",
keywords = "Altruistic games, Congestion games, Inefficiency of equilibria, Price of anarchy, Price of stability, Risk-averse players, Universal taxes",
author = "Pieter Kleer and Guido Sch{\"a}fer",
year = "2019",
month = "1",
day = "6",
doi = "10.1016/j.tcs.2018.04.025",
language = "English",
volume = "754",
pages = "65--87",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",

}

Tight inefficiency bounds for perception-parameterized affine congestion games. / Kleer, Pieter; Schäfer, Guido.

In: Theoretical Computer Science, Vol. 754, 06.01.2019, p. 65-87.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - Tight inefficiency bounds for perception-parameterized affine congestion games

AU - Kleer, Pieter

AU - Schäfer, Guido

PY - 2019/1/6

Y1 - 2019/1/6

N2 - We introduce a new model of congestion games that captures several extensions of the classical congestion game introduced by Rosenthal in 1973. The idea here is to parameterize both the perceived cost of each player and the social cost function of the system designer. Intuitively, each player perceives the load induced by the other players by an extent of ρ≥0, while the system designer estimates that each player perceives the load of all others by an extent of σ≥0. For specific choices of ρ and σ we obtain extensions such as altruistic player behavior, risk sensitive players and the imposition of taxes on the resources. We derive tight bounds on the price of anarchy and the price of stability for a large range of parameters. Our bounds provide a complete picture of the inefficiency of equilibria for these games. As a result, we obtain tight bounds on the price of anarchy and the price of stability for the above mentioned extensions. Our results also reveal how one should “design” the cost functions of the players in order to reduce the price of anarchy. Somewhat counterintuitively, if each player cares about all other players to the extent of ρ=0.625 (instead of 1 in the standard setting) the price of anarchy reduces from 2.5 to 2.155 and this is best possible.

AB - We introduce a new model of congestion games that captures several extensions of the classical congestion game introduced by Rosenthal in 1973. The idea here is to parameterize both the perceived cost of each player and the social cost function of the system designer. Intuitively, each player perceives the load induced by the other players by an extent of ρ≥0, while the system designer estimates that each player perceives the load of all others by an extent of σ≥0. For specific choices of ρ and σ we obtain extensions such as altruistic player behavior, risk sensitive players and the imposition of taxes on the resources. We derive tight bounds on the price of anarchy and the price of stability for a large range of parameters. Our bounds provide a complete picture of the inefficiency of equilibria for these games. As a result, we obtain tight bounds on the price of anarchy and the price of stability for the above mentioned extensions. Our results also reveal how one should “design” the cost functions of the players in order to reduce the price of anarchy. Somewhat counterintuitively, if each player cares about all other players to the extent of ρ=0.625 (instead of 1 in the standard setting) the price of anarchy reduces from 2.5 to 2.155 and this is best possible.

KW - Altruistic games

KW - Congestion games

KW - Inefficiency of equilibria

KW - Price of anarchy

KW - Price of stability

KW - Risk-averse players

KW - Universal taxes

UR - http://www.scopus.com/inward/record.url?scp=85046123230&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85046123230&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2018.04.025

DO - 10.1016/j.tcs.2018.04.025

M3 - Article

VL - 754

SP - 65

EP - 87

JO - Theoretical Computer Science

T2 - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -