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.

Conditional preference networks (CP-nets) are a compact but powerful formalism to represent and reason with qualitative preferences using the notion of conditional preferential independence. However, they suffer from incomparabilities between possible outcomes. Several works have attempted to overcome this weakness by quantifying CP-nets. This paper proposes a new approach combining two of the most interesting extensions of CP-nets, namely Probabilistic CP-nets (PCP-nets) using probability distribution to model uncertainty in different preference statements and Weighted CP-nets (WCP-nets) adding weights to express the relative importance of some attribute values regarding others. The new model so-called PWCP-nets combines the two models by handling both uncertainty and weights. Experimental results show the efficiency of this rich extension of CP-nets compared to PCP-nets and WCP-nets.

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.

A Probabilistic Conditional Preference network (PCP-net) provides a compact representation of preferences characterized with uncertainty. We propose to enrich the expressive power of the PCP-net by adding constraints between some of the variables. We call this new model, the Constrained PCP-net (CPCP-net). We study the key preference reasoning task with the proposed CPCP-net which consists in finding the most probable optimal outcome i.e. the most probable outcome that best represents the preferences while satisfying all the constraints. In this regard, a variant of the Branch and Bound algorithm has been proposed and experimentally evaluated on CPCP-net instances, randomly generated based on the RB-model. The results of these experiments show that the new proposed solving method is capable of returning the most probable optimal outcome in a reasonable time.

The use of possibilistic networks for representing conditional preference statements on discrete variables has been proposed only recently. The approach uses non-instantiated possibility weights to define conditional preference tables. Moreover, additional information about the relative strengths of these symbolic weights can be taken into account. The fact that at best we have some information about the relative values of these weights acknowledges the qualitative nature of preference specification. These conditional preference tables give birth to vectors of symbolic weights that reflect the preferences that are satisfied and those that are violated in a considered situation. The comparison of such vectors may rely on different orderings: the ones induced by the product-based, or the minimum-based chain rule underlying the possibilistic network, the discrimin, or leximin refinements of the minimum-based ordering, as well as Pareto ordering, and the symmetric Pareto ordering that refines it. A thorough study of the relations between these orderings in presence of vector components that are symbolic rather numerical is presented. In particular, we establish that the product-based ordering and the symmetric Pareto ordering coincide in presence of constraints comparing pairs of symbolic weights. This ordering agrees in the Boolean case with the inclusion between the sets of preference statements that are violated. The symmetric Pareto ordering may be itself refined by the leximin ordering. The paper highlights the merits of product-based possibilistic networks for representing preferences and provides a comparative discussion with CP-nets and OCF-networks.

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 validation of any database mining methodology goes through an evaluation process where benchmarks availability is essential. In this paper, we aim to randomly generate relational database benchmarks that allow to check probabilistic dependencies among the attributes. We are particularly interes ted in Probabilistic relational models (PRMs). These latter extend Bayesian networks (BNs) to a relational data mining context that enable effective and robust reasoning about relational data structures. Even though a panoply of works have focused, separately, on Bayesian networks and relational databases random generation, no work has been identified for PRMs on that track. This paper provides an algorithmic approach allowing to generate random PRMs from scratch to cover the absence of generation process. The proposed method allows to generate PRMs as well as synthetic relational data from a randomly generated relational schema and a random set of probabilistic dependencies. This can be of interest for machine learning researchers to evaluate their proposals in a common framework, as for databases designers to evaluate the effectiveness of the components of a database management system.

This paper raises the question of collective decisionmaking under possibilistic uncertainty; We study fouregalitarian decision rules and show that in the contextof a possibilistic representation of uncertainty, the useof an egalitarian collective utility function allows toget rid of the Timing Effect. Making a step further,we prove that if both the agents’ preferences and thecollective ranking of the decisions satisfy Dubois andPrade’s axioms (1995), and particularly risk aversion,and Pareto Unanimity, then the egalitarian collectiveaggregation is compulsory. This result can be seen asan ordinal counterpart of Harsanyi’s theorem (1955).

Manipulation becomes harder when manipulators are uncertain about the preferences of sincere voters. Elicitation may communicate information, of sincere voters' votes, to a manipulator, allowing him to vote strategically. In this paper, a multi-round elicitation process, of sincere voters' preferences, is derived that yields to an optimal manipulation with minimal information elicited. Through in-depth experimental study, this paper answers the question: How many candidates, per sincere voter, are needed to be known for an optimal manipulation? Probabilistic models such as IC and SP-IC are used to complete preference profiles.

Probabilistic relational models (PRMs) extend Bayesian networks (BNs) to a relational data mining context. Even though a panoply of works have focused, separately, on Bayesian networks and relational databases random generation, no work has been identified for PRMs on that track. This paper provides an algorithmic approach allowing to generate random PRMs from scratch to cover the absence of generation process. The proposed method allows to generate PRMs as well as synthetic relational data from a randomly generated relational schema and a random set of probabilistic dependencies. This can be of interest for machine learning researchers to evaluate their proposals in a common framework, as for databases designers to evaluate the effectiveness of the components of a database management system.

Within the last years, probabilistic causality has become a very active research topic in artificial intelligence and statistics communities. Due to its high impact in various applications involving reasoning tasks, machine learning researchers have proposed a number of techniques to learn Causal Bayesian Networks. Within the existing works in this direction, few studies have explicitly considered the role that decisional guidance might play to alternate between observational and experimental data processing. In this paper, we spread our previous works which foster greater collaboration between causal discovery and ontology evolution so as to evaluate them on real case study.

This paper emphasizes on handling uncertain and causal information in a min-based possibility theory framework. More precisely, we focus on studying the representational point of view of interventions under a compilation framework. We propose two compilation-based inference algorithms for min-based possibilistic causal networks based on encoding the augmented network into a propositional theory and compiling this output in order to efficiently compute the effect of both observations and interventions.

Bow tie diagrams have become popular methods in risk analysis and safety management. This tool describes graphically, in the same scheme, the whole scenario of an identified risk and its respective preventive and protective barriers. The major problem with bow tie diagrams is that they remain limited by their technical level and by their restriction to a graphical representation of different scenario without any consideration to the dynamic aspect of real systems. Recently we have proposed a new Bayesian approach to construct bow tie diagrams for risk analysis [1]. This approach learns the bow tie structure from real data and improves them by adding a new numerical component allowing us to model in a more realistic manner the system behavior. In this paper we propose to extend this approach by adding the barriers implementation in order to construct the whole bow ties. To this end we will use the numerical component, previously defined in the learning phase, and the analytic hierarchical process (AHP).

This paper proposes a partial implementation of an integrated Quality, Security and Environment management system to deal with the definition of an appropriate global management plan. This implementation is based on the multi-objective influence diagrams which are one of the most commonly used graphical decision models for reasoning under uncertainty with multiple objectives.

In this paper, we propose a new method, named Greedy Equivalence Search-Expectation Maximization (GES-EM), for learning Bayesian networks from incomplete data. Our method extends the recently proposed Greedy Equivalence Search (GES) algorithm10 to deal with incomplete data. For the quality evaluation of learned networks, we make use of the expected Bayesian Information Criterion (BIC) scoring function. In addition, we propose a new structural evaluation criterion. This so-called SEC criterion is more suitable than existing structural evaluation criteria, since it is based on the comparison of learned networks to the generating ones through Completed Partially Directed Acyclic Graphs (CPDAGs). Experimental results show that GES-EM algorithm yields more accurate structures than the standard Alternating Model Selection-Expectation Maximization (AMS-EM) algorithm.15.

Independence relations play an important role in uncertain reasoning based on Bayesian networks. In particular, they are useful in decomposing joint distributions into more elementary local ones. Recently, in a possibility theory framework, several qualitative independence relations have been proposed, where uncertainty is encoded by means of a complete pre-order between states of the world. This paper studies the well-known graphoid properties of these qualitative independences. Contrary to the probabilistic independence, several qualitative independence relations are not necessarily symmetric. Therefore, we also analyze the symmetric counterparts of graphoid properties (called reverse graphoid properties).

This paper presents a method for classifying objects in an uncertain context using decision trees. Uncertainty is related to attributes' values of objects to classify and is handled in a qualitative possibilistic framework. Then, an evaluation method to judge the classification efficiency, in an uncertain context, is proposed.

The notion of independence is central in many information processing areas, such as multiple criteria decision making, databases, or uncertain reasoning. This is especially true in the later case, where the success of Bayesian networks is basically due to the graphical representation of independence they provide. This paper first studies qualitative independence relations when uncertainty is encoded by a complete pre-order between states of the world. While a lot of work has focused on the formulation of suitable definitions of independence in uncertainty theories our interest in this paper is rather to formulate a general definition of independence based on purely ordinal considerations, and that applies to all weakly ordered settings. The second part of the paper investigates the impact of the embedding of qualitative independence relations into the scale-based possibility theory. The absolute scale used in this setting enforces the commensurateness between local pre-orders (since they share the same scale). This leads to an easy decomposability property of the joint distributions into more elementary relations on the basis of the independence relations. Lastly we provide a comparative study between already known definitions of possibilistic independence and the ones proposed here.