=Paper=
{{Paper
|id=Vol-1751/AICS_2016_paper_46
|storemode=property
|title=None
|pdfUrl=https://ceur-ws.org/Vol-1751/AICS_2016_paper_46.pdf
|volume=Vol-1751
}}
==None==
<pdf width="1500px">https://ceur-ws.org/Vol-1751/AICS_2016_paper_46.pdf</pdf>
<pre>
 Fast Algorithms for the Preference Consistency
     Problem Based on Hierarchical Models

                 A.-M. George and N. Wilson and B. O’Sullivan

                            Insight Centre, UCC, Ireland



Summary
In fields like recommender systems and multi-objective decision making, one
wants to reason over user preferences. It is often difficult or excessively time-
consuming to elicit all user preferences. We aim to elicit only a few preferences
from the user and deduce other preferences. Here, we need to check if the users
statements are consistent, i.e., do not contradict each other. Otherwise, one could
deduce any arbitrary preference statement. Checking consistency and deducing
a preference statement is mutually expressive for hierarchical user models, and
NP-complete and coNP-complete, respectively. In this paper, we construct and
compare algorithmic approaches to solve the Preference Consistency Problem
(PCP) for preference statements based on hierarchical models. Here, instances
contain a set of preference statements that are direct comparisons (strict and
non-strict) between some alternatives, and a set of evaluations functions by which
all alternatives can be rated. An instance is consistent based on hierarchical pref-
erence models, if there exists an hierarchy of evaluation functions that induces
an order relation on the alternatives by which all preference statements are sat-
isfied. We develop three approaches to solve PCP. The first involves a Mixed
Integer Linear Programming (MILP) formulation, the other two are recursive
algorithms based on properties that allow to prune the search space and num-
ber of backtracks. Our experiments on synthetic data show that the recursive
algorithms are extremely fast compared to solving the MILP formulation [1].


References
1. George, A.M., Wilson, N., O’Sullivan, B.: Towards fast algorithms for the preference
   consistency problem based on hierarchical models. In: IJCAI ’16, New York, USA,
   July 09-15, 2016, Proceedings. (2016)

</pre>