Author name cluster

Marie van den Bogaard

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

2 author rows

MFCS Conference 2023 Conference Paper

Rational Verification for Nash and Subgame-Perfect Equilibria in Graph Games

Léonard Brice
Jean-François Raskin
Marie van den Bogaard

We study a natural problem about rational behaviors in multiplayer non-zero-sum sequential infinite duration games played on graphs: rational verification, that consists in deciding whether all the rational answers to a given strategy satisfy some specification. We give the complexities of that problem for two major concepts of rationality: Nash equilibria and subgame-perfect equilibria, and for three major classes of payoff functions: energy, discounted-sum, and mean-payoff.

Details

Highlights Conference 2022 Conference Abstract

On the Complexity of SPEs in Parity Games

Marie van den Bogaard

In this talk, we present the main ideas behind solving the constrained existence problem for Subgame Perfect Equilibria in multiplayer parity games. We present new complexity results that close gaps in the literature. Our techniques are based on a recent characterization of SPEs in prefix-independent games that is grounded on the notions of requirements and negotiation, and according to which the plays supported by SPEs are exactly the plays consistent with the requirement that is the least fixed point of the negotiation function. The new results are as follows. First, checking that a given requirement is a fixed point of the negotiation function is an NP-complete problem. Second, we show that the SPE constrained existence problem is NP-complete, this problem was previously known to be ExpTime-easy and NP-hard. This talk is based on results obtained in a joint work with Léonard Brice and Jean-François Raskin (Universit\'e libre de Bruxelles), presented at CSL this year.

Details

CSL Conference 2022 Conference Paper

On the Complexity of SPEs in Parity Games

Léonard Brice
Jean-François Raskin
Marie van den Bogaard

We study the complexity of problems related to subgame-perfect equilibria (SPEs) in infinite duration non zero-sum multiplayer games played on finite graphs with parity objectives. We present new complexity results that close gaps in the literature. Our techniques are based on a recent characterization of SPEs in prefix-independent games that is grounded on the notions of requirements and negotiation, and according to which the plays supported by SPEs are exactly the plays consistent with the requirement that is the least fixed point of the negotiation function. The new results are as follows. First, checking that a given requirement is a fixed point of the negotiation function is an NP-complete problem. Second, we show that the SPE constrained existence problem is NP-complete, this problem was previously known to be ExpTime-easy and NP-hard. Third, the SPE constrained existence problem is fixed-parameter tractable when the number of players and of colors are parameters. Fourth, deciding whether some requirement is the least fixed point of the negotiation function is complete for the second level of the Boolean hierarchy. Finally, the SPE-verification problem - that is, the problem of deciding whether there exists a play supported by a SPE that satisfies some LTL formula - is PSpace-complete, this problem was known to be ExpTime-easy and PSpace-hard.

Details

CSL Conference 2018 Conference Paper

Beyond Admissibility: Dominance Between Chains of Strategies

Nicolas Basset
Ismaël Jecker
Arno Pauly
Jean-François Raskin
Marie van den Bogaard

Admissible strategies, i. e. those that are not dominated by any other strategy, are a typical rationality notion in game theory. In many classes of games this is justified by results showing that any strategy is admissible or dominated by an admissible strategy. However, in games played on finite graphs with quantitative objectives (as used for reactive synthesis), this is not the case. We consider increasing chains of strategies instead to recover a satisfactory rationality notion based on dominance in such games. We start with some order-theoretic considerations establishing sufficient criteria for this to work. We then turn our attention to generalised safety/reachability games as a particular application. We propose the notion of maximal uniform chain as the desired dominance-based rationality concept in these games. Decidability of some fundamental questions about uniform chains is established.

Details

Highlights Conference 2018 Conference Abstract

Beyond Admissibility: Rationality in Quantitative Games

Marie van den Bogaard

ABSTRACT. When modelling interactive scenarios with games played on nite graphs, one can face the situation that a player has no winning strategy, that is, no behaviour that allows her to attain her objective regardless of the behaviours of the other players. In such cases, one may wonder what constitutes a rational behaviour. In the boolean setting, admissi- bility has been shown to be a good criterion for rationality: indeed, an admissible strategy is a strategy that is not dominated: no other strategy would yield a better outcome against every behaviour of the other players. Furthermore, each strategy is either admissible or dominated by an admissible strategy. This property is fundamental in the sense that for any behaviour, there always exists a corresponding rational behaviour. This fundamental property does not hold anymore in the quantitative setting. We show that by switching from judging each individual strategy as rational or not to considering families of strategies that share a common behaviour pattern, we can recover a satisfactory rationality notion. Finally, we exhibit a sucient condition for a game to satisfy a similar fundamental property lifted to family of strategies.

Details

Highlights Conference 2015 Conference Abstract

Consensus game acceptors

Marie van den Bogaard

We present a game for recognising formal languages, in which two players with imperfect information need to coordinate on a common decision, given private input strings correlated by a finite graph. The players have a joint objective to avoid an inadmissible decision, in spite of the uncertainty induced by the input. We show that the acceptor model based on consensus games characterises context-sensitive languages, and conversely, that winning strategies in such games can be described by context-sensitive languages. We also discuss consensus game acceptors with a restricted observation pattern that describe nondeterministic linear-time languages. Joint work with Dietmar Berwanger. To appear in DLT 2015.

Details