EUVIMEDEUVIMED entdecken
Crossref

How Hard Is It to Explain Preferences Using Few Boolean Attributes?

Clemens Anzinger, Jiehua Chen, Christian Hatschka, Manuel Sorge, Alexander Temper

Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (20) · 16639-16646

DOI: 10.1609/aaai.v40i20.38705 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Clemens Anzinger und 4 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 possesses a subset of binary 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 want to know whether there is a k-attribute model explaining the profile. We establish a complexity dichotomy for the number of attributes k: BAM is linear-time solvable for k≤2 but NP-complete for k≥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), showing 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.

Zitieren

APA

Anzinger, C., Chen, J., Hatschka, C., Sorge, M., & Temper, A. (2026). How Hard Is It to Explain Preferences Using Few Boolean Attributes?. Proceedings of the AAAI Conference on Artificial Intelligence, 40(20), 16639-16646. https://doi.org/10.1609/aaai.v40i20.38705

Vancouver

Anzinger C, Chen J, Hatschka C, Sorge M, Temper A. How Hard Is It to Explain Preferences Using Few Boolean Attributes?. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(20):16639-16646. doi:10.1609/aaai.v40i20.38705

BibTeX
@article{Anzinger2026,
  author = {Anzinger, Clemens and Chen, Jiehua and Hatschka, Christian and Sorge, Manuel and Temper, Alexander},
  title = {How Hard Is It to Explain Preferences Using Few Boolean Attributes?},
  journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
  year = {2026},
  volume = {40},
  number = {20},
  pages = {16639--16646},
  doi = {10.1609/aaai.v40i20.38705}
}
Kostenlos starten →