Efficient Exact Computation of Setwise Minimax Regret for Interactive Preference Elicitation - Sorbonne Université
Conference Papers Year : 2021

Efficient Exact Computation of Setwise Minimax Regret for Interactive Preference Elicitation

Federico Toffano
  • Function : Author
  • PersonId : 1091093
Nic 2021 Wilson
  • Function : Author
  • PersonId : 1091094

Abstract

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.
Fichier principal
Vignette du fichier
SMMR_AAMAS_finalSubmission.pdf (669.25 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

hal-03142685 , version 1 (16-02-2021)

Identifiers

  • HAL Id : hal-03142685 , version 1

Cite

Federico Toffano, Paolo Viappiani, Nic 2021 Wilson. Efficient Exact Computation of Setwise Minimax Regret for Interactive Preference Elicitation. 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2021), May 2021, Online, United Kingdom. ⟨hal-03142685⟩
87 View
64 Download

Share

More