Computing Equilibria with Partial Commitment

Vincent Conitzer

Abstract

Traditional game theory often focuses on two extremes: simultaneous-move Nash Equilibria and full-commitment Stackelberg Equilibria. This research bridges this gap by introducing a model of partial commitment, where a follower can observe only a subset of the leader's potential strategies. We analyze two solution concepts: Stackelberg Equilibrium with Limited Observation (SELO) and its signaling-enhanced variant (SESLO). Our findings demonstrate that while finding an optimal strategy under limited observation is NP-hard, the introduction of a trusted mediator for signaling makes the problem computationally tractable and significantly enhances the leader's utility.

Introduction

In many real-world strategic interactions, commitment is neither absent nor absolute. Consider a security scenario where a defender employs both visible and undercover patrols. An attacker might observe the general distribution of visible measures but remain unable to distinguish between specific undercover tactics. This "middle ground" is the focus of this paper, which formalizes how partial observability affects equilibrium computation and player utility.

Partial Commitment and Indistinguishable Strategies

The core of this model is the Subset of Indistinguishable Strategies (SIS). Instead of observing the leader's exact action, the follower observes which SIS the leader's chosen action belongs to. To maintain credibility, the leader must play a strategy that is a best-response within the chosen SIS, as the follower cannot detect deviations that stay within the same subset.

Figure 1: A sample payoff matrix used to analyze strategic interactions under varying levels of observability.

Solution Concepts: SELO and SESLO

The paper introduces two primary solution concepts to address this environment:

  1. Stackelberg Equilibrium with Limited Observation (SELO): The leader chooses a strategy to maximize utility, constrained by the fact that they must play optimally within each SIS to remain "undetectable" to a rational follower.
  2. Stackelberg Equilibrium with Signaling and Limited Observation (SESLO): This model introduces a trusted mediator who provides private signals to both players, similar to a Correlated Equilibrium. This signaling mechanism allows for coordination that can bypass some of the constraints of pure partial commitment.

Computational Complexity

A significant contribution of this work is the categorization of the computational difficulty of these equilibria.

  • SELO is NP-hard: Even when the indistinguishable sets are as small as size 2, finding the optimal strategy is computationally difficult. This is because SELO generalizes the problem of finding the best Nash Equilibrium.
  • SESLO is in P: Surprisingly, the addition of signaling simplifies the problem. The author provides a constructive solution using Linear Programming (LP), proving that SESLO can be computed in polynomial time.

Key Insights and Utility Jumps

Simulations on 1,000 randomly generated games (ranging from $5\times5$ to $15\times15$) reveal a striking "diminishing returns" property of commitment. The most significant utility gains for the leader occur when moving from zero observability (a single SIS) to just a small amount of observability (two SISes).

Figure 3: A complex payoff matrix illustrating how high-value outcomes can lead to significant utility 'jumps' as observability increases.

In larger games, the leader's utility often jumps from Nash-like levels (~0.84) to Stackelberg-like levels (~0.96) almost immediately upon the introduction of minimal commitment power. This suggests that in complex security environments, even a small amount of transparency can be highly beneficial for the defender.

Conclusion

This research provides a robust framework for understanding the spectrum between Nash and Stackelberg equilibria. By proving the tractability of signaling-based models and highlighting the disproportionate value of initial observability, the paper offers practical insights for designing security protocols and strategic communication systems. Future work will explore these dynamics in the context of learning and limited observations by the follower.

Summary updated

Abstract

In security games, the solution concept commonly used is that of a Stackelberg equilibrium where the defender gets to commit to a mixed strategy. The motivation for this is that the attacker can repeatedly observe the defender’s actions and learn her distribution over actions, before acting himself. If the actions were not observable, Nash (or perhaps correlated) equilibrium would arguably be a more natural solution concept. But what if some, but not all, aspects of the defender’s actions are observable? In this paper, we introduce solution concepts corresponding to this case, both with and without correlation. We study their basic properties, whether these solutions can be efficiently computed, and the impact of additional observability on the utility obtained.
BibTeX
@inproceedings{conitzer2016computing,
  author = {Vincent Conitzer},
  title = {{Computing Equilibria with Partial Commitment}},
  booktitle = {WINE},
  year = {2016},
  url = {https://openreview.net/forum?id=w1a0jxulsr},
}
Figure