Approximate Equilibrium and Incentivizing Social Coordination

Elliot Anshelevich, Shreyas SekarAAAI 2014 · DOI

Introduction

In game theory, coordination games model scenarios where players benefit from choosing the same strategy, such as companies adopting a common technical standard. However, real-world coordination is often hindered by intrinsic preferences and asymmetric relationships. These factors can lead to coordination failures, where agents are trapped in inefficient equilibria, or the non-existence of a stable Nash Equilibrium altogether. This paper explores how to nudge self-interested agents toward better collective outcomes by computing "almost stable" solutions and using small financial incentives to stabilize the social optimum.

Modeling Social Coordination Games

The authors introduce Social Coordination Games (SCGs), where a player's utility is the sum of their intrinsic preference for a strategy and the benefits derived from others choosing the same strategy. To handle the complexities of asymmetry, they define the Maximum Relationship Imbalance (MRI, denoted as $\gamma$). When $\gamma=1$, the game is symmetric; as $\gamma$ increases, the power imbalance between players grows.

Because a strict Nash Equilibrium may not exist or may be highly inefficient, the study focuses on $\alpha$-Approximate Equilibrium. In this framework, a player only switches strategies if their utility can be improved by a factor of at least $\alpha$.

The Stability-Welfare Trade-off

A central finding is the trade-off between the stability requirement ($\alpha$) and the resulting social welfare. By relaxing stability, it becomes possible to guarantee solutions with significantly higher social welfare.

Figure 1: Social welfare as a fraction of the optimum (OPT) increases as the stability requirement is relaxed (higher $\alpha$).

As shown in Figure 1, increasing the stability factor $\alpha$ allows the algorithm to capture a larger fraction of the maximum possible social welfare ($OPT$). For instance, in symmetric games, a 2-Approximate Equilibrium can capture at least 50% of $OPT$. The authors highlight that for $\alpha < 1.414$, an approximate equilibrium might not exist at all, making their results near the theoretical limit.

Key Results and Algorithmic Efficiency

The authors provide a polynomial-time algorithm to compute these equilibria. They demonstrate that even as asymmetry ($\gamma$) increases, the welfare remains a predictable fraction of the optimum, though it declines as the imbalance grows.

Figure 2: Social welfare as a fraction of OPT decreases as the maximum relationship imbalance ($\gamma$) increases.

Beyond finding approximate equilibria, the paper introduces a "Direct Payment Scheme." They prove a duality: if an algorithm fails to find a high-welfare approximate equilibrium, the social optimum ($OPT$) is relatively inexpensive to stabilize through small central payments. This suggests that a central authority can either find a good "almost stable" solution for free or "buy" a perfect one at a low cost.

Conclusion and Future Directions

While the paper provides strong theoretical bounds for pairwise coordination, it notes that finding the absolute social optimum is NP-hard. Future research could extend these models to supermodular coordination, where the benefits of group coordination exceed the sum of individual parts, or explore dynamic environments where preferences and relationships evolve over time.

Summary updated

BibTeX
@inproceedings{anshelevich2014approximate,
  author = {Elliot Anshelevich and Shreyas Sekar},
  title = {{Approximate Equilibrium and Incentivizing Social Coordination}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2014},
  doi = {10.1609/aaai.v28i1.8789},
}
Figure