Research Menu:

Current research activities
Publications
current students
past PhDs
A tutorial on utility functions
 Software
     aGrUM

My research activities are centered around Decision Theory. More precisely, I am interested in the mathematical models lying behind our decision making processes. To make it short, consider I ask you whether you want to play to a certain game (decision ) or not (decision ). If I do not tell you which game it is, you will probably have some difficulty telling me which decision you would prefer. Now I explain to you that the game simply consists in giving you $100. You will certainly tell me that you prefer decision to , which could be denoted mathematically by , where is a binary relation over decisions. One question that naturally arises is: why did you prefer to ? Simply because the consequence (or outcome) of taking this decision, i.e. winning $100, seems more appealing than that of decision , i.e. winning nothing. Hence , our preference relation over decisions, reflects our preferences over the consequences of the decisions. This explains why one aspect of my researches concerns the mathematical models representing preference relations over consequence sets.

Let us now change the above game as follows: instead of giving you $100, I toss a coin, and if the head obtains, I give you $100, but if the tail obtains, you lose $200. Now which decision do you prefer? Here, if the coin is fair, you will probably prefer to because there is a substantial chance that results in losing $200. However if the coin is such that the probability that the head obtains is 99.99%, you may prefer because the chance of losing $200 is very small. This means that preference relation does not only take into account your preferences over outcomes, but it also take into account the uncertainty about the realisation of the outcomes. Probabilities are a popular model of uncertainty, and since the late 80's and Pearl's seminal book, graphical models have been widely used for their encoding and their computation. This explains why my second research field concerns graphical models. It turns out that graphical models also prove useful for preference encodings.

Representation of the Decision Maker's Preferences

Mathematically, modeling preferences over a set of decisions or over a set of consequences merely amounts to finding a binary relation over pairs decisions or pairs of consequences. For instance, assume that a Decision Maker (DM) has some preferences over a set = {eat some chicken, eat some fish, eat an apple pie, eat a soup}. For any pair of elements of , the following may happen:

  1. the Decision Maker may not be able to compare and , i.e. she cannot say whether she prefers to or to . This may be the case for ="eat a soup" and ="eat an apple pie" since one is a starter and the other is a dessert.

  2. the Decision Maker may prefer to or to , or even be indifferent between and .

Mathematically, the Decision Maker's preferences may be represented by a binary relation on such that means the DM prefers to or is indifferent between and . Thus and being incomparable is equivalent to Not () and Not (). The strict preference of to can be denoted by and Not (), and the indifference between and is captured by and .

The qualitative aspect of binary relation makes it not particularly well suited for fast computation, in particular if one wishes to find the best decision under a given set of constraints. Hence, in practical situations, this relation need often be encoded numerically. One of the most popular encoding is that of utility functions, a.k.a. utilities. The idea is to use a mapping u from to , the set of the real numbers, assigning numbers to elements of such that the higher the more preferred. More formally, u is defined as:

for all .


In practical situations, the DM decisions take into account multiple conflicting objectives, hence the outcome set is a multidimensional space and the outcomes are tuples (of attributes) . Thus utilities are functions of tuples. This is a major problem when they are to be constructed. Indeed, as each Decision Maker has her own preferences, utilities differ from one DM to another. So the only way to construct the DM's utlities is to ask her some questions. But when questions involve to many different attributes, they become too complicated for the human brain to handle and the DM is not able to give accurate answers. In order to simplify the questions, assumptions on the structure of the utilities need be made. One of the most popular is the additive decomposition:

.


During my PhD thesis, I have studied testable conditions on the DM preference relation ensuring the existence of additively decomposable utility functions (additive utilities for short). I am still interested in decompositions of utilities, but I now study more complicated decompositions such as generalized additive decompositions (GAI): instead of splitting the overall utility into pieces, each one depending only on one attribute, GAI splits it into utilities over some (possibly overlapping) sets of attributes. For instance~:

.

Graphical Models

Among graphical models, I am especially interested in Bayesian networks (BN) and GAI-nets. The former are powerful tools of the Artificial Intelligence community enabling fast computation of probabilities (marginal, conditional, a priori or a posteriori probabilities). To achieve this result, BN use graphical structures that encode knowledge about the decomposition of joint probability distributions of interest. GAI-nets are rather similar in spirit, except that instead of decomposing a probability distribution over random variables, they decompose attributes or criteria of preference tuples.

Mainly my current activities on graphical models can be divided into three classes:

  • Until now, I was mainly concerned with the improvement of BN computation algorithms. In the literature, roughly two main approaches emerged: directed and undirected methods. It is commonly thought that undirected methods outperform directed ones. One of my goals was to unify both types of methods to show that directed methods can compete with undirected ones. Using the advantages of each kind of method, this unification enabled the improvement of all the algorithms.
  • As I mentioned, Bayesian networks are graphical structures. These represent the decomposition of joint probabilities. Hence they are specific for each problem of interest. In theory, if you possess a sufficiently good database of values of the random variables you are interested in, computer programs should be able to learn the graph structure of the BN (using for instance statistical independence tests). In practice, however, such programs do not always produce high quality graphs. This explains why I am now beginning to work on learning methods.
  • My last main research activity concerns GAI-nets. This field is rather new. The idea is to take advantage of some decomposition of the Decision Maker's preference relations to be able to elicit efficiently his/her preferences, and to answer quickly to questions such as "does the Decision Maker prefers this alternative to that one?" or "what is the preferred alternative of the Decision Maker?". Efficient elicitation procedures could prove useful for instance for web shopping sites.