# Most General Winning Secure Equilibria Synthesis in Graph Games

arXiv: https://arxiv.org/abs/2401.09957 · HTML: https://mlsanity.com/paper/2401.09957/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jan 2024.

## Built on by (most cited first, 1 of 1)

- [Follow the STARs: Dynamic ω-Regular Shielding of Learned Policies](https://mlsanity.com/paper/2505.14689/) (2025)

## Abstract (arXiv)

This paper considers the problem of co-synthesis in k-player games over a finite graph where each player has an individual ω-regular specification φi. In this context, a secure equilibrium (SE) is a Nash equilibrium w.r.t. the lexicographically ordered objectives of each player to first satisfy their own specification, and second, to falsify other players' specifications. A winning secure equilibrium (WSE) is an SE strategy profile (πi)i∈[1;k] that ensures the specification φ:=bigwedgei∈[1;k]φi if no player deviates from their strategy πi. Distributed implementations generated from a WSE make components act rationally by ensuring that a deviation from the WSE strategy profile is immediately punished by a retaliating strategy that makes the involved players lose. In this paper, we move from deviation punishment in WSE-based implementations to a distributed, assume-guarantee based realization of WSE. This shift is obtained by generalizing WSE from strategy profiles to specification profiles (varphii)i∈[1;k] with bigwedgei∈[1;k]varphii = φ, which we call most general winning secure equilibria (GWSE). Such GWSE have the property that each player can individually pick a strategy πi winning for varphii (against all other players) and all resulting strategy profiles (πi)i∈[1;k] are guaranteed to be a WSE. The obtained flexibility in players' strategy choices can be utilized for robustness and adaptability of local implementations. Concretely, our contribution is three-fold: (1) we formalize GWSE for k-player games over finite graphs, where each player has an ω-regular specification φi; (2) we devise an iterative semi-algorithm for GWSE synthesis in such games, and (3) obtain an exponential-time algorithm for GWSE synthesis with parity specifications φi.