skip to main content
10.5555/1283383.1283404acmconferencesArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
Article

Strong price of anarchy

Published:07 January 2007Publication History

ABSTRACT

A strong equilibrium (Aumann 1959) is a pure Nash equilibrium which is resilient to deviations by coalitions. We define the strong price of anarchy to be the ratio of the worst case strong equilibrium to the social optimum. In contrast to the traditional price of anarchy, which quantifies the loss incurred due to both selfishness and lack of coordination, the strong price of anarchy isolates the loss originated from selfishness from that obtained due to lack of coordination. We study the strong price of anarchy in two settings, one of job scheduling and the other of network creation. In the job scheduling game we show that for unrelated machines the strong price of anarchy 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 strong price of anarchy 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.

References

References are not available

Recommendations

Comments

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Sign in
  • Published in

    cover image ACM Conferences
    SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms
    January 2007
    1322 pages
    ISBN:9780898716245
    • Conference Chair:
    • Harold Gabow

    Publisher

    Society for Industrial and Applied Mathematics

    United States

    Publication History

    • Published: 7 January 2007

    Check for updates

    Qualifiers

    • Article

    Acceptance Rates

    SODA '07 Paper Acceptance Rate139of382submissions,36%Overall Acceptance Rate411of1,322submissions,31%

PDF Format

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader