You are here

Efficient Exact Computation of Setwise Minimax Regret

Authors: 

Federico Toffano, Paolo Viappiani, Nic Wilson

Publication Type: 
Refereed Conference Meeting Proceeding
Abstract: 
A key issue in incremental 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 is 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 simple model of user utility as a weighted sum of the criteria; in this case when the user makes a choice we learn 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.
Conference Name: 
Workshop ModRef - The 26th International Conference on Principles and Practice of Constraint Programming
Digital Object Identifer (DOI): 
10.NA
Publication Date: 
07/09/2020
Institution: 
Dublin City University (DCU)
Open access repository: 
Yes