A logical description of priority separable games

Das, Ramit and Ramanujam, R. and Simon, Sunil (2025) A logical description of priority separable games. Synthese, 206 (4). ISSN 1573-0964

Full text not available from this repository. (Request a copy)

Abstract

A major drawback of strategic games is that the representation is not compact: an explicit representation of the payoff functions is exponential in the number of players. Separable games are succinct: payoffs are specified for pairwise interactions, and from these, payoffs are computed for strategy profiles. We consider such games, but with qualitative payoffs, and use priority orderings on players to specify the net payoff for a player from the payoffs in pairwise subgames. We show that checking existence of Nash equilibrium in priority separable games is NP-complete. We describe these equilibria in Monadic Least Fixed Point Logic (MLFP). We then extend the description to games over arbitrarily many players using second order relational variables, but restrict their use in a parameterised form giving us a model checking procedure that is also NP-complete.

Item Type:	Article
Authors:	Das, Ramit and Ramanujam, R. and Simon, Sunil
Document Language:	Language English
Subjects:	Computer science, information & general works Azim Premji Foundation Structure > Azim Premji University - Bengaluru > Computer science, information & general works Social sciences > Economics Natural Sciences > Mathematics
Divisions:	Azim Premji University - Bengaluru > School of Arts and Sciences
Full Text Status:	None
URI:	http://publications.azimpremjiuniversity.edu.in/id/eprint/6908
Publisher URL:	https://doi.org/10.1007/s11229-025-05277-z

Actions (login required)

View Item