Strong price of anarchy

Nir Andelman, Michal Feldman and Yishay Mansour

Games and Economic Behavior, 2009, vol. 65, issue 2, 289-317

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.

Keywords: Strong; equilibrium; Price; of; anarchy; Strong; price; of; anarchy; Coalitions; Congestion; games; Network; formation; Job; scheduling (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (23)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0899-8256(08)00068-7
Full text for ScienceDirect subscribers only

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:eee:gamebe:v:65:y:2009:i:2:p:289-317

Access Statistics for this article

Games and Economic Behavior is currently edited by E. Kalai

More articles in Games and Economic Behavior from Elsevier
Bibliographic data for series maintained by Catherine Liu ().