Strong price of anarchy

• 成果类型: Article
• 署名作者: Andelman, Nir; Feldman, Michal; Mansour, Yishay
• 署名单位: Hebrew University of Jerusalem; Hebrew University of Jerusalem; Tel Aviv University
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2008.03.005
• 发表日期: 2009
• 页码: 289-317
• 关键词: Strong equilibrium; Price of anarchy; Strong price of anarchy; coalitions; Congestion games; network formation; Job scheduling

摘要

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 front 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. (C) 2008 Elsevier Inc. All rights reserved.