Strong price of anarchy |
| |
Authors: | Nir Andelman Michal Feldman Yishay Mansour |
| |
Affiliation: | 1. Department of Statistics and the Federmann Center for the Study of Rationality, The Hebrew University of Jerusalem, Israel;2. Intelligent Transport Systems Lab, Swinburne University of Technology, Australia |
| |
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: | |
本文献已被 ScienceDirect 等数据库收录! |
|