TY - JOUR
T1 - Efficient minimal preference change
AU - Alechina, Natasha
AU - Liu, Fenrong
AU - Logan, Brian
N1 - Publisher Copyright:
© The Author, 2015. Published by Oxford University Press. All rights reserved. For Permissions, please email: [email protected]
PY - 2015
Y1 - 2015
N2 - 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.
AB - 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.
KW - Complexity
KW - Minimal contraction
KW - Preference aggregation
KW - Preference change
UR - http://www.scopus.com/inward/record.url?scp=85065642113&partnerID=8YFLogxK
U2 - 10.1093/logcom/exv027
DO - 10.1093/logcom/exv027
M3 - Article
AN - SCOPUS:85065642113
SN - 0955-792X
VL - 28
SP - 1715
EP - 1733
JO - Journal of Logic and Computation
JF - Journal of Logic and Computation
IS - 8
ER -