* Mindruta et al. (2016) Mindruta D, Moeen M, Agarwal R (2016) A two-sided matching approach for partner selection and assessing complementarities in partners’ attributes in inter-firm alliances. _Strategic Management JOURNAL_ 37(1):206–231.
  * Monderer and Shapley (1996) Monderer D, Shapley L (1996) Potential games. _Games and Economic Behavior_ 14:124–143.
  * Murray et al. (2006) Murray IA, Ghahramani Z, MacKay DJC (2006) Mcmc for doubly-intractable distributions. _Uncertainty in Artificial Intelligence_ .
  * Nakajima (2007) Nakajima R (2007) Measuring peer effects on youth smoking behavior. _Review of Economic Studies_ 74(3):897–935.
  * Powell et al. (1996) Powell WW, Koput KW, Smith-Doerr L (1996) Interorganizational collaboration and the locus of innovation: Networks of learning in biotechnology. _Administrative Science Quarterly_ 41:116–145.
  * Reuer and Lahiri (2013) Reuer JJ, Lahiri N (2013) Searching for alliance partners: Effects of geographic distance on the formation of r&d collaborations. _Organization Science_ 25(1):283–298.
  * Rivera et al. (2010) Rivera MT, Soderstrom SB, Uzzi B (2010) Dynamics of dyads in social networks: Assortative, relational, and proximity mechanisms. _annual Review of Sociology_ 36:91–115.
  * Robins et al. (2007) Robins G, Snijders T, Wang P, Handcock M, Pattison P (2007) Recent developments in exponential random graph (p*) models for social networks. _Social Networks_ .
  * Rosenkopf and Padula (2008) Rosenkopf L, Padula G (2008) Investigating the microstructure of network evolution: Alliance formation in the mobile communications industry. _Organization Science_ 19:669–687.
  * Rothaermel and Boeker (2008) Rothaermel FT, Boeker W (2008) Old technology meets new technology: Complementarities, similarities, and alliance formation. _Strategic Management JOURNAL_ 29(1):47–77.
  * Shipilov and Li (2012) Shipilov AV, Li SX (2012) The missing link: The effect of customers on the formation of relationships among producers in the multiplex triads. _Organization Science_ 23(2):472–491.
  * Snijders (2002) Snijders TA (2002) Markov chain monte carlo estimation of exponential random graph models. _Journal of Social Structure_ 3(2).
  * Snijders et al. (2010) Snijders TA, Van de Bunt GG, Steglich CE (2010) Introduction to stochastic actor-based models for network dynamics. _Social networks_ 32(1):44–60.
  * Sorensen (2007) Sorensen M (2007) How smart is smart money? a two-sided matching model of venture capital. _The Journal of Finance_ 62(6):2725–2762.
  * Sorenson and Stuart. (2001) Sorenson O, Stuart T (2001) Syndication networks and the spatial distribution of venture capital investments. amer. _American Journal of Sociology_ 106:1546–1588.
  * Sorenson and Stuart (2008) Sorenson O, Stuart T (2008) Bringing the context back in: settings and the search for syndicate partners in venture capital investment networks. _Administrative Science Quarterly_ 53:266–298.
  * Stern et al. (2014) Stern I, Dukerich JM, Zajac E (2014) Unmixed signals: How reputation and status affect alliance formation. _Strategic Management JOURNAL_ 35(4):512–531.
  * Stivala et al. (2016) Stivala AD, Koskinen JH, Rolls DA, Wang P, Robins GL (2016) Snowball sampling for estimating exponential random graph models for large networks. _Social Networks_ 47:167–188.
  * Tortoriello et al. (2012) Tortoriello M, Reagans R, McEvily B (2012) Bridging the knowledge gap: The influence of strong ties, network cohesion, and network range on the transfer of knowledge between organizational units. _Organization Science_ 23(4):1024–1039.
  * Wasserman and Faust (1994) Wasserman S, Faust K (1994) _Social Network Analysis: Methods and Applications_ (Cambridge University Press).
  * Wasserman and Pattison (1996) Wasserman S, Pattison P (1996) Logit models and logistic regressions for social networks: I. an introduction to markov graphs and p*. _Psychometrika_ 61(3):401–425.
  * Wilson (1968) Wilson R (1968) The theory of syndicates. _Econometrica: journal of the Econometric Society_ 119–132.
  * Zaheer and Soda (2009) Zaheer A, Soda G (2009) Network evolution: The origins of structural holes. _Administrative Science Quarterly_ 54(1):1–31.
  * Zhang et al. (2017) Zhang L, Gupta AK, Hallen BL (2017) The conditional importance of prior ties: A group-level analysis of venture capital syndication. _Academy of Management Journal_ 60(4):1360–1386.


# An AGM Approach to Revising Preferences

Adrian Haret1 Johannes P. Wallner2
1ILLC, University of Amsterdam
2TU Graz
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We look at preference change arising out of an interaction between two
elements: the first is an initial preference ranking encoding a pre-existing
attitude; the second element is new preference information signaling input
from an authoritative source, which may come into conflict with the initial
preference. The aim is to adjust the initial preference and bring it in line
with the new preference, without having to give up more information than
necessary. We model this process using the formal machinery of belief change,
along the lines of the well-known AGM approach. We propose a set of
fundamental rationality postulates, and derive the main results of the paper:
a set of representation theorems showing that preference change according to
these postulates can be rationalized as a choice function guided by a ranking
on the comparisons in the initial preference order. We conclude by presenting
operators satisfying our proposed postulates. Our approach thus allows us to
situate preference revision within the larger family of belief change
operators.

##  1 Introduction

Preferences play a central role in theories of decision making, as part of the
mechanism underlying intentional behavior and rational choice, both in
economic models of rational agency as well as in formal models of artificial
agents supposed to interact with the world and each other (?; ?; ?; ?). Since
such interactions take place in dynamic environments, it can be expected that
preferences change in response to new developments.

In this paper we are interested in preference change occurring when new
preference information, denoted by $o$, becomes available and has to be taken
at face value, thereby prompting a change in prior preference information,
denoted by $\pi$. The change, we require, should preserve as much useful
information from $\pi$ as can be afforded.

Preference change thus described is a pervasive phenomenon, arising in many
contexts spanning the realms of both human and artificial agency. Thus, there
is a distinguished tradition in Economics and Philosophy that looks at
examples of conflict between an agent’s subjective preference (what we call
here the initial, or prior preference $\pi$) and a second-order preference,
often standing for a commitment or moral rule (what we call here the new
preference information $o$): subjective versus ‘ethical’ preferences (?), lack
of will, or _akrasia_ (?), moral commitments (?), second-order volitions (?)
and second-order preferences (?) all fall under this heading.

The same challenge can occur in technological applications, from updating CP-
nets (?) to changing the order in which search results are displayed on a page
in response to user provided specifications. At the same time, similar topics
are emerging in the discussion on ethical decision making for artificial
agents (?) and in issues related to the _alignment problem_ (?): an artificial
agent dealing with humans will have to learn their preferences, but as it
cannot do so instantaneously, it must presumably acquire the relevant
information in intermediate steps, revising along the way.

Thus, whether it is the internal conflict between an agent’s private leanings
and the better angels of its nature, or a content provider wanting to tailor
its products for a better user experience, many cases of preference change
involve a conflict between two types of preferences, one of which is perceived
as having priority over the other. However, even though the need to reconcile
conflicting preferences in favor of one of them is widely acknowledged, a
concrete mechanism for resolving preference conflicts, that works for general
preference orders, is often overlooked.

In keeping with prominent approaches to belief change, which model rational
change using a plausibility relation over the states of affairs undergoing
revision, and echoing a suggestion of Amartya Sen to the effect that conflicts
among preferences can be understood using rankings over the preferences
themselves (?), we propose formalizing preference change using preferences
over the basic elements of a preference order, as illustrated in the following
example.

$\pi$$1$$2$$3$$o$$1$$2$$3$$\pi_{1}$$1$$2$$3$$\pi_{2}$$1$$2$$3$$\pi_{3}$$1$$2$$3$
Figure 1:  Revising preference order $\pi$ by $o$: simply adding $o$ to $\pi$
leads to a cycle, so if $o$ is accepted then a choice needs to be made
regarding which of the initial comparisons of $\pi$ to keep; potential
candidates for the revised order are $\pi_{1}$, $\pi_{2}$ or $\pi_{3}$. A
direct comparison ranking $i$ better than $j$ is depicted by a solid arrow
from $i$ to $j$, with comparisons inferred by transitivity depicted by dotted
arrows.

######  Example 1.

The initial preference $\pi$ is such that, as a result of explicit assertion,
item $1$ is ranked better than $2$ and $2$ is ranked better than $3$; by
virtue of transitivity, it is also inferred that $1$ is considered better than
$3$. We want to revise $\pi$ by a preference $o$, according to which $3$ is
better than $1$ (see Figure 1). The simplest solution is to add $o$ to $\pi$
(i.e., include the comparisons contained in both), but the transitivity
requirement leads to a cycle between $1$, $2$ and $3$, which we would like to
avoid. We are thus in a situation where $\pi$ and $o$ cannot be jointly
accepted, but since $o$, we stipulate, must be accepted, something must be
given up from $\pi$ (though, we ask, no more than strictly necessary). How is
the decision to be made? We suggest that an implicit preference over the
comparisons of $\pi$ that were explicitly provided can provide an answer: if
the comparison of $1$-vs-$2$ (the edge from $1$ to $2$ in Figure 1) is
preferred to the one of $2$-vs-$3$ then the result is $\pi_{1}$, which holds
on to $1$-vs-$2$ from $\pi$ and together with $o$ infers, by transitivity,
that $3$ is better than $2$; alternatively, a preference for $2$-vs-$3$ over
$1$-vs-$2$ leads to $\pi_{2}$ as the result, while indifference between the
two comparisons means that both are given up, resulting in $\pi_{3}$. Thus,
preference over comparisons in $\pi$ translates as choice over how to go about
revising $\pi$. Interestingly, we may also reason in the opposite direction:
observing choice behavior across different instances of revision allows us to
infer preferences over comparisons in $\pi$, e.g., revising to $\pi_{1}$,
rather than to $\pi_{2}$ or $\pi_{3}$, can be rationalized as saying that the
comparison of $1$-vs-$2$ is considered better than $2$-vs-$3$.

Our purpose here is to formalize the type of reasoning illustrated in Example
1 by rationalizing preference change as a type of choice function on what we
will call the _direct comparisons of $\pi$_, i.e., the explicit preferences
assumed to be given in $\pi$. Since a conflict between $\pi$ and $o$ forces
some of the direct comparisons of $\pi$ to be renounced, additional
information in the form of a preference order over the direct comparisons of
$\pi$ will serve as guide to the choice function. The aim, in this, is not
legislate on what is the right choice to make; rather, it is to make sure that
whatever the choice is, it is made in a coherent way.

### Contributions.

We present a mechanism for revising a preference order $\pi$ that is based on
an underlying preference relation over the basic, atomic comparisons of $\pi$.
This mechanism proceeds sequentially, by working its way through the
underlying preference relation and adding as many of the direct comparisons of
$\pi$ as possible, while avoiding a conflict with $o$. We present a set of
conditions under which the preference order on direct comparisons of $\pi$
exists and has desired properties, and characterize the revision mechanism
using a set of intuitive normative principles, i.e., rationality postulates in
the AGM mould (?). The significance of our approach lies in laying bare the
theoretical requirements and basic assumptions for mechanisms intended to
revise preferences.

### Related work.

Our work complements existing research, but manages to occupy a distinct niche
in a broader landscape. Some previous work labeled as preference revision (?;
?; ?), looks at changes in preferences prompted by a change in beliefs. Here
we abstract away from the source of the new information, choosing to focus
exclusively on a mechanism that can be used for resolving conflicts: the
rational thing to do when knowing that, for some reason or other, one’s
preference has to change. Other work (?) describes preference change when
preferences are represented using CP-nets (?), or dynamic epistemic logic (?),
in the context of declarative debugging (?), or databases (?), and therefore
comes with additional structural constraints. In contrast, we have opted to
represent preferences as strict partial orders over a set of items: we believe
this straightforward formulation allows the basic issue signaled by Amartya
Sen (?), to be visible and tackled head on.

Apart from the issues raised in the Economics literature about second-order
desires (?; ?; ?; ?; ?), the basic phenomenon of preference change has also
been raised in explicit connection to belief change (?; ?; ?), but a
representation in terms of preferences on the comparisons present in the
preference orders, along the lines suggested here, has, to the best of our
knowledge, not yet been given. Much existing work proceeds by putting forward
some concrete preference revision mechanism, possibly by shifting some
elements of the original preference around, and occasionally with a remark on
the similarity between this operation and a belief revision operation (?; ?;
?; ?). What our work adds to these models is an analysis in terms of
postulates and representation results.

The postulates we put forward for preference revision bear a distinct
resemblance to the AGM postulates employed for belief revision (?; ?; ?):
given that changing one’s mind involves choosing some parts of a belief to
keep and some to remove, this is no coincidence. Indeed, the two problems are
similar, though the structural particularities of preferences (in particular,
the requirement that they are transitive) mean that transfer of insights from
belief revision to preference revision is by no means straightforward.

### Outline.

The rest of the paper is structured as follows. In Section 2 we introduce
notation and the basic elements of our model. In Section 3 we provide a
constructive way of revising a preference order, based on rankings of the
direct comparisons. In Section 4 we provide a set of intuitive postulates
together with their motivations, and discuss their appropriateness for the
purpose of modelling preference revision. In Section 5 we identify a set of
conditions under which these postulates can be applied. In Section 6 we show
that the postulates presented in Section 4 characterize the procedure
described in Section 3. Section 7 discusses concrete preference revision
operators, and Section 8 offers concluding remarks.

##  2 Preliminaries

We assume a finite set $V$ of items, standing for the objects an agent can
have preferences over. If $\pi$ is a binary relation on a set $V$ of items,
then $\pi$ is a _strict partial order (spo) on $V$_ if $\pi$ is transitive and
irreflexive, and we write $\mathcal{O}_{V}$ for the set of strict partial
orders on $V$. If $\pi$ is an spo on a set $V$ of items, then $\pi$ is a
_strict linear order on $V$_ if $\pi$ is also total, in addition to being
transitive and irreflexive. A _chain on $V$_ is a strict linear order on a
subset of $V$. We write $\mathcal{C}_{V}$ for the set of chains on $V$.
FInally, $\pi$ is a total preorder on $V$ if $\pi$ is transitive and total,
with $\mathcal{T}_{V}$ being the set of total preorders on $V$. Note that in
the following we will typically be interested in total preorders on $V\times
V$, i.e., total preorders on the set of comparisons of items in $V$.

If $\pi$ is an spo on a set of items $V$, then a _comparison $(i,j)$ of $\pi$_
is an element $(i,j)\in\pi$, for some items $i,j\in V$, interpreted as saying
that, in the context of $\pi$, $i$ is considered strictly better than $j$. To
simplify notation, we sometimes also refer to comparisons with the letter $c$.
We often have to consider the union $\pi_{1}\cup\pi_{2}$ of two spos, which is
not guaranteed to be an spo, since transitivity is not preserved under unions.
If this is the case, we typically have to substitute $\pi_{1}\cup\pi_{2}$ for
its _transitive closure_ , denoted by $(\pi_{1}\cup\pi_{2})^{+}$. Since
preferences are required to be transitive, we write a sequence of comparisons
$\\{(1,2),(2,3)\dots,(m{-}1,m)\\}^{+}$ as $(1,\dots,m)$.

If $\pi=(i_{1},\dots,i_{m})$ is a chain on $V$, a _direct comparison of $\pi$_
is a comparison $(i_{k},i_{k+1})\in\pi$, i.e., a comparison between $i_{k}$
and its direct successor in $\pi$, with $\delta_{\pi}$ being the set of direct
comparisons of $\pi$. The assumption is that direct comparisons are the result
of explicit information, and are basic in the sense that they cannot be
inferred by transitivity using other comparisons in $\pi$. Given preference
orders $\pi\in\mathcal{C}_{V}$ and $o\in\mathcal{O}_{V}$, we want to carve out
the possible options for the revision of $\pi$ by $o$. For this we use the set
$\lfloor{o}\rfloor_{\pi}$ of _$\pi$ -completions of $o$_, defined as:

$\lfloor{o}\rfloor_{\pi}=\\{(o\cup\delta)^{+}\in\mathcal{O}_{V}\mid\delta\subseteq\delta_{\pi}\\}.$

The intuition is that a $\pi$-completion of $o$ is a preference order
constructed from $o$ using some, and only, direct comparisons in $\pi$, i.e.,
information originating exclusively from the two sources given as input. We
will expect that a preference revision operator selects one element of this
set as the revision result.

Though taking $(\pi\cup o)^{+}$ as the result of revising $\pi$ by $o$ is not,
in general, feasible, we still want to identify parts of $(\pi\cup o)^{+}$
that are uncontroversial. To that end, the _cycle-free part $\alpha_{\pi}^{o}$
of $(\pi\cup o)^{+}$_ is defined as:

$\alpha_{\pi}^{o}=\\{({i},{i}{+}{1})\in(\pi\cup
o)^{+}\mid({i}{+}{1},i)\notin(\pi\cup o)^{+}\\},$

i.e., the set of comparisons of $(\pi\cup o)^{+}$ not involved in a cycle with
the comparisons of $o$. The _cyclic part $\kappa_{\pi}^{o}$ of $\pi$ with
respect to $o$_ is defined as:

$\kappa_{\pi}^{o}=\\{({i},{i}{+}{1})\in\delta_{\pi}\mid({i}{+}{1},i)\in(\pi\cup
o)^{+}\\},$

i.e., the set of direct comparisons of $\pi$ involved in a cycle with $o$.

######  Example 2.

For $\pi$ and $o$ as in Example 1, we have that
$\delta_{\pi}=\\{(1,2),(2,3)\\}$, while the $\pi$-completions of $o$ are
$\lfloor{o}\rfloor_{\pi}=\\{(3,1,2),(2,3,1),(3,1)\\}$, i.e., the spos obtained
by adding to $o$ either of the elements of $\delta_{\pi}$, or none
(corresponding to $\pi_{1}$, $\pi_{2}$ and $\pi_{3}$). The cyclic part of
$\pi$ with respect to $o$ is $\kappa_{\pi}^{o}=\delta_{\pi}=\\{(1,2),(2,3)\\}$
and the cycle-free part of $\pi$ with respect to $o$ is
$\alpha_{\pi}^{o}=\emptyset$.

##  3 A General Method for Revising Preferences

A _preference revision operator $\triangleright$_ is a function
$\triangleright\colon\mathcal{C}_{V}\times\mathcal{O}_{V}\rightarrow\mathcal{O}_{V}$
taking a chain $\pi$ and an spo $o$ as input, and returning an spo
$\pi\triangleright o$ as output.

The choice of input and output can be motivated by imagining that $\pi$ stands
for an existing priority ranking, e.g., the ordering of items on a webpage,
whereas the new information $o$ is provided by a user and is more likely to be
incomplete.

In addition, we may look at this in light of the material that is to come:
since we will be rationalizing preference revision operators using preferences
(i.e., preorders) on comparisons, an spo as output reflects the fact that
certain comparisons are considered equally good, and must be given up
together. The unfortunate effect of this is that the input and output formats
do not match, which makes it unclear, at this point, whether we can iterate
the revision operation. That being said, the output can (and will) be
tightened to a chain: provided that the preferences guiding revision are a
linear order (i.e., there are no ties). We touch on this aspect at the end of
Section 6.

We start, then, by presenting a general procedure for revising preferences
that, as advertised, utilizes total preorders on the set $\delta_{\pi}$ of
direct comparisons of $\pi$: thus, a _preference assignment $a$_ is a function
$a\colon\mathcal{C}_{V}\rightarrow\mathcal{T}_{V\times V}$ mapping every
preference $\pi\in\mathcal{C}_{V}$ to a total preorder $\leq_{\pi}$ on
elements of $V\times V$, i.e., on pairwise comparisons on the items of $V$, of
which we are interested only in the preorder on $\delta_{\pi}$. In typical AGM
manner, a comparison $c_{i}\leq_{\pi}c_{j}$ in the context of a preorder
$\leq_{\pi}$ on $\delta_{\pi}$ means that $c_{i}$ is _better_ than $c_{j}$.

If $\pi\in\mathcal{C}_{V}$, $o\in\mathcal{O}_{V}$ and $\leq_{\pi}$ is a total
preorder on $\delta_{\pi}$, then, for $i\geq 1$, the _$\leq_{\pi}$ -level $i$
of $\delta_{\pi}$_, denoted $\mathit{lvl}_{\leq}^{i}(\delta_{\pi})$, contains
the $i^{\text{th}}$ best elements of $\delta_{\pi}$ according to $\leq_{\pi}$,
i.e.,
$\mathit{lvl}^{1}_{\leq_{\pi}}(\delta_{\pi})=\min_{\leq_{\pi}}(\delta_{\pi})$,
$\mathit{lvl}^{i+1}_{\leq_{\pi}}(\delta_{\pi})=\min_{\leq_{\pi}}(\delta_{\pi}\setminus\bigcup_{1\leq
j\leq i}\mathit{lvl}^{j}_{\leq_{\pi}}(\delta_{\pi}))$, etc. Note that the
$\leq_{\pi}$-levels of $\delta_{\pi}$ partition $\delta_{\pi}$ and, since
$\delta_{\pi}$ is finite, there exists a $j>0$ such that
$\mathit{lvl}^{i}_{\leq_{\pi}}(\delta_{\pi})=\emptyset$, for all $i\geq j$.
The _addition operator ${\operatorname{add}}^{i}_{\leq_{\pi}}(o)$_ is defined,
for any $o\in\mathcal{O}_{V}$ and $i\geq 0$, as follows:

$\displaystyle{\operatorname{add}}_{\leq_{\pi}}^{0}(o)$
$\displaystyle=(o\cup\alpha_{\pi}^{o})^{+},$
$\displaystyle{\operatorname{add}}_{\leq_{\pi}}^{i}(o)$
$\displaystyle=\begin{cases}({\operatorname{add}}^{i-1}_{\leq_{\pi}}(o)\cup(\mathit{lvl}_{\leq_{\pi}}^{i}(\delta_{\pi})\cap\kappa_{\pi}^{o}))^{+},~{}\text{if
in}~{}\mathcal{O}_{V},\\\
{\operatorname{add}}_{\leq_{\pi}}^{i-1}(o),~{}\text{otherwise}.\end{cases}$

Intuitively, the addition operator starts by adding to $o$ all the direct
comparisons of $\pi$ that are not involved in a cycle with it, i.e., which are
not under contention by the accrual of new preference information. Then, at
every further step $i>0$, the addition operator tries to add all comparisons
on level $i$ of $\delta_{\pi}$ that are involved in a cycle with $o$: if the
resulting set of comparisons can be construed as a spo (by taking its
transitive closure) the operation is successful, and the new comparisons are
added; if not, the addition operator does nothing. Since the addition of new
comparison follows the order $\leq_{\pi}$, this ensures that better quality
comparisons are considered before lower quality ones.

Note that this procedure guarantees that there are always _some_ comparisons
in $\pi\triangleright o$, i.e., we have that $o\subseteq\pi\triangleright o$,
regardless of anything else. Note, also, that the number of non-empty levels
in $\delta_{\pi}$ is finite and the addition operation eventually reaches a
fixed point, i.e., there exists $j\geq 0$ such that
${\operatorname{add}}^{i}_{\leq_{\pi}}(o)={\operatorname{add}}^{j}_{\leq_{\pi}}(o)$,
for any $i\geq j$. We denote by ${\operatorname{add}}_{\leq_{\pi}}^{\ast}(o)$
the fixed point of this operator and take it as the defining expression of a
preference revision operator: if $a$ is a preference assignment, then the _$a$
-induced preference revision operator $\triangleright^{a}$_ is defined, for
any $\pi\in\mathcal{C}_{V}$ and $o\in\mathcal{O}_{V}$, as:

$\pi\triangleright^{a}o={\operatorname{add}}^{\ast}_{\leq_{\pi}}(o).$

Note that, by design,
${\operatorname{add}}^{\ast}_{\leq_{\pi}}(o)\in\mathcal{O}_{V}$, i.e., the
operator $\triangleright$ is well defined.

$\pi$$1$$2$$3$$4$$o$$1$$2$$3$$4$$(\pi\cup
o)^{+}$$1$$2$$3$$4$$\leq_{\pi}$$(1,2)$$(2,3)$,
$(3,4)$$\mathit{lvl}^{1}_{\leq_{\pi}}(\pi)$$\mathit{lvl}^{2}_{\leq_{\pi}}(\pi)$
Figure 2:  Preference revision by adding direct comparisons from $\pi$ to $o$,
using the preorder $\leq_{\pi}$. In $\leq_{\pi}$ lower means better; the
comparison $(3,4)$ is ignored by the addition operator because it is not
involved in a cycle with $o$ (and is added at the beginning anyway).

######  Example 3.

Consider initial preference order $\pi=(1,2,3,4)$ and new information
$o=(3,1)$. We obtain that the direct comparisons of $\pi$ are
$\delta_{\pi}=\\{(1,2),(2,3),(3,4)\\}$. Suppose, now, that there is a total
preorder $\leq_{\pi}$ on $\delta_{\pi}$ according to which
$(1,2)<_{\pi}(2,3)\approx_{\pi}(3,4)$, as depicted in Figure 2. To construct
$\pi\triangleright o$, the addition operator starts from
${\operatorname{add}}^{0}_{\leq_{\pi}}(o)=(\\{(3,1)\\}\cup\\{(1,4),(2,4),(3,4)\\})^{+}$,
i.e., $o$ itself together with $\alpha_{\pi}^{o}$, the cycle-free part of
$\pi$ with respect to $o$. At the next step the addition operator tries to add
$(1,2)$, which it can do successfully; at the next step it attempts to add
$(2,3)$, which creates a conflict with $(3,1)$ and $(1,2)$, added previously.
After this there are no more comparisons to add.

##  4 Postulates for Preference Revision

We show now that the procedure described in Section 3 can be characterized
with a set of AGM-like postulates that do not reference any concrete revision
procedure and are, by themselves, intuitive enough to provide reasonable
constraints on any preference revision operator.

The first two postulates we consider apply to any chain
$\pi\in\mathcal{C}_{V}$, spo $o\in\mathcal{O}_{V}$ and preference revision
operator
$\triangleright\colon\mathcal{C}_{V}\times\mathcal{O}_{V}\rightarrow\mathcal{O}_{V}$,
and are as follows:

($\mathrm{P}_{1}$)

$\pi\triangleright o\in\lfloor{o}\rfloor_{\pi}$.

($\mathrm{P}_{2}$)

$\alpha_{\pi}^{o}\subseteq\pi\triangleright o$.

Postulates $\mathrm{P}_{1-2}$ require the result to be formed by adding
elements from $\pi$ to the new information $o$, and to be of a certain
admissible type, i.e., an spo. They are meant to capture preference revision
in its most uncontroversial aspects, yet they still require some careful
unpacking.

Postulate $\mathrm{P}_{1}$ states that $\pi\triangleright o$ is a
$\pi$-completion of $o$, i.e., a preference order constructed only by adding
direct comparisons from $\pi$ to $o$. Unfolding its consequences, postulate
$\mathrm{P}_{1}$ ensures that:

($i$)

$\pi\triangleright o\in\mathcal{O}_{V}$, i.e., $\pi\triangleright o$ is a
chain on $V$,

($ii$)

$o\subseteq\pi\triangleright o$, i.e., $\pi\triangleright o$ contains all the
information present in $o$, and

($iii$)

$\pi\triangleright o\subseteq(\pi\cup o)^{+}$, i.e., $\pi\triangleright o$ is
contained in the binary relation obtained by simply adding $o$ to $\pi$, and
adding all the comparisons inferred by transitivity.

In terms of AGM propositional belief revision, postulate $\mathrm{P}_{1}$ does
the same duty as the _Closure_ , _Success_ , _Inclusion_ and _Consistency_
postulates (?; ?). These postulate mandate that the revision result should be
a propositional theory (i.e., have a required format), that the new
information should be accepted, and that, unless the new information is
inconsistent, the revision result should be consistent.

Given this observation, a question emerges as to why not use conditions
($i$)-($iii$) as postulates instead of the proposed $\mathrm{P}_{1}$. The
reason is that $\mathrm{P}_{1}$ contains an element that lacks from conditions
($i$)-($iii$): what $\mathrm{P}_{1}$ adds is the requirement that
$\pi\triangleright o$ is to be constructed using only direct comparisons of
$\pi$ (in addition to $o$), and the reason why such a condition is desirable
is to prevent $\pi\triangleright o$ from having opinions on items over which
no opinion had been expressed before revision. The issue is illustrated in
Example 4.

######  Example 4.

Consider preferences $\pi$ and $o$ as in Example 1, and an additional spo
$\pi_{4}=\\{(3,1),(3,2)\\}$. Note that $\pi_{4}$ is such that
$o\subseteq\pi_{4}\subseteq(\pi\cup o)^{+}$ and therefore satisfies conditions
($i$)-($iii$) expressed above, so that according to conditions ($i$)-($iii$)
preference $\pi_{4}$ is a viable revision result.

At the same time, we do not want to consider $\pi_{4}$ as a potential
candidate for the revision result: the comparison $(3,2)$ occurs neither in
$\pi$ nor in $o$ as a direct comparison, and there is reason to think that
adding it would be unjustified: a rational preference revision operator should
not be allowed to return $\pi_{4}$ when revising $\pi$ by $o$. By contrast,
when the comparison $(3,2)$ does occur, e.g., in the desirable preference
order $\pi_{1}=(3,1,2)$, it occurs as the result of inference from $(3,1)$,
which is added from $o$, and $(1,2)$, which is preserved from $\pi$.

Postulate $\mathrm{P}_{2}$ says that the cycle-free part of $\pi$ with respect
to $o$ is to be preserved in $\pi\triangleright o$, and is meant to preserve
the parts of $(\pi\cup o)^{+}$ that are not up for dispute. Note that in the
case when $(\pi\cup o)^{+}$ does not contain a cycle then
$\alpha_{\pi}^{o}=(\pi\cup o)^{+}$, and $\mathrm{P}_{2}$ together with
$\mathrm{P}_{1}$ imply that $\pi\triangleright o=(\pi\cup o)^{+}$: this is the
case when revision is easy, and nothing special needs to be done. Throughout
all this, postulate $\mathrm{P}_{2}$ serves the same function as the _Vacuity_
postulate in propositional revision (?; ?): in the ideal case, when $o$ can
simply be added to $\pi$, applying postulate $\mathrm{P}_{2}$ results in the
union of the two structures.

So far we have established that, if there is no conflict between $\pi$ and
$o$, i.e., no cycle arises by adding $o$ to $\pi$, then we can simply add $o$
to $\pi$; and if there is a conflict, then $\triangleright$ must choose
between the direct comparisons of $\pi$ involved in the cycle. This choice,
however, must be coherent in a precise sense: we expect the choices to be
indicative of an underlying preference over direct comparisons, which remains
stable across different instances of revision. This sense of coherence is
illustrated by Example 5.

######  Example 5.

Consider revising $\pi=(1,2,3,4)$, depicted in Figure 2, by $o_{1}=(4,1)$.
SInce adding $(\pi\cup o)^{+}$ contains a cycle, revision requires a choice
between comparisons $(1,2)$, $(2,3)$ and $(3,4)$: assume $(1,2)$ is chosen,
suggesting $(1,2)$ is better than $(2,3)$ and $(3,4)$. Suppose, now, that we
add $o_{2}=\\{(3,4)\\}$ and revise by $(o_{1}\cup
o_{2})^{+}=\\{(3,4),(4,1),(3,1)\\}$: another cycle is formed, and a choice is
necessary, this time only between $(1,2)$ and $(2,3)$. In accordance with the
previous decision, $(1,2)$ should be chosen here as well.

The choice behavior of a revision operator has to reflect an implicit
preference order over the direct comparisons of $\pi$, and this is handled by
the following postulates, meant to apply to any chain $\pi\in\mathcal{C}_{V}$,
spos $o_{1},o_{2}\in\mathcal{O}_{V}$ such that $(o_{1}\cup
o_{2})^{+}\in\mathcal{O}_{V}$, and a preference revision operator
$\triangleright$:

($\mathrm{P}_{3}$)

$\pi\triangleright(o_{1}\cup o_{2})^{+}\subseteq((\pi\triangleright o_{1})\cup
o_{2})^{+}$.

($\mathrm{P}_{4}$)

If $((\pi\triangleright o_{1})\cup o_{2})^{+}\in\mathcal{O}_{V}$, then
$((\pi\triangleright o_{1})\cup o_{2})^{+}\subseteq\pi\triangleright(o_{1}\cup
o_{2})^{+}$.

There is a similarity between postulates $\mathrm{P}_{3}$ and $\mathrm{P}_{4}$
and the _Superexpansion_ and _Subexpansion_ postulates, respectively, from
propositional belief revision (?; ?), which ensure that the choice between two
options is stable and independent of alternatives not directly involved.
Postulates $\mathrm{P}_{3-4}$ are meant to ensure the same here. However, it
turns out that in the context of preference revision this happens only under a
specific set of conditions, which we elaborate on in the following section.

##  5 Coordination

In this section we identify the precise conditions under which it makes sense
to apply postulates $\mathrm{P}_{3-4}$, presented in Section 4. Before doing
so, we introduce some additional notation.

If $o_{1}$ and $o_{2}$ are spos, we say that $o_{1}$ and $o_{2}$ are
_coordinated with respect to $\pi$_ if for any set
$\delta\subseteq\kappa_{\pi}^{o_{1}}$ such that for every direct comparison
$(i,{i}{+}{1})\in\delta$, neither $(i,{i}{+}{1})$ nor $({i}{+}{1},i)$ is in
$(o_{1}\cup o_{2})^{+}$, it holds that if
$(o_{1}\cup\delta)^{+}\in\mathcal{O}_{V}$, then $((o_{1}\cup
o_{2})^{+}\cup\delta)^{+}\in\mathcal{O}_{V}$. In other words, if $\pi$ and
$o_{1}$ form a cycle and we want to add $o_{2}$ as well, then we direct our
attention to the direct comparisons in $\pi$ that are not directly ruled out
by $(o_{1}\cup o_{2})^{+}$, i.e., such that neither these comparisons nor
their inverses are contained in $(o_{1}\cup o_{2})^{+}$. The property of
coordination says that if we can consistently add some of these comparisons to
$o_{1}$, then it must be the case that we can also add them to $(o_{1}\cup
o_{2})^{+}$. Intuitively, coordination means that adding extra information
$o_{2}$ does not step on $o_{1}$’s toes, by rendering unviable any comparisons
that were previously viable. The following example makes this clearer.

$\pi$$1$$2$$3$$4$$\leq_{\pi}$$(1,2)$$(2,3)$$(3,4)$$o_{1}$$1$$2$$3$$4$$o_{2}$$1$$2$$3$$4$$\pi\triangleright(o_{1}\cup
o_{2})^{+}$$1$$2$$3$$4$$((\pi\triangleright o_{1})\cup o_{2})^{+}$$1$$2$$3$$4$
Figure 3:  Postulates $\mathrm{P}_{3-4}$ are satisfied only if $o_{1}$ and
$o_{2}$ are coordinated with respect to $\pi$.

######  Example 6.

Take $\pi=(1,2,3,4)$ and $o_{1}=(4,1)$, $o_{2}=(3,1)$. The direct comparisons
of $\pi$ that are involved in a cycle with $o_{1}$ are
$\kappa_{\pi}^{o_{1}}=\\{(1,2),(2,3),(3,4)\\}$, so that revision by $o_{1}$
requires making a choice between these comparisons. This choice, we expect, is
done on the basis of some implicit preference over the comparisons, which
guides revision even when we add additional information in the form of
$o_{2}$. Notice, now, that neither of $(1,2)$, $(2,3)$ and $(3,4)$ is
individually ruled out by $(o_{1}\cup o_{2})^{+}$: we have, for instance, that
$(1,2)\notin(o_{1}\cup o_{2})^{+}$ and $(2,1)\notin(o_{1}\cup o_{2})^{+}$; the
same holds for $(2,3)$ and $(3,4)$. The significance of this is that adding
$o_{2}$ to $o_{1}$ does not alter the menu: the choice is still one over
comparisons $(1,2)$, $(2,3)$ and $(3,4)$.

The problem, however, is that whereas with $o_{1}$ the choice is relatively
unconstrained, meaning we can choose any proper subset of
$\\{(1,2),(2,3),(3,4)\\}$ to add to $(4,1)$, adding the additional comparison
$(3,1)$ complicates things. To see how, consider the set of comparisons
$\delta=\\{(1,2),(2,3)\\}$. These comparisons can be consistently added to
$o_{1}$, i.e., $(o_{1}\cup\delta)^{+}\in\mathcal{O}_{V}$, but not to
$(o_{1}\cup o_{2})^{+}$, i.e., $((o_{1}\cup
o_{2})^{+}\cup\delta)^{+}\notin\mathcal{O}_{V}$. According to our definition,
this implies that $o_{1}$ and $o_{2}$ are not coordinated with respect to
$\pi$. Thus, whereas with $o_{1}$ can be augmented with both $(1,2)$ and
$(2,3)$, $o_{1}$ and $o_{2}$ do not allow adding both comparisons _together_.
This, then, has a knock-down effect in that it makes it possible to add
comparison $(3,4)$, irrespective of where it is in the preorder on
comparisons.

In such a situation, then, the specific details of how the choice problem is
constructed makes the position of $(3,4)$ in the overall preference order over
comparisons irrelevant. Consequently, expecting our axioms to take the
preference order into account will land us into trouble. To see this, onsider
preorder $\leq_{\pi}$ in Figure 3, where $(3,4)$ is the least preferred
comparison, and the revision operator $\triangleright$ induced by it. We have
that $(3,4)\in\pi\triangleright(o_{1}\cup o_{2})^{+}$, but
$(3,4)\notin((\pi\triangleright o_{1})\cup o_{2})^{+}$, i.e., postulate
$\mathrm{P}_{3}$ is not satisfied.

This fact is related with the lack of coordination between $o_{1}$ and
$o_{2}$, as the addition of $o_{2}$ tampers with the choice problem: though we
can still add either one of the three comparisons, as mentioned above, we
cannot add $(1,2)$ and $(2,3)$ together anymore, which in turn means that
$(3,4)$ can be added regardless of its position in $\leq_{\pi}$ the preorder.

Example 6 is a case in which lack of coordination creates a situation where
postulate $\mathrm{P}_{3}$ is not satisfied. We do not mean to imply, however,
that there is anything wrong with postulate $\mathrm{P}_{3}$, or with
uncoordinated preference information. Rather, we take the moral to be that we
need postulates tailored to cases that do _not_ look like the one in Example
6, in which preference information over the direct comparisons is rendered
unusable by the overriding structural constraints of working with preference
orders.

In other words, we want the behavior of a revision operator to reflect the
preference information over the direct comparisons: however, the requirement
of transitivity means that, in the interest of consistency, we sometimes have
to add comparisons that were not explicitly chosen, and this can interfere
with the preference information over the comparisons of $\pi$. Thus, the
significance of coordination, as the following theorem shows, is that it is
needed in order for postulates $\mathrm{P}_{3-4}$ to be effective at ensuring
that choice across different types of incoming preferences is coherent.

######  Theorem 1.

If $a\colon\mathcal{C}_{V}\rightarrow\mathcal{T}_{V\times V}$ is a preference
assignment and $\triangleright^{a}$ is the $a$-induced revision operator,
then, $\triangleright^{a}$ satisfies postulates $\mathrm{P}_{3-4}$ if and only
if, for any chain $\pi\in\mathcal{C}_{V}$ and spos
$o_{1},o_{2}\in\mathcal{O}_{V}$, it holds that $o_{1}$ and $o_{2}$ are
coordinated with respect to $\pi$.

###### Proof.

(“$\Leftarrow$”) Take $o_{1},o_{2}\in\mathcal{O}_{V}$ that are coordinated
with respect to $\pi$. We will show that, for any preorder $\leq_{\pi}$ on
$\delta_{\pi}$, the $a$-induced revision operator $\triangleright^{a}$
satisfies postulates $\mathrm{P}_{3-4}$. Since $\triangleright^{a}$ satisfies
postulates $\mathrm{P}_{3-4}$ trivially if $(\pi\cup
o_{1})^{+}\in\mathcal{O}_{V}$, we look at the case when
$\kappa_{\pi}^{o_{1}}\neq\emptyset$, i.e., when $(\pi\cup o_{1})^{+}$ contains
a cycle.

For postulate $\mathrm{P}_{3}$, assume there is a comparison
$c^{\star}\in{\operatorname{add}}^{\ast}_{\leq_{\pi}}(o_{1}\cup o_{2})^{+}$
such that $c^{\star}\notin({\operatorname{add}}^{\ast}_{\leq_{\pi}}(o_{1})\cup
o_{2})^{+}$. If $c^{\star}\in(o_{1}\cup o_{2})^{+}$ then a contradiction
follows immediately. We thus have to look at the case when
$c^{\star}\notin(o_{1}\cup o_{2})^{+}$, which contains two subcases of its
own.

_Case 1_. If $c^{\star}\in\delta_{\pi}$, then by our assumption we have that
$c^{\star}\in\kappa_{\pi}^{o_{1}}$, i.e., $c^{\star}$ is involved in some
cycle with $o_{1}$. From
$c^{\star}\notin{\operatorname{add}}^{\ast}_{\leq_{\pi}}(o_{1})$ we infer that
there must be a set $\delta\subseteq\delta_{\pi}$ of direct comparisons of
$\pi$ that precede $c^{\star}$ in $\leq_{\pi}$, are added to $o_{1}$ before
it, and prevent $c^{\star}$ itself from being added. In particular, this means
that $(o_{1}\cup\delta)^{+}\in\mathcal{O}_{V}$, but
$((o_{1}\cup\delta)^{+}\cup\\{c^{\star}\\})^{+}\notin\mathcal{O}_{V}$. At the
same time, we know that
$c^{\star}\in{\operatorname{add}}^{\ast}_{\leq_{\pi}}(o_{1}\cup o_{2})^{+}$,
i.e., $c^{\star}$ can be consistently added to $(o_{1}\cup o_{2})^{+}$. Note
that this happens after all the comparisons in $\delta$, which precede it in
$\leq_{\pi}$, have been considered as well. This implies that not all of the
comparisons in $\delta$ can be added to $(o_{1}\cup o_{2})^{+}$, since if they
could, then the cycle formed with $o_{1}$, $\delta$ and $c^{\star}$ would be
reproduced here as well. If not all of the comparisons in $\delta$ can be
added to $(o_{1}\cup o_{2})^{+}$, this must be because $((o_{1}\cup
o_{2})^{+}\cup\delta)^{+}$ contains a cycle, i.e., $((o_{1}\cup
o_{2})^{+}\cup\delta)^{+}\notin\mathcal{O}_{V}$. This now contradicts the fact
that $o_{1}$ and $o_{2}$ are coordinated with respect to $\pi$.

_Case 2_. If $c^{\star}$ is not a direct comparison of $\pi$, then it is
inferred by transitivity using at least one direct comparison of $\pi$ added
previously. We apply the reasoning in Case 1 to these direct comparisons to
show that they are in $({\operatorname{add}}^{\ast}_{\leq_{\pi}}(o_{1})\cup
o_{2})^{+}$, which implies that
$c^{\star}\in({\operatorname{add}}^{\ast}_{\leq_{\pi}}(o_{1})\cup o_{2})^{+}$
as well.

For postulate $\mathrm{P}_{4}$, take
$c^{\star}\in({\operatorname{add}}^{\ast}_{\leq_{\pi}}(o_{1})\cup o_{2})^{+}$
and assume $c^{\star}\notin{\operatorname{add}}^{\ast}_{\leq_{\pi}}(o_{1}\cup
o_{2})^{+}$. As before, the non-obvious case is when
$c^{\star}\notin(o_{1}\cup o_{2})^{+}$. If $c^{\star}\in\delta_{\pi}$, then
from the assumption that
$c^{\star}\notin{\operatorname{add}}^{\ast}_{\leq_{\pi}}(o_{1}\cup o_{2})^{+}$
we conclude that there is a set $\delta\subseteq\kappa_{\pi}^{o_{1}}$ of
comparisons that precede $c^{\star}$ in $\leq_{\pi}$, are added to $(o_{1}\cup
o_{2})^{+}$ before it and, in concert with $(o_{1}\cup o_{2})^{+}$, block
$c^{\star}$ from being added, i.e., such that:

$((o_{1}\cup o_{2})^{+}\cup\delta)^{+}\in\mathcal{O}_{V},$

but $((o_{1}\cup o_{2})^{+}\cup\delta^{\prime})^{+}\notin\mathcal{O}_{V}$,
where $\delta^{\prime}=\delta\cup\\{c_{\star}\\}$. From the second to last
result we infer that $\delta$ can be added consistently to $(o_{1}\cup
o_{2})^{+}$ and, since we have that
$c^{\star}\in({\operatorname{add}}^{\ast}_{\leq_{\pi}}(o_{1})\cup o_{2})^{+}$
as well, we obtain that and $c^{\star}$ can be added consistently to $o_{1}$.
In other words, it holds that
$(o_{1}\cup\delta^{\prime})^{+}\in\mathcal{O}_{V}$. Together with the previous
result this contradicts the fact that $o_{1}$ and $o_{2}$ are coordinated with
respect to $\pi$.

The case when $c^{\star}\notin(o_{1}\cup o_{2})^{+}$ is treated analogously as
for postulate $\mathrm{P}_{3}$.

(“$\Rightarrow$”) Assume that there are $o_{1},o_{2}\in\mathcal{O}_{V}$ not
coordinated with respect to $\pi$, i.e., there exists a set
$\delta\subseteq\kappa_{\pi}^{o_{1}}$ of direct comparisons of $\pi$ that are
involved in a cycle with $o_{1}$ and are such that
$(o_{1}\cup\delta)^{+}\in\mathcal{O}_{V}$ and $((o_{1}\cup
o_{2})^{+}\cup\delta)^{+}\notin\mathcal{O}_{V}$. Additionally, we have that
neither of the comparisons in $\delta$, or their inverses, are in $(o_{1}\cup
o_{2})^{+}$. We infer that there must exist a comparison
$c^{\star}\in(\kappa_{\pi}^{o_{1}}\setminus\delta)$ that completes the cycle.
We will show that there exists a preorder $\leq_{\pi}$ such that the revision
operator induced by it does not satisfy $\mathrm{P}_{3}$. Take a preorder
$\leq_{\pi}$ on $\delta_{\pi}$ that arranges the elements of $\delta$ in a
linear order at the bottom of $\leq_{\pi}$, i.e., such that
$c_{j}<_{\pi}c_{l}$, for any $c_{j}\in\delta$ and $c_{l}\notin\delta$, and
$c^{\star}$ the maximal element in $\leq_{\pi}$, i.e.,
$c_{j}<_{\pi}c^{\star}$, for any $c_{j}\in\delta$. This implies, in
particular, that $c_{j}<_{\pi}c^{\star}$, for any $c_{j}\in\delta$.

Note, now, that
$c^{\star}\in{\operatorname{add}}_{\leq_{\pi}}^{\ast}(o_{1}\cup o_{2})^{+}$:
this is because, by assumption, not all of the comparisons in $\delta$ can be
added to $(o_{1}\cup o_{2})^{+}$, and this makes it possible for $c^{\star}$
to be added. On the other hand,
$c^{\star}\notin({\operatorname{add}}^{\ast}_{\leq_{\pi}}(o_{1})\cup
o_{2})^{+}$: this is because here we can, again by assumption, consistently
add $\delta$ to $o_{1}$ and, since $c^{\star}$ is the last in line to be
added, the inevitability of creating a cycle with $\delta$ and the rest of the
comparisons of $o_{1}$ makes it impossible to do so consistently. We obtain
that $c^{\star}\in{\operatorname{add}}_{\leq_{\pi}}^{\ast}(o_{1}\cup
o_{2})^{+}$ but
$c^{\star}\notin({\operatorname{add}}^{\ast}_{\leq_{\pi}}(o_{1})\cup
o_{2})^{+}$, i.e., postulate $\mathrm{P}_{3}$ is not satisfied. Concurrently,
there will be a comparison in $\delta$ that occurs in
$({\operatorname{add}}^{\ast}_{\leq_{\pi}}(o_{1})\cup o_{2})^{+}$ that does
not make it into ${\operatorname{add}}^{\ast}_{\leq_{\pi}}(o_{1}\cup
o_{2})^{+}$, showing that $\mathrm{P}_{4}$ is not satisfied either. ∎

Theorem 1 shows that coordination is needed in order to make sure that
postulates $\mathrm{P}_{3-4}$ work, and we will henceforth assume that $o_{1}$
and $o_{2}$ are coordinated with respect to $\pi$ whenever we apply these
postulates.

##  6 Characterizing Preference Revision as Choice Over Comparisons

We show now that the procedure described in Section 3 is characterized by the
postulates introduced in Section 4, under the restrictions established through
Theorem 1. Theorem 2 shows that the procedure in Section 3 yields preference
revision operators that satisfy postulates $\mathrm{P}_{1-4}$.

######  Theorem 2.

If $a\colon\mathcal{C}_{V}\rightarrow\mathcal{T}_{V\times V}$ is a preference
assignment, then the revision operator $\triangleright^{a}$ induced by it
satisfies postulates $\mathrm{P}_{1-4}$, for any $\pi\in\mathcal{C}_{V}$ and
$o,o_{1},o_{2}\in\mathcal{O}_{V}$ such that $o_{1}$, $o_{2}$ are coordinated
with respect to $\pi$.

###### Proof.

Satisfaction of postulates $\mathrm{P}_{1-2}$ is straightforward. For
$\mathrm{P}_{1}$, since at every step ${\operatorname{add}}^{i}_{\leq_{\pi}}$
selects some direct comparisons in $\pi$ to add to $o$, the end result
satisfies the condition for being in $\lfloor{o}\rfloor_{\pi}$. For
$\mathrm{P}_{2}$, note that $(\pi\cup
o)^{+}\subseteq{\operatorname{add}}^{0}_{\leq_{\pi}}(o)\subseteq{\operatorname{add}}_{\leq_{\pi}}^{\ast}(o)$.
Since $o_{1}$ and $o_{2}$ are assumed to be coordinated with respect to $\pi$,
satisfaction of postulates $\mathrm{P}_{3-4}$ is guaranteed by Theorem 1. ∎

For the converse, we want to show that any preference revision operator
satisfying $\mathrm{P}_{1-4}$ can be rationalized using a preference
assignment.

To that end, we will construct the preorder $\leq_{\pi}$ from binary
comparisons, but we must first figure out how to compare two direct
comparisons $({k},{k}{+}{1})$ and $({l},{l}{+}{1})$. This is done by creating
a situation where we cannot add both and hence one has to be given up. We will
use a special type of preference order to induce a choice between these
comparisons. If $\pi\in\mathcal{C}_{V}$ is a chain and
$({k},{k}{+}{1}),({l},{l}{+}{1})\in\delta_{\pi}$ are direct comparisons of
$\pi$, the _choice inducing preference $o_{k,l}$ for $({k},{k}{+}{1})$ and
$({l},{l}{+}{1})$_ is defined as $o_{k,l}=\\{({k}{+}{1},l),(l{+}1,k)\\}$. The
following example illustrates this notion.

$\pi$$1$$2$$3$$4$

$o_{1,3}$$1$$2$$3$$4$

$\pi_{1}$$1$$2$$3$$4$

$\pi_{2}$$1$$2$$3$$4$

$\pi_{3}$$1$$2$$3$$4$

Figure 4:  Revision of $\pi$ by $o_{1,3}$ forces a choice between direct
comparisons $(1,2)$ and $(3,4)$: since keeping both $(1,2)$ and $(3,4)$ is not
possible, at least one of them, potentially both, must be discarded. Depending
on the choice made, possible results are $\pi_{1}$, $\pi_{2}$ and $\pi_{3}$.

######  Example 7.

To induce a choice between direct comparisons $(1,2)$ and $(3,4)$ in Figure 4,
revise by $o_{1,3}=\\{(2,3),(4,1)\\}$. Note that effectiveness of this
maneuver hinges on the choice being confined to the direct comparisons of
$\pi$: if inferred comparisons were allowed to be part of the choice,
$o_{1,3}$ loses its power to discriminate between $(1,2)$ and $(3,4)$: if, for
instance, $(1,3)$ and $(2,4)$ are chosen, then $(2,1)$ and $(4,3)$ have to be
inferred, leaving no space for a choice between $(1,2)$ and $(3,4)$, i.e.,
$o_{1,3}$ would tell us nothing about the implicit preference between $(1,2)$
and $(3,4)$. We can also see that comparison of $(1,2)$ and $(2,3)$ is done by
revising by $(3,1)$.

Conversely, if $({k},{k}{+}{1}),({l},{l}{+}{1})\in\delta_{\pi}$ and
$\triangleright$ is a preference revision operator, then the _revealed order
$\leq^{\triangleright}_{\pi}$ between $({k},{k}{+}{1})$ and $({l},{l}{+}{1})$_
is defined as:

$({k},{k}{+}{1})\leq^{\triangleright}_{\pi}({l},{l}{+}{1})~{}\textnormal{if}~{}({l},{l}{+}{1})\notin\pi\triangleright
o_{k,l}.$

Intuitively, $({l},{l}{+}{1})$ being discarded from $\pi\triangleright
o_{k,l}$ signals that it is considered less important than $({k},{k}{+}{1})$.

The primary question at this point is whether the revealed preference relation
$\leq^{\triangleright}_{\pi}$, as defined above, is transitive. We show next
that the answer is yes.

$\pi$$i$$i{+}1$$\bullet$$j$$j{+}1$$\bullet$$k$${k}{+}{1}$$\triangleright$$o$$i$$i{+}1$$\bullet$$j$$j{+}1$$\bullet$$k$${k}{+}{1}$$=$$\pi\triangleright
o$$i$$i{+}1$$\bullet$$j$$j{+}1$$\bullet$$k$${k}{+}{1}$ Figure 5:  To show that
$\leq_{\pi}^{\triangleright}$ is transitive, we show first that
$({k},{k}{+}{1})\notin\pi\triangleright o$. Bullets indicate other potential
items in $\pi$; faded arrows indicate comparisons that may not be in
$\pi\triangleright o$, but can be consistently added to it.

######  Lemma 1.

If $\triangleright$ satisfies postulates $\mathrm{P}_{1-4}$, then the revealed
preference relation $\leq_{\pi}^{\triangleright}$ is transitive.

###### Proof.

Take $\pi\in\mathcal{C}_{V}$ and
$({i},{i}{+}{1}),({j},{j}{+}{1}),({k},{k}{+}{1})\in\delta_{\pi}$ such that
$({i},{i}{+}{1})\leq^{\triangleright}_{\pi}({j},{j}{+}{1})\leq^{\triangleright}_{\pi}({k},{k}{+}{1})$
(we can assume that $i<j<k$). To show that
$({i},{i}{+}{1})\leq^{\triangleright}_{\pi}({j},{j}{+}{1})$, take
$o\in\mathcal{O}_{V}$ that contains all direct comparisons in $\pi$ up to $k$,
except $({i},{i}{+}{1})$, $({j},{j}{+}{1})$ and $({k},{k}{+}{1})$, plus the
comparison $({k}{+}{1},i)$. In other words, $o$ is such that if
$({i},{i}{+}{1})$, $({j},{j}{+}{1})$ and $({k},{k}{+}{1})$ were added to it, a
cycle would form. The first step involves showing that
$({k},{k}{+}{1})\notin\pi\triangleright o$. To see why this is the case, note
first that, by design, not all of $({i},{i}{+}{1})$, $({j},{j}{+}{1})$ and
$({k},{k}{+}{1})$ can be in $\pi\triangleright o$, i.e., at least one of them
must be left out. We now do a case analysis to show that, either way,
$({k},{k}{+}{1})$ ends up being left out.

_Case 1_. If $({k},{k}{+}{1})\notin\pi\triangleright o$, the conclusion is
immediate.

_Case 2_. If $({j},{j}{+}{1})\notin\pi\triangleright o$, then we can safely
add $({i},{i}{+}{1})$ to $\pi\triangleright o$: this is because the inference
of the opposite comparison, i.e., $(i{+}1,i)$, can be done only by adding all
comparisons on the path from $i{+}1$ to $i$, and the absence of
$({j},{j}{+}{1})$ means this inference is blocked. Using $\mathrm{P}_{3-4}$ we
can now conclude that $((\pi\triangleright
o)\cup\\{({i},{i}{+}{1})\\})^{+}=\pi\triangleright(o\cup\\{({i},{i}{+}{1})\\})^{+}$
(see Figure 5). Note, we can separate $o\cup\\{({i},{i}{+}{1})\\}$ into
$o_{j,k}=\\{(k{+}1,j),(j{+}1,k)\\}$ and all the comparisons on the path from
$k{+}1$ to $j$, plus the comparisons on the path from $j{+}1$ to $k$. Call
this latter preference $o^{\prime}$. We thus have that
$(o\cup\\{({i},{i}{+}{1})\\})^{+}=(o_{j,k}\cup o^{\prime})^{+}$ and, applying
$\mathrm{P}_{3}$, we obtain that:

$\pi\triangleright(o\cup\\{({i},{i}{+}{1})\\})^{+}=\pi\triangleright(o_{j,k}\cup
o^{\prime})^{+}\subseteq((\pi\triangleright o_{j,k})\cup o^{\prime})^{+}.$

Since, by definition, $({k},{k}{+}{1})\notin\pi\triangleright o_{j,k}$ and
$({k},{k}{+}{1})\notin o^{\prime}$, It follows that:

$({k},{k}{+}{1})\notin\pi\triangleright(o\cup\\{({i},{i}{+}{1})\\})^{+},$

then:

$({k},{k}{+}{1})\notin((\pi\triangleright o)\cup\\{({i},{i}{+}{1})\\})^{+},$

and, finally, that:

$({k},{k}{+}{1})\notin\pi\triangleright o.$

_Case 3_. If $({i},{i}{+}{1})\notin\pi\triangleright o$, then we can safely
add $({k},{k}{+}{1})$ to $\pi\triangleright o$ and, by reasoning similar to
above, show that $({j},{j}{+}{1})\notin\pi\triangleright o$. Here we invoke
Case 2.

With the fact that $({k},{k}{+}{1})\notin\pi\triangleright o$ in hand, we can
add $({j},{j}{+}{1})$ to $\pi\triangleright o$ (by reasoning similar to
above), because the path from $j{+1}$ to $j$ in $\pi\triangleright o$ is
blocked by the absence of $({k},{k}{+}{1})$. Using postulates
$\mathrm{P}_{3-4}$, we conclude that:

$\displaystyle((\pi\triangleright o)\cup\\{({j},{j}{+}{1})\\})^{+}$
$\displaystyle=\pi\triangleright(o\cup\\{({j},{j}{+}{1})\\})^{+}$
$\displaystyle=\pi\triangleright(\\{(i{+}1,\dots,k),(k{+1},i)\\})^{+}$
$\displaystyle=((\pi\triangleright o_{i,k})\cup\\{(i{+}1,\dots,k)\\})^{+}.$

Since $({k},{k}{+}{1})\notin((\pi\triangleright
o)\cup\\{({j},{j}{+}{1})\\})^{+}$, we conclude that
$({k},{k}{+}{1})\notin\pi\triangleright o_{i,k}$, which implies that
$({i},{i}{+}{1})\leq^{\triangleright}_{\pi}({k},{k}{+}{1})$. ∎

Lemma 1 is crucial for the following representation result, as it indicates
that we can identify the revealed preference relation with the underlying
preference over direct comparisons of $\pi$ driving revision.

######  Theorem 3.

If $\triangleright$ is a revision operator satisfying postulates
$\mathrm{P}_{1-4}$, for any $\pi\in\mathcal{C}_{V}$ and
$o,o_{1},o_{2}\in\mathcal{O}_{V}$ such that $o_{1}$, $o_{2}$ are coordinated
with respect to $\pi$, then there exists a preference assignment $a$ such that
$\triangleright$ is the $a$-induced revision operator.

###### Proof.

For any $\pi\in\mathcal{C}_{V}$, take $\leq_{\pi}$ to be the revealed
preference relation $\leq^{\triangleright}_{\pi}$. By Lemma 1, we know that
$\leq_{\pi}$ is transitive, so the only thing left to is show is that
$\pi\triangleright o={\operatorname{add}}^{\ast}_{\leq_{\pi}}(o)$. We do this
in two steps.

(“$\subseteq$”) For one direction, Take $(j,k)\in\pi\triangleright o$ and
suppose $(j,k)\notin{\operatorname{add}}^{\ast}_{\leq_{\pi}}(o)$. Clearly, it
cannot be the case that $(j,k)\in o$, so we conclude that $(j,k)$ is either a
direct comparison of $\pi$, or is inferred by transitivity using direct
comparisons in $\pi$ and $o$.

_Case 1_. If $(j,k)\in\delta_{\pi}$, then we can write $(j,k)$ as
$({j},{j}{+}{1})$, Suppose that $({j},{j}{+}{1})$ is on level $i$ of
$\delta_{\pi}$: this means that if $({j},{j}{+}{1})$ does not get added to
${\operatorname{add}}^{\ast}_{\leq_{\pi}}(o)$ at step $i$, then, since it
cannot be inferred by transitivity, it does not get added at all. The fact
that $({j},{j}{+}{1})\notin{\operatorname{add}}^{\ast}_{\leq_{\pi}}(o)$ thus
means that $({j},{j}{+}{1})$ forms a cycle with some comparisons in $o$ and
comparisons in $\pi$ on levels $l\leq i$. First, note that $({j},{j}{+}{1})$
cannot form a cycle with elements of $o$ only, since that would imply that
$(j{+}1,j)\in o$ and that would exclude the possibility that
$({j},{j}{+}{1})\in\pi\triangleright o$. Thus, at least one other comparison
in the cycle must come from $\pi$. We can state, now, that, since
$(j{+}1,j)\in\pi\triangleright o$, then at least one of these comparisons must
be absent in $\pi\triangleright o$, i.e., there exists a direct comparison
$({k},{k}{+}{1})\in\delta_{\pi}$ such that
$({k},{k}{+}{1})\in\mathit{lvl}^{j}_{\leq_{\pi}}(\pi)$, for some $j\leq i$,
$({k},{k}{+}{1})\notin\pi\triangleright o$ and $({j},{j}{+}{1})$,
$({k},{k}{+}{1})$, plus some other comparisons in $o$ and $\pi$ form a cycle.
This means that it is safe to add $o^{\prime}$ to $\pi\triangleright o$, where
$o^{\prime}$ contains all comparisons on the path from ${k}{+}{1}$ to $j$,
plus the comparison on the path from $j{+}1$ to $k$. We can rewrite
$o^{\prime}$ by separating out $({k}{+}{1},j)$ and $(j{+}1,k)$, i.e.,
$o^{\prime}=(o_{j,k}\cup o^{\prime})^{+}$. Applying postulates
$\mathrm{P}_{3-4}$, we now get that

$\displaystyle((\pi\triangleright o)\cup o^{\prime})^{+}$
$\displaystyle=\pi\triangleright(o\cup o^{\prime})^{+}$
$\displaystyle=\pi\triangleright(o_{j,k}\cup o^{\prime})^{+}$
$\displaystyle\subseteq((\pi\triangleright o_{j,k})\cup o^{\prime})^{+}.$

Using the assumption that $({j},{j}{+}{1})\in\pi\triangleright o$ and the fact
that $({j},{j}{+}{1})\notin{o^{\prime}}$, we can thus infer that
$({j},{j}{+}{1})\in\pi\triangleright o_{j,k}$. This, in turn, implies that
$({j},{j}{+}{1})<_{\pi}({k},{k}{+}{1})$ and hence $({j},{j}{+}{1})$ belongs to
a lower level of $\delta_{\pi}$ than $({k},{k}{+}{1})$: but this contradicts
the conclusion drawn earlier that $({k},{k}{+}{1})$ belongs to a level $l\leq
i$, where $i$ is the level of $({j},{j}{+}{1})$.

_Case 2_. If $(j,k)$ is not a direct comparison of $\pi$, then it is inferred
from some direct comparisons of $\pi$ that end up in $\pi\triangleright o$,
together with comparisons in $o$. We can now apply the reasoning from Case 1
to the direct comparisons of $\pi$ that go into inferring $(j,k)$, to show
that they must be in ${\operatorname{add}}^{\ast}_{\leq_{\pi}}(o)$. This, in
turn, implies that $(j,k)$ will be in
${\operatorname{add}}^{\ast}_{\leq_{\pi}}(o)$ as well.

The reasoning for the other direction is similar. ∎

Theorems 2 and 3 describe preference revision operators that rely on total
preorders $\leq_{\pi}$ on $\delta_{\pi}$, where a tie between two direct
comparisons means that if they cannot both be added, then they are both passed
over. We can eliminate this indeciseveness by using _linear_ orders on
$\delta_{\pi}$ instead of preorders: this ensures that any two direct
comparisons of $\pi$ can be clearly ranked with respect to each other, and
that a revision operator is always in a position to choose among them. On the
postulate site, linear orders can be characterized by tightening the notion of
a $\pi$-completion and, with it, postulate $\mathrm{P}_{1}$. Thus, a _decisive
$\pi$-completion of $o$_ is defined as:

$\lfloor{o}\rfloor^{\mathsf{D}}_{\pi}=\\{(o\cup\delta)^{+}\in\mathcal{O}_{V}\mid\emptyset\subset\delta\subseteq\delta_{\pi}\\}.$

Changing the format of the revision output requires changing the postulate
that speaks about this format as well. The decisive version of
$\mathrm{P}_{1}$ is then written, for any $\pi\in\mathcal{C}_{V}$ and
$o\in\mathcal{O}_{V}$, as:

($\mathrm{P}_{\mathsf{D}}$)

$\pi\triangleright o\in\lfloor{o}\rfloor^{\mathsf{D}}_{\pi}$.

A _decisive preference assignment $a$_ is a function
$a\colon\mathcal{C}_{V}\rightarrow\mathcal{C}_{V\times V}$ mapping every
$\pi\in\mathcal{C}_{V}$ to a linear preorder $<_{\pi}$ on $\delta_{\pi}$. We
can now show the following result.

######  Theorem 4.

A revision operator $\triangleright$ satisfies postulates
$\mathrm{P}_{\mathsf{D}}$ and $\mathrm{P}_{2-4}$ if and only if there exists a
decisive preference assignment $a$ such that, for any $\pi\in\mathcal{C}_{V}$
and $o,o_{1},o_{2}\in\mathcal{O}_{V}$ such that $o_{1}$, $o_{2}$ are
coordinated with respect to $\pi$, $\triangleright$ is the $a$-induced
preference revision operator.

###### Proof.

The proofs for Theorems 2 and 3 work here with minimal adjustments. Note that
when choosing between two direct comparisons, postulate
$\mathrm{P}_{\mathsf{D}}$ does not allow $\triangleright$ to be indifferent
anymore. This means that the revealed preference relation on $\delta_{\pi}$
ends up being linear. ∎

We can see, thus, that what seems like a weakness in the original formulation
of the problem, i.e., the mismatch in type between the input (a chain) and the
output (an spo) of a revision operator, can be resolved by requiring the
ranking on comparisons to be strict. However, in the present setup this
amounts to a less general result, which is why we presented our work in this
manner.

##  7 Concrete Preference Revision Operators

Theorems 2, 3 and 4 articulate an important lesson: preference revision
performed in a principled manner, i.e., in accordance with $\mathrm{P}_{1-4}$
or $\mathrm{P}_{\mathsf{D}}$ and $\mathrm{P}_{2-4}$, involves having
preferences over comparisons. Thus, to obtain concrete operators one must look
at ways of ranking the comparisons in a preference $\pi$. We sketch here two
simple solutions, as proof of concept.

The _trivial assignment $a^{\mathrm{t}}$_ is defined by taking:

$({i},{i}{+}{1})\approx^{\mathrm{t}}_{\pi}({j},{j}{+}{1}),$

while the _lexicographic assignment $a^{\mathrm{lex}}$_ is defined by taking:

$({i},{i}{+}{1})<^{\mathrm{lex}}_{\pi}({j},{j}{+}{1}),$

if $i<j$, for any $\pi\in\mathcal{C}_{V}$ and
$({i},{i}{+}{1}),({j},{j}{+}{1})\in\pi$. Intuitively, the trivial assignment
makes all direct comparisons of $\pi$ equally desirable, while the
lexicographic assignment orders them in lexicographic order.

These assignments induce the _trivial_ and _lexicographic_ operators
$\triangleright^{\mathrm{t}}$ and $\triangleright^{\mathrm{lex}}$,
respectively. It is straightforward to see that $\leq_{\pi}^{\mathrm{t}}$ is a
preorder and $<^{\mathrm{lex}}_{\pi}$ is a linear order, prompting the
following result.

######  Proposition 1.

The operator $\triangleright^{\mathrm{t}}$ satisfies postulates
$\mathrm{P}_{1-4}$. The operator $\triangleright^{\mathrm{lex}}$ satisfies
postulates $\mathrm{P}_{\mathsf{D}}$ and $\mathrm{P}_{2-4}$.

The following example illustrates that the two operators can give different
results on the same input.

######  Example 8.

For $\pi$ and $o$ as in Example 1, the trivial operator ranks all direct
comparisons of $\pi$, i.e., $(1,2)$ and $(2,3)$, equally, and hence either
adds all or none of them to $o$. Since adding both leads to a cycle, it ends
up adding none and hence $\pi\triangleright^{\mathrm{t}}o=(3,1)$.

The lexicographic assignment ranks $(1,2)$ as better than $(2,3)$, and hence
adds $(1,2)$ after which it runs out of options, i.e.,
$\pi\triangleright^{\mathrm{lex}}o=(3,1,2)$.

##  8 Conclusion

We have presented a model of preference change according to which revising a
preference $\pi$ goes hand in hand with having preferences over the
comparisons of $\pi$, thereby providing a rigorous formal treatment to
intuitions found elsewhere in the literature (?; ?). Interestingly, the
postulates describing preference revision are analogous to existing postulates
offered for propositional enforcement (?), an operation used to model changes
in Abstract Argumentation Frameworks (AFs) (?).

Our treatment unearthed interesting aspects of preference revision, such as
the issue of coordination between successive instances of new preference
information (Section 4) and the non-obvious solution to the question of how to
rank two comparisons relative to each other (Section 6). These aspects are
taken for granted in regular propositional revision, but prove key to
successful application of revision to the more specialized context of
transitive relations on a set of items, i.e., preference orders. In this
respect, preference revision is akin to revision for fragments of
propositional logic (?; ?), and raises the possibility of exporting this
approach to other formalisms in this family. The addition procedure in
particular, lends itself to application in other formalisms by slight tweaking
of the acceptance condition, and could thus supply some interesting lessons
for revision in general, in particular to revision-like operators for
specialized formalisms, such as that of AFs, mentioned above.

There is also ample space for future work with respect to the present
framework itself. To facilitate exposition of the main ideas we imposed
certain restrictions on the primary notions. Lifting these restrictions would
yield broader results that would potentially cover more ground and apply to a
more diverse set of inputs. We can consider, for instance, revising strict
partial orders in general (not just linear orders), and using rankings that
involve all comparisons of the initial preference order (not just the direct
ones). As the space of possibilities becomes larger, the choice problems on
this space become increasingly more complex as well. Finding the right
conditions under which the choice mechanism corresponds to a set of appealing
postulates requires a delicate balance of many elements, and holds the promise
for interesting results.

## References

  * Alchourrón, Gärdenfors, and Makinson 1985 Alchourrón, C. E.; Gärdenfors, P.; and Makinson, D.  1985\.  On the Logic of Theory Change: Partial Meet Contraction and Revision Functions.  The Journal of Symbolic Logic 50(2):510–530.
  * Benthem and Liu 2014 Benthem, J., and Liu, F.  2014\.  Deontic Logic and Preference Change.  IfCoLog Journal of Logics and their Applications 1(2):1–46.
  * Boutilier et al. 2004 Boutilier, C.; Brafman, R. I.; Domshlak, C.; Hoos, H. H.; and Poole, D.  2004\.  CP-nets: A Tool for Representing and Reasoning with Conditional Ceteris Paribus Preference Statements.  Journal of Artificial Intelligence Research (JAIR) 21:135–191.
  * Bradley 2007 Bradley, R.  2007\.  The kinematics of belief and desire.  Synthese 156(3):513–535.
  * Cadilhac et al. 2015 Cadilhac, A.; Asher, N.; Lascarides, A.; and Benamara, F.  2015\.  Preference change.  Journal of Logic, Language and Information 24(3):267–288.
  * Chomicki and Song 2005 Chomicki, J., and Song, J.  2005\.  Monotonic and Nonmonotonic Preference Revision.  In Proc. IJCAI 2005 Multidisciplinary Workshop on Advances in Preference Handling.
  * Chomicki 2003 Chomicki, J.  2003\.  Preference formulas in relational queries.  ACM Trans. Database Syst. 28(4):427–466.
  * Creignou et al. 2018 Creignou, N.; Haret, A.; Papini, O.; and Woltran, S.  2018\.  Belief Update in the Horn Fragment.  In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI 2018), 1781–1787.
  * Delgrande, Peppas, and Woltran 2018 Delgrande, J. P.; Peppas, P.; and Woltran, S.  2018\.  General Belief Revision.  Journal of the ACM (JACM) 65(5):29:1–29:34.
  * Dell’Acqua and Pereira 2005 Dell’Acqua, P., and Pereira, L. M.  2005\.  Preference Revision Via Declarative Debugging.  In Portuguese Conference on Artificial Intelligence, 18–28.  Springer.
  * Domshlak et al. 2011 Domshlak, C.; Hüllermeier, E.; Kaci, S.; and Prade, H.  2011\.  Preferences in AI: An Overview.  Artificial Intelligence 175(7-8):1037–1052.
  * Dung 1995 Dung, P. M.  1995\.  On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming and n-Person Games.  Artif. Intell. 77(2):321–358.
  * Fermé and Hansson 2018 Fermé, E. L., and Hansson, S. O.  2018\.  Belief Change: Introduction and Overview.  Springer Briefs in Intelligent Systems. Springer.
  * Frankfurt 1988 Frankfurt, H. G.  1988\.  Freedom of the Will and the Concept of a Person.  In What is a person? Springer.  127–144.
  * Freund 2004 Freund, M.  2004\.  On the revision of preferences and rational inference processes.  Artificial Intelligence 152(1):105–137.
  * Grüne-Yanoff and Hansson 2009a Grüne-Yanoff, T., and Hansson, S. O., eds.  2009a.  Preference Change: Approaches from Philosophy, Economics and Psychology, volume 42 of Theory and Decision Library A.  Springer.
  * Grüne-Yanoff and Hansson 2009b Grüne-Yanoff, T., and Hansson, S. O.  2009b.  From Belief Revision to Preference Change.  In Preference Change: Approaches from Philosophy, Economics and Psychology. Springer.  159–184.
  * Grüne-Yanoff 2013 Grüne-Yanoff, T.  2013\.  Preference change and conservatism: comparing the bayesian and the AGM models of preference revision.  Synthese 190(14):2623–2641.
  * Hansson 1995 Hansson, S. O.  1995\.  Changes in preference.  Theory and Decision 38(1):1–28.
  * Hansson 2017 Hansson, S. O.  2017\.  Logic of Belief Revision.  In Zalta, E. N., ed., The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University, winter 2017 edition.
  * Haret, Wallner, and Woltran 2018 Haret, A.; Wallner, J. P.; and Woltran, S.  2018\.  Two Sides of the Same Coin: Belief Revision and Enforcing Arguments.  In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI 2018), 1854–1860.
  * Harsanyi 1955 Harsanyi, J. C.  1955\.  Cardinal Welfare, Individualistic Ethics, and Interpersonal Comparisons of Utility.  Journal of Political Economy 63(4):309–321.
  * Jeffrey 1974 Jeffrey, R. C.  1974\.  Preference among preferences.  Journal of Philosophy 71(13):377–391.
  * Katsuno and Mendelzon 1992 Katsuno, H., and Mendelzon, A. O.  1992\.  Propositional Knowledge Base Revision and Minimal Change.  Artificial Intelligence 52(3):263–294.
  * Lang and van der Torre 2008 Lang, J., and van der Torre, L. W. N.  2008\.  Preference Change Triggered by Belief Change: A Principled Approach.  In Proceedings of the 8th International Conference on Logic and the Foundations of Game and Decision Theory (LOFT 8), 86–111.
  * Liu 2011 Liu, F.  2011\.  Reasoning About Preference Dynamics, volume 354 of Synthese Library.  Springer.
  * Ma, Benferhat, and Liu 2012 Ma, J.; Benferhat, S.; and Liu, W.  2012\.  Revising Partial Pre-Orders with Partial Pre-Orders: A Unit-Based Revision Framework.  In Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning (KR 2012), 633–637.
  * Nozick 1994 Nozick, R.  1994\.  The Nature of Rationality.  Princeton University Press.
  * Pigozzi, Tsoukiàs, and Viappiani 2016 Pigozzi, G.; Tsoukiàs, A.; and Viappiani, P.  2016\.  Preferences in artificial intelligence.  Annals of Mathematics and Artificial Intelligence 77(3-4):361–401.
  * Rossi and Mattei 2019 Rossi, F., and Mattei, N.  2019\.  Building Ethically Bounded AI.  In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI 2019), 9785–9789.
  * Rossi, Venable, and Walsh 2011 Rossi, F.; Venable, K. B.; and Walsh, T.  2011\.  A Short Introduction to Preferences: Between Artificial Intelligence and Social Choice.  Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan & Claypool Publishers.
  * Russell 2019 Russell, S.  2019\.  Human Compatible: Artificial Intelligence and the Problem of Control.  Penguin.
  * Sen 1977 Sen, A. K.  1977\.  Rational Fools: A Critique of the Behavioral Foundations of Economic Theory.  Philosophy & Public Affairs 317–344.