Paolo Viappiani

AAMAS Conference 2026 Conference Paper

Fairness in Cooperative Multi-objective Multi-agent Reinforcement Learning using Expected Utility

• Fares Chouaki
• Aurélie Beynier
• Nicolas Maudet
• Paolo Viappiani

Fairness as equity and compromise across multiple viewpoints is a necessary consideration in any decision that is evaluated from several possibly conflicting perspectives. It is also a property that artificial decision-making agents should uphold to be deployable to real-worldproblems. However, existingworkinsequentialdecisionmaking ensures fairness among agents or objectives but struggles with real-world problems that are both multi-agent and multiobjective. Furthermore, research integrating fairness into Multi- ObjectiveReinforcementLearning(MORL)isfocusedonoptimizing the Scalarized Expected Return (SER) criterion while mostly ignoring the Expected Scalarized Return (ESR) criterion. We argue that fairness in MORL should also be investigated under ESR since it is sometimes more suitable when solving problems where fairness matters. In this paper, we study objective-wise fairness in cooperative multi-agent multi-objective decision-making under ESR. We propose the first algorithm that learns efficient decentralized policies while enforcing fairness across objectives under ESR. We identify a key challenge in this setting related to policy conditioning on globally accumulated returns, which hinders decentralized learning and execution, and we present an approach to address it based on inter-agent communication. Experiments on discrete and continuous control tasks demonstrate that our method outperforms existing baselines.

AAMAS Conference 2026 Conference Paper

Multi-Objective Categorical Deep Q-Networks

• Farès Chouaki
• Aurélie Beynier
• Nicolas Maudet
• Paolo Viappiani

Motivated by recent advances in distributional reinforcement learning on the one hand and Multi-Objective Reinforcement Learning (MORL) on the other, we propose MO-CDQN, a value-based algorithmthat, givenapossiblynon-linearscalarizationfunction, learns the policy with maximal expected scalarized return. Leveraging the Kantorovich-Rubinstein duality, we prove the theoretical validity of our method for Lipschitz-continuous scalarization functions. We establish that the state-action return distributions learned by our algorithm converge to a fixed point whose expected scalarized return is optimal. Our approach is then extended to propose the first valuebased multi-policy algorithm for solving MORL problems under the expected scalarized return criterion. The proposed algorithms are tested on several environments from the MO-gymnasium benchmark. The results are promising and show that, on the one hand, our algorithm learns policies better than those obtained by existing approaches in the literature while requiring fewer interactions with the environment. On the other hand, given a set of scalarization functions, our multi-policy algorithm takes advantage of its offpolicy nature to successfully optimize several policies concurrently and efficiently provide a set of policies, each optimal for a given scalarization function.

AAMAS Conference 2025 Conference Paper

Fairness in Cooperative Multi-agent Multi-objective Reinforcement Learning using the Expected Scalarized Return

• Farès Chouaki
• Aurélie Beynier
• Nicolas Maudet
• Paolo Viappiani

Fairness is essential for deploying artificial decision-making agents in the real world. Existing work in sequential decision-making ensures fairness among agents or objectives but struggles with real-world problems that are both multi-agent and multi-objective. Furthermore, research integrating fairness into Multi-Objective Reinforcement Learning (MORL) is focused on ensuring fairness over the objectives only on the average of several executions of a policy, which is achived by optimizing the policy’s scalarized expected return (SER). To achieve fairness over objectives during each execution the expected scalarized return (ESR) of a policy needs to be optimized instead. This paper presents an argument on the necessity of using ESR in the context of fair multi-objective decision-making and proposes the first mono-policy algorithm able to learn efficient decentralized policies while ensuring fairness across objectives under ESR.

ECAI Conference 2025 Conference Paper

From Order Lifting to Social Ranking: Recovering Preferences from Partial Extensions

• Ariane Ravier
• Sébastien Konieczny
• Stefano Moretti 0001
• Paolo Viappiani

Several methods have been introduced in the literature to extend preferences over items from a population to preferences over the groups they may form - a problem known as the Order Lifting problem. The converse matter of deducing preferences over items from expressed preferences over the coalitions that may be formed within a population - a problem known as the Social Ranking Problem - has also been studied more recently. In this paper, we investigate the links between these two problems: after an examination of the general case, we consider the impact of missing information, by studying which social ranking methods allow for the most accurate recovery of initial preferences over items, depending on the amount of missing information about coalitions. Finally, we consider the specific case in which preferences are only expressed over coalitions of same size, and examine the accuracy of social ranking methods when faced with impartial information about preferences over k-sized coalitions.

TMLR Journal 2024 Journal Article

Personalized Algorithmic Recourse with Preference Elicitation

• Giovanni De Toni
• Paolo Viappiani
• Stefano Teso
• Bruno Lepri
• Andrea Passerini

Algorithmic Recourse (AR) is the problem of computing a sequence of actions that -- once performed by a user -- overturns an undesirable machine decision. It is paramount that the sequence of actions does not require too much effort for users to implement. Yet, most approaches to AR assume that actions cost the same for all users, and thus may recommend unfairly expensive recourse plans to certain users. Prompted by this observation, we introduce PEAR, the first human-in-the-loop approach capable of providing personalized algorithmic recourse tailored to the needs of any end-user. PEAR builds on insights from Bayesian Preference Elicitation to iteratively refine an estimate of the costs of actions by asking choice set queries to the target user. The queries themselves are computed by maximizing the Expected Utility of Selection, a principled measure of information gain accounting for uncertainty on both the cost estimate and the user's responses. PEAR integrates elicitation into a Reinforcement Learning agent coupled with Monte Carlo Tree Search to quickly identify promising recourse plans. Our empirical evaluation on real-world datasets highlights how PEAR produces high-quality personalized recourse in only a handful of iterations.

ECAI Conference 2023 Conference Paper

Environmentally-Aware Bundle Recommendation Using the Choquet Integral

• Marco Bronzini
• Erich Robbi
• Paolo Viappiani
• Andrea Passerini

Nowadays, the environmental footprint of a process has become an important aspect to be considered in each human activity from industrial production to logistics. Despite this increased awareness, environmental friendliness is a quite new aspect in the IT sector and even less considered in the field of recommendation systems. Bundle recommendation aims to generate bundles of associated products that users tend to consume as a whole under certain circumstances, and poses additional challenges in terms of environmental friendliness. Nevertheless, current bundle recommendation systems fail to consider the environmental impact of the product bundle when generating recommendations. We introduce a new preference-based approach for bundle recommendation exploiting the Choquet integral. This allows us to formalize preferences for coalitions of environmental-related attributes, thus recommending product bundles accounting for synergies among product attributes. An experimental evaluation on a dataset of local food products in Northern Italy shows how the Choquet integral allows to naturally formalize a sensible notion of environmental friendliness, and that standard approaches based on weighted sums of attributes end up recommending bundles with lower environmental friendliness even if weights are explicitly learned to maximize it.

AAMAS Conference 2021 Conference Paper

Efficient Exact Computation of Setwise Minimax Regret for Interactive Preference Elicitation

• Federico Toffano
• Paolo Viappiani
• Nic Wilson

A key issue in artificial intelligence methods for interactive preference elicitation is choosing at each stage an appropriate query to the user, in order to find a near-optimal solution as quickly as possible. A theoretically attractive method is to choose a query that minimises max setwise regret (which corresponds to the worst case loss response in terms of value of information). We focus here on the situation in which the choices are represented explicitly in a database, and with a model of user utility as a weighted sum of the criteria; in this case when the user makes a choice, an agent learns a linear constraint on the unknown vector of weights. We develop an algorithmic method for computing minimax setwise regret for this form of preference model, by making use of a SAT solver with cardinality constraints to prune the search space, and computing max setwise regret using an extreme points method. Our experimental results demonstrate the feasibility of the approach and the very substantial speed up over the state of the art.

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.

AIJ Journal 2020 Journal Article

On the equivalence of optimal recommendation sets and myopically optimal query sets

• Paolo Viappiani
• Craig Boutilier

Preference elicitation is an important component in many AI applications, including decision support and recommender systems. Such systems must assess user preferences, based on interactions with their users, and make recommendations using (possibly incomplete and imprecise) beliefs about those preferences. Mechanisms for explicit preference elicitation—asking users to answer direct queries about their preferences—can be of great value; but due to the cognitive and time cost imposed on users, it is important to minimize the number of queries by asking those that have high (expected) value of information. An alternative approach is to simply make recommendations and have users provide feedback (e. g. , accept a recommendation or critique it in some way) and use this more indirect feedback to gradually improve the quality of the recommendations. Due to inherent uncertainty about a user's true preferences, often a set of recommendations is presented to the user at each stage. Conceptually, a set of recommendations can also be viewed as choice query, in which the user indicates which option is most preferred from that set. Because of the potential tension between making a good set recommendation and asking an informative choice query, we explore the connection between the two. We consider two different models of preference uncertainty and optimization: (a) a Bayesian framework in which a posterior over user utility functions is maintained, optimal recommendations are assessed using expected utility, and queries are assessed using expected value of information; and (b) a minimax-regret framework in which user utility uncertainty is strict (represented by a polytope), recommendations are made using the minimax-regret robustness criterion, and queries are assessed using worst-case regret reduction. We show that, somewhat surprisingly, in both cases, there is no tradeoff to be made between good recommendations and good queries: we prove that the optimal recommendation set of size k is also an optimal choice query of size k. We also examine the case where user responses to choice queries are error prone (using both constant and mixed multinomial logit noise models) showing the results are robust to this form of noise. In both frameworks, our theoretical results have practical consequences for the design of interactive recommenders. Our results also allow us to design efficient algorithms to compute optimal query/recommendation sets. We develop several such algorithms (both exact and approximate) for both settings and provide empirical validation of their performance.

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.

IJCAI Conference 2016 Conference Paper

Constructive Preference Elicitation by Setwise Max-Margin Learning

• Stefano Teso
• Andrea Passerini
• Paolo Viappiani

In this paper we propose an approach to preference elicitation that is suitable to large configuration spaces beyond the reach of existing state-of-the-art approaches. Our setwise max-margin method can be viewed as a generalization of max-margin learning to sets, and can produce a set of diverse items that can be used to ask informative queries to the user. Moreover, the approach can encourage sparsity in the parameter space, in order to favor the assessment of utility towards combinations of weights that concentrate on just few features. We present a mixed integer linear programming formulation and show how our approach compares favourably with Bayesian preference elicitation alternatives and easily scales to realistic datasets.

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.

UAI Conference 2016 Conference Paper

Model-Free Reinforcement Learning with Skew-Symmetric Bilinear Utilities

• Hugo Gilbert
• Bruno Zanuttini
• Paul Weng
• Paolo Viappiani
• Esther Nicart

In reinforcement learning, policies are typically evaluated according to the expectation of cumulated rewards. Researchers in decision theory have argued that more sophisticated decision criteria can better model the preferences of a decision maker. In particular, Skew-Symmetric Bilinear (SSB) utility functions generalize von Neumann and Morgenstern’s expected utility (EU) theory to encompass rational decision behaviors that EU cannot accommodate. In this paper, we adopt an SSB utility function to compare policies in the reinforcement learning setting. We provide a model-free SSB reinforcement learning algorithm, SSB Q-learning, and prove its convergence towards a policy that is -optimal according to SSB. The proposed algorithm is an adaptation of fictitious play [Brown, 1951] combined with techniques from stochastic approximation [Borkar, 1997]. We also present some experimental results which evaluate our approach in a variety of settings.

IJCAI Conference 2015 Conference Paper

Characterization of Scoring Rules with Distances: Application to the Clustering of Rankings

• Paolo Viappiani

Positional scoring rules are often used for rank aggregation. In this work we study how scoring rules can be formulated as the minimization of some distance measures between rankings, and we also consider a new family of aggregation methods, called biased scoring rules. This work extends a previous known observation connecting Borda count with the minimization of the sum of the Spearman distances (calculated with respect to a set of input rankings). In particular we consider generalizations of the Spearman distance that can give different weights to items and positions; we also handle the case of incomplete rank data. This has applications in the clustering of rank data, where two main steps need to be performed: aggregating rankings of the same cluster into a representative ranking (the cluster’s centroid) and assigning each ranking to its closest centroid. Using the proper combination of scoring rules (for aggregation) and distances (for assignment), it is possible to perform clustering in a computationally efficient way and as well account for specific desired behaviors (give more weight to top positions, bias the centroids in favor of particular items).

IJCAI Conference 2015 Conference Paper

Solving MDPs with Skew Symmetric Bilinear Utility Functions

• Hugo Gilbert
• Olivier Spanjaard
• Paolo Viappiani
• Paul Weng

In this paper we adopt Skew Symmetric Bilinear (SSB) utility functions to compare policies in Markov Decision Processes (MDPs). By considering pairs of alternatives, SSB utility theory generalizes von Neumann and Morgenstern’s expected utility (EU) theory to encompass rational decision behaviors that EU cannot accommodate. We provide a game-theoretic analysis of the problem of identifying an SSB-optimal policy in finite horizon MDPs and propose an algorithm based on a double oracle approach for computing an optimal (possibly randomized) policy. Finally, we present and discuss experimental results where SSB-optimal policies are computed for a popular TV contest according to several instantiations of SSB utility functions.

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 2011 Conference Paper

Recommendation Sets and Choice Queries: There Is No Exploration/Exploitation Tradeoff!

• Paolo Viappiani
• Craig Boutilier

NeurIPS Conference 2010 Conference Paper

Optimal Bayesian Recommendation Sets and Myopically Optimal Choice Query Sets

• Paolo Viappiani
• Craig Boutilier

Bayesian approaches to utility elicitation typically adopt (myopic) expected value of information (EVOI) as a natural criterion for selecting queries. However, EVOI-optimization is usually computationally prohibitive. In this paper, we examine EVOI optimization using \emph{choice queries}, queries in which a user is ask to select her most preferred product from a set. We show that, under very general assumptions, the optimal choice query w. r. t. \ EVOI coincides with \emph{optimal recommendation set}, that is, a set maximizing expected utility of the user selection. Since recommendation set optimization is a simpler, submodular problem, this can greatly reduce the complexity of both exact and approximate (greedy) computation of optimal choice queries. We also examine the case where user responses to choice queries are error-prone (using both constant and follow mixed multinomial logit noise models) and provide worst-case guarantees. Finally we present a local search technique that works well with large outcome spaces.

AAAI Conference 2010 Conference Paper

Simultaneous Elicitation of Preference Features and Utility

• Craig Boutilier
• Kevin Regan
• Paolo Viappiani

Most frameworks for utility elicitation assume a predefined set of features over which user preferences are expressed. We consider utility elicitation in the presence of subjective or user-defined features, whose definitions are not known in advance. We treat the problem of learning a user’s feature definition as one of concept learning, but whose goal is to learn only enough about the concept definition to enable a good decision to be made. This is complicated by the fact that user utility is unknown. We describe computational procedures for identifying optimal alternatives w. r. t minimax regret in the presence of both utility and concept uncertainty; and develop several heuristic query strategies that focus simultaneously on reduction of relevant concept and utility uncertainty.

ICML Conference 2009 Conference Paper

Online feature elicitation in interactive optimization

• Craig Boutilier
• Kevin Regan 0001
• Paolo Viappiani

AAAI Conference 2006 Conference Paper

Evaluating Preference-based Search Tools: A Tale of Two Approaches

• Paolo Viappiani

People frequently use the world-wide web to find their most preferred item among a large range of options. We call this task preference-based search. The most common tool for preference-based search on the WWW today obtains users’ preferences by asking them to fill in a form. It then returns a list of items that most closely match these preferences. Recently, several researchers have proposed tools for preference-based search that elicit preferences from the critiques a user actively makes on examples shown to them. We carried out a user study in order to compare the performance of traditional preference-based search tools using form-filling with two different versions of an example-critiquing tool. The results show that example critiquing achieves almost three times the decision accuracy, while requiring only slightly higher interaction effort.