Top

Theory and Decision

Published in:

30-06-2016

Explaining robust additive utility models by sequences of preference swaps

Authors: K. Belahcene, C. Labreuche, N. Maudet, V. Mousseau, W. Ouerdane

Published in: Theory and Decision | Issue 2/2017

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

As decision-aiding tools become more popular everyday—but at the same time more sophisticated—it is of utmost importance to develop their explanatory capabilities. Some decisions require careful explanations, which can be challenging to provide when the underlying mathematical model is complex. This is the case when recommendations are based on incomplete expression of preferences, as the decision-aiding tool has to infer despite this scarcity of information. This step is key in the process but hardly intelligible for the user. The robust additive utility model is a necessary preference relation which makes minimal assumptions, at the price of handling a collection of compatible utility functions, virtually impossible to exhibit to the user. This strength for the model is a challenge for the explanation. In this paper, we come up with an explanation engine based on sequences of preference swaps, that is, pairwise comparison of alternatives. The intuition is to confront the decision maker with “elementary” comparisons, thus building incremental explanations. Elementary here means that alternatives compared may only differ on two criteria. Technically, our explanation engine exploits some properties of the necessary preference relation that we unveil in the paper. Equipped with this, we explore the issues of the existence and length of the resulting sequences. We show in particular that in the general case, no bound can be given on the length of explanations, but that in binary domains, the sequences remain short.

next article A simple framework for the axiomatization of exponential and quasi-hyperbolic discounting

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

Equally preferred, or indifferent, alternatives are pairs in the symmetric part of the relation \(\mathcal {R}\) : \(\forall x,y \in \mathbb {X}, x\, \sim \, y \iff \{(x,y),(y,x)\}\subset \mathcal {R}\).

We note that [MH07,MH05] also propose to enrich the original even swaps method in a way that accounts for incomplete knowledge about the value function. They consider a “practical dominance” notion when the value of an alternative is at least as high as the value of another one with every feasible combination of parameters, this perspective being very close to the one developed in [GMS08] (see next section). However, this notion is only used for pre-processing dominated alternatives, and not integrated in the swap process, let alone used for explanatory purposes.

The diameter in the graph is the longest distance between two vertices in graph.

The set \(\mathbb {V}_\mathcal {P}\) is not empty, as it contains at least all uniform value functions. It may sometimes come down to contain only these, if the preference information is somewhat inconsistent. Any uniform value function \(V_{\mathrm {uniform}}\) leads to a degenerated, complete relation \(\mathcal {R}_{V_{\mathrm {uniform}}} \equiv \mathbb {X}^2\).

mth-order cancelation axiom: consider \(m+1\) alternatives \(x^{(k)}\) in \(\mathbb {X},\ k\in \{0,1,\dots ,m\}\). Let \(y^{(k)}\) in \(\mathbb {X},\ k\in \{0,1,\dots ,m\}\) \(m+1\) alternatives such that, for every criterion \(i\in N\), \((y^{(0)}_i, y^{(1)}_i, \dots ,y^{(m)}_i)\) is a permutation of \((x^{(0)}_i, x^{(1)}_i, \dots ,x^{(m)}_i)\). Then, \([(x^{(k)},y^{(k)})\in \mathcal {R}, \forall k\in \{0,1,\dots ,m-1\}]\Rightarrow (y^{(m)},x^{(m)})\in \mathcal {R}\).

Aingworth, D., Chekuri, C., & Motwani, R. 1996. Fast estimation of diameter and shortest paths (without matrix multiplication). In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’96, pp. 547–553

Bana e Costa, C. A., & Vansnick, J.C. (1995). General overview of the MACBETH approach. In Pardalos P. M., Siskos Y., & Zopounidis C., (Eds.) Advances in Multicriteria Analysis, pages 93–100. Dordrecht: Kluwer Academic Publishers

Bana e Costa, C. A., Lourenço J. C., Chagas, M. P. & Bana e Costa, J. C. (2008). Development of reusable bid evaluation models for the portuguese electric transmission company. Decision Analysis, 5(1):22–42

Boutilier, C., Brafman, R. I., Domshlak, C., Hoos, H. H., & Poole, D. (2004). Cp-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements. J. Artif. Intell. Res. (JAIR), 21, 135–191.

Brafman, R. I., Domshlak, C., & Shimony, S. E. (2006). On graphical modeling of preference and importance. J. Artif. Intell. Res. (JAIR), 25, 389–424.

Carenini, G., & Moore, J. D. (2006). Generating and evaluating evaluative arguments. Artificial Intelligence Journal, 170, 925–952.CrossRef

Ch. Labreuche, Maudet N., & Ouerdane W. (2011). Minimal and complete explanations for critical multi-attribute decisions. In Algorithmic Decision Theory (ADT), pp. 121–134, Piscataway, NJ, USA

Ch. Labreuche, Maudet, N., & Ouerdane, W. (2012). Justifying dominating options when preferences are incomplete. In Proceedings of the European Conference on Artificial Intelligence, 242, pp 486–491, Montpellier, France, IOS Press

Eiter, T., & Gottlob, G. (1995). The complexity of logic-based abduction. J. ACM, 42(1), 3–42.CrossRef

Even, S., & Tarjan, R. E. (1975). Network flow and testing graph connectivity. SIAM J. Comput., 4(4), 507–518.CrossRef

Fishburn, P.C. (1997). Cancellation conditions for multiattribute preferences on finite sets. In Mark, H. Karwan, J. S., & Jyrki W. (Eds.) Essays In Decision Making, pp. 157–167. Springer Berlin Heidelberg

Friedrich, G., & Zanker, M. (2011). A taxonomy for generating explanations in recommender systems. AI Magazine, 32(3), 90–98.

Greco, S., Słowinski, R., Figueira, J., & Mousseau, V. (2010). Robust ordinal regression. In Trends in Multiple Criteria Decision Analysis, pp 241–284. Springer Verlag

Greco, S., Mousseau, V., & Słowinski, R. (2008). Ordinal regression revisited: Multiple criteria ranking with a set of additive value functions. European Journal of Operational Research, 191, 416–436.CrossRef

Hammond, J., Keeney, R., & Raiffa, H. (1998). Even Swaps: a rational method for making trade-offs. Harvard Business Review, 137–149

Herlocker, J. L., Konstan, J. A., & Riedl, J.(2000). Explaining collaborative filtering recommendations. In Proceedings of the ACM conference on Computer Supported Cooperative Work, pp. 241–250

Jacquet-Lagrèze, E., & Siskos, Y. (1982). Assessing a set of additive utility functions for multicriteria decision making: the UTA method. European Journal of Operational Research, 10, 151–164.CrossRef

Kazman, R., Klein, M., & Clements, P. (2000). ATAM: Method for Architecture Evaluation. TECHNICAL REPORT, CMU/SEI-2000-TR-004, http://www.sei.cmu.edu/reports/00tr004.pdf

Klein, D. A. (1994). Decision analytic intelligent systems: automated explanation and knowledge acquisition. Lawrence Erlbaum Associates.

Krantz, D. H., Luce, R. D., Suppes, P., & Tversky, A. (1971). Foundations of measurement, volume 1: Additive and Polynomial Representations. Academic Press

Labreuche, Ch. (2011). A general framework for explaining the results of a multi-attribute preference model. Artificial Intelligence Journal, 175, 1410–1448.CrossRef

Michell, Joel. (1988). Some problems in testing the double cancellation condition in conjoint measurement. Journal of Mathematical Psychology, 32(4), 466–473.CrossRef

Nic, W. (2011). Computational techniques for a simple theory of conditional preferences. Artificial Intelligence, 175(7–8):1053–1091. Representing, Processing, and Learning Preferences: Theoretical and Practical Challenges.

Nunes, I., Miles, S., Luck, M., Barbosa, S., & Lucena, C. (2014) Pattern-based explanation for automated decisions. In Proceedings of the 21st European Conference on Artificial intelligence, pp. 669–674. IOS Press

O’Sullivan, B., Papadopoulos, A., Faltings, B., & Pu, P. (2007). Representative explanations for over-constrained problems. In Proceedings of the 22nd national conference on Artificial intelligence, pp. 323–328. AAAI Press

Pu, P., & Chen, L. (2007). Trust-inspiring explanation interfaces for recommender systems. Knowledge-Based Systems, 20(6):542 – 556. Special Issue On Intelligent User Interfaces.

Spliet, R., & Tervonen, T. (2014). Preference inference with general additive value models and holistic pair-wise statements. European Journal of Operational Research, 232(3), 607–612.CrossRef

Symeonidis, P., Nanopoulos, A., & Manolopoulos, Y. (2009). MoviExplain: a recommender system with explanations. In Proceedings of the third ACM conference on Recommender systems (RecSys’09), pp. 317–320, New York, NY, USA, 2009. ACM.

Ulrich, J. (2004) Quickxplain: Preferred explanations and relaxations for over-constrained problems. In Proceedings of the 19th National Conference on Artificial Intelligence, pages 167–172, Menlo Park, California, 2004. AAAI Press /The MIT Press.

Title: Explaining robust additive utility models by sequences of preference swaps
Authors: K. Belahcene
C. Labreuche
N. Maudet
V. Mousseau
W. Ouerdane
Publication date: 30-06-2016
Publisher: Springer US
Published in: Theory and Decision / Issue 2/2017
Print ISSN: 0040-5833
Electronic ISSN: 1573-7187
DOI: https://doi.org/10.1007/s11238-016-9560-1

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 2/2017

The efficiency of crackdowns: a lab-in-the-field experiment in public transportations

Gender differences in ambiguity aversion under different outcome correlation structures

A simple framework for the axiomatization of exponential and quasi-hyperbolic discounting

A note on a recent paper by Dagsvik on IIA and random utilities

Social comparison and risk taking behavior

Pool size and the sustainability of optimal risk-sharing agreements

Premium Partner