Choice Logics and Their Computational Properties

Michael Bernreiter, Jan Maly, Stefan WoltranIJCAI 2021 · DOI

TL;DR

This paper introduces a general framework for "choice logics," unifying existing formalisms like QCL and CCL and enabling the definition of new ones. The authors analyze the computational complexity of these logics and provide characterizations for strong equivalence, a key concept for simplifying logical formulas.

What Problem Does This Paper Address?

Representing and reasoning about preferences is crucial in AI. Logic-based formalisms like Qualitative Choice Logic (QCL) and Conjunctive Choice Logic (CCL) have emerged as powerful tools for this, integrating truth and preference representation. However, existing analyses of these logics are often done on a case-by-case basis, despite their shared features. This calls for a more general framework that can encompass QCL, CCL, and potentially many other related choice logics, allowing for uniform analysis of their properties, such as strong equivalence and computational complexity. Furthermore, while QCL and CCL are useful, they might not capture all desired preference structures, motivating the need for a flexible framework to define new logics.

Methods

The core contribution is a general framework for choice logics. This framework defines a choice logic by specifying its set of choice connectives and providing functions for "optionality" (bounding the possible satisfaction degrees) and "satisfaction degree" (assigning a numerical value to how well an interpretation satisfies a formula). This allows for the easy definition of new choice logics by simply defining these functions for new connectives.

The paper then uses this framework to:

  • Formally define QCL and CCL, and introduce two new logics: Lexicographic Choice Logic (LCL) and Simple Conjunctive Choice Logic (SCCL).
  • Characterize strong equivalence by relating it to simpler notions like degree-equivalence and full equivalence, depending on whether the logic is "optionality-ignoring" or "optionality-differentiating."
  • Analyze the computational complexity of key decision problems related to satisfaction degrees and preferred models for these choice logics.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Unification is Powerful: A single framework can elegantly capture existing choice logics (QCL, CCL) and facilitate the creation of new ones (LCL, SCCL), enabling uniform analysis.
  • Optionality Matters for Equivalence: The concept of "optionality" plays a crucial role in determining when strong equivalence (replacing formulas without changing preferred models) simplifies to degree-equivalence or full equivalence. This provides a deeper understanding of how preferences are structured.
  • Complexity Varies: The computational complexity of reasoning tasks, particularly finding preferred models, varies significantly across different choice logics, ranging from NP-complete to A2P-complete. This highlights the trade-offs between expressiveness and computational tractability.
  • LCL's Lexicographic Power: LCL offers a way to encode lexicographic orderings over variables more compactly than QCL, CCL, or SCCL, but at the cost of higher computational complexity for certain problems.

Key Results

  • The paper formally defines a general framework for choice logics, encompassing QCL and CCL, and introduces LCL and SCCL.
  • It provides characterizations for strong equivalence:
  • For optionality-ignoring logics (like SCCL), strong equivalence is equivalent to degree-equivalence.
  • For optionality-differentiating logics (like QCL, CCL, LCL), strong equivalence is equivalent to full equivalence.
  • Computational complexity results for tractable choice logics are presented:
  • L-DEGREECHECKING is in P.
  • L-DEGREESAT is NP-complete.
  • L-PREFMODELCHECKING is in coNP.
  • L-PREFMODELSAT is O2P-complete for QCL, CCL, and SCCL, and A2P-complete for LCL.
  • Equivalence problems (full, degree, strong) are generally coNP-complete.

Limitations and Future Work

  • Tractability Assumption: The complexity analysis focuses on "tractable" choice logics, where optionality and degree functions are computable in polynomial time. The paper acknowledges that more complex logics might exist.
  • Nonmonotonic Consequence Relations: The authors suggest investigating how nonmonotonic consequence relations (like those for QCL) can be integrated into their general framework and analyzing their computational complexity.
  • Associativity and Normal Forms: Further work could explore characterizing associativity for other choice connectives and developing general concepts for normal forms, extending existing work on QCL and CCL.
  • Strong Equivalence for Non-Differentiating Logics: The complexity of checking strong equivalence for choice logics that are neither optionality-ignoring nor optionality-differentiating remains an open question.

Summary updated

BibTeX
@inproceedings{bernreiter2021choice,
  author = {Michael Bernreiter and Jan Maly and Stefan Woltran},
  title = {{Choice Logics and Their Computational Properties}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/247},
}
Figure