DROPS

Document

DOI: 10.4230/LIPIcs.CSL.2026.34

Memory Requirements in Non-Zero-Sum Games

Authors: Yoav Feinstein and Orna Kupferman

Published in: LIPIcs, Volume 363, 34th EACSL Annual Conference on Computer Science Logic (CSL 2026)

Abstract

The interaction between a system and the components modeling its environment is traditionally modeled by a multi-player game played on a finite graph. In zero-sum games, the players have conflicting objectives, and it is clear that increasing the memory of the environment players can only make it harder for the system to win. In non-zero-sum games, the objectives of the players may overlap. There, typical questions concern the stability of the game and the equilibria the players may reach. In particular, in rational synthesis (RS), the goal is to find an equilibrium that satisfies the objective of the system. We study how the memory of the environment players may affect the existence of an RS solution. As we show, the picture is diverse, even when the objectives of all players are memoryless. On the one hand, when stability amounts to a Nash equilibrium (NE), then increasing the memory of the environment may only help the system to suggest an RS solution. On the other hand, when the notion of stability involves deviations by coalitions of environment players, for example in a strong Nash equilibrium (SNE), then increasing their memory may sometimes enable and sometimes prevent the existence of an RS solution. We study memory bounds for the players, showing that the memory required may be polynomial in an NE-RS solution and exponential in an SNE-RS solution. We also solve the SNE-RS problem, show that it is PSPACE-complete, and relate the differences between NE and SNE with the differences between cooperative and non-cooperative RS.

Cite as

Yoav Feinstein and Orna Kupferman. Memory Requirements in Non-Zero-Sum Games. In 34th EACSL Annual Conference on Computer Science Logic (CSL 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 363, pp. 34:1-34:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{feinstein_et_al:LIPIcs.CSL.2026.34,
  author =	{Feinstein, Yoav and Kupferman, Orna},
  title =	{{Memory Requirements in Non-Zero-Sum Games}},
  booktitle =	{34th EACSL Annual Conference on Computer Science Logic (CSL 2026)},
  pages =	{34:1--34:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-411-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{363},
  editor =	{Guerrini, Stefano and K\"{o}nig, Barbara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2026.34},
  URN =		{urn:nbn:de:0030-drops-254597},
  doi =		{10.4230/LIPIcs.CSL.2026.34},
  annote =	{Keywords: Non-Zero-Sum Games, Synthesis, Memory}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2023.26

Monotonicity Characterizations of Regular Languages

Authors: Yoav Feinstein and Orna Kupferman

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract

Each language L ⊆ Σ^* induces an infinite sequence Pr(L,n)_{n=1}^∞, where for all n ≥ 1, the value Pr(L,n) ∈ [0,1] is the probability of a word of length n to be in L, assuming a uniform distribution on the letters in Σ. Previous studies of Pr(L,n)_{n=1}^∞ for a regular language L, concerned zero-one laws, density, and accumulation points. We study monotonicity of Pr(L,n)_{n=1}^∞, possibly in the limit. We show that monotonicity may depend on the distribution of letters, study how operations on languages affect monotonicity, and characterize classes of languages for which the sequence is monotonic. We extend the study to languages L of infinite words, where we study the probability of lasso-shaped words to be in L and consider two definitions for Pr(L,n). The first refers to the probability of prefixes of length n to be extended to words in L, and the second to the probability of word w of length n to be such that w^ω is in L. Thus, in the second definition, monotonicity depends not only on the length of w, but also on the words being periodic.

Cite as

Yoav Feinstein and Orna Kupferman. Monotonicity Characterizations of Regular Languages. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 26:1-26:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{feinstein_et_al:LIPIcs.FSTTCS.2023.26,
  author =	{Feinstein, Yoav and Kupferman, Orna},
  title =	{{Monotonicity Characterizations of Regular Languages}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{26:1--26:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.26},
  URN =		{urn:nbn:de:0030-drops-193998},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.26},
  annote =	{Keywords: Regular Languages, Probability, Monotonicity, Automata}
}

Search Results

Documents authored by Feinstein, Yoav

Memory Requirements in Non-Zero-Sum Games

Abstract

Cite as

Monotonicity Characterizations of Regular Languages

Abstract

Cite as

Thanks for your feedback!

Could not send message