Skip to main content

Research Repository

Advanced Search

Efficient minimal preference change

Alechina, Natasha; Liu, Fenrong; Logan, Brian

Authors

Natasha Alechina

Fenrong Liu

Brian Logan



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. doi: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 (OUP)
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 http://eprints.nottingham.ac.uk/id/eprint/33703
Publisher URL http://logcom.oxfordjournals.org/content/early/2015/05/13/logcom.exv027
Copyright Statement Copyright information regarding this work can be found at the following address: http://eprints.nottingham.ac.uk/end_user_agreement.pdf
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

Files


submitted-jlc-pr.pdf (280 Kb)
PDF

Copyright Statement
Copyright information regarding this work can be found at the following address: http://eprints.nottingham.ac.uk/end_user_agreement.pdf





You might also like



Downloadable Citations