Efficient exact computation of setwise minimax regret for interactive preference elicitation

Simple item page
dc.contributor.authorToffano, Federico
dc.contributor.authorViappiani, Paolo
dc.contributor.authorWilson, Nic
dc.contributor.funderScience Foundation Irelanden
dc.contributor.funderHorizon 2020en
dc.contributor.funderEuropean Regional Development Funden
dc.date.accessioned2021-10-05T15:05:26Z
dc.date.available2021-10-05T15:05:26Z
dc.date.issued2021-05-03
dc.date.updated2021-10-05T14:58:20Z
dc.description.abstractA 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.en
dc.description.sponsorshipScience Foundation Ireland (under Grant No. 12/RC/2289-P2 which is co-funded under the European Regional Development Fund); European Commission (INDECOD project (International Emerging Action) of CNRS, and by the LOGISTAR project, which is funded by the European Commission under the Horizon 2020 programme)en
dc.description.statusPeer revieweden
dc.description.versionPublished Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.citationToffano, F., Viappiani, P. and Wilson, N. (2021) 'Efficient Exact Computation of Setwise Minimax Regret for Interactive Preference Elicitation', Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems, Virtual Event, United Kingdom: International Foundation for Autonomous Agents and Multiagent Systems, pp. 1326–1334.en
dc.identifier.endpage1334en
dc.identifier.isbn978-1-4503-8307-3
dc.identifier.startpage1326en
dc.identifier.urihttps://hdl.handle.net/10468/12053
dc.language.isoenen
dc.publisherACM; International Foundation for Autonomous Agents and Multiagent Systemsen
dc.relation.projectinfo:eu-repo/grantAgreement/SFI/SFI Research Centres/12/RC/2289/IE/INSIGHT - Irelands Big Data and Analytics Research Centre/en
dc.relation.projectinfo:eu-repo/grantAgreement/EC/H2020::RIA/769142/EU/Enhanced data management techniques for real time logistics planning and scheduling/LOGISTARen
dc.relation.urihttps://dl.acm.org/doi/10.5555/3463952.3464105
dc.rights© 2021 International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.en
dc.subjectSetwise minimax regreten
dc.subjectHuman-agent interactionen
dc.subjectInteractive preference elicitationen
dc.titleEfficient exact computation of setwise minimax regret for interactive preference elicitationen
dc.typeConference itemen
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
3463952.3464105.pdf
Size:
1.18 MB
Format:
Adobe Portable Document Format
Description:
Published version
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
2.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Computer Science - Conference Items
Insight Centre for Data Analytics - Conference Items