In order to capture a larger range of decision rules, this paper extends the seminal work of [Friedman and Halpern, 1995, Chu and Halpern, 2003, 2004] about Generalized Expected Utility. We introduce the notion of algebraic mass function (and of algebraic Möbius transform) and provide a new algebraic expression for expected utility based on such functions. This utility, that we call "XEU", generalizes Chu and Halpern’s GEU to non-decomposable measures and allows for the representation of several rules that could not be captured up to this point, and noticeably, of the Choquet integral. A representation theorem is provided that shows that only a very weak condition is needed for a rule in order to be representable as a XEU.

Decision theory and game theory are both interdisciplinary domains that focus on modelling and {analyzing} decision-making processes. On the one hand, decision theory aims to account for the possible behaviors of an agent with respect to an uncertain situation. It thus provides several frameworks to describe the decision-making processes in this context, including that of belief functions. On the other hand, game theory focuses on multi-agent decisions, typically with probabilistic uncertainty (if any), hence the so-called class of Bayesian games. In this paper, we use the Coq/SSReflect proof assistant to formally prove the results we obtained in [Pierre Pomeret{-}Coquot et al., 2022]. First, we formalize a general theory of belief functions with finite support, and structures and solutions concepts from game theory. On top of that, we extend Bayesian games to the theory of belief functions, so that we obtain a more expressive class of games we refer to as Bel games; it makes it possible to better capture human behaviors with respect to lack of information. Next, we provide three different proofs of an extended version of the so-called Howson-Rosenthal’s theorem, showing that Bel games can be casted into games of complete information, i.e., without any uncertainty. We thus embed this class of games into classical game theory, enabling the use of existing algorithms.

In order to reduce the size of compiled forms in knowledge compilation, we propose a new approach based on a splitting of the main representation into a nucleus representation and satellite representations. Nucleus representation is the projection of the original representation onto the "main" variables and satellite representations define the other variables according to the nucleus. We propose a language and a method, aimed at OBDD/OMDD representations, to compile into this split form. Our experimental study shows major size reductions on configuration- and diagnosis- oriented benchmarks.

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.

In decision problems involving two dimensions (like several agents in uncertainty) the properties of expected utility ensure that the result of a two-stepped procedure evaluation does not depend on the order with which the aggregations of local evaluations are performed (e.g., agents first, uncertainty next, or the converse). We say that the aggregations on each dimension commute. In a previous conference paper, Ben Amor, Essghaier and Fargier have shown that this property holds when using pessimistic possibilistic integrals on each dimension, or optimistic ones, while it fails when using a pessimistic possibilistic integral on one dimension and an optimistic one on the other. This paper studies and completely solves this problem when more general Sugeno integrals are used in place of possibilistic integrals, leading to double Sugeno integrals. The results show that there are capacities other than possibility and necessity measures that ensure commutation of Sugeno integrals. Moreover, the relationship between two-dimensional capacities and the commutation property for their projections is investigated.

This paper considers the task of learning the preferences of users on a combinatorial set of alternatives, as it can be the case for example with online configurators. In many settings, what is available to the learner is a set of positive examples of alternatives that have been selected during past interactions. We propose to learn a model of the users' preferences that ranks previously chosen alternatives as high as possible. In this paper, we study the particular task of learning conditional lexicographic preferences. We present an algorithm to learn several classes of lexicographic preference trees, prove convergence properties of the algorithm, and experiment on both synthetic data and on a real-world bench in the domain of recommendation in interactive configuration.

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.

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

The frameworks dedicated to the representation of quantitative temporal constraint satisfaction problems, as rich as they are in terms of expressiveness, define difficult requests - typically NP-complete decision problems. It is therefore adventurous to use them for an online resolution. Hence the idea to compile the original problem into a form that could be easily solved. Difference Decision Diagrams (DDDs) have been proposed by [1] as a possible way to cope with this difficulty, following a compilation-based approach. In this article, we draw a compilation map that evaluates the relative capabilities of these languages (TCSP, STP, DTP and DDD) in terms of algorithmic efficiency, succinctness and expressiveness.

Valued decision diagrams (VDDs) are data structures that represent functions mapping variable-value assignments to non-negative real numbers. They prove useful to compile cost functions, utility functions, or probability distributions. While the complexity of some queries (notably optimization) and transformations (notably conditioning) on VDD languages has been known for some time, there remain many significant queries and transformations, such as the various kinds of cuts, marginalizations, and combinations, the complexity of which has not been identified so far. This paper contributes to filling this gap and completing previous results about the time and space efficiency of VDD languages, thus leading to a knowledge compilation map for real-valued functions. Our results show that many tasks that are hard on valued CSPs are actually tractable on VDDs.

Constraint Satisfaction Problems (CSPs) offer a powerful framework for representing a great variety of problems. The difficulty is that most of the requests associated with CSPs are NP-hard. As these requests must be addressed online, Multivalued Decision Diagrams (MDDs) have been proposed as a way to compile CSPs. In the present paper, we draw a compilation map of MDDs, in the spirit of the NNF compilation map, analyzing MDDs according to their succinctness and to their playtime transformations and queries. Deterministic ordered MDDs are a generalization of ordered binary decision diagrams to non-Boolean domains: unsurprisingly, they have similar capabilities. More interestingly, our study puts forward the interest of non-deterministic ordered MDDs: when restricted to Boolean domains, this fragment captures OBDD and DNF as proper subsets and has performances close to those of DNNF. The comparison to classical, deterministic MDDs shows that relaxing the determinism requirement leads to an increase in succinctness and allows more transformations to be satisfied in polytime (typically, the disjunctive ones). Experiments on random problems confirm the gain in succinctness.

International audience

In this paper, we study the knowledge compilation task for propositional epistemic logic S5. We first extend many of the queries and transformations considered in the classical knowledge compilation map to S5. We then show that the notion of disjunctive normal form (DNF) can be profitably extended to the epistemic case; we prove that the DNF fragment of S5, when appropriately defined, satisfies essentially the same queries and transformations as its classical counterpart.

Knowledge compilation [6, 5, 14, 8] consists in transforming a problem offline into a form which is tractable online. In this paper, we introduce new structures, based on the notion of interval automaton (IA), adapted to the compilation of problems involving both discrete and continuous variables, and especially of decision policies and transition tables, in the purpose of controlling autonomous systems.

The existence of powerful constraint satisfaction algorithms is not the sole reason of the wide success of the CSP framework. The interest of this framework is also that it offers a generic and simple way for the modeling of real world applications. Nevertheless these applications call for tasks that often differ from a classical search for a solution. The aim of the present paper is not to provide the AI community with new and efficient algorithms, but with new requests and more generally new needs. All of them are issued from the analysis of the business needs that arise around the design and exploitation of the vehicle range at Renault, the French car manufacturer. Viewing this application as a fruitful source of research problematics for the community, we present a formalization and a theoretical study, in terms on complexity, of the series of requests risen by the application.

We extend the knowledge compilation map introduced by Darwiche and Marquis with new propositional fragments obtained by applying closure principles to several fragments studied so far. We investigate two closure principles: disjunction and implicit forgetting (i.e., existential quantification). Each introduced fragment is evaluated w.r.t. several criteria, including the complexity of basic queries and transformations, and its spatial efficiency is also analyzed.

Making a decision is often a matter of listing and comparing positive and negative arguments. In such cases, the evaluation scale for decisions should be considered bipolar, that is, negative and positive values should be explicitly distinguished. That is what is done, for example, in Cumulative Prospect Theory. However, contraryto the latter framework that presupposes genuine numerical assessments, human agents often decide on the basis of an ordinal ranking of the pros and the cons, and by focusing on the most salient arguments. In other terms, the decision process is qualitative as well as bipolar. In this article, based on a bipolar extension of possibility theory, we define and axiomatically characterize several decision rules tailored for the joint handling of positive and negative arguments in an ordinal setting. The simplest rules can be viewed as extensions of the maximin and maximax criteria to the bipolar case, and consequently suffer from poor decisive power. More decisive rules that refine the former are also proposed. These refinements agree both with principles of efficiency and with the spirit of order-of-magnitude reasoning, that prevails in qualitative decision theory. The most refined decision rule uses leximin rankings of the pros and the cons, and the ideas of counting arguments of equal strength and cancelling pros by cons. It is shown to come down to a special case of Cumulative Prospect Theory, and to subsume the ``Take the Best'' heuristic studied by cognitive psychologists.

In this paper, we introduce a new way of looking at fuzzy intervals. Instead of considering them as fuzzy sets, we see them as crisp sets of entities we call gradual (real) numbers. They are a gradual extension of real numbers, not of intervals. Such a concept is apparently missing in fuzzy set theory. Gradual numbers basically have the same algebraic properties as real numbers, but they are functions. A fuzzy interval is then viewed as a pair of fuzzy thresholds, which are monotonic gradual real numbers. This view enables interval analysis to be directly extended to fuzzy intervals, without resorting to alpha-cuts, in agreement with Zadeh's extension principle. Several results show that interval analysis methods can be directly adapted to fuzzy interval computation where end- points of intervals are changed into left and right fuzzy bounds. Our approach is illustrated on two known problems: computing fuzzy weighted averages and determining fuzzy floats and latest starting times in activity network scheduling.

The profile method gives a tool to perform fuzzy interval computation under a condition of local monotony of considered functions. This is a plain extension of interval analysis to fuzzy intervals, viewed as pairs of fuzzy bounds. This method yields exact results without applying interval analysis to alpha-cuts. After a refresher on the notion of profile and its use in fuzzy interval analysis, we adapt the profile method to the computation of the empirical variance of a tuple of fuzzy intervals. To this end, we first reconsider results obtained by Ferson et al. on computation of the empirical variance of a set of intervals. Finally we apply our results to the definition of the variance of a single fuzzy interval, viewed as a family of its alpha-cuts, and compare this definition to previous ones

We introduce a new method for computing functions of fuzzy intervals under various monotonicity assumptions on the concerned functions. Our method makes exact computation for all possibility degrees, without resorting to /spl alpha/-cuts. We formally present the notion of left and right profiles of fuzzy intervals as a tool for fuzzy interval computation. Several results show that interval analysis methods can be directly adapted to fuzzy interval computation where end point of intervals are changed into left and right profiles. Our approach is illustrated by numerous simple examples all along the paper, and a special section is devoted to the application of these concepts to different known problems.

An accepted belief is a proposition considered likely enough by an agent, to be inferred from as if it were true. This paper bridges the gap between probabilistic and logical representations of accepted beliefs. To this end, natural properties of relations on propositions, describing relative strength of belief are augmented with some conditions ensuring that accepted beliefs form a deductively closed set. This requirement turns out to be very restrictive. In particular, it is shown that the sets of accepted belief of an agent can always be derived from a family of possibility rankings of states. An agent accepts a proposition in a given context if this proposition is considered more possible than its negation in this context, for all possibility rankings in the family. These results are closely connected to the non-monotonic 'preferential' inference system of Kraus, Lehmann and Magidor and the so-called plausibility functions of Friedman and Halpern. The extent to which probability theory is compatible with acceptance relations is laid bare. A solution to the lottery paradox, which is considered as a major impediment to the use of non-monotonic inference is proposed using a special kind of probabilities (called lexicographic, or big-stepped). The setting of acceptance relations also proposes another way of approaching the theory of belief change after the works of Gärdenfors and colleagues. Our view considers the acceptance relation as a primitive object from which belief sets are derived in various contexts.

This article proposes a principled approach to multicriteria decision making (MCDM) where the worth of decisions along attributes is not supposed to be quantified, as in multiattribute utility theory, or even measured on a unique scale. This approach actually generalizes additive concordance rules a la Electre and is rigorously justified in an axiomatic way by representation theorems. We indeed show that the use of a generalized concordance (GC) rule is the only possible approach when in a purely ordinal framework and that the satisfaction of very simple principles forces the use of possibility theory as the unique way of expressing the importance of coalitions of criteria. © 2003 Wiley Periodicals, Inc.

This paper investigates to what extent a purely symbolic approach to decision making under uncertainty is possible, in the scope of artificial intelligence. Contrary to classical approaches to decision theory, we try to rank acts without resorting to any numerical representation of utility or uncertainty, and without using any scale on which both uncertainty and preference could be mapped. Our approach is a variant of Savage's where the setting is finite, and the strict preference on acts is a partial order. It is shown that although many axioms of Savage theory are preserved and despite the intuitive appeal of the ordinal method for constructing a preference over acts, the approach is inconsistent with a probabilistic representation of uncertainty. The latter leads to the kind of paradoxes encountered in the theory of voting. It is shown that the assumption of ordinal invariance enforces a qualitative decision procedure that presupposes a comparative possibility representation of uncertainty, originally due to Lewis, and usual in nonmonotonic reasoning. Our axiomatic investigation thus provides decision-theoretic foundations to the preferential inference of Lehmann and colleagues. However, the obtained decision rules are sometimes either not very decisive or may lead to overconfident decisions, although their basic principles look sound. This paper points out some limitations of purely ordinal approaches to Savage-like decision making under uncertainty, in perfect analogy with similar difficulties in voting theory.

The problem of combining pieces of information issued from several sources can be encountered in various fields of application. This paper aims at presenting the different aspects of information fusion in different domains, such as databases, regulations, preferences, sensor fusion, etc., at a quite general level. We first present different types of information encountered in fusion problems, and different aims of the fusion process. Then we focus on representation issues which are relevant when discussing fusion problems. An important issue is then addressed, the handling of conflicting information. We briefly review different domains where fusion is involved, and describe how the fusion problems are stated in each domain. Since the term fusion can have different, more or less broad, meanings, we specify later some terminology with respect to related problems, that might be included in a broad meaning of fusion. Finally we briefly discuss the difficult aspects of validation and evaluation. © 2001 John Wiley & Sons, Inc.

This paper deals with the fuzzy project scheduling approach, where fuzzy intervals model uncertain durations of tasks. While it is easy to compute fuzzy earliest starting dates of tasks in the critical path method, the problem of determining latest starting dates and slack times is much more tricky and has never been solved in a fully satisfactory manner in the past. Here, we propose a rigorous treatment of this problem in series-parallel graphs, in the framework of possibility theory. The main difficulty lies in the fact that the variation of latest starting dates and slack times, as a function of task durations, is not straightforward to predict for general graph topologies. However, it is easier in the case of series-parallel graphs. The case of interval-valued durations is first addressed, and then extended to fuzzy intervals.

Temporal Constraint Networks (TCN) allow one to express minimal and maximal durations between time-points. Although being used in many research areas, this model disregards the contingent nature of some constraints, whose effective duration cannot be decided by the system but is provided by the external world. We propose an extension of TCN based on the definition of the Simple Temporal Problem under Uncertainty (STPU) in which the classical network consistency property must be redefined in terms of controllability: intuitively, we would like to say that a network is controllable iff it is consistent in any situation (i.e. any assignment of the whole set of contingent intervals) that may arise in the external world. Three levels of controllability must be distinguished, namely the Strong, the Weak and the Dynamic ones. This paper provides a full characterization of those properties and their usefulness in practice, and proposes algorithms for checking them. Complexity issues and tractable equivalence classes are only partially tackled, since it is still the topic of on-going work. All the same, hardness is discussed and argued, giving evidence for the general intractability of Dynamic controllability, which is the most commonly required property in domains such as planning or scheduling.