Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Alechina, Natasha; Liu, Fenrong; Logan, Brian (2015)
Publisher: Oxford University Press
Languages: English
Types: Article
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.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [1] Natasha Alechina, Fenrong Liu, and Brian Logan. Minimal preference change. In Davide Grossi, Olivier Roy, and Huaxin Huang, editors, Proceedings Fourth International Workshop on Logic, Rationality and Interaction (LORI-IV), volume 8196 of LNCS, pages 15-26, Hangzhou, China, October 2013. Springer.
    • [2] Natasha Alechina, Fenrong Liu, and Brian Logan. Postulates and a lineartime algorithm for minimal preference contraction. In Workshop on Logical Aspects of Multi-Agent Systems (LAMAS 2014), Informal Proceedings, 2014.
    • [3] Hajnal Andre´ka, Mark Ryan, and Pierre-Yves Schobbens. Operators and laws for combining preference relations. Journal of Logic and Computation, 12(1):13-53, 2002.
    • [4] K. J. Arrow. A difficulty in the concept of social welfare. Journal of Political Economy, 58(4):328-346, 1950.
    • [5] Nick Baigent. Preference proximity and anonymous social choice. The Quarterly Journal of Economics, 102(1):161-170, 1987.
    • [6] Johan van Benthem and Fenrong Liu. Dynamic logic of preference upgrade. Journal of Applied Non-Classical Logic, 17:157-182, 2007.
    • [7] Richard Booth and Thomas Meyer. How to revise a total preorder. Journal of Philosophical Logic, 40:193-238, 2011.
    • [8] Craig Boutilier. Iterated revision and minimal change of conditional beliefs. Journal of Philosophical Logic, 25(3):263-305, 1996.
    • [9] Vincent Conitzer, Je´roˆme Lang, and Lirong Xia. Hypercubewise preference aggregation in multi-issue domains. In In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI-2011), 2011.
    • [10] Adnan Darwiche and Judea Pearl. On the logic of iterated belief revision. Artificial Intelligence, 89:1-29, 1997.
    • [11] James P. Delgrande, Didier Dubois, and Je´roˆme Lang. Iterated revision as prioritized merging. In Patrick Doherty, John Mylopoulos, and Christopher A. Welty, editors, Proceedings, Tenth International Conference on Principles of Knowledge Representation and Reasoning, Lake District of the United Kingdom, June 2-5, 2006, pages 210-220. AAAI Press, 2006.
    • [12] Conal Duddy and Ashley Piggins. A measure of distance between judgment sets. Social Choice and Welfare, 39(4):855-867, 2012.
    • [13] Peter C. Fishburn. Condorcet social choice functions. SIAM Journal on Applied Mathematics, 33(3):469-489, 1977.
    • [14] Peter Ga¨rdenfors. Knowledge In Flux: Modeling the Dynamics of Epistemic States. MIT Press, 1988.
    • [15] Umberto Grandi. Binary Aggregation with Integrity Constraints. PhD thesis, ILLC, University of Amsterdam, 2012.
    • [16] Till Gru¨ne-Yanoff and Sven Ove Hansson, editors. Preference Change: Approaches from Philosophy, Economics and Psychology. Theory and Decision Library. Springer, 2009.
    • [17] So¨ren Hallden. On the Logic of “Better”. Lund, 1957.
    • [18] Sven Ove Hansson. Changes in preference. Theory and Decision, 38:1-28, 1995.
    • [19] Sven Ove Hansson. Semi-revision (invited paper). Journal of Applied NonClassical Logics, 7(2), 1997.
    • [20] Sven Ove Hansson. Multiple and iterated contraction reduced to single-step single-sentence contraction. Synthese, 173(2):153-177, 2010.
    • [21] John G. Kemeny. Mathematics without numbers. Daedalus, 88(4):577-591, 1959.
    • [22] Christian Klamler. A distance measure for choice functions. Daedalus, 30:419-425, 2008.
    • [23] Martin Lackner, Reinhard Pichler, Stefan Ru¨mmele, and Stefan Woltran. Multicut on graphs of bounded clique-width. In Guohui Lin, editor, Combinatorial Optimization and Applications - 6th International Conference, COCOA 2012, Banff, AB, Canada, August 5-9, 2012. Proceedings, volume 7402 of Lecture Notes in Computer Science, pages 115-126. Springer, 2012.
    • [24] Cline Lafage and Jrme Lang. Propositional distances and compact preference representation. European Journal of Operational Research, 160(3):741-761, 2005.
    • [25] Je´roˆme Lang and Leendert van der Torre. From belief change to preference change. In Proceedings of the 18th European Conference on Artificial Intelligence (ECAI-2008), pages 351-355, 2008.
    • [26] Isaac Levi. Subjunctives, dispositions and chances. Synthese, 34:423-455, 1977.
    • [27] Zhen Liang and Jeremy Seligman. A logical model of the dynamics of peer pressure. Electronic Notes in Theoretical Computer Science, 278:275-288, 2011.
    • [28] Fenrong Liu. Reasoning about Preference Dynamics, volume 354 of Synthese Library. Springer, 2011.
    • [29] Fenrong Liu. A two-level perspective on preference. Journal of Philosophical Logic, 40:421-439, 2011.
    • [30] Jianbing Ma, Salem Benferhat, and Weiru Liu. Revision over partial preorders: A postulational study. In Eyke Hu¨llermeier, Sebastian Link, Thomas Fober, and Bernhard Seeger, editors, Scalable Uncertainty Management - 6th International Conference, SUM 2012, Marburg, Germany, September 17- 19, 2012. Proceedings, volume 7520 of Lecture Notes in Computer Science, pages 219-232. Springer, 2012.
    • [31] Hannu Nurmi. A comparison of some distance-based choice rules in ranking environments. Theory and Decision, 57(1):5-24, 2004.
    • [32] Maria Silvia Pini, Francesca Rossi, Kristen Brent Venable, and Toby Walsh. Incompleteness and incomparability in preference aggregation: Complexity results. Artificial Intelligence, 175(7-8):1272-1289, 2011.
    • [33] Hans Rott. Modellings for belief change: Base contraction, multiple contraction, and epistemic entrenchment. In David Pearce and Gerd Wagner, editors, Logics in AI, European Workshop, JELIA '92, Berlin, Germany, September 7-10, 1992, Proceedings, volume 633 of Lecture Notes in Computer Science, pages 139-153. Springer, 1992.
    • [34] Marija Slavkovik and Thomas A˚gotnes. Measuring dissimilarity between judgment sets. In Eduardo Ferme´ and Joa˜o Leite, editors, Proceedings of the 14th European Conference on Logics in Artificial Intelligence (JELIA 2014, volume 8761 of Lecture Notes in Computer Science, pages 609-617. Springer, 2014.
    • [35] Georg Henrik von Wright. The Logic of Preference. Edinburgh: Edinburgh University Press, 1963.
    • [36] Peyton Young and Arthur Levenglick. A consistent extension of Condorcet's election principle. SIAM Journal on Applied Mathematics, 35(2):285-300, 1978.
  • No related research data.
  • Discovered through pilot similarity algorithms. Send us your feedback.

Share - Bookmark

Cite this article