Learning monotone preferences using a majority rule sorting model

• Author: Vincent Mousseau,Marc Pirlot,Olivier Sobrie
• Date: 01 September 2019
• Published date: 01 September 2019
• DOI: http://doi.org/10.1111/itor.12512

Intl. Trans. in Op. Res. 26 (2019) 1786–1809

DOI: 10.1111/itor.12512

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Learning monotone preferences using a majority rule sorting

model

Olivier Sobriea,b, Vincent Mousseauband Marc Pirlota

aFacult ´

e Polytechnique, Universit´

e de Mons, rue de Houdain, 7000 Mons, Belgium

bLGI, CentraleSup´

elec, Universit´

e Paris-Saclay, Gif sut Yvette, France

E-mail: olivier.sobrie@gmail.com [Sobrie]; vincent.mousseau@ecp.fr [Mousseau]; marc.pirlot@umons.ac.be [Pirlot]

Received 10 March 2017; receivedin revised form 9 October 2017; accepted 30 December 2017

Abstract

We consider the problem of learning a function assigning objects into ordered categories. The objects are

described by a vector of attribute values and the assignment function is monotone w.r.t. the attribute values

(monotone sorting problem). Our approach is based on a model used in multicriteria decision analysis

(MCDA), called MR-Sort. This model determines the assigned class on the basis of a majority rule and

an artificial object that is a typical lower profile of the category. MR-Sort is a simplified variant of the

ELECTRE TRI method. We describe an algorithm designed for learning such a model on the basis of

assignment examples. We compare its performance with choquistic regression,a method recently proposed in

the preference learning community, and with UTADIS,another MCDA method leaning on an additive value

function (utility) model. Our experimentation shows that MR-Sort competes with the other two methods,

and leads to a model that is interpretable.

Keywords:multiple criteria decision analysis; classification; majority rule sorting; preference learning; heuristic

1. Introduction

Sorting problems frequently arise in real-life contexts. For instance, a committee is assigned the

task of separating good projects from bad ones, a jury has to assign grades to students. To select

the category in which an alternative (e.g., a project, a student) should be assigned, a common and

intuitive approach consists in analyzing its characteristics recorded as the value of attributes, also

called criteria (e.g., for grading a student, the marks obtained in the different subjects). In both

examples above, categories are specified before sorting takes place and they are orderedto reflect the

preference of the decision maker (DM). Furthermore,the grading of students typically is monotone

w.r.t. the marks obtained. Better marks cannot lead to a worse grade.

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

O. Sobrie et al. / Intl. Trans. in Op. Res. 26 (2019) 1786–1809 1787

These two properties, that is, sorting in ordered classes by rules that are monotone w.r.t. attribute

values, characterize the kind of sorting problems we want to address with the algorithm presented

in this paper. Formally, each alternative ain a set Ais described as a vector (a1,...,aj,...,an),

where ajis the value of aon the jth attribute. This value is an element of the attribute’s scale Xj,

endowed with a preference order j.ThesetofalternativesAmay thus be seen as a subset of the

Cartesian product, X=n

j=1Xj. Sorting the alternatives in the ordered categories Cp··· C1

(where describes the DM’s preference order on the categories) amounts to define a function

g:A⊆X→{C1,...,Cp}. The sorting function gis monotone if an alternativeacannot be assigned

to a less preferred category than an alternative bwhenever ais at least as good as bon all attributes.

Precisely, for all a,b∈A, with ajjbjfor all j,wehaveg(a)g(b)or g(a)=g(b).

In the preference learning (PL) community, learning such monotone assignment functions on the

basis of assignment examples is referred to as monotone learning (Tehrani et al., 2012).

In the multiple criteria decision analysis (MCDA)community, sorting alternatives into categories

on the basis of their evaluation on a family of criteria is one of the central problems (Figueira et al.,

2013). In contrast with machine learning usage, MCDA puts the emphasis on interaction with the

DM. Their preferences are usually elicited in the course of an interactive process and explicitly

incorporated in the sorting model. There are two main categories of MCDA models that have been

used for sorting purposes:

1. Methods based on the construction of an overall score or value function aggregating all at-

tributes. The weighted sum and the additive value function models (Belton and Stewart, 2002,

Chapter 6) belong to this category. Basically, an alternative is assigned to a category whenever

its score (or value) reaches some lower threshold value and is smaller than the lower threshold

of the category just above.

2. Methods based on outranking relations. They are inspired by social choice theory and rely on

pairwise comparisons of alternatives. Well-known in this family are the ELECTRE methods

and, in particular, ELECTRE TRI. In this framework, an alternative is assigned to a category

if it is preferred to the lower profile of the category, but is not preferred to the lower profile

of the category just above. The preference (called outranking) of an alternative over another

is determined by means of a concordance-nondiscordance rule. Such a rule checks whether the

former is at least as good as the latter on a sufficiently strong coalition of criteria and whether

there is no criteria on which the former alternative is unacceptably worse than the latter.

For a detailed presentation of such methods, the reader is referred to Doumpos and Zopounidis

(2002) and Zopounidis and Doumpos (2002).

Eliciting the parameters of a model in MCDA can either be done directly or indirectly. Since

MCDA favors interactions with the DM, the parameters are often elicited through directly asking

the DM questions that determine or restrict the range of variation of the model’s parameters.

Questioning proceduresare often cognitively demanding while DMs are usually verybusy. Therefore,

indirect methods havebeen developed based on a learning set consisting, for instance, of assignment

examples, in the case of a sorting problem.Several learning algorithms were proposed in the MCDA

literature,in particular based on linear programing. It is the case of the UTADIS method developed

by Jacquet-Lagr`

eze and Siskos (1982) (see also Doumpos and Zopounidis, 2002, Chapter 4).

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation of OperationalResearch Societies