Computation and complexity of preference inference based on hierarchical models

Simple item page
dc.contributor.authorWilson, Nic
dc.contributor.authorGeorge, Anne-Marie
dc.contributor.authorO'Sullivan, Barry
dc.contributor.funderScience Foundation Irelanden
dc.date.accessioned2020-12-01T15:20:11Z
dc.date.available2020-12-01T15:20:11Z
dc.date.issued2015-07
dc.date.updated2020-11-04T13:17:32Z
dc.description.abstractPreference Inference involves inferring additional user preferences from elicited or observed preferences, based on assumptions regarding the form of the user's preference relation. In this paper we consider a situation in which alternatives have an associated vector of costs, each component corresponding to a different criterion, and are compared using a kind of lexicographic order, similar to the way alternatives are compared in a Hierarchical Constraint Logic Programming model. It is assumed that the user has some (unknown) importance ordering on criteria, and that to compare two alternatives, firstly, the combined cost of each alternative with respect to the most important criteria are compared; only if these combined costs are equal, are the next most important criteria considered. The preference inference problem then consists of determining whether a preference statement can be inferred from a set of input preferences. We show that this problem is coNP-complete, even if one restricts the cardinality of the equal-importance sets to have at most two elements, and one only considers non-strict preferences. However, it is polynomial if it is assumed that the user's ordering of criteria is a total ordering; it is also polynomial if the sets of equally important criteria are all equivalence classes of a given fixed equivalence relation. We give an efficient polynomial algorithm for these cases, which also throws light on the structure of the inference.en
dc.description.statusPeer revieweden
dc.description.versionAccepted Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.citationWilson, N., George, A.-M. and O'Sullivan, B. (2015) 'Computation and Complexity of Preference Inference Based on Hierarchical Models', IJCAI'15: Proceedings of the 24th International Conference on Artificial Intelligence, Buenos Aires, Argentina, 25–31 July, pp. 3271–3277. isbn: 978-1-57735-738-4en
dc.identifier.endpage3277en
dc.identifier.isbn978-1-57735-738-4
dc.identifier.startpage3271en
dc.identifier.urihttps://hdl.handle.net/10468/10796
dc.language.isoenen
dc.publisherAAAI Press / International Joint Conferences on Artificial Intelligenceen
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.urihttps://www.ijcai.org/Proceedings/2015
dc.rights© 2015 International Joint Conferences on Artificial Intelligence.en
dc.subjectPreference inference techniquesen
dc.subjectArtificial intelligence (AI)en
dc.subjectAI technologyen
dc.subjectPreference Inferenceen
dc.titleComputation and complexity of preference inference based on hierarchical modelsen
dc.typeConference itemen
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
HCLP-Preference-Logic-ijcai15.pdf
Size:
265.35 KB
Format:
Adobe Portable Document Format
Description:
Accepted 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