Régis Sabbadin

AAMAS Conference 2026 Conference Paper

Efficiently Computing Approximate Nash Equilibria in Multi-Adversarial Team Games

• Prasanna Maddila
• Régis Sabbadin
• Meritxell Vinyals

Adversarial Team Games (ATG), as introduced by von Stengel and Koller, model strategic interactions in which a team of agents – sharing a common objective but unable to coordinate their actions – faces a single adversary. While computing an exact Nash Equilibrium (NE) in ATGs has been shown to be CLS-complete, a fully polynomial-time approximation scheme (FPTAS) has been developed, enabling the efficient computation of approximate NE in time polynomial in both the natural parameters of the game and the inverse of the approximation error. However, existing results only apply to single-adversary scenarios, leaving the common case of multiple independent adversaries — prevalent in applications such as anti-poaching, robotic planning, and hider-seeker games — largely unexplored. This paper bridges this gap by introducing the Multi-Adversarial Team Game (MATG) framework, a natural generalization of ATGs to scenarios involving several independent adversaries. Our main contribution is to generalize techniques from the single-adversary setting to develop an FPTAS for computing NE in the more general class of MATGs. Beyond our theoretical contributions, we present the first empirical evaluation of this family of algorithms in both ATGs and MATGs, demonstrating the scalability to many adversaries.

EWRL Workshop 2024 Workshop Paper

APE: An Anti-poaching Multi-Agent Reinforcement Learning Benchmark

• Prasanna Maddila
• Casellas Eric
• Patrick Chabrier
• Régis Sabbadin
• Meritxell Vinyals

Widespread poaching threatens many endangered species today, requiring robust strategies to coordinate ranger patrols and effectively deter poachers within protected areas. Recent research has modeled this problem as a strategic game between rangers and poachers, resulting in anti-poaching becoming a popular application domain within game theory and multi-agent research communities. Unfortunately, the lack of a standard open-source implementation of the anti-poaching game hinders the reproducibility and advancement of current research in the field. This paper aims to fill this gap by providing the first open-source standardised environment for the anti-poaching game. Our contributions are as follows: (1) we formalise anti-poaching as a Partially Observable Stochastic Game; (2) we provide the Anti-Poaching Environment (APE), an open-source Python implementation of a simulator for this game using the PettingZoo API, which is compatible with many existing multi-agent reinforcement learning (MARL) libraries; and (3) we illustrate how to apply deep reinforcement-learning algorithms from the RLlib library, in order to compute cooperative and cooperative-competitive equilibria of APE instances.

AAMAS Conference 2022 Conference Paper

A Path-following Polynomial Equations Systems Approach for Computing Nash Equilibria

• Hélène Fargier
• Paul Jourdan
• Régis Sabbadin

This paper presents a path-following combinatorial framework based on systems of polynomial equations to compute a mixed Nash equilibrium in 𝑁-person games. We provide the first detailed implementable description of Wilson’s path-following method, extending Lemke-Howson’s algorithm to N-person games and handling degenerate games. Our approach resembles, in some respects, support enumeration methods. We thus compare both approaches, theoretically and experimentally. Then, we show that the pathfollowing approach allows to deal with a large family of succinctly expressed games: hypergraphical games, graphical games and polymatrix games. The described algorithms have been implemented in Python, making use of Sagemath libraries to solve systems of polynomial equations, allowing an experimental comparison of the different combinatorial approaches on a large variety of games.

KR Conference 2020 Conference Paper

Ordinal Polymatrix Games with Incomplete Information

• Nahla Ben Amor
• Hélène Fargier
• Régis Sabbadin
• Meriem Trabelsi

Possibilistic games with incomplete information (Π-games) constitute a suitable framework for the representation of ordinal games under incomplete knowledge. However, representing a Π-game in standard normal form requires an extensive expression of the utility functions and the possibility distribution, namely, on the product spaces of actions and types. In the present work, we propose a less costly view of Π-games, namely min-based polymatrix Π-games, which allows to concisely specify Π-games with local interactions. This framework allows, for instance, the compact representation of coordination games under uncertainty where the satisfaction of an agent is high if and only if her strategy is coherent with all of her neighbors, the game being possibly only incompletely known to the agents. Then, an important result of this paper is to show that a min-based polymatrix Π-game can be transformed, in polynomial time, into a (complete information) min-based polymatrix game with identical pure Nash equilibria. Finally, we show that the latter family of games can be solved through a MILP formulation. Experiments on variants of the GAMUT problems confirm the feasibility of this approach.

IJCAI Conference 2019 Conference Paper

Possibilistic Games with Incomplete Information

• Nahla Ben Amor
• Helene Fargier
• Régis Sabbadin
• Meriem Trabelsi

Bayesian games offer a suitable framework for games where the utility degrees are additive in essence. This approach does nevertheless not apply to ordinal games, where the utility degrees do not capture more than a ranking, nor to situations of decision under qualitative uncertainty. This paper proposes a representation framework for ordinal games under possibilistic incomplete information (π-games) and extends the fundamental notion of Nash equilibrium (NE) to this framework. We show that deciding whether a NE exists is a difficult problem (NP-hard) and propose a Mixed Integer Linear Programming (MILP) encoding. Experiments on variants of the GAMUT problems confirm the feasibility of this approach.

IJCAI Conference 2017 Conference Paper

Equilibria in Ordinal Games: A Framework based on Possibility Theory.

• Nahla Ben Amor
• Helene Fargier
• Régis Sabbadin

The present paper proposes the first definition of mixed equilibrium for ordinal games. This definition naturally extends possibilistic (single agent) decision theory. This allows us to provide a unifying view of single and multi-agent qualitative decision theory. Our first contribution is to show that ordinal games always admit a possibilistic mixed equilibrium, which can be seen as a qualitative counterpart to mixed (probabilistic) equilibrium. Then, we show that a possibilistic mixed equilibrium can be computed in polynomial time (wrt the size of the game), which contrasts with pure Nash or mixed probabilistic equilibrium computation in cardinal game theory. The definition we propose is thus operational in two ways: (i) it tackles the case when no pure Nash equilibrium exists in an ordinal game; and (ii) it allows an efficient computation of a mixed equilibrium.

ECAI Conference 2016 Conference Paper

Leader-Follower MDP Models with Factored State Space and Many Followers - Followers Abstraction, Structured Dynamics and State Aggregation

• Régis Sabbadin
• Anne-France Viet

The Leader-Follower Markov Decision Processes (LF-MDP) framework extends both Markov Decision Processes (MDP) and Stochastic Games. It provides a model where an agent (the leader) can influence a set of other agents (the followers) which are playing a stochastic game, by modifying their immediate reward functions, but not their dynamics. It is assumed that all agents act selfishly and try to optimize their own long-term expected reward. Finding equilibrium strategies in a LF-MDP is hard, especially when the joint state space of followers is factored. In this case, it takes exponential time in the number of followers. Our theoretical contribution is threefold. First, we analyze a natural assumption (substitutability of followers), which holds in many applications. Under this assumption, we show that a LF-MDP can be solved exactly in polynomial time, when deterministic equilibria exist for all games encountered in the LF-MDP. Second, we show that an additional assumption of sparsity of the problem dynamics allows us to decrease the exponent of the polynomial. Finally, we present a state-aggregation approximation, which decreases further the exponent and allows us to approximately solve large problems. We empirically validate the LF-MDP approach on a class of realistic animal disease control problems. For problems of this class, we find deterministic equilibria for all games. Using our first two results, we are able to solve the exact LF-MDP problem with 15 followers (compared to 6 or 7 in the original model). Using state-aggregation, problems with up to 50 followers can be solved approximately. The approximation quality is evaluated by comparison with the exact approach on problems with 12 and 15 followers.

ECAI Conference 2016 Conference Paper

Lexicographic Refinements in Possibilistic Decision Trees

• Nahla Ben Amor
• Zeineb El Khalfi
• Hélène Fargier
• Régis Sabbadin

Possibilistic decision theory has been proposed twenty years ago and has had several extensions since then. Because of the lack of decision power of possibilistic decision theory, several refinements have then been proposed. Unfortunately, these refinements do not allow to circumvent the difficulty when the decision problem is sequential. In this article, we propose to extend lexicographic refinements to possibilistic decision trees. We show, in particular, that they still benefit from an Expected Utility (EU) grounding. We also provide qualitative dynamic programming algorithms to compute lexicographic optimal strategies. The paper is completed with an experimental study that shows the feasibility and the interest of the approach.

ICAPS Conference 2015 Conference Paper

An Online Replanning Approach for Crop Fields Mapping with Autonomous UAVs

• Alexandre Albore
• Nathalie Peyrard
• Régis Sabbadin
• Florent Teichteil-Königsbuch

For managing production at the scale of crop fields, maps of plant pests are used to support farmer decisions. Such maps are costly to obtain since they require intensive surveys in the field, most of the time performed by human annotators or with human-controlled Unmanned Aerial Vehicles (UAVs). In this paper, we look at the next challenge from an AI planning point of view: flying fully autonomous UAVs equipped with online sequential decision-making capabilities for pests sampling and mapping in crop fields. Following existing work, we use a Markov Random Field framework to represent knowledge about the uncertain map and its quality, in order to compute an optimised pest-sampling policy. Since this planning problem is Pspace hard, thus too hard to be exactly solved either offline or online, we propose an approach interleaving planning and execution, inspired by recent works on fault-tolerant planning. From past observations at a given time step, we compute a full plan consisting in a sequence of observed locations and expected observations untill the end of the pest-sampling phase. The plan is then applied until the number of actual observations that differ from expected ones exceeds a given threshold, which triggers a new replanning episode. Our planning method favourably compares on the problem of weed map construction against an existing greedy approach - the only one working online - while adding the advantage of being adapted to the autonomous UAVs' flying time constraints.

ECAI Conference 2014 Conference Paper

Finding good stochastic factored policies for factored Markov decision processes

• Julia Radoszycki
• Nathalie Peyrard
• Régis Sabbadin

We propose a framework for approximate resolution of MDPs with factored state space, factored action space and additive reward, based on (i) considering stochastic factored policies (SFPs) with a given structure, (ii) using variational approximations to estimate SFP values and (iii) using local continuous optimization algorithms to compute "good" SFPs. We have implemented and tested an algorithm (CA-LBP), involving a loopy belief propagation algorithm and a coordinate ascent procedure. Experiments show that CA-LBP performs as well as a state-of-the-art algorithm dedicated to a specific sub-class of FA-FMDPs, and that CA-LBP can be applied to general FA-FMDPs with up to 100 binary state variables and 100 binary action variables.

AAAI Conference 2013 Conference Paper

A Tractable Leader-Follower MDP Model for Animal Disease Management

• Régis Sabbadin
• Anne-France Viet

Sustainable animal disease management requires to design and implement control policies at the regional scale. However, for diseases which are not regulated, individual farmers are responsible for the adoption and successful application of control policies at the farm scale. Organizations (groups of farmers, health institutions. ..) may try to influence farmers’ control actions through financial incentives, in order to ensure sustainable (from the health and economical point of views) disease management policies. Economics / Operations Research frameworks have been proposed for modeling the effect of incentives on agents. The Leader-Follower Markov Decision Processes framework is one such framework, that combines Markov Decision Processes (MDP) and stochastic games frameworks. However, since finding equilibrium policies in stochastic games is hard when the number of players is large, LF-MDP problems are intractable. Our contribution, in this article, is to propose a tractable model of the animal disease management problem. The tractable model is obtained through a few simple modeling approximations which are acceptable when the problem is viewed from the organization side. As a result, we design a polynomial-time algorithm for animal disease management, which we evaluate on a case study inspired from the problem of controlling the spread of the Porcine Reproductive and Respiratory Syndrome (PRRS). Content Area: Animal infectious disease management.

ECAI Conference 2012 Conference Paper

A Reinforcement-Learning Algorithm for Sampling Design in Markov Random Fields

• Mathieu Bonneau
• Nathalie Peyrard
• Régis Sabbadin

Optimal sampling in spatial random fields is a complex problem, which mobilizes several research fields in spatial statistics and artificial intelligence. In this paper we consider the case where observations are discrete-valued and modelled by a Markov Random Field. Then we encode the sampling problem into the Markov Decision Process (MDP) framework. After exploring existing heuristic solutions as well as classical algorithms from the field of Reinforcement Learning (RL), we design an original algorithm, LSDP (Least Square Dynamic Programming), which uses simulated trajectories to solve approximately any finite-horizon MDP problem. Based on an empirical study of the behaviour of these different approaches on binary models, we derive the following conclusions: i) a naï ve heuristic, consisting in sampling sites where marginals are the most uncertain, is already an efficient sampling approach; ii) LSDP outperforms all the classical RL approaches we have tested; iii) LSDP outperforms the heuristic in cases when reconstruction errors have a high cost, or sampling actions are constrained. In addition, LSDP readily handles action costs in the optimisation problem, as well as cases when some sites of the MRF can not be observed.

ECAI Conference 2010 Conference Paper

Decision-theoretic Optimal Sampling in Hidden Markov Random Fields

• Nathalie Peyrard
• Régis Sabbadin
• U. Farrokh Niaz

Computation of the Most Probable Explanation (MPE) when probabilistic knowledge is expressed as a factored distribution is a classical AI reasoning problem: complete evidence is available about the values of some of the variables which are observed, and the problem consists in finding the most probable assignment of the remaining variables given the evidence. However, optimising the choice of the variables to observe (the sample) in order to maximise the MPE probability is a less classical and more difficult problem. In this article we tackle this question of optimal sampling in structured problems under limited budget, within the framework of Hidden Markov Random Fields (HMRF). The value of a sample (which we seek to optimise) is the expectation, over all possible sample outputs (observations), of the MPE probability. The contributions of this article are: i) an original probabilistic model for optimal sampling in HMRF ii) computational complexity results about this problem, leading in particular to approximability/inapproximability results and iii) an exact solution algorithm and two approximate solution algorithms of decreasing time complexity, which we empirically evaluate on a problem of spatial sampling for occurrence map restoration.

AIJ Journal 2008 Journal Article

Complexity results and algorithms for possibilistic influence diagrams

• Laurent Garcia
• Régis Sabbadin

In this article we present the framework of Possibilistic Influence Diagrams (PID), which allows to model in a compact form problems of sequential decision making under uncertainty, when only ordinal data on transitions likelihood or preferences are available. The graphical part of a PID is exactly the same as that of usual influence diagrams, however the semantics differ. Transition likelihoods are expressed as possibility distributions and rewards are here considered as satisfaction degrees. Expected utility is then replaced by anyone of the two possibilistic qualitative utility criteria (optimistic and pessimistic) for evaluating strategies in a PID. We then describe decision tree-based methods for evaluating PID and computing optimal strategies and we study the computational complexity of PID optimisation problems for both cases. Finally, we propose a dedicated variable elimination algorithm that can be applied to both optimistic and pessimistic cases for solving PID.

AAAI Conference 2007 Conference Paper

Purely Epistemic Markov Decision Processes

• Régis Sabbadin

Planning under uncertainty involves two distinct sources of uncertainty: uncertainty about the effects of actions and uncertainty about the current state of the world. The most widely developed model that deals with both sources of uncertainty is that of Partially Observable Markov Decision Processes (POMDPs). Simplifying POMDPs by getting rid of the second source of uncertainty leads to the well-known framework of fully observable MDPs. Getting rid of the first source of uncertainty leads to a less widely studied framework, namely, decision processes where actions cannot change the state of the world and are only intended to bring some information about the (static) state of the world. Such “purely epistemic” processes are very relevant, since many practical problems (such as diagnosis, database querying, or preference elicitation) fall into this class. However, it is not known whether this specific restriction of POMDP is computationally simpler than POMDPs. In this paper we establish several complexity results for purely epistemic MDPs (EMDPs). We first show that short-horizon policy existence in EMDPs is PSPACE-complete. Then we focus on the specific case of EMDPs with reliable observations and show that in this case, policy existence is “only” NP-complete; however, we show that this problem cannot be approximated with a bounded performance ratio by a polynomial-time algorithm.

ECAI Conference 2006 Conference Paper

Approximate Linear-Programming Algorithms for Graph-Based Markov Decision Processes

• Nicklas Forsell
• Régis Sabbadin

In this article, we consider a form of compact representation of MDP based on graphs, and we propose an approximate solution algorithm derived from this representation. The approach we propose belongs to the family of Approximate Linear Programming methods, but the graph-structure we assume allows it to become particularly efficient. The proposed method complexity is linear in the number of variables in the graph and only exponential in the width of a dependency graph among variables.

ECAI Conference 2006 Conference Paper

Mean Field Approximation of the Policy Iteration Algorithm for Graph-Based Markov Decision Processes

• Nathalie Peyrard
• Régis Sabbadin

In this article, we consider a compact representation of multidimensional Markov Decision Processes based on Graphs (GMDP). The states and actions of a GMDP are multidimensional and attached to the vertices of a graph allowing the representation of local dynamics and rewards. This approach is in the line of approaches based on Dynamic Bayesian Networks. For policy optimisation, a direct application of the Policy Iteration algorithm, of exponential complexity in the number of nodes of the graph, is not possible for such high dimensional problems and we propose an approximate version of this algorithm derived from the GMDP representation. We do not try to approximate directly the value function, as usually done, but we rather propose an approximation of the occupation measure of the model, based on the mean field principle. Then, we use it to compute the value function and derive approximate policy evaluation and policy improvement methods. Their combination yields an approximate Policy Iteration algorithm of linear complexity in terms of the number of nodes of the graph. Comparisons with the optimal solution, when available, and with a naive short-term policy demonstrate the quality of the proposed procedure.

ECAI Conference 2006 Conference Paper

Possibilistic Influence Diagrams

• Laurent Garcia
• Régis Sabbadin

In this article we present the framework of Possibilistic Influence Diagrams (PID), which allow to model in a compact form problems of sequential decision making under uncertainty, when only ordinal data on transitions likelihood or preferences are available. The graphical part of a PID is exactly the same as that of usual influence diagrams, however the semantics differ. Transition likelihoods are expressed as possibility distributions and rewards are here considered as satisfaction degrees. Expected utility is then replaced by anyone of two possibilistic qualitative utility criteria for evaluating strategies in a PID. We describe a decision tree-based method for evaluating PID and computing optimal strategies. We then study the computational complexity of PID-related problems (computation of the value of a policy, computation of an optimal policy).

AIJ Journal 2005 Journal Article

Qualitative decision under uncertainty: back to expected utility

• Hélène Fargier
• Régis Sabbadin

Different qualitative models have been proposed for decision under uncertainty in Artificial Intelligence, but they generally fail to satisfy the principle of strict Pareto dominance or principle of “efficiency”, in contrast to the classical numerical criterion—expected utility. Among the most prominent examples of qualitative models are the qualitative possibilistic utilities (QPU) and the order of magnitude expected utilities (OMEU). They are both appealing but inefficient in the above sense. The question is whether it is possible to reconcile qualitative criteria and efficiency. The present paper shows that the answer is yes, and that it leads to special kinds of expected utilities. It is also shown that although numerical, these expected utilities remain qualitative: they lead to different decision procedures based on min, max and reverse operators only, generalizing the leximin and leximax orderings of vectors.

ECAI Conference 2002 Conference Paper

Graph partitioning techniques for Markov Decision Processes decomposition

• Régis Sabbadin

EAAI Journal 2001 Journal Article

Possibilistic Markov decision processes

• Régis Sabbadin

In this article we propose a synthesis of recent works concerning a qualitative approach, based on possibility theory, to multi-stage decision under uncertainty. Our framework is a qualitative possibilistic counterpart to Markov decision processes (MDP), for which we propose dynamic programming-like algorithms. The classical MDP algorithms and their possibilistic counterparts are then experimentally compared on a family of benchmark examples. Finally, we also explore the case of partial observability, thus providing qualitative counterparts to the partially observable Markov decision processes framework.

ECAI Conference 2000 Conference Paper

Empirical Comparison of Probabilistic and Possibilistic Markov Decision Processes Algorithms

• Régis Sabbadin

UAI Conference 1999 Conference Paper

A Possibilistic Model for Qualitative Sequential Decision Problems under Uncertainty in Partially Observable Environments

• Régis Sabbadin

In this article we propose a qualitative (ordinal) counterpart for the Partially Observable Markov Decision Processes model (POMDP) in which the uncertainty, as well as the preferences of the agent, are modeled by possibility distributions. This qualitative counterpart of the POMDP model relies on a possibilistic theory of decision under uncertainty, recently developed. One advantage of such a qualitative framework is its ability to escape from the classical obstacle of stochastic POMDPs, in which even with a finite state space, the obtained belief state space of the POMDP is infinite. Instead, in the possibilistic framework even if exponentially larger than the state space, the belief state space remains finite.

ECAI Conference 1998 Conference Paper

Decision As Abduction?

• Régis Sabbadin

UAI Conference 1998 Conference Paper

Qualitative Decision Theory with Sugeno Integrals

• Didier Dubois
• Henri Prade
• Régis Sabbadin

This paper presents an axiomatic framework for qualitative decision under uncertainty in a finite setting. The corresponding utility is expressed by a sup-min expression, called Sugeno (or fuzzy) integral. Technically speaking, Sugeno integral is a median, which is indeed a qualitative counterpart to the averaging operation underlying expected utility. The axiomatic justification of Sugeno integral-based utility is expressed in terms of preference between acts as in Savage decision theory. Pessimistic and optimistic qualitative utilities, based on necessity and possibility measures, previously introduced by two of the authors, can be retrieved in this setting by adding appropriate axioms.