Affordable Access

Publisher Website

Strong price of anarchy

Authors
Journal
Games and Economic Behavior
0899-8256
Publisher
Elsevier
Publication Date
Volume
65
Issue
2
Identifiers
DOI: 10.1016/j.geb.2008.03.005
Keywords
  • Strong Equilibrium
  • Price Of Anarchy
  • Strong Price Of Anarchy
  • Coalitions
  • Congestion Games
  • Network Formation
  • Job Scheduling
Disciplines
  • Design

Abstract

Abstract A strong equilibrium is a pure Nash equilibrium which is resilient to deviations by coalitions. We define the strong price of anarchy (SPoA) to be the ratio of the worst strong equilibrium to the social optimum. Differently from the Price of Anarchy (defined as the ratio of the worst Nash Equilibrium to the social optimum), it quantifies the loss incurred from the lack of a central designer in settings that allow for coordination. We study the SPoA in two settings, namely job scheduling and network creation. In the job scheduling game we show that for unrelated machines the SPoA can be bounded as a function of the number of machines and the size of the coalition. For the network creation game we show that the SPoA is at most 2. In both cases we show that a strong equilibrium always exists, except for a well defined subset of network creation games.

There are no comments yet on this publication. Be the first to share your thoughts.