How Hard is it to Explain Preferences Using Few Boolean Attributes?

AI summary

Overview

• Research area: Computational social choice and multi-agent systems, specifically the algorithmic and parameterized complexity of preference modeling with Boolean attribute models (BAMs).
• Technical level: Advanced. The paper is a theory paper built on NP-completeness reductions (from 3-Coloring), 2-SAT reductions, and parameterized complexity (FPT, problem kernels, W[1]-hardness).
• Scope in one sentence: The paper maps out exactly when the problem of explaining a preference profile with a small number of Boolean attributes is easy and when it is hard, across the parameters number of attributes k, number of alternatives m, and number of voters n, and for variants where part of the model is already known.

What This Paper Is About

In a Boolean attribute model, every alternative either has or does not have each of a set of Boolean attributes (a restaurant either accepts credit cards or does not), and every voter cares about some subset of those attributes; a voter prefers alternative a to b exactly when a has more of the attributes that voter cares about. The paper asks how hard it is, given only a preference profile and an integer k, to decide whether such a model with at most k attributes exists, and it identifies which parameters of the input make that question tractable or intractable. The authors note that although attribute models are common in the literature, they are not aware of prior work on computing such models and checking how well they fit data.

Key Contributions

1. A complexity dichotomy in the number of attributes: BAM is solvable in linear time for k ≤ 2 but NP-complete for k ≥ 3, and the hardness already appears for preference orders of length two with k = 3.
2. A parameterized complexity classification: BAM is fixed-parameter tractable (FPT) with respect to the number of alternatives m and with respect to n + k, while the complexity with respect to the number of voters n alone is left open; a linear-time algorithm is given for the special case of two voters.
3. An analysis of partially specified models: For BAM with Cares (the voters' cares function is given) and BAM with Has (the alternatives' has function is given), the paper establishes NP-hardness for both, showing that BAM with Cares is generally harder than BAM whereas BAM with Has is generally more tractable, except that BAM with Has is NP-hard even for a single voter.
4. Structural lemmas that bound and characterize solutions: including lower and upper bounds on how many attributes a voter must care about or an alternative must have, a bound linking two voters' ranks of a shared alternative to k, and the existence of a k-BAM for k ≥ (m − 1) · m or k ≥ (m − 1) · n.

Main Findings

• Hardness in general: BAM is NP-complete. The reduction is from 3-Coloring, and the resulting instance uses k = 3 and only preference orders of length two.
• Dichotomy for k: BAM is NP-hard for k ≥ 3 (Theorem 1) but solvable in O(n) linear time for k ≤ 2 (Theorem 2), via a reduction to 2-SAT.
• Tractability for extreme preference lengths: If every preference order in the profile has length k + 1, BAM is solvable in polynomial time |P|^{O(1)} (Proposition 1). The paper states that the case of preference length exactly k remains open.
• FPT in the number of alternatives: BAM is solvable in 2^{O(m³)} · |P|^{O(1)} time, i.e., FPT with respect to m (Theorem 3), using an algorithm that branches on the attribute subsets of alternatives. This follows structurally from the fact that a k-BAM with k ≥ (m − 1) · m or k ≥ (m − 1) · n always exists.
• FPT in n + k: By bounding the sum of preference-order lengths by n · (k + 1), BAM is solvable in 2^{O((n · (k + 1))³)} · |P|^{O(1)} time, i.e., FPT with respect to n + k (Corollary 1).
• Open for n alone: The complexity of BAM with respect to the single parameter n is stated as an open question; attempts at showing W[1]-hardness were unsuccessful and the authors weakly conjecture that BAM is FPT with respect to n.
• Two voters are easy: For n = 2, the minimum number k of attributes can be determined in O(m) time, and a corresponding k-BAM can be computed in O(m²) time (Theorem 4). The analysis uses three attribute types: cared about by the first voter only, by the second only, and by both.
• BAM with Cares is harder: It is NP-complete, remains NP-hard even when m ≥ 3, and remains NP-hard even when k ≥ 6. It is FPT with respect to n + k.
• BAM with Has is more tractable but not easy: It is NP-complete, and remains NP-hard even for one voter (n = 1). It is FPT with respect to m, with respect to k, and with respect to n + m.
• Model checking is easy: Verifying whether a given (AT, has, cares) triple explains a profile can be done in polynomial time, which places all three problems in NP.
• Structural bounds: In any k-BAM, |≻_v| − 1 ≤ |cares(v)| ≤ k for every voter, and |≻_v| − r_v(c) − 1 ≤ |has(c)| ≤ k − r_v(c) for every ranked alternative. Also, if a k-BAM exists, then for any alternative c and voters v, w with r_v(c) ≥ r_w(c), it holds that |≻_w| − r_w(c) + r_v(c) ≤ k + 1, which yields lower bounds on k.
• Parameters k and m are interchangeable for complete preferences: For complete preference profiles, m − 1 ≤ k ≤ m(m − 1), so a voting problem is FPT with respect to m if and only if it is FPT with respect to k.

Methodology in Plain English

The authors treat the problem purely as a computational decision problem: given a profile plus an integer k, does a k-attribute model exist? They first show that checking a proposed model is easy, which puts the problem in NP. To show it is hard, they take an NP-complete graph problem, 3-Coloring, and build a preference profile from it: each graph vertex becomes an alternative, each vertex gets three voters that force it to have at most one attribute, each edge gets two voters with opposite orders that force adjacent vertices to get different attributes, and extra dummy alternatives and voters are added to pin down how many attributes each dummy holds. A valid 3-coloring then corresponds exactly to a valid 3-attribute model, so deciding one solves the other.

For the tractable cases, they reduce the two-attribute problem to 2-SAT to get a linear-time algorithm, and they design algorithms that guess the attribute set of each alternative and then check, voter by voter, whether some set of cared-about attributes can explain that voter's order. For the two-voter case, they categorize attributes by which voters care about them and compute the minimum number of attributes of each category needed, then argue no smaller model can exist.

Why This Matters

The paper supplies the first complexity-theoretic map of when preference data can be compressed into a small Boolean attribute model, distinguishing settings where exact algorithms are viable from settings where practitioners should expect intractability. For research, it establishes that attribute-based preference domains—one of the simplest multi-dimensional restricted domains—have a sharp tractability boundary, and it motivates the study of richer variants such as low-dimensional multi-peaked domains.

Real-world applications the paper motivates:

• Stable matching: If a Boolean k-attribute model is known, stable matchings can be computed in O(4^k · n · (k + log n)) time, which is almost linear in n for small k (Künnemann et al. 2019).
• Preference elicitation: Instead of asking voters to rank many alternatives, one can ask which of a few attributes matter, following work applying this principle to compute Borda winners efficiently (Benabbou et al. 2016).
• Explaining AI decisions: When preferences come from a black-box machine-learning model and the features each alternative has are known, the task reduces to selecting the attributes the model relied on (Holzinger et al. 2020).
• Multi-criteria decision making and additive utility learning: The paper relates BAMs to UTA-style methods that learn weighted-sum utility functions over attributes for one or several decision makers (Siskos, Grigoroudis, and Matsatsinis 2016; Auriau et al. 2024).

For industry, the results give a concrete signal about when attribute-based personalization, recommendation, or explanation pipelines can be solved exactly and efficiently, and when they should be treated as NP-hard and handled with heuristics or with the tractable special cases the paper identifies (few attributes, two attributes, two voters, few alternatives, or partially known models).

Future Directions

• Settle the complexity with respect to the number of voters n. The paper leaves this open, reports unsuccessful attempts at W[1]-hardness, and weakly conjectures that BAM is FPT in n.
• Resolve the preference-length case ℓ = k. Polynomial-time solvability is shown for length k + 1 and NP-hardness for length two with k = 3, but the case where every preference order has exactly k entries is stated as open.
• Extend the analysis to more variants of partial information. The paper shows a sharp asymmetry between BAM with Cares (harder) and BAM with Has (more tractable), leaving room for other partial-information settings and further parameter combinations, including those marked as unresolved in the result table.
• Transfer the results to richer preference domains. The authors position BAMs as one of the simplest multi-dimensional restricted domains and suggest this may inform investigation into more sophisticated low-dimensional variants, including multi-dimensional versions of single-peaked preferences.

Target Audience

Researchers in computational social choice, multi-agent systems, and algorithmic game theory; complexity theorists working on parameterized algorithms and NP-hardness reductions; and machine-learning or decision-making practitioners who use attribute-based or additive-utility models for preference learning, elicitation, and explainability. The paper is entirely theoretical—no empirical experiments or dataset evaluations are reported—so readers looking for practical benchmarks will need to consult other work.

Authors’ abstract

We study the computational complexity of explaining preference data through Boolean attribute models (BAMs), motivated by extensive research involving attribute models and their promise in understanding preference structure and enabling more efficient decision-making processes. In a BAM, each alternative has a subset of Boolean attributes, each voter cares about a subset of attributes, and voters prefer alternatives with more of their desired attributes. In the BAM problem, we are given a preference profile and a number k, and want to know whether there is a Boolean k-attribute model explaining the profile. We establish a complexity dichotomy for the number of attributes k: BAM is linear-time solvable for $k \le 2$ but NP-complete for $k \ge 3$. The problem remains hard even when preference orders have length two. On the positive side, BAM becomes fixed-parameter tractable when parameterized by the number of alternatives m. For the special case of two voters, we provide a linear-time algorithm. We also analyze variants where partial information is given: When voter preferences over attributes are known (BAM WITH CARES) or when alternative attributes are specified (BAM WITH HAS), we show that for most parameters BAM WITH CARES is more difficult whereas BAM WITH HAS is more tractable except for being NP-hard even for one voter.