Academic literature on the topic 'Concurrent stochastic game'

This article is a tutorial introduction to stochastic games, first introduced by Shapley in 1953. The presentation is based around several classical examples of such games, and focusses on the question of strategy complexity in terms of parameters such as the cardinality of the state space, branching factor of the transition function, and whether the game is concurrent or turn-based. Our goal is to give a practical introduction to stochastic games, the notion of values and strategies, and the memory requirements of optimal and ε-optimal strategies in different games.

Opponent modeling is the ability to use prior knowledge and observations in order to predict the behavior of an opponent. This survey presents a comprehensive overview of existing opponent modeling techniques for adversarial domains, many of which must address stochastic, continuous, or concurrent actions, and sparse, partially observable payoff structures. We discuss all the components of opponent modeling systems, including feature extraction, learning algorithms, and strategy abstractions. These discussions lead us to propose a new form of analysis for describing and predicting the evolution of game states over time. We then introduce a new framework that facilitates method comparison, analyze a representative selection of techniques using the proposed framework, and highlight common trends among recently proposed methods. Finally, we list several open problems and discuss future research directions inspired by AI research on opponent modeling and related research in other disciplines.

AbstractAutomated verification techniques for stochastic games allow formal reasoning about systems that feature competitive or collaborative behaviour among rational agents in uncertain or probabilistic settings. Existing tools and techniques focus on turn-based games, where each state of the game is controlled by a single player, and on zero-sum properties, where two players or coalitions have directly opposing objectives. In this paper, we present automated verification techniques for concurrent stochastic games (CSGs), which provide a more natural model of concurrent decision making and interaction. We also consider (social welfare) Nash equilibria, to formally identify scenarios where two players or coalitions with distinct goals can collaborate to optimise their joint performance. We propose an extension of the temporal logic rPATL for specifying quantitative properties in this setting and present corresponding algorithms for verification and strategy synthesis for a variant of stopping games. For finite-horizon properties the computation is exact, while for infinite-horizon it is approximate using value iteration. For zero-sum properties it requires solving matrix games via linear programming, and for equilibria-based properties we find social welfare or social cost Nash equilibria of bimatrix games via the method of labelled polytopes through an SMT encoding. We implement this approach in PRISM-games, which required extending the tool’s modelling language for CSGs, and apply it to case studies from domains including robotics, computer security and computer networks, explicitly demonstrating the benefits of both CSGs and equilibria-based properties.

The design and control of autonomous systems that operate in uncertain or adversarial environments can be facilitated by formal modeling and analysis. Probabilistic model checking is a technique to automatically verify, for a given temporal logic specification, that a system model satisfies the specification, as well as to synthesize an optimal strategy for its control. This method has recently been extended to multiagent systems that exhibit competitive or cooperative behavior modeled via stochastic games and synthesis of equilibria strategies. In this article, we provide an overview of probabilistic model checking, focusing on models supported by the PRISM and PRISM-games model checkers. This overview includes fully observable and partially observable Markov decision processes, as well as turn-based and concurrent stochastic games, together with associated probabilistic temporal logics. We demonstrate the applicability of the framework through illustrative examples from autonomous systems. Finally, we highlight research challenges and suggest directions for future work in this area. Expected final online publication date for the Annual Review of Control, Robotics, and Autonomous Systems, Volume 5 is May 2022. Please see http://www.annualreviews.org/page/journal/pubdates for revised estimates.

On étudie des jeux à deux joueuses (A et B) sur des graphes. À partir d'un état du graphe, les joueuses interagissent pour aller d'un état à un autre.Ceci induit une suite infinie d'états à laquelle une fonction de gain mesurable associe une valeur dans [0, 1]. La Joueuse A (resp. B) tente de maximiser (resp.minimiser) l'espérance de cette fonction de gain.Les jeux à tours, i.e. les jeux tels qu'à chaque état une seule joueuse choisit(une loi de probabilités sur) l'état suivant, ont de nombreuses bonnes propriétés.Par exemple, dans tous les jeux à tours perd/gagne déterministes, une joueuse a une stratégie gagnante. De plus, dans les jeux de parité à tours finis, les deux joueuses ont des stratégies optimales positionnelles. A contrario, les jeux concurrents, i.e. les jeux tels qu'à chaque état les deux joueuses concourent au choix d'une loi de probabilité sur les états suivants, se comportent mal. Ainsi, il existe des jeux concurrents de parité déterministes tels que : aucune des joueuses n'a de stratégie gagnante ; aucune joueuse n'a de stratégie optimale, même stochastique. De plus, lorsque c'est possible, jouer de manière optimale peut nécessiter une mémoire infinie. Le but de ce manuscrit est d'enrichir notre compréhension du comportement des jeux concurrents. Pour ce faire, on étudie la notion de forme de jeu. Les formes de jeu sont les objets mathématiques qui décrivent les interactions (locales) des joueuses à chaque état d'un jeu concurrent. Les formes de jeu sont définies par un ensemble de stratégies locales par joueuse, un ensemble d'issues et une fonction envoyant une paire d'une stratégie locale par joueuse sur une loi de probabilités sur les issues. Généralement, dans les articles sur les jeux concurrents, les interactions locales sont des formes de jeu standard (finies) :les ensembles de stratégies locales sont des lois de probabilités sur les ensembles(finis) d'actions sous-jacents. Ici, on définie des formes de jeu plus générales,que l'on appelle formes de jeu arbitraires. Certains des résultats établis dans ce manuscrit supposent que les interactions locales sont standard, tandis que les autres ne font pas de telles hypothèses.Premièrement, on prouve des résultats généraux sur les jeux concurrents,avec très peu d'hypothèses sur les fonctions de gain et les interactions locales.En particulier, on considère un résultat crucial sur les jeux concurrents : la détermination de Blackwell de Martin, qui peut être énoncé comme suit. Soit un jeu concurrent dont toutes les interactions locales sont standards finies.Depuis chaque état, il existe une valeur u dans [0, 1] telle que les stratégies de la Joueuse A (resp. B) peuvent garantir que l'espérance de la fonction de gain est au moins (resp. au plus) égal à n'importe quel seuil en-dessous(resp. au-dessus) de u. On généralise ce résultat aux jeux dont les formes de jeu sont arbitraires et en déduisons d'autres résultats sur les jeux concurrents. On prouve également d'autres résultats sur les jeux concurrents, en particulier sur les stratégies optimales en sous-jeu. Deuxièmement, on étudie le comportement des jeux de parité concurrents finis en termes d'existence et de nature des stratégies (presque) optimales (en sous-jeu), avec très peu d'hypothèses sur les interactions locales.Troisièmement, on définie des ensembles de jeux concurrents qui ont certaines des propriétés des jeux à tours tout en étant plus généraux que les jeux à tours. Ainsi, étant donné une propriété souhaitable des jeux concurrents, oncaractérise tout d'abord les formes de jeu qui garantissent que tous les jeuxsimples qui les utilisent comme interactions locales satisfont cette propriété. Oncaractérise ainsi les formes de jeu qui se comportent bien individuellement. Onmontre ensuite que tous les jeux concurrents qui utilisent ces formes de jeucomme interactions locales satisfont également cette propriété. Ces formes de jeux se comportent également bien collectivement
We study games played by two players, Player A and Player B, on a graph. Starting from a state of the graph, the players interact to move from state to state. This induces an infinite sequence of states, which is mapped to a value in [0, 1] by a measurable payoff function. Player A (resp. B) tries to maximize (resp. minimize) the expected value of this payoff function.Turn-based games, i.e. games where at each state only one player chooses a (probability distribution over) successor state, enjoy many nice properties.For instance, in all deterministic win/lose turn-based games, from each state,one of the players has a winning strategy. In addition, in finite turn-based parity games, both players have positional optimal strategies from each state.By contrast, concurrent games, i.e. games where at each state both players interact concurrently, i.e. simultaneously, to generate a probability distributionover successor states, behave much more poorly. Indeed, there are very simple deterministic concurrent parity games such that: neither player has a winning strategy; neither player has an optimal strategy, even a stochastic one. Inaddition, when optimal strategies do exist, they may require infinite memory. The goal of this dissertation is to give significant insight on how concurrent games behave. To do so, we study the notion of game form. Game forms arethe mathematical objects that describe the (local) interactions of the players at each state of a concurrent game. Game forms are defined by a set of local strategies per player, a set of outcomes and a function mapping a pair of one local strategy per player to a probability distribution over outcomes. Generally,in the literature on concurrent games, local interactions are standard (finite)game forms: the sets of local strategies are distributions over underlying (finite) sets of actions. In this dissertation, we define and study more general gameforms, which we call arbitrary game forms. Some of the results we prove hold even with arbitrary local interactions, the others use a standard assumption onthe local interactions involved.First, we prove general results on concurrent games, with very few assumptions on the payoff functions and local interactions involved. In particular, we consider a crucial result on concurrent games: Martin's result on Blackwell determinacy, which can be stated as follows. Consider a concurrent game whereall local interactions are standard finite. From each state, there is a value u in[0, 1] such that Player A's (resp. B's) strategies can guarantee that the expected value of the measurable payoff function is above (resp. below) any threshold below (resp. above) u. We generalize this result to games with arbitrary gameforms. We deduce from this generalization other results on concurrent games,possibly using standard local interactions, which could not have been obtained directly from the original result by Martin. We also prove other results on concurrent games, in particular results related to subgame optimal strategies.Second, we study how finite-state concurrent parity games behave in termsof existence and nature of (almost and/or subgame) optimal strategies, with very few assumptions on the local interactions involved.Third, we define subsets of concurrent games that enjoy some of the nice properties of turn-based games while being more general than turn-based games.These subsets are constructed via local-global transfers, which is a novel approach. Specifically, given a desirable property on concurrent games, we first characterize the game forms that ensure that all simple games using them aslocal interactions satisfy this property. Thus, we characterize the game formsthat behave well individually. We then show that all concurrent games that use these game forms as local interactions also satisfy this property. Thus, we show that these game forms also behave well collectively, hence globally

Ce travail se concentre sur l'étude de jeux joués sur des graphes finis, parun nombre arbitraire de joueurs, dont les objectifs ne sont pas antagonistes.Chaque joueur représente un agent, c'est-à-dire un programme, un processus,ou un périphérique, qui interagit avec les autres joueurs et leurenvironnement commun dans le but de satisfaire au mieux son objectifindividuel.Des concepts telsque les équilibres de Nash, permettant d'exprimer l'optimalité des stratégiesdes joueurs, ont été étudiés dans un cadre déterministe, et l'existencede tels équilibres n'est pas assurée, même lorsque les objectifs des joueurssont de simples conditions d'accessibilité ou de sûreté. En effet, lorsqueles joueurs jouent de manière déterministe, le système évolue en conservantune certaine symmétrie, ce qui nous motive à considérer un modèle stochastiqueoù les joueurs et l'environnement sont sources d'aléa. Dans le premier cas,nous montrons que les concepts classiques d'équilibres de Nash ne peuventêtre calculés, et introduisons des notions approchées d'équilibrescalculables. Dans le deuxième cas, nous nous intéressons à l'analyse desystèmes composés d'un nombre arbitraires de processus, dont l'éxécutionest déterminée par un ordonnanceur, c'est-à-dire l'environnement,probabiliste
We study games played on graphs by an arbitrary number of players withnon-zero sum objectives. The players representagents (programs, processes or devices) that can interact to achieve their ownobjectives as much as possible. Solution concepts, as Nash Equilibrium, forsuch optimal plays,need not exist when restricting topure deterministic strategies, even with simple reachability or safetyobjectives. The symmetry induced by deterministic behavioursmotivates the studies where eitherthe players or the environment can use randomization. In the first case, weshow that classical concepts are undecidable with a fixednumber of agents and propose computable approximations.In the second case, we studyrandomization as a reasonable policy for scheduling an arbitrary number ofprocesses

Cette thèse étudie l’évolution des marchés du gaz naturel en Europe jusqu’en 2035 en utilisant les outils de la modélisation. Le modèle proposé, intitulé GaMMES, repose sur une description oligopolistique des marchés et ses principaux avantages sont les suivants : un niveau de détail important de la structure économique de la chaîne gazière et une prise en compte endogène des contrats de long-terme en amont ainsi que de la substitution avec les produits pétroliers et le charbon, au niveau de la demande. Dans un premier temps, nous étudions la question de la sécurité d’approvisionnement en gaz en Europe et les conditions favorables à la régulation des marchés vulnérables au risque de rupture d’approvisionnement, notamment de la part de la Russie. Trois études de cas sont proposées selon le degré de dépendance et la nature de régulation en place : le marché allemand des années 1980 et les marchés actuels de la Bulgarie et de l’Espagne. Nous étudions en particulier l’évolution des caractéristiques des marchés en fonction du risque de rupture et le type de régulation à mettre en place afin d’assurer l’optimalité du bien-être social. Ensuite, nous proposons un modèle de type systèmes dynamiques afin de prendre en compte la substitution énergétique entre le charbon, le pétrole et le gaz naturel. Notre approche permet d’estimer une nouvelle forme fonctionnelle de la fonction de demande pour le gaz naturel, qui englobe à la fois la substitution énergétique et les inerties de consommation dues aux investissements des usagers finaux. Dans un troisième temps, nous utilisons cette fonction de demande dans un modèle d’équilibre partiel des marchés du gaz naturel en Europe. Le modèle GaMMES, écrit sous forme de problème de complémentarité, représente les principaux acteurs de l’industrie du gaz naturel en considérant leurs interactions stratégiques et les pouvoirs de marchés. Il a été appliqué au marché du gaz naturel en Europe du nord-est afin d’étudier l’évolution, jusqu’en 2035, de la consommation, des prix spot, des prix et volumes long-terme, de la production et de la dépendance par rapport aux imports étrangers. Finalement, nous proposons une extension stochastique du modèle GaMMES afin d’analyser l’impact de la forte fluctuation du prix du Brent sur les marchés gaziers. Une étude économétrique a été menée afin de calculer la loi de probabilité du prix du pétrole, lorsqu’il est modélisé en tant que variable aléatoire, dans le but de construire et pondérer l’arbre des scénarii. Les résultats permettent de comprendre comment l’aléa modifie les comportements stratégiques des acteurs, notamment au niveau des contrats de long-terme. Enfin, la valeur de la solution stochastique est calculée afin de quantifier l’importance de la prise en compte des fluctuations du prix du pétrole pour chaque acteur de la chaîne
This thesis studies the evolution of the natural gas markets in Europe, until 2035, using optimization theory tools. The model we develop, named GaMMES, is based on an oligopolistic description of the markets. Its main advantages are the following: we consider an important level of detail in the economic structure of the gas chain and we endogenously take into account long-term contracts in the upstream as well as energy substitution between gas, oil, and coal in the demand. In the first part of this thesis, we study the issue of security of supply in Europe and the conditions under which it is necessary to regulate the gas markets that are strongly dependent on foreign imports. Three case studies are then presented, regarding the level of dependence and the markets' specificities: the German gas trade of the 1980s and the current Spanish and Bulgarian markets. We study in particular the evolution of the markets' outcome as a function of the supply disruption probability and the kind of regulation to implement in order to maximize the social welfare. In the second part, we develop a system dynamics model in order to capture fuel substitution between oil, coal, and natural gas. Our approach allows one to calculate a new functional form of the demand function for natural gas that contains energy substitution and consumption inertia effects due to end-users' investments. In the third part, we take advantage of our demand function and use it in a partial equilibrium model of natural gas markets in Europe. The GaMMES model, when written as a complementarity problem, describes the principal gas chain actors as well as their strategic interactions and market power. It was applied to the northwestern European gas trade to analyze the evolution of consumption, spot and long-term contract prices and volumes, production, and natural gas dependence, until 2035. In the last part, we present a stochastic extension of the GaMMES model in order to study the impact of the strong Brent price fluctuation on the gas markets. An econometric analysis allowed us to calculate the probability law of the oil price, when taken as a random variable, in order to construct the scenario tree and estimate its weights. Our results show how uncertainty changes the strategic behavior, in particular for the long-term contracting activity. Finally, the value of the stochastic solution is calculated to quantify the importance of taking into account randomness in the optimization programs of the gas chain actors

AbstractGame-theoretic techniques and equilibria analysis facilitate the design and verification of competitive systems. While algorithmic complexity of equilibria computation has been extensively studied, practical implementation and application of game-theoretic methods is more recent. Tools such as PRISM-games support automated verification and synthesis of zero-sum and ($$\varepsilon $$ ε -optimal subgame-perfect) social welfare Nash equilibria properties for concurrent stochastic games. However, these methods become inefficient as the number of agents grows and may also generate equilibria that yield significant variations in the outcomes for individual agents. We extend the functionality of PRISM-games to support correlated equilibria, in which players can coordinate through public signals, and introduce a novel optimality criterion of social fairness, which can be applied to both Nash and correlated equilibria. We show that correlated equilibria are easier to compute, are more equitable, and can also improve joint outcomes. We implement algorithms for both normal form games and the more complex case of multi-player concurrent stochastic games with temporal logic specifications. On a range of case studies, we demonstrate the benefits of our methods.

AbstractWe investigate concurrent two-player win/lose stochastic games on finite graphs with prefix-independent objectives. We characterize subgame optimal strategies and use this characterization to show various memory transfer results: 1) For a given (prefix-independent) objective, if every game that has a subgame almost-surely winning strategy also has a positional one, then every game that has a subgame optimal strategy also has a positional one; 2) Assume that the (prefix-independent) objective has a neutral color. If every turn-based game that has a subgame almost-surely winning strategy also has a positional one, then every game that has a finite-choice (notion to be defined) subgame optimal strategy also has a positional one.We collect or design examples to show that our results are tight in several ways. We also apply our results to Büchi, co-Büchi, parity, mean-payoff objectives, thus yielding simpler statements.

Rational verification is the problem of determining which temporal logic properties will hold in a multi-agent system, under the assumption that agents in the system act rationally, by choosing strategies that collectively form a game-theoretic equilibrium. Previous work in this area has largely focussed on deterministic systems. In this paper, we develop the theory and algorithms for rational verification in probabilistic systems. We focus on concurrent stochastic games (CSGs), which can be used to model uncertainty and randomness in complex multi-agent environments. We study the rational verification problem for both non-cooperative games and cooperative games in the qualitative probabilistic setting. In the former case, we consider LTL properties satisfied by the Nash equilibria of the game and in the latter case LTL properties satisfied by the core. In both cases, we show that the problem is 2EXPTIME-complete, thus not harder than the much simpler verification problem of model checking LTL properties of systems modelled as Markov decision processes (MDPs).