This paper defines the framework of hypergraphical Bayesian games, which allows to concisely specify Bayesian games with local interactions. This framework generalizes both normal-form Bayesian games and hypergraphical games (including polymatrix games). Establishing a generalization of Howson and Rosenthal's Theorem, we show that hypergraphical Bayesian games can be transformed, in polynomial time, into equivalent complete-information hypergraphical games. This result has several consequences. It involves that finding an$\varepsilon$-Nash equilibrium in a hypergraphical Bayesian game or an exact mixed Nash equilibrium in a polymatrix Bayesian game is PPAD-complete, while checking the existence of a pure Nash equilibrium defines a NP-complete problem. It also allows to make use of existing solution algorithms for hypergraphical games to solve hypergraphical and standard normal form Bayesian games.

Graphical games allow to concisely represent games where the utility received by each player depends on strategies played by a (hopefully small) subset of the players only. Recently, Graphical Ordinal Games have been proposed as a framework for game theory where utility degrees are ordinal. The concept of probabilistic mixed-Nash equilibrium is irrelevant in this framework since ordinal utility degrees cannot be averaged. Instead, possibilistic mixed equilibria have been proposed as a principled solution concept in such games. A generic possibilistic mixed equilibrium computation algorithm has been proposed, which applies to ordinal games, be they in standard normal form or graphical form. However, this algorithm only computes a single least-specific equilibrium. When analyzing ordinal games, one may be interested in finding every least-specific equilibria or in counting them. In this paper, we propose two original algorithms for computing all least-specific possibilistic mixed equilibria in Ordinal Graphical games. We first focus on tree-structured Ordinal Graphical Games and propose the Possibilistic Tree-Nash algorithm (-Tree-Nash), a possibilistic counterpart of the Tree-Nash algorithm proposed by Kearns et al. for (cardinal) graphical games. Then, we propose the Search All Equilibria algorithm (SAE) which computes all least-specific mixed equilibria of an arbitrary Ordinal Graphical Game. We provide algorithmic complexity results as well as an experimental evaluation of both algorithms.

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.

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.

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.

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.

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.

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.

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).

In conservation biology and natural resource management, adaptive management is an iterative process of improving management by reducing uncertainty via monitoring. Adaptive management is the principal tool for conserving endangered species under global change, yet adaptive management problems suffer from a poor suite of solution methods. The common approach used to solve an adaptive management problem is to assume the system state is known and the system dynamics can be one of a set of pre-defined models. The solution method used is unsatisfactory, employing value iteration on a discretized belief MDP which restricts the study to very small problems. We show how to overcome this limitation by modelling an adaptive management problem as a restricted Mixed Observability MDP called hidden model MDP (hmMDP). We demonstrate how to simplify the value function, the backup operator and the belief update computation. We show that, although a simplified case of POMDPs, hm-MDPs are PSPACE-complete in the finite-horizon case. We illustrate the use of this model to manage a population of the threatened Gouldian finch, a bird species endemic to Northern Australia. Our simple modelling approach is an important step towards efficient algorithms for solving adaptive management problems.

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.

We propose a framework and algorithms for reinforcement learning in sequential decision problems under uncertainty in which the rewards are qualitative, and/or are temporarily aggregated by a "minimum" instead of a sum as in the classical Markov decision processes framework. The framework is based on a "possibilistic" version of Markov decision processes and the learning algorithms are based on indirect methods in which the possibilistic model of the problem is learned while the problem itself is solved, using dynamic programming.

This paper describes a logical machinery for computing decisions, where the available knowledge on the state of the world is described by a possibilistic propositional logic base (i.e., a collection of logical statements associated with qualitative c