Jérôme Mengin

AAAI Conference 2026 Conference Paper

Explaining Tournament Solutions with Minimal Supports

• Clément Contet
• Umberto Grandi
• Jérôme Mengin

Tournaments are widely used models to represent pairwise dominance between candidates, alternatives, or teams. We study the problem of providing certified explanations for why a candidate appears among the winners under various tournament rules. To this end, we identify minimal supports—minimal sub-tournaments in which the candidate is guaranteed to win regardless of how the rest of the tournament is completed (that is, the candidate is a necessary winner of the sub-tournament). This notion corresponds to an abductive explanation for the question,"Why does the winner win the tournament?"—a central concept in formal explainable AI. We focus on common tournament solutions: the top cycle, the uncovered set, the Copeland rule, the Borda rule, the maximin rule, and the weighted uncovered set. For each rule we determine the size of the smallest minimal supports, and we present polynomial-time algorithms to compute them for all solutions except for the weighted uncovered set, for which the problem is NP-complete. Finally, we show how minimal supports can serve to produce compact, certified, and intuitive explanations for tournament solutions.

ECAI Conference 2024 Conference Paper

Abductive and Contrastive Explanations for Scoring Rules in Voting

• Clément Contet
• Umberto Grandi
• Jérôme Mengin

We view voting rules as classifiers that assign a winner (a class) to a profile of voters’ preferences (an instance). We propose to apply techniques from formal explainability, most notably abductive and contrastive explanations, to identify minimal subsets of a preference profile that either imply the current winner or explain why a different candidate was not elected. Formal explanations turn out to have strong connections with classical problems studied in computational social choice such as bribery, possible and necessary winner identification, and preference learning. We design algorithms for computing abductive and contrastive explanations for scoring rules. For the Borda rule, we find a lower bound on the size of the smallest abductive explanations, and we conduct simulations to identify correlations between properties of preference profiles and the size of their smallest abductive explanations.

IJCAI Conference 2024 Conference Paper

Learning Conditional Preference Networks: An Approach Based on the Minimum Description Length Principle

• Pierre-François Gimenez
• Jérôme Mengin

CP-nets are a very expressive graphical model for the representation of preferences over combinatorial spaces. They are particularly well suited for settings where an important task is to compute the optimal completion of some partially specified alternative; this is for instance the case of interactive configurators, where preferences can be used, at every step of the interaction, to guide the decision maker towards a satisfactory configuration. Learning CP-nets turns out to be challenging when the input data has the form of pairwise comparisons between alternatives. Furthermore, this type of preference data is not commonly stored: it can be elicitated but this puts an additional burden on the decision maker. In this article, we propose a new method for learning CP-nets from sales history, a kind of data readily available in many e-commerce applications. The approach is based on the the minimum description length (MDL) principle. We show some theoretical properties of this learning task, namely its sample complexity and its NP-completeness, and we experiment this learning algorithm in a recommendation settings with a real sales history from a car maker.

ECAI Conference 2023 Conference Paper

Conditionally Acyclic CO-Networks for Efficient Preferential Optimization

• Pierre-François Gimenez
• Jérôme Mengin

This paper focuses on graphical models for modelling preferences in combinatorial space and their use for item optimisation. The preferential optimisation task seeks to find the preferred item containing some defined values, which is useful for many recommendation settings in e-commerce. We show that efficient (i. e. , with polynomial time complexity) preferential optimisation is achieved with a subset of cyclic CP-nets called conditional acyclic CP-net. We also introduce a new graphical preference model, called Conditional-Optimality networks (CO-networks), that are more concise than conditional acyclic CP-nets and LP-trees but have the same expressiveness with respect to optimisation. Finally, we empirically show that preferential optimisation can be used for encoding alternatives into partial instantiations and vice versa, paving the way towards CO-nets and CP-nets unsupervised learning with the minimal description length (MDL) principle.

AAMAS Conference 2021 Conference Paper

A Knowledge Compilation Map for Conditional Preference Statements-based Languages

• Hélène Fargier
• Jérôme Mengin

Conditional preference statements have been used to compactly represent preferences over combinatorial domains. They are at the core of CP-nets and their generalizations, and lexicographic preference trees. Several works have addressed the complexity of some queries (optimization, dominance in particular). We extend in this paper some of these results, and study other queries which have not been addressed so far, like equivalence, thereby contributing to a knowledge compilation map for languages based on conditional preference statements. We also introduce a new parameterised family of languages, which enables to balance expressiveness against the complexity of some queries.

AAAI Conference 2018 Conference Paper

Learning Lexicographic Preference Trees From Positive Examples

• Hélène Fargier
• Pierre-François Gimenez
• Jérôme Mengin

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

AIJ Journal 2018 Journal Article

Voting on multi-issue domains with conditionally lexicographic preferences

• Jérôme Lang
• Jérôme Mengin
• Lirong Xia

One approach to voting on several interrelated issues consists in using a language for compact preference representation, from which the voters' preferences are elicited and aggregated. Such a language can usually be seen as a domain restriction. We consider a well-known restriction, namely, conditionally lexicographic preferences, where both the relative importance between issues and the preference between the values of an issue may depend on the values taken by more important issues. The naturally associated language consists in describing conditional importance and conditional preference by trees together with conditional preference tables. In this paper, we study the aggregation of conditionally lexicographic preferences for several common voting rules and several classes of lexicographic preferences. We address the computation of the winning alternative for some important rules, both by identifying the computational complexity of the relevant problems and by showing that for several of them, computing the winner reduces in a very natural way to a maxsat problem.

UAI Conference 2013 Conference Paper

Probabilistic Conditional Preference Networks

• Damien Bigot
• Bruno Zanuttini
• Hélène Fargier
• Jérôme Mengin

This paper proposes a “probabilistic” extension of conditional preference networks as a way to compactly represent a probability distributions over preference orderings. It studies the probabilistic counterparts of the main reasoning tasks, namely dominance testing and optimisation from the algorithmical and complexity viewpoints. Efficient algorithms for tree-structured probabilistic CP-nets are given. As a by-product we obtain a lineartime algorithm for dominance testing in standard, tree-structured CP-nets.

ECAI Conference 2010 Conference Paper

Learning conditionally lexicographic preference relations

• Richard Booth 0001
• Yann Chevaleyre
• Jérôme Lang
• Jérôme Mengin
• Chattrakul Sombattheera

We consider the problem of learning a user's ordinal preferences on a multiattribute domain, assuming that her preferences are lexicographic. We introduce a general graphical representation called LP-trees which captures various natural classes of such preference relations, depending on whether the importance order between attributes and/or the local preferences on the domain of each attribute is conditional on the values of other attributes. For each class we determine the Vapnik-Chernovenkis dimension, the communication complexity of preference elicitation, and the complexity of identifying a model in the class consistent with a set of user-provided examples.

IJCAI Conference 2009 Conference Paper

• Jérôme Lang
• Jérôme Mengin

We address the problem of learning preference relations on multi-attribute (or combinatorial) domains. We do so by making a very simple hypothesis about the dependence structure between attributes that the preference relation enjoys, namely separability (no preferential dependencies between attributes). Given a set of examples consisting of comparisons between alternatives, we want to output a separable CP-net, consisting of local preferences on each of the attributes, that fits the examples. We consider three forms of compatibility between a CP-net and a set of examples, and for each of them we give useful characterizations as well as complexity results.

JELIA Conference 2008 Conference Paper

Uniform Interpolation by Resolution in Modal Logic

• Andreas Herzig
• Jérôme Mengin

Abstract The problem of computing a uniform interpolant of a given formula on a sublanguage is known in Artificial Intelligence as variable forgetting. In propositional logic, there are well known methods for performing variable forgetting. Variable forgetting is more involved in modal logics, because one must forget a variable not in one world, but in several worlds. It has been shown that modal logic K has the uniform interpolation property, and a method has recently been proposed for forgetting variables in a modal formula (of mu-calculus) given in disjunctive normal form. However, there are cases where information comes naturally in a more conjunctive form. In this paper, we propose a method, based on an extension of resolution to modal logics, to perform variable forgetting for formulae in conjunctive normal form, in the modal logic K.

JELIA Conference 2004 Conference Paper

Logical Connectives for Nonmonotonicity: A Choice Function-Based Approach

• Jérôme Mengin

Abstract Several semantics for logics that model defeasible inference are based on the idea that not all models of a set F of classical formulas should be considered, but only some of them, the preferred ones. Recently, Daniel Lehmann proved that a very general family of nonmonotonic inference relations can be obtained by using choice functions, that pick some of the models of a given set of logical formulas. However, in this setting the choice function is fixed. This paper describes a semantics where the choice function is defined by formulas: instead of associating a set of models with each formula of the language, we associate a choice function which picks some models. The choice functions are defined for atomic formulas first, and then inductively for every formula, using for each connective a corresponding operator for combining choice functions. We show that this approach generalises classical logic: the choice function associated to a classical formula ϕ is the function that picks, from a set of models M, the elements of M that satisfy ϕ in the classical sense. We then describe operations on choice functions that correspond to connectives meaning for example: “p if it is consistent” or “p prior to q”.

JELIA Conference 2004 Conference Paper

On Sceptical Versus Credulous Acceptance for Abstract Argument Systems

• Sylvie Doutre
• Jérôme Mengin

Abstract At a high level of abstraction, many systems of argumentation can be represented by a set of abstract arguments, and a binary relation between these abstract arguments describing how they contradict each other. Acceptable sets of arguments, called extensions, can be defined as sets of arguments that do not contradict one another, and attack all their attackers. We are interested in this paper in answering the question: is a given argument in all extensions of an argumentation system? In fact, what is likely to be useful in AI systems is not a simple yes/no answer, but some kind of well-argued answer, called a proof: if an argument is in every extension, why is it so? Several authors have described proofs that explain why a given argument is in at least one extension. In this paper, we show that a proof that an argument is in every extension can be a proof that some meta -argument is in at least one extension of a meta -argumentation system: this meta-argumentation system describes relationships between sets of arguments of the initial system.

NMR Workshop 2004 Conference Paper

On sceptical vs credulous acceptance for abstract argument systems

• Sylvie Doutre
• Jérôme Mengin

At a high level of abstraction, many systems of argumentation can be represented by a set of abstract arguments, and a binary relation between these abstract arguments describing how they contradict each other. Acceptable sets of arguments, called extensions, can be defined as sets of arguments that do not contradict one another, and attack all their attackers. We are interested in this paper in answering the question: is a given argument in all extensions of an argumentation system? In fact, what is likely to be useful in AI systems is not a simple yes/no answer, but some kind of well-argued answer, called a proof: if an argument is in every extension, why is it so? We describe a close connection between this problem and proofs that some meta-argument is in at least one extension of a meta-argumentation system, describing relationships between sets of arguments of the initial system.

NMR Workshop 2002 Conference Paper

"Minimal defence": a refinement of the preferred semantics for argumentation frameworks

• Claudette Cayrol
• Sylvie Doutre
• Marie-Christine Lagasquie-Schiex
• Jérôme Mengin

Dung’s abstract framework for argumentation enables a study of the interactions between arguments based solely on an “attack” binary relation on the set of arguments. Various ways to solve conflicts between contradictory pieces of information have been proposed in the context of argumentation, nonmonotonic reasoning or logic programming, and can be captured by appropriate semantics within Dung’s framework. A common feature of these semantics is that one can always maximize in some sense the set of acceptable arguments. We propose in this paper to extend Dung’s framework in order to allow for the representation of what we call “restricted” arguments: these arguments should only be used if absolutely necessary, that is, in order to support other arguments that would otherwise be defeated. We modify Dung’s preferred semantics accordingly: a set of arguments becomes acceptable only if it contains a minimum of restricted arguments, for a maximum of unrestricted arguments.

ECAI Conference 1998 Conference Paper

On the Logic of Exceptions

• Jérôme Mengin

ECAI Conference 1994 Conference Paper

Prioritized Conflict Resolution for Default Reasoning

• Jérôme Mengin