Efficient minimal preference change

Alechina, Natasha; Liu, Fenrong; Logan, Brian

Abstract

In this article, we study a minimal change approach to preference dynamics. We treat a set of preferences as a special kind of theory, and define minimal change preference contraction and revision operations in the spirit of the Alchourrón, Gärdenfors, and Makinson theory of belief revision. We characterise minimal contraction of preference sets by a set of postulates and prove a representation theorem. We also give a linear time algorithm which implements minimal contraction by a single preference. We then define minimal contraction by a set of preferences, and show that the problem of a minimal contraction by a set of preferences is NP-hard.

Citation

Alechina, N., Liu, F., & Logan, B. (2018). Efficient minimal preference change. Journal of Logic and Computation, 28(8), 1715–1733. https://doi.org/10.1093/logcom/exv027

• Journal Article Type: Article
• Acceptance Date: Apr 29, 2015
• Online Publication Date: May 14, 2015
• Publication Date: Dec 1, 2018
• Deposit Date: Jun 5, 2016
• Publicly Available Date: Jun 5, 2016
• Journal: Journal of Logic and Computation
• Print ISSN: 0955-792X
• Electronic ISSN: 1465-363X
• Publisher: Oxford University Press
• Peer Reviewed: Peer Reviewed
• Volume: 28
• Issue: 8
• Pages: 1715–1733
• DOI: https://doi.org/10.1093/logcom/exv027
• Keywords: Preference change; minimal contraction; complexity; preference aggregation
• Public URL: https://nottingham-repository.worktribe.com/output/752047
• Publisher URL: http://logcom.oxfordjournals.org/content/early/2015/05/13/logcom.exv027
• Additional Information: This is a pre-copyedited, author-produced PDF of an article accepted for publication in Journal of Logic and Computation following peer review. The version of record J Logic Computation (2015); doi: 10.1093/logcom/exv027 is available online at: http://logcom.oxfordjournals.org/content/early/2015/05/13/logcom.exv027
• Contract Date: Jun 5, 2016