Checking Consistency of CP-Theory Preferences in Polynomial Time
Authors: Erik Rauer, Samik Basu, Vasant Honavar
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We present a new sufficient condition for consistency of preferences and show that the condition can be checked in polynomial time in settings of practical relevance (locally consistent or binary domain preference variables). We discuss a sufficient condition of consistency for CPtheory preferences based on the acyclicity of H(P). Theorem 1 (Cardinality-based Conditional Acyclicity). Given a set P of preference statements, if P is locally consistent and H(P) is acyclic, then P is consistent. The proof of the above theorem relies on the concept of a complete search tree (cs-tree) introduced in (Wilson 2006). |
| Researcher Affiliation | Academia | 1 Department of Computer Science, Iowa State University, USA 2 Artificial Intelligence Research Laboratory 3 Institute for Computational and Data Sciences 4 College of Information Sciences and Technology, Pennsylvania State University, USA EMAIL, EMAIL |
| Pseudocode | No | The paper describes methods in prose, such as the "Checking cc-acyclic Condition" and "Finding the Top k Outcomes" sections, but does not present structured pseudocode or algorithm blocks with specific labels like "Algorithm 1" or "Pseudocode". |
| Open Source Code | No | The paper does not include any explicit statement about releasing source code, a link to a repository, or mention of code in supplementary materials. The "Future Directions" section states: "We also plan to implement and empirically compare the cc-acyclic condition and the resulting upper approximation with those proposed by (Wilson 2011)", indicating that implementation is a future goal rather than an existing release. |
| Open Datasets | No | The paper uses illustrative examples of preference statements, such as those presented in "Table 1: A set P of preference statements" and "Example 1. Consider the preference statements {pi | i [1, 6]} over V = {A, B, C} in Table 1", which appear to be synthetic for the purpose of demonstrating the theory, and does not provide access information for any publicly available or open dataset. |
| Dataset Splits | No | The paper does not use any external datasets for empirical evaluation; therefore, there is no discussion of dataset splits. |
| Hardware Specification | No | The paper is theoretical in nature and does not describe any experimental setup or mention specific hardware (like GPU models, CPU types, or cloud resources) used for running experiments. |
| Software Dependencies | No | The paper is theoretical and focuses on mathematical proofs and conditions. It does not mention any specific software, libraries, or solvers with version numbers that would be required for replication. |
| Experiment Setup | No | The paper is theoretical and does not include an experimental section. Therefore, it does not provide details on experimental setup, hyperparameters, or training configurations. |