Patrice Perny

AAAI Conference 2024 Conference Paper

Learning GAI-Decomposable Utility Models for Multiattribute Decision Making

• Margot Herin
• Patrice Perny
• Nataliya Sokolovska

We propose an approach to learn a multiattribute utility function to model, explain or predict the value system of a Decision Maker. The main challenge of the modelling task is to describe human values and preferences in the presence of interacting attributes while keeping the utility function as simple as possible. We focus on the generalized additive decomposable utility model which allows interactions between attributes while preserving some additive decomposability of the evaluation model. We present a learning approach able to identify the factors of interacting attributes and to learn the utility functions defined on these factors. This approach relies on the determination of a sparse representation of the ANOVA decomposition of the multiattribute utility function using multiple kernel learning. It applies to both continuous and discrete attributes. Numerical tests are performed to demonstrate the practical efficiency of the learning approach.

IJCAI Conference 2024 Conference Paper

Online Learning of Capacity-Based Preference Models

• Margot Herin
• Patrice Perny
• Nataliya Sokolovska

In multicriteria decision making, sophisticated decision models often involve a non-additive set function (named capacity) to define the weights of all subsets of criteria. This makes it possible to model criteria interactions, leaving room for a diversity of attitudes in criteria aggregation. Fitting a capacity-based decision model to a given Decision Maker is a challenging problem and several batch learning methods have been proposed in the literature to derive the capacity from a database of preference examples. In this paper, we introduce an online algorithm for learning a sparse representation of the capacity, designed for decision contexts where preference examples become available sequentially. Our method based on regularized dual averaging is also well fitted to decision contexts involving a large number of preference examples or a large number of criteria. Moreover, we propose a variant making it possible to include normative constraints on the capacity (e. g. , monotonicity, supermodularity) while preserving scalability, based on the alternating direction method of multipliers.

IJCAI Conference 2023 Conference Paper

Learning Preference Models with Sparse Interactions of Criteria

• Margot Herin
• Patrice Perny
• Nataliya Sokolovska

Multicriteria decision making requires defining the result of conflicting and possibly interacting criteria. Allowing criteria interactions in a decision model increases the complexity of the preference learning task due to the combinatorial nature of the possible interactions. In this paper, we propose an approach to learn a decision model in which the interaction pattern is revealed from preference data and kept as simple as possible. We consider weighted aggregation functions like multilinear utilities or Choquet integrals, admitting representations including non-linear terms measuring the joint benefit or penalty attached to some combinations of criteria. The weighting coefficients known as Möbius masses model positive or negative synergies among criteria. We propose an approach to learn the Möbius masses, based on iterative reweighted least square for sparse recovery, and dualization to improve scalability. This approach is applied to learn sparse representations of the multilinear utility model and conjunctive/disjunctive forms of the discrete Choquet integral from preferences examples, in aggregation problems possibly involving more than 20 criteria.

UAI Conference 2022 Conference Paper

Learning sparse representations of preferences within Choquet expected utility theory

• Margot Herin
• Patrice Perny
• Nataliya Sokolovska

This paper deals with preference elicitation within Choquet Expected Utility (CEU) theory for decision making under uncertainty. We consider the Savage’s framework with a finite set of states and assume that preferences of the Decision Maker over acts are observable. The CEU model involves two parameters that must be tuned to the value system of the decision maker: a set function (capacity) modeling weights attached to events, of size exponential in the number of states, and a utility function defined on the space of outcomes. Our aim is to learn a sparse representation of the CEU model from preference data. We propose and test a preference learning approach based on a spline representation of utilities and the sparse learning of capacities to obtain CEU models achieving a good tradeoff between the aim of sparsity and the expressivity required by preference data.

AAAI Conference 2021 Conference Paper

Combining Preference Elicitation with Local Search and Greedy Search for Matroid Optimization

• Nawal Benabbou
• Cassandre Leroy
• Thibaut Lust
• Patrice Perny

We propose two incremental preference elicitation methods for interactive preference-based optimization on weighted matroid structures. More precisely, for linear objective (utility) functions, we propose an interactive greedy algorithm interleaving preference queries with the incremental construction of an independent set to obtain an optimal or nearoptimal base of a matroid. We also propose an interactive local search algorithm based on sequences of possibly improving exchanges for the same problem. For both algorithms, we provide performance guarantees on the quality of the returned solutions and the number of queries. Our algorithms are tested on the uniform, graphical and scheduling matroids to solve three different problems (committee election, spanning tree, and scheduling problems) and evaluated in terms of computation times, number of queries, and empirical error.

AAMAS Conference 2021 Conference Paper

Rank Aggregation by Dissatisfaction Minimisation in the Unavailable Candidate Model

• Arnaud Grivet Sébert
• Nicolas Maudet
• Patrice Perny
• Paolo Viappiani

In this paper, we extend the unavailable candidate model [10] and present two new voting rules based on a finer notion of disagreement, called dissatisfaction, which depends on the ranks of the candidates, considered among all the candidates (ex ante dissatisfaction rule) or only among the available candidates (ex post dissatisfaction rule). We provide algorithmic results for the two rules and show that apparently very different voting rules such as scoring rules or Kemeny rule can be unified under the same aggregation concept: expectation of dissatisfaction under the availability distribution.

ECAI Conference 2020 Conference Paper

New Computational Models for the Choquet Integral

• Hugo Martin 0002
• Patrice Perny

Multiobjective optimization is a central problem in a wide range of contexts, such as multi-agent optimization and multicriteria decision support or decision under risk and uncertainty. The presence of several objectives leads to multiple non-dominated solutions and requires the use of a sophisticated decision model allowing various attitudes towards preference aggregation. The Choquet Integral is one of the most expressive parameterized models introduced in decision theory to scalarize performance vectors and support decision making. However, its use in optimization contexts raises computational issues. This paper proposes new computational models based on mathematical programming to optimize the Choquet integral on implicit sets. A new linearization of the Choquet integral exploiting the vertices of the core of the convex capacity is proposed, combined with a constraint generation algorithm. Then the computational model is extended to the bipolar Choquet Integral to allow asymmetric aggregation with respect to a specific reference point.

AAAI Conference 2019 Conference Paper

Active Preference Learning Based on Generalized Gini Functions: Application to the Multiagent Knapsack Problem

• Nadjet Bourdache
• Patrice Perny

We consider the problem of actively eliciting preferences from a Decision Maker supervising a collective decision process in the context of fair multiagent combinatorial optimization. Individual preferences are supposed to be known and represented by linear utility functions defined on a combinatorial domain and the social utility is defined as a generalized Gini Social evaluation Function (GSF) for the sake of fairness. The GSF is a non-linear aggregation function parameterized by weighting coefficients which allow a fine control of the equity requirement in the aggregation of individual utilities. The paper focuses on the elicitation of these weights by active learning in the context of the fair multiagent knapsack problem. We introduce and compare several incremental decision procedures interleaving an adaptive preference elicitation procedure with a combinatorial optimization algorithm to determine a GSF-optimal solution. We establish an upper bound on the number of queries and provide numerical tests to show the efficiency of the proposed approach.

IJCAI Conference 2019 Conference Paper

BiOWA for Preference Aggregation with Bipolar Scales: Application to Fair Optimization in Combinatorial Domains

• Hugo Martin
• Patrice Perny

We study the biOWA model for preference aggregation and multicriteria decision making from bipolar rating scales. A biOWA is an ordered doubly weighted averaging extending standard ordered weighted averaging (OWA) and allowing a finer control of the importance attached to positive and negative evaluations in the aggregation. After establishing some useful properties of biOWA to generate balanced Pareto-optimal solutions, we address fair biOWA-optimization problems in combinatorial domains. We first consider the use of biOWA in multi-winner elections for aggregating graded approval and disapproval judgements. Then we consider the use of biOWA for solving robust path problems with costs expressing gains and losses. A linearization of biOWA is proposed, allowing both problems to be solved by MIP. A path-ranking algorithm for biOWA optimization is also proposed. Numerical tests are provided to show the practical efficiency of our models.

IJCAI Conference 2019 Conference Paper

Incremental Elicitation of Rank-Dependent Aggregation Functions based on Bayesian Linear Regression

• Nadjet Bourdache
• Patrice Perny
• Olivier Spanjaard

We introduce a new model-based incremental choice procedure for multicriteria decision support, that interleaves the analysis of the set of alternatives and the elicitation of weighting coefficients that specify the role of criteria in rank-dependent models such as ordered weighted averages (OWA) and Choquet integrals. Starting from a prior distribution on the set of weighting parameters, we propose an adaptive elicitation approach based on the minimization of the expected regret to iteratively generate preference queries. The answers of the Decision Maker are used to revise the current distribution until a solution can be recommended with sufficient confidence. We present numerical tests showing the interest of the proposed approach.

IJCAI Conference 2017 Conference Paper

Adaptive Elicitation of Preferences under Uncertainty in Sequential Decision Making Problems

• Nawal Benabbou
• Patrice Perny

This paper aims to introduce an adaptive preference elicitation method for interactive decision support in sequential decision problems. The Decision Maker's preferences are assumed to be representable by an additive utility, initially unknown or imperfectly known. We first study the determination of possibly optimal policies when admissible utilities are imprecisely defined by some linear constraints derived from observed preferences. Then, we introduce a new approach interleaving elicitation of utilities and backward induction to incrementally determine an optimal or near-optimal policy. We propose an interactive algorithm with performance guarantees and describe numerical experiments demonstrating the practical efficiency of our approach.

AAMAS Conference 2017 Conference Paper

Coalition Structure Generation and CS-core: Results on the Tractability Frontier for games represented by MC-nets

• Julien Lesca
• Patrice Perny
• Makoto Yokoo

IJCAI Conference 2017 Conference Paper

Incremental Decision Making Under Risk with the Weighted Expected Utility Model

• Hugo Gilbert
• Nawal Benabbou
• Patrice Perny
• Olivier Spanjaard
• Paolo Viappiani

This paper deals with decision making under risk with the Weighted Expected Utility (WEU) model, which is a model generalizing expected utility and providing stronger descriptive possibilities. We address the problem of identifying, within a given set of lotteries, a (near-)optimal solution for a given decision maker consistent with the WEU theory. The WEU model is parameterized by two real-valued functions. We propose here a new incremental elicitation procedure to progressively reduce the imprecision about these functions until a robust decision can be made. We also give experimental results showing the practical efficiency of our method.

AIJ Journal 2017 Journal Article

Incremental elicitation of Choquet capacities for multicriteria choice, ranking and sorting problems

• Nawal Benabbou
• Patrice Perny
• Paolo Viappiani

This paper proposes incremental preference elicitation methods for multicriteria decision making with a Choquet integral. The Choquet integral is an evaluation function that performs a weighted aggregation of criterion values using a capacity function assigning a weight to any coalition of criteria, thus enabling positive and/or negative interactions among them and covering an important range of possible decision behaviors. However, the specification of the capacity involves many parameters which raises challenging questions, both in terms of elicitation burden and guarantee on the quality of the final recommendation. In this paper, we investigate the incremental elicitation of the capacity through a sequence of preference queries (questions) selected one-by-one using a minimax regret strategy so as to progressively reduce the set of possible capacities until the regret (the worst-case “loss” due to reasoning with only partially specified capacities) is low enough. We propose a new approach designed to efficiently compute minimax regret for the Choquet model and we show how this approach can be used in different settings: 1) the problem of recommending a single alternative, 2) the problem of ranking alternatives from best to worst, and 3) sorting several alternatives into ordered categories. Numerical experiments are provided to demonstrate the practical efficiency of our approach for each of these situations.

UAI Conference 2016 Conference Paper

Incremental Preference Elicitation for Decision Making Under Risk with the Rank-Dependent Utility Model

• Patrice Perny
• Paolo Viappiani
• Abdellah Boukhatem

agent. Considering this context, our paper aims at providing new tools for interactive decision support under risk. This work concerns decision making under risk with the rank-dependent utility model (RDU), a generalization of expected utility providing enhanced descriptive possibilities. We introduce a new incremental decision procedure, involving monotone regression spline functions to model both components of RDU, namely the probability weighting function and the utility function. First, assuming the utility function is known, we propose an elicitation procedure that incrementally collects preference information in order to progressively specify the probability weighting function until the optimal choice can be identified. Then, we present two elicitation procedures for the construction of a utility function as a monotone spline. Finally, numerical tests are provided to show the practical efficiency of the proposed methods. Decision under risk is a standard formal framework for handling uncertainty in decision making, characterized by a probabilistic representation of uncertainty. In this framework, risky prospects are represented by probability distributions with a finite support, namely lotteries. In the seminal work of Bernoulli (1738; refer to [1954] for an English translation) and in the theory of von Neumann and Morgenstern (vNM) [1947], the values of lotteries are measured in terms of expected utility (EU). This well-known decision criterion is linear in probabilities and characterized by a utility function encoding the subjective value of any possible consequence for the DM; EU is used to compare lotteries and choice problems are solved by EU maximization. This choice model has been axiomatically justified in the context of risk by vNM [1947], but also in the more general context of uncertainty introduced by Savage [1954], where probabilities are not assumed to exist a priori.

ECAI Conference 2016 Conference Paper

Solving Multi-Agent Knapsack Problems Using Incremental Approval Voting

• Nawal Benabbou
• Patrice Perny

In this paper, we study approval voting for multi-agent knapsack problems under incomplete preference information. The agents consider the same set of feasible knapsacks, implicitly defined by a budget constraint, but they possibly diverge in the utilities they attach to items. Individual utilities being difficult to assess precisely and to compare, we collect approval statements on knapsacks from the agents with the aim of determining the optimal solutions by approval voting. We first propose a search procedure based on mixed-integer programming to explore the space of utilities compatible with the known part of preferences in order to determine or approximate the set of possible approval winners. Then, we propose an incremental procedure combining preference elicitation and search in order to determine the set of approval winners without requiring the full elicitation of the agents' preferences. Finally, the practical efficiency of these procedures is illustrated by various numerical tests.

ECAI Conference 2016 Conference Paper

Using the Sugeno Integral in Optimal Assignment Problems with Qualitative Utilities

• Soufiane Drissi Oudghiri
• Patrice Perny
• Olivier Spanjaard
• Mohamed Hachimi

This paper is devoted to the assignment problem when the preferences of the agents are defined by qualitative utilities. In this setting, it is not possible to compare assignments by summing up individual utilities because the sum operation becomes meaningless. We study here the optimization of a Sugeno integral of the individual utilities. We show that the problem is NP-hard in the general case, but we also identify special cases that are solvable in polynomial time. Furthermore, we provide a mixed integer programming formulation in the general case, which leads to a compact formulation for k-minitive capacities.

IJCAI Conference 2015 Conference Paper

Combining Preference Elicitation and Search in Multiobjective State-Space Graphs

• Nawal Benabbou
• Patrice Perny

The aim of this paper is to propose a new approach interweaving preference elicitation and search to solve multiobjective optimization problems. We present an interactive search procedure directed by an aggregation function, possibly non-linear (e. g. an additive disutility function, a Choquet integral), defining the overall cost of solutions. This function is parameterized by weights that are initially unknown. Hence, we insert comparison queries in the search process to obtain useful preference information that will progressively reduce the uncertainty attached to weights. The process terminates by recommending a near-optimal solution ensuring that the gap to optimality is below the desired threshold. Our approach is tested on multiobjective state space search problems and appears to be quite efficient both in terms of number of queries and solution times.

AAAI Conference 2015 Conference Paper

Incremental Weight Elicitation for Multiobjective State Space Search

• Nawal Benabbou
• Patrice Perny

This paper proposes incremental preference elicitation methods for multiobjective state space search. Our approach consists in integrating weight elicitation and search to determine, in a vector-valued state-space graph, a solution path that best fits the Decision Maker’s preferences. We first assume that the objective weights are imprecisely known and propose a state space search procedure to determine the set of possibly optimal solutions. Then, we introduce incremental elicitation strategies during the search that use queries to progressively reduce the set of admissible weights until a nearlyoptimal path can be identified. The validity of our algorithms is established and numerical tests are provided to test their efficiency both in terms of number of queries and solution times.

ECAI Conference 2014 Conference Paper

Incremental Elicitation of Choquet Capacities for Multicriteria Decision Making

• Nawal Benabbou
• Patrice Perny
• Paolo Viappiani

The Choquet integral is one of the most sophisticated and expressive preference models used in decision theory for multicriteria decision making. It performs a weighted aggregation of criterion values using a capacity function assigning a weight to any coalition of criteria, thus enabling positive and/or negative interactions among criteria and covering an important range of possible decision behaviors. However, the specification of the capacity involves many parameters which raises challenging questions, both in terms of elicitation burden and guarantee on the quality of the final recommendation. In this paper, we investigate the incremental elicitation of the capacity through a sequence of preference queries selected one-by-one using a minimax regret strategy so as to progressively reduce the set of possible capacities until a decision can be made. We propose a new approach designed to efficiently compute minimax regret for the Choquet model. Numerical experiments are provided to demonstrate the practical efficiency of our approach.

AAAI Conference 2014 Conference Paper

Voting with Rank Dependent Scoring Rules

• Judy Goldsmith
• Jérôme Lang
• Nicholas Mattei
• Patrice Perny

Positional scoring rules in voting compute the score of an alternative by summing the scores for the alternative induced by every vote. This summation principle ensures that all votes contribute equally to the score of an alternative. We relax this assumption and, instead, aggregate scores by taking into account the rank of a score in the ordered list of scores obtained from the votes. This defines a new family of voting rules, rank-dependent scoring rules (RDSRs), based on ordered weighted average (OWA) operators, which, include all scoring rules, and many others, most of which of new. We study some properties of these rules, and show, empirically, that certain RDSRs are less manipulable than Borda voting, across a variety of statistical cultures.

UAI Conference 2013 Conference Paper

Approximation of Lorenz-Optimal Solutions in Multiobjective Markov Decision Processes

• Patrice Perny
• Paul Weng
• Judy Goldsmith
• Josiah P. Hanna

This paper is devoted to fair optimization in Multiobjective Markov Decision Processes (MOMDPs). A MOMDP is an extension of the MDP model for planning under uncertainty while trying to optimize several reward functions simultaneously. This applies to multiagent problems when rewards define individual utility functions, or in multicriteria problems when rewards refer to different features. In this setting, we study the determination of policies leading to Lorenz-nondominated tradeoffs. Lorenz dominance is a refinement of Pareto dominance that was introduced in Social Choice for the measurement of inequalities. In this paper, we introduce methods to efficiently approximate the sets of Lorenz-non-dominated solutions of infinite-horizon, discounted MOMDPs. The approximations are polynomial-sized subsets of those solutions.

SoCS Conference 2013 Conference Paper

Bidirectional Preference-Based Search for State Space Graph Problems

• Lucie Galand
• Anisse Ismaili
• Patrice Perny
• Olivier Spanjaard

In multiobjective state space graph problems, each solution-path is evaluated by a cost vector. These cost vectors can be partially or completely ordered using a preference relation compatible with Pareto dominance. In this context, multiobjective preference-based search (MOPBS) aims at computing the preferred feasible solutions according to a predefined preference model, these preferred solutions being a subset (possibly the entire set) of Pareto optima. Standard algorithms for MOPBS perform a unidirectional search developing the search tree forward from the initial state to a goal state. Instead, in this paper, we focus on bidirectional search algorithms developing simultaneously one forward and one backward search tree. Although bi-directional search has been tested in various single objective problems, its efficiency in a multiobjective setting has never been studied. In this paper, we present several implementations of bidirectional preference-based search convenient for the multiobjective case and investigate their efficiency.

IJCAI Conference 2013 Conference Paper

Dominance Rules for the Choquet Integral in Multiobjective Dynamic Programming

• Lucie Galand
• Julien Lesca
• Patrice Perny

Multiobjective Dynamic Programming (MODP) is a general problem solving method used to determine the set of Pareto-optimal solutions in optimization problems involving discrete decision variables and multiple objectives. It applies to combinatorial problems in which Pareto-optimality of a solution extends to all its sub-solutions (Bellman principle). In this paper we focus on the determination of the preferred tradeoffs in the Pareto set where preference is measured by a Choquet integral. This model provides high descriptive possibilities but the associated preferences generally do not meet the Bellman principle, thus preventing any straightforward adaptation of MODP. To overcome this difficulty, we introduce here a general family of dominance rules enabling an early pruning of some Pareto-optimal sub-solutions that cannot lead to a Choquet optimum. Within this family, we identify the most efficient dominance rules and show how they can be incorporated into a MODP algorithm. Then we report numerical tests showing the actual efficiency of this approach to find Choquet-optimal tradeoffs in multiobjective knapsack problems.

ECAI Conference 2012 Conference Paper

Almost-truthful Mechanisms for Fair Social Choice Functions

• Julien Lesca
• Patrice Perny

This paper deals with the implementation of Social Choice Functions in fair multiagent decision problems. In such problems the determination of the best alternatives often relies on the maximization of a non-utilitarian Social Welfare Function so as to account for equity. However, in such decision processes, agents may have incentive to misreport their preferences to obtain more favorable choices. It is well known that, for Social Choice Functions based on the maximization of an affine aggregator of individual utilities, we can preclude any manipulation by introducing payments (VCG mechanisms). Unfortunately such truthful mechanisms do not exist for non-affine maximizers (Roberts' Theorem). For this reason, we introduce here a notion of "almost-truthfulness" and investigate the existence of payments enabling the elaboration of almost-truthful mechanisms for non-additive Social Welfare Functions such as Social Gini Evaluation Functions used in fair optimization.

AAAI Conference 2012 Conference Paper

Sequential Decision Making with Rank Dependent Utility: A Minimax Regret Approach

• Gildas Jeantet
• Patrice Perny
• Olivier Spanjaard

This paper is devoted to sequential decision making with Rank Dependent expected Utility (RDU). This decision criterion generalizes Expected Utility and enables to model a wider range of observed (rational) behaviors. In such a sequential decision setting, two conflicting objectives can be identified in the assessment of a strategy: maximizing the performance viewed from the initial state (optimality), and minimizing the incentive to deviate during implementation (deviationproofness). In this paper, we propose a minimax regret approach taking these two aspects into account, and we provide a search procedure to determine an optimal strategy for this model. Numerical results are presented to show the interest of the proposed approach in terms of optimality, deviation-proofness and computability.

AAMAS Conference 2010 Conference Paper

Infinite order Lorenz dominance for fair multiagent optimization

• Boris Golden
• Patrice Perny

This paper deals with fair assignment problems in decisioncontexts involving multiple agents. In such problems, eachagent has its own evaluation of costs and we want to find afair compromise solution between individual point of views. Lorenz dominance is a standard decision model used in Economics to refine Pareto dominance while favoring solutionsthat fairly share happiness among agents. In order to enhance the discrimination possibilities offered by Lorenz dominance, we introduce here a new model called infinite orderLorenz dominance. We establish a representation result forthis model using an ordered weighted average with decreasing weights. Hence we exhibit some properties of infinite order Lorenz dominance that explain how fairness is achievedin the aggregation of individual preferences. Then we explain how to solve fair assignment problems of m items ton agents, using infinite order Lorenz dominance and othermodels used for measuring inequalities. We show that thisproblem can be reformulated as a 0-1 non-linear optimization problems that can be solved, after a linearization step, by standard LP solvers. We provide numerical results showing the efficiency of the proposed approach on various instances of the paper assignment problem.

ECAI Conference 2010 Conference Paper

LP Solvable Models for Multiagent Fair Allocation Problems

• Julien Lesca
• Patrice Perny

This paper proposes several operational approaches for solving fair allocation problems in the context of multiagent optimization. These problems arise in various contexts such as assigning conference papers to referees or sharing of indivisible goods among agents. We present and discuss various social welfare functions that might be used to maximize the satisfaction of agents while maintaining a notion of fairness in the distribution. All these welfare functions are in fact non-linear, which precludes the use of classical min-cost max-flow algorithms for finding an optimal allocation. For each welfare function considered, we present a Mixed Integer Linear Programming formulation of the allocation problem that can be efficiently solved using standard solvers. The results of numerical tests we conducted on realistic cases are given at the end of the paper to confirm the practical feasibility of the proposed approaches.

ECAI Conference 2010 Conference Paper

On Finding Compromise Solutions in Multiobjective Markov Decision Processes

• Patrice Perny
• Paul Weng

IJCAI Conference 2009 Conference Paper

• Jean-Philippe Dubus
• Christophe Gonzales
• Patrice Perny

This paper deals with multiobjective optimization in the context of multiattribute utility theory. The alternatives (feasible solutions) are seen as elements of a product set of attributes and preferences over solutions are represented by generalized additive decomposable (GAI) utility functions modeling individual preferences or criteria. Due to decomposability, utility vectors attached to solutions can be compiled into a graphical structure closely related to junction trees, the so-called GAI net. We first show how the structure of the GAI net can be used to determine efficiently the exact set of Paretooptimal solutions in a product set and provide numerical tests on random instances. Since the exact determination of the Pareto set is intractable in worst case, we propose a near admissible algorithm with performance guarantee, exploiting the GAI structure to approximate the set of Pareto optimal solutions. We present numerical experimentations, showing that both utility decomposition and approximation significantly improve resolution times in multiobjective search problems.

IJCAI Conference 2009 Conference Paper

• Jean-Philippe Dubus
• Christophe Gonzales
• Patrice Perny

This paper deals with Decision-Making in the context of multiattribute utility theory and, more precisely, with the problem of efficiently determining the best alternative w. r. t. an agent’s preferences (choice problem). We assume that alternatives are elements of a product set of attributes and that the agent’s preferences are represented by a generalized additive decomposable (GAI) utility on this set. Such a function allows an efficient representation of interactions between attributes while preserving some decomposability of the model. GAI utilities can be compiled into graphical structures called GAI networks that can be exploited to solve choice problems using collect/distribute schemes essentially similar to those used in Bayesian networks. In this paper, rather than directly using this scheme on the GAI network for determining the most preferred alternative, we propose to work with another GAI function, acting as an upper-bound on utility values and enhancing the model’s decomposability. This method still provides the exact optimal solution but speeds up significantly the search. It proves to be particularly useful when dealing with choice and ranking under constraints and within collective Decision-Making, where GAI nets tend to have a large size. We present an efficient algorithm for determining this new GAI function and provide experimental results highlighting the practical efficiency of our procedure.

ECAI Conference 2008 Conference Paper

Near Admissible Algorithms for Multiobjective Search

• Patrice Perny
• Olivier Spanjaard

In this paper, we propose near admissible multiobjective search algorithms to approximate, with performance guarantee, the set of Pareto optimal solution paths in a state space graph. Approximation of Pareto optimality relies on the use of an epsilon-dominance relation between vectors, significantly narrowing the set of non-dominated solutions. We establish correctness of the proposed algorithms, and discuss computational complexity issues. We present numerical experimentations, showing that approximation significantly improves resolution times in multiobjective search problems.

IJCAI Conference 2007 Conference Paper

• Patrice Perny
• Olivier Spanjaard
• Louis-Xavier Storme

We investigate search problems under risk in state-space graphs, with the aim of finding optimal paths for risk-averse agents. We consider problems where uncertainty is due to the existence of different scenarios of known probabilities, with different impacts on costs of solution-paths. We consider various non-linear decision criteria (EU, RDU, Yaari) to express risk averse preferences; then we provide a general optimization procedure for such criteria, based on a path-ranking algorithm applied on a scalarized valuation of the graph. We also consider partial preference models like second order stochastic dominance (SSD) and propose a multiobjective search algorithm to determine SSD-optimal paths. Finally, the numerical performance of our algorithms are presented and discussed.

AIJ Journal 2007 Journal Article

Corrigendum to “Qualitative decision theory with preference relations and comparative uncertainty: an axiomatic approach” [Artificial Intelligence 148 (1–2) (2003) 219–260]

• Didier Dubois
• Hélène Fargier
• Patrice Perny

UAI Conference 2007 Conference Paper

Search for Choquet-optimal paths under uncertainty

• Lucie Galand
• Patrice Perny

Abstract Choquet expected utility (CEU) is one of the most sophisticated decision criteria used in decision theory under uncertainty. It provides a generalisation of expected utility enhancing both descriptive and prescriptive possibilities. In this paper, we investigate the use of CEU for path-planning under uncertainty with a special focus on robust solutions. We first recall the main features of the CEU model and introduce some examples showing its descriptive potential. Then we focus on the search for Choquet-optimal paths in multivalued implicit graphs where costs depend on different scenarios. After discussing complexity issues, we propose two different heuristic search algorithms to solve the problem. Finally, numerical experiments are reported, showing the practical efficiency of the proposed algorithms.

ECAI Conference 2006 Conference Paper

Reference-Dependent Qualitative Models for Decision Making Under Uncertainty

• Patrice Perny
• Antoine Rolland

The aim of this paper is to introduce and investigate a new family of purely qualitative models for decision making under uncertainty. Such models do not require any numerical representation and rely only on the definition of a preference relation over consequences and a relative likelihood relation on the set of events. Within this family, we focus on decision rules using reference levels in the comparison of acts. We investigate both the descriptive potential of such rules and their axiomatic foundations. We introduce in a Savage-like framework, a new axiom requiring that the Decision Maker's preference between two acts depends on the respective positions of their consequences relatively to reference levels. Under this assumption we determine the only possible form of the decision rule and characterize some particular instances of this rule under transitivity constraints.

ECAI Conference 2006 Conference Paper

Search for Compromise Solutions in Multiobjective State Space Graphs

• Lucie Galand
• Patrice Perny

The aim of this paper is to introduce and solve new search problems in multiobjective state space graphs. Although most of the studies concentrate on the determination of the entire set of Pareto optimal solution paths, the size of which can be, in worst case, exponential in the number of nodes, we consider here more specialized problems where the search is focused on Pareto solutions achieving a well-balanced compromise between the conflicting objectives. After introducing a formal definition of the compromise search problem, we discuss computational issues and the complexity of the problem. Then, we introduce two algorithms to find the best compromise solution-paths in a state space graph. Finally, we report various numerical tests showing that, as far as compromise search is concerned, both algorithms are very efficient (compared to MOA*) but they present contrasted advantages discussed in the conclusion.

IJCAI Conference 2005 Conference Paper

Algebraic Markov Decision Processes

• Patrice Perny
• Olivier Spanjaard
• Paul

In this paper, we provide an algebraic approach to Markov Decision Processes (MDPs), which allows a unified treatment of MDPs and includes many existing models (quantitative or qualitative) as particular cases. In algebraic MDPs, rewards are expressed in a semiring structure, uncertainty is represented by a decomposable plausibility measure valued on a second semiring structure, and preferences over policies are represented by Generalized Expected Utility. We recast the problem of finding an optimal policy at a finite horizon as an algebraic path problem in a decision rule graph where arcs are valued by functions, which justifies the use of the Jacobi algorithm to solve algebraic Bellman equations. In order to show the potential of this general approach, we exhibit new variations of MDPs, admitting complete or partial preference structures, as well as probabilistic or possibilistic representation of uncertainty.

KR Conference 2004 Conference Paper

GAI Networks for Utility Elicitation

• Christophe Gonzales
• Patrice Perny

This paper deals with preference representation and elicitation in the context of multiattribute utility theory under risk. Assuming the decision maker behaves according to the EU model, we investigate the elicitation of generalized additively decomposable utility functions on a product set (GAI-decomposable utilities). We propose a general elicitation procedure based on a new graphical model called a GAI-network. The latter is used to represent and manage independences between attributes, as junction graphs model independences between random variables in Bayesian networks. It is used to design an elicitation questionnaire based on simple lotteries involving completely specified outcomes. Our elicitation procedure is convenient for any GAI-decomposable utility function, thus enhancing the possibilities offered by UCP-networks.

UAI Conference 2003 Conference Paper

An Axiomatic Approach to Robustness in Search Problems with Multiple Scenarios

• Patrice Perny
• Olivier Spanjaard

This paper is devoted to the search of robust solutions in state space graphs when costs depend on scenarios. We first present axiomatic requirements for preference compatibility with the intuitive idea of robustness.This leads us to propose the Lorenz dominance rule as a basis for robustness analysis. Then, after presenting complexity results about the determination of robust solutions, we propose a new sophistication of A* specially designed to determine the set of robust paths in a state space graph. The behavior of the algorithm is illustrated on a small example. Finally, an axiomatic justification of the refinement of robustness by an OWA criterion is provided.

AIJ Journal 2003 Journal Article

Qualitative decision theory with preference relations and comparative uncertainty: An axiomatic approach

• Didier Dubois
• Hélène Fargier
• Patrice Perny

This paper investigates a purely qualitative approach to decision making under uncertainty. Since the pioneering work of Savage, most models of decision under uncertainty rely on a numerical representation where utility and uncertainty are commensurate. Giving up this tradition, we relax this assumption and introduce an axiom of ordinal invariance requiring that the Decision Maker's preference between two acts only depends on the relative position of their consequences for each state. Within this qualitative framework, we determine the only possible form of the corresponding decision rule. Then assuming the transitivity of the strict preference, the underlying partial confidence relations are those at work in non-monotonic inference and thus satisfy one of the main properties of possibility theory. The satisfaction of additional postulates of unanimity and anonymity enforces the use of a necessity measure, unique up to a monotonic transformation, for encoding the relative likelihood of events.

AAAI Conference 2002 Conference Paper

On Preference-Based Search in State Space Graphs

• Patrice Perny

The aim of this paper is to introduce a general framework for preference-based search in state space graphs with a focus on the search of the preferred solutions. After introducing a formal definition of preference-based search problems, we introduce the PBA∗ algorithm, a generalization of the A∗ algorithm, designed to process quasi-transitive preference relations defined over the set of solutions. Then, considering a particular subclass of preference structures characterized by two axioms called Weak Preadditivity and Monotonicity, we establish termination, completeness and admissibility results for PBA∗. We also show that previous generalizations of A∗ are particular instances of PBA∗. The interest of our algorithm is illustrated on a preference-based web access problem.

KR Conference 2002 Conference Paper

On the limitations of ordinal approaches to decision-making

• Didier Dubois
• Helene Fargier
• Patrice Perny

UAI Conference 1999 Conference Paper

Qualitative Models for Decision Under Uncertainty without the Commensurability Assumption

• Hélène Fargier
• Patrice Perny

This paper investigates a purely qualitative version of Savage's theory for decision making under uncertainty. Until now, most representation theorems for preference over acts rely on a numerical representation of utility and uncertainty where utility and uncertainty are commensurate. Disrupting the tradition, we relax this assumption and introduce a purely ordinal axiom requiring that the Decision Maker (DM) preference between two acts only depends on the relative position of their consequences for each state. Within this qualitative framework, we determine the only possible form of the decision rule and investigate some instances compatible with the transitivity of the strict preference. Finally we propose a mild relaxation of our ordinality axiom, leaving room for a new family of qualitative decision rules compatible with transitivity.