Olivier Spanjaard

ECAI Conference 2024 Conference Paper

Learning and Optimizing with an SSB Representation of Intransitive Preferences on Sets

• Hugo Gilbert
• Mohamed Ouaguenouni
• Olivier Spanjaard

We propose a Skew-Symmetric Bilinear (SSB) model to represent intransitive preferences on subsets of a ground set of items. More precisely, the SSB model accounts for preference intensities between pairs of subsets. We provide a procedure to learn the parameters of the SSB model from a set of known pairwise preferences between subsets, managing to find a sparse model, and as simple as possible in terms of the degree of interaction between items. The SSB model can be viewed as a concise representation of a weighted tournament on subsets. We study the complexity of determining the winners according to various tournament rules. Numerical tests on synthetic and real-world data are carried out.

ECAI Conference 2023 Conference Paper

A Hybrid Approach to Preference Learning with Interaction Terms

• Hugo Gilbert
• Mohamed Ouaguenouni
• Meltem Öztürk
• Olivier Spanjaard

Preference learning is an essential component in numerous applications, such as recommendation systems, decision-making processes, and personalized services. We propose here a novel approach to preference learning that interleaves Gaussian Processes (GP) and Robust Ordinal Regression (ROR). A Gaussian process gives a probability distribution on the latent function values that generate users’ preferences. Our method extends the traditional non-parametric Gaussian process framework by approximating the latent function by a very flexible parameterized function, that we call θ-additive function, where θ is the parameter set. The set θ reflects the degree of sophistication of the generalized additive model that can potentially represent the user’s preferences. To learn what are the components of θ, we update a probability distribution on the space of all possible sets θ, depending on the ability of the parameterized function to approximate the latent function. We predict pairwise preferences by using the parameter set θ that maximizes the posterior distribution and by performing robust ordinal regression based on this parameter set. Experimental results on synthetic data demonstrate the effectiveness and robustness of our proposed methodology.

ECAI Conference 2023 Conference Paper

Algorithmic Recognition of 2-Euclidean Preferences

• Bruno Escoffier
• Olivier Spanjaard
• Magdaléna Tydrichová

A set of voters’ preferences on a set of candidates is 2-Euclidean if candidates and voters can be mapped to the plane so that the preferences of each voter decrease with the Euclidean distance between her position and the positions of candidates. Based on geometric properties, we propose a recognition algorithm, that returns either “yes” (together with a planar positioning of candidates and voters) if the preferences are 2-Euclidean, or “no” if it is able to find a concise certificate that they are not, or “unknown” if a time limit is reached. Our algorithm outperforms a quadratically constrained programming solver achieving the same task, both in running times and the percentage of instances it is able to recognize. In the numerical tests conducted on the PrefLib library of preferences, 91. 5% (resp. 4. 5%) of the available sets of complete strict orders are proven not to be (resp. to be) 2-Euclidean, and the status of only 4. 5% of them could not be decided. Furthermore, for instances involving 5 (resp. 6, 7) candidates, we were able to find planar representations that are compatible with 87. 4% (resp. 58. 1%, 60. 1%) of voters’ preferences.

AAMAS Conference 2023 Conference Paper

Robust Ordinal Regression for Collaborative Preference Learning with Opinion Synergies

• Hugo Gilbert
• Mohamed Ouaguenouni
• Meltem Öztürk
• Olivier Spanjaard

This work focuses on a robust learning methodology in a collaborative filtering context. We wish to predict preferences between alternatives characterized by binary attributes, where each attribute represents the opinion of a reference user on the alternative. The model whose parameters we learn is general enough to be compatible with any strict weak order on the attribute vectors, thanks to the consideration of opinion synergies. Moreover, we accept not to predict some preferences if the data collected are not compatible with a reliable prediction. A predicted preference will be considered reliable if all the simplest models explaining the training data agree on it. Following the robust ordinal regression methodology, our predictions are based on an ordinal dominance relation between alternatives introduced by Fishburn and LaValle [11] which relies on an uncertainty set encompassing the possible values of the parameters of the multi-attribute utility function.

TCS Journal 2022 Journal Article

Beyond pairwise comparisons in social choice: A setwise Kemeny aggregation problem

• Hugo Gilbert
• Tom Portoleau
• Olivier Spanjaard

In this paper, we advocate the use of setwise contests for aggregating a set of input rankings into an output ranking. We propose a generalization of the Kemeny rule where one minimizes the number of k-wise disagreements instead of pairwise disagreements (one counts 1 disagreement each time the top choice in a subset of alternatives of cardinality at most k differs between an input ranking and the output ranking). After an algorithmic study of this k-wise Kemeny aggregation problem, we introduce a k-wise counterpart of the majority graph. This graph reveals useful to divide the aggregation problem into several sub-problems, which enables to speed up the exact computation of a consensus ranking. By introducing a k-wise counterpart of the Spearman distance, we also provide a 2-approximation algorithm for the k-wise Kemeny aggregation problem. We conclude with numerical tests.

AAAI Conference 2020 Conference Paper

Beyond Pairwise Comparisons in Social Choice: A Setwise Kemeny Aggregation Problem

• Hugo Gilbert
• Tom Portoleau
• Olivier Spanjaard

In this paper, we advocate the use of setwise contests for aggregating a set of input rankings into an output ranking. We propose a generalization of the Kemeny rule where one minimizes the number of k-wise disagreements instead of pairwise disagreements (one counts 1 disagreement each time the top choice in a subset of alternatives of cardinality at most k differs between an input ranking and the output ranking). After an algorithmic study of this k-wise Kemeny aggregation problem, we introduce a k-wise counterpart of the majority graph. It reveals useful to divide the aggregation problem into several sub-problems. We conclude with numerical tests.

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.

UAI Conference 2017 Conference Paper

Complexity of Solving Decision Trees with Skew-Symmetric Bilinear Utility

• Hugo Gilbert
• Olivier Spanjaard

We study the complexity of solving decision trees with a Skew-Symmetric Bilinear (SSB) utility function. The SSB model is an extension of Expected Utility (EU) with enhanced descriptive possibilities. Unlike EU, the optimality principle does not hold for SSB, which makes its optimization trickier. We show that determining an SSB optimal plan is NP-hard if one only considers deterministic plans while it is polynomial time if one allows randomized plans. With the Weighted EU model (a special case of SSB), the problem becomes polynomial in both settings. Our numerical tests show the operationality of the methods.

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.

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

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.

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

Kemeny Elections with Bounded Single-Peaked or Single-Crossing Width

• Denis Cornaz
• Lucie Galand
• Olivier Spanjaard

This paper is devoted to complexity results regarding specific measures of proximity to singlepeakedness and single-crossingness, called “singlepeaked width” [Cornaz et al. , 2012] and “singlecrossing width”. Thanks to the use of the PQ-tree data structure [Booth and Lueker, 1976], we show that both problems are polynomial time solvable in the general case (while it was only known for single-peaked width and in the case of narcissistic preferences). Furthermore, we establish one of the first results (to our knowledge) concerning the effect of nearly single-peaked electorates on the complexity of an NP-hard voting system, namely we show the fixed-parameter tractability of Kemeny elections with respect to the parameters “singlepeaked width” and “single-crossing width”.

ECAI Conference 2012 Conference Paper

Bounded Single-Peaked Width and Proportional Representation

• Denis Cornaz
• Lucie Galand
• Olivier Spanjaard

This paper is devoted to the proportional representation (PR) problem when the preferences are clustered single-peaked. PR is a "multi-winner" election problem, that we study in Chamberlin and Courant's scheme [6]. We define clustered single-peakedness as a form of single-peakedness with respect to clusters of candidates, i. e. subsets of candidates that are consecutive (in arbitrary order) in the preferences of all voters. We show that the PR problem becomes polynomial when the size of the largest cluster of candidates (width) is bounded. Furthermore, we establish the polynomiality of determining the single-peaked width of a preference profile (minimum width for a partition of candidates into clusters compatible with clustered single-peakedness) when the preferences are narcissistic (i. e. , every candidate is the most preferred one for some voter).

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.

AIJ Journal 2011 Journal Article

Computing rank dependent utility in graphical models for sequential decision problems

• Gildas Jeantet
• Olivier Spanjaard

This paper is devoted to automated sequential decision in AI. More precisely, we focus here on the Rank Dependent Utility (RDU) model. This model is able to encompass rational decision behaviors that the Expected Utility model cannot accommodate. However, the non-linearity of RDU makes it difficult to compute an RDU-optimal strategy in sequential decision problems. This has considerably slowed the use of RDU in operational contexts. In this paper, we are interested in providing new algorithmic solutions to compute an RDU-optimal strategy in graphical models. Specifically, we present algorithms for solving decision tree models and influence diagram models of sequential decision problems. For decision tree models, we propose a mixed integer programming formulation that is valid for a subclass of RDU models (corresponding to risk seeking behaviors). This formulation reduces to a linear program when mixed strategies are considered. In the general case (i. e. , when there is no particular assumption on the parameters of RDU), we propose a branch and bound procedure to compute an RDU-optimal strategy among the pure ones. After highlighting the difficulties induced by the use of RDU in influence diagram models, we show how this latter procedure can be extended to optimize RDU in an influence diagram. Finally, we provide empirical evaluations of all the presented algorithms.

IJCAI Conference 2011 Conference Paper

Resolute Choice in Sequential Decision Problems with Multiple Priors

• H
• eacute; l
• egrave; ne Fargier
• Gildas Jeantet
• Olivier Spanjaard

This paper is devoted to sequential decision making under uncertainty, in the multi-prior framework of Gilboa and Schmeidler [1989]. In this setting, a set of probability measures (priors) is defined instead of a single one, and the decision maker selects a strategy that maximizes the minimum possible value of expected utility over this set of priors. We are interested here in the resolute choice approach, where one initially commits to a complete strategy and never deviates from it later. Given a decision tree representation with multiple priors, we study the problem of determining an optimal strategy from the root according to min expected utility. We prove the intractability of evaluating a strategy in the general case. We then identify different properties of a decision tree that enable to design dedicated resolution procedures. Finally, experimental results are presented that evaluate these procedures.

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.

ICAPS Conference 2008 Conference Paper

Rank-Dependent Probability Weighting in Sequential Decision Problems under Uncertainty

• Gildas Jeantet
• Olivier Spanjaard

This paper is devoted to the computation of optimal strategies in automated sequential decision problems. We consider here problems where one seeks a strategy which is optimal for rank dependent utility (RDU). RDU generalizes von Neumann and Morgenstern's expected utility (by probability weighting) to encompass rational decision behaviors that EU cannot accomodate. The induced algorithmic problem is however more difficult to solve since the optimality principle does not hold anymore. More crucially, we prove here that the search for an optimal strategy (w. r. t. RDU) in a decision tree is an NP-hard problem. We propose an implicit enumeration algorithm to compute optimal rank dependent utility in decision trees. The performances of our algorithm on randomly generated instances and real-world instances of different sizes are presented and discussed.

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.

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.

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.