Eliminating Inconsistencies among CP-Theory Qualitative Preferences

Inconsistency in preference reasoning arises when a set of preferences implies that an outcome is preferred over itself. In multi-agent settings, conflicting preferences of the agents lead to inconsistencies in their collective preferences. We examine the problem of establishing consistency by selectively discarding a subset of input preferences, where preferences are expressed qualitatively in CP-theory language. Specifically, we explore two variants (1) identifying a minimal set of preferences to discard in order to eliminate inconsistencies, and (2) finding a set of preferences whose removal minimally alters the induced dominance so as to eliminate the inconsistencies. We show that both minimization problems are NP-complete. We propose an iterative Integer Linear Programming (ILP)-based approach to their solution. Finally, we present experimental results that demonstrate the feasibility of our solution. We observe that optimizing one objective in isolation often compromises the other. We explore sequential strategies that prioritize one objective followed by the optimization of the other, and propose an empirically balanced approach that achieves improved overall outcomes.