{'fraction_non_alphanumeric': 0.04677787644297856, 'fraction_numerical': 0.015317772421666879, 'mean_word_length': 3.795893536121673, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 1, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
List-rationalizable choice

A choice function is list rational(izable) if there is a fixed list such that for each choice set, successive comparison of the alternatives by following the list retrieves the chosen alternative. We extend the formulation of list rationality to stochastic choice setup. We say two alternatives are related if the stochastic path independence condition is violated between these alternatives. We show that a random choice function is list rational if and only if this relation is acyclic. Our characterization for deterministic choice functions follows as a corollary. By using this characterization, we relate list rationality to two-stage choice procedures.


Introduction
We analyze a boundedly rational choice procedure that we call list-rational(izable) choice. A list-rational decision maker chooses from a set of alternatives as follows. First, he orders the alternatives according to a list. Then he compares the first and second alternatives in the list and records the winner, which is then compared to the next alternative. This process of carrying the current winner to the next round continues until the last alternative in the list is compared to the winner from the previous round. The winner of the last round is regarded as the choice made from the entire set. A list-rational decision maker orders the entire set of alternatives according to a single list, and follows the restriction of this list to make a choice from each subset.
To motivate list rationality, consider a decision maker who learns the details of each alternative sequentially. Suppose that this decision maker is unable to recall all the encountered alternatives, but has a single memory cell used to store an alternative to choose whenever the process is interrupted. For such a decision maker, list rationality is a natural procedure. The decision maker orders the alternatives in the form of a list and stores the first alternative in his memory cell. Then whenever he is faced with a new alternative, he decides whether to keep the stored alternative or to replace it with the Kemal Yildiz: kemal.yildiz@bilkent.edu.tr new one. In the same vein, Salant (2003) argues that list rationality is the unique choice procedure that uses a single memory cell.
The experimental literature also discusses why decision makers adopt procedures similar to list rationality. For example, Shugan (1980) proposes a formulation based on cost of thinking, and argues that the lowest choice cost would be achieved by first choosing from among a pair of alternatives with low thinking cost and then comparing the chosen alternative to the next. Similarly, Russo and Rosen (1975) argue that decision makers follow list rationality 1 to minimize the short-term memory load. 2 In a rather recent study, Liu and Simonson (2005) argue that decision makers guided through listrational choice procedure are more confident in their choices compared to nonguided decision makers. 3 In this paper, we formally model and analyze the list-rational choice procedure. The idea that list-following behavior can be modeled as a choice procedure is not new. Salant and Rubinstein (2006) analyze a choice model in which decision makers choose from lists, rather than from choice sets. Put differently, the list is assumed to be exogenous and is considered as a frame (Salant and Rubinstein 2008) for the associated choice problem. In contrast, our list-rational decision maker chooses from choice sets in a way that the choice behavior is driven by a list that is unobserved by outsiders. To model the list as a subjective part of the choice procedure is of interest, since even if alternatives are exogenously presented in a particular order, due to other cognitive limitations, a decision maker can follow a different virtual ordering. For example, a decision maker can start the comparison from an alternative that he considers as a reference point (Tversky and Kahneman 1991), can group similar items together (Russo and Rosen 1975), or can form the list to minimize the total cost of thinking (Shugan 1980).
In our analysis, we provide choice theoretical foundations for list rationality both in deterministic and stochastic choice setups. To characterize list rationality, the main task is to identify the unobserved list followed by the decision maker from his observed choice behavior. We can identify the unobserved list if we can infer that an alternative unambiguously follows 4 another alternative in the decision maker's considerations. Consider the stochastic choice setup in which the decision maker's choice reveals a probability measure over each choice set. In this setting, we say an alternative x is revealed-to-follow another alternative y if there is a choice set S that contains x but not 1 List rationality is referred to as standard revision and is described on page 267 of Russo and Rosen (1975).
2 See Russo and Rosen (1975, p. 272). 3 Subjects are asked to make a choice from a set of 10 products according to two procedures. In the first procedure, subjects were presented all 10 product offers together and asked to indicate the one they are most interested in. Then they were asked whether they wanted to buy the selected product. In the second procedure, subjects were asked to make a choice from the same set of 10 products according to list rationality by following an exogenously specified list. Once the last item in the list was considered, participants were asked to decide whether they wanted to buy the selected product. The authors observed that the subjects in the latter treatment are more likely to buy their selected product (45%) than those in the former treatment (34%). 4 That is, for a given pair of alternatives, in each list that is consistent with the observed choice behavior, the first one follows the second.
y, such that the choice probability of x from S ∪ {y} is different than the choice probability of x from S multiplied by the choice probability of x when compared to y. We show that a decision maker is list rational if and only if the revealed-to-follow relation is acyclic. 5 As a corollary, we obtain the characterization for the deterministic case. Moreover, the revealed-to-follow relation induces all possible lists that are consistent with the observed choices of the decision maker. Finally, we relate list rationality to two-stage choice procedures analyzed extensively in the literature. 6 In particular, we consider the shortlisting procedure Mariotti 2007, Au andKawai 2011). We provide characterizations of shortlisting and list rationality based on the acyclicity of an underlying binary relation. We believe that comparing these two binary relations facilitates comparisons between these choice procedures.

Relation to the literature
Our model belongs to the growing body of research in boundedly rational choice theory. This literature seeks to explain choice behavior that cannot be explained by the maximization of a single preference relation. In most of these models, a choice procedure is proposed that contains not only the decision maker's (welfare) preference, but also a behavior pattern for using this preference. Several of these models are consistent with a well known choice anomaly, having binary choice cycles. 7 Since a list-rational decision maker can compare pairs of alternatives in any arbitrary way, he can exhibit any binary choice cycle. Compared with these models, the set of list-rational choice functions is nested by the set of choice functions analyzed by Xu and Zhou (2007), Apesteguia and Ballester (2013), Masatlioglu et al. (2012), and is nonnested with the set of choice functions analyzed by Mariotti (2007, 2012) and Cherepanov et al. (2013). Horan (2011) analyzes an extension of choice by game trees (Xu and Zhou 2007) in which players choose actions by using binary relations that can be intransitive. A particular case of this model 8 is observationally equivalent to list rationality, and a different characterization of list rationality in the deterministic choice setup follows from the general characterization provided in this paper. This characterization is built on a partitional weakening of path independence based on choices from three-element sets. In contrast, both in deterministic and stochastic choice setups, we derive our characterization and identification results from our revealed-to-follow relation. Apesteguia et al. (2014) axiomatically characterize equilibrium choices of two agenda-voting institutions in which the agenda to be followed is unobservable. Among these, the amendment (Anglo-American) procedure is behaviorally similar to list rationality. The main difference is that while a choice function is defined only over all 5 That is, for each set of alternatives {x 1 x n }, if for each i ∈ {1 n − 1}, x i is revealed-to-follow x i+1 , then we cannot have x n revealed-to-follow x 1 . 6 For example, Manzini and Mariotti (2007), Lleras et al. (2010), Tyson (2008), and Manzini et al. (2013). 7 That is, an alternative x is chosen when compared to another alternative y, and y is chosen when compared to a third alternative z, but z is chosen when compared to x. For experimental findings, see Tversky (1969), Loomes et al. (1991). 8 Similar to our Example 2. possible subsets of alternatives, a voting rule is additionally defined over the preferences of the voters. Salant and Rubinstein (2006) and Salant (2011) discuss variants of list-rational choice procedure as examples when lists are observable. Apesteguia and Ballester (2013) investigate choice functions that are sequentially rationalizable and show that list-rational choice functions belong to this family.

List-rational choice
Given a finite alternative set X, any nonempty subset S is called a choice set. Let denote the collection of all choice sets. A choice function c specifies the observed choice c(S) from the choice set S; that is, a choice function c : → X such that for each S ∈ , c(S) ∈ S. A list-rational choice procedure has two primitives: a list and an asymmetric binary relation used to compare pairs of alternatives. A list f is an ordering-a complete, transitive, and antisymmetric binary relation-on X such that for each x y ∈ X, we write x f y if and only if x follows y in the considerations of the decision maker. A list-rational decision maker who orders the alternatives according to f, chooses from a choice set as follows: First, he compares the first and second alternatives. Then he compares the current choice to the third alternative in the list. This process of carrying the current choice to the next round continues until the end of the list is reached. In the final round, the decision maker chooses between the choice from the previous round and the last alternative. This final binary choice determines the alternative chosen from the entire set. Next, to get a formal description of this procedure, we provide a recursive formulation for list rationality. Definition 1. A choice function c is list-rational if there exists a list f such that for each S ∈ , if x is the last alternative in S according to f, then We illustrate list-rational choice behavior by presenting two choice procedures. Although these procedures have different formulations, we argue that each can be represented as a list-rational choice procedure.
Example 1 (Rational choice). The decision maker has a preference relation 9 over the alternative set, and chooses the -best alternative from each choice set. Since is transitive, for any list f followed by the decision maker, from each choice set S, the same alternative, max(S ), is chosen. ♦ Example 2 (Choice by a binary game tree). The primitive of this choice procedure is an extensive form game G in which there are two players and a binary game tree such that each alternative appears as an end node of the tree only once. Each player has a preference relation over the alternative set. 10 At each decision node, players successively decide whether to stop or to continue as to maximize their preferences. Choosing to stop directly leads to one of the terminal nodes in which the associated alternative is chosen. For each choice set S, consider the reduced game G|S derived from G by retaining only the paths that lead to terminal nodes having outcomes in S. From each choice set S, the decision maker chooses the subgame perfect Nash equilibrium outcome of the reduced game G|S. Each choice function that can be rationalized via such an extensive form game is list-rational. To see this, list the alternatives according to the reverse order of appearance in the game tree. Next, note that for each choice set, the alternative that is chosen according to Definition 1 is the one that is obtained by applying backward induction. Hence the equivalence follows. ♦

List-rational random choice
Instead of observing a decision maker's choice from each set only once, suppose that we observe repeated choice behavior of the decision maker. Suppose the decision maker does not always choose the same alternative from each set, but his choice rather reveals consistent frequencies. For each choice set S and alternative x, let C x (S) be the frequency with which the decision maker chooses x from the set S. Thus, we obtain a random choice function (r.c.f.) C that assigns each choice set S a probability measure over S. List-rational random choice procedure has two primitives: a deterministic list and a random binary relation used to compare pairs of alternatives. The list f followed by a list-rational decision maker is deterministic and, as before, gives an ordering of the alternatives. However, the decision maker's binary comparisons can be random. In contrast, Salant and Rubinstein (2006) formulate a general model in which the list can be random. As they put it, if the list is exogenously given in the description of a choice problem, then it may be natural to consider an underlying random process that transforms sets into lists. However, we consider the list as a subjective part of the choice procedure. Moreover, for list rationality, if the comparison between two alternatives is deterministic, then among them the same alternative is chosen irrespective of the followed list. We find this property particularly restrictive for random choice functions. However, as an extension of random utility models (Block and Marschak 1960), one can think of a model in which both the list and the binary comparisons are random. Next, we formulate the list-rational random choice procedure.
Definition 2. An r.c.f. C is list-rational if there exists a list f such that for each S ∈ , if x is the last alternative in S according to f, then 10 Each player can be interpreted as a different self of a single decision maker that concentrates on a particular aspect of the alternative set. and for each y ∈ S \ x, C y (S) = C y (S \ x) · C y (x y) A deterministic choice function can be thought of as a random choice function such that from each choice set an alternative is chosen with probability 1. For deterministic choice functions, the above formulation boils down to the list-rational choice procedure. To see this, suppose x is the last alternative in choice set S according to list f and z is chosen from S \ x. If x is chosen from S, then it follows from (1) that C x (x z) = 1; thus x = c(c(S \ x) x). If another alternative y is chosen from S, then it follows from (2) that z = y and C y (x y) = 1; thus y = c(c(S \ x) x).
A random choice function satisfies (strong) monotonicity if the choice probability of an existing alternative necessarily decreases in response to the addition of a new alternative. Most of the random choice models examined in the literature, such as the Luce rule (Luce 1959), satisfy monotonicity. A list-rational decision maker may violate monotonicity since list-following choice behavior exhibits a recency effect 11 as our next example illustrates.
Example 3. Let X = {x 1 x 2 y}. Suppose that x 1 and x 2 are similar alternatives, for example, different recordings of the same Beethoven symphony, while y is a distinct alternative, for example, a Debussy suite. Suppose between any pair of these three recordings the decision maker chooses with equal probabilities. Now, it seems natural to choose from the set {x 1 x 2 y} with probabilities 0 25, 0 25, and 0 5, respectively. 12 Suppose our list-rational decision maker follows the list f where y f x 2 f x 1 . Now, x 1 wins the comparison to x 2 with 0 5 probability. If this is the case, then x 1 is compared to y, and x 1 wins this comparison with another 0 5 probability. Hence, x 1 is chosen from the entire set with 0 25 probability. Similarly, x 2 is chosen with 0 25 probability. Since y beats the winner of the previous round regardless of whether it is x 1 or x 2 with 0 5 probability, y is chosen with 0 5 probability. Hence, we obtain C x 1 (S) = C x 2 (S) = 0 25, and C y (S) = 0 5. ♦

Results
First, we provide a characterization of list rationality in the stochastic choice setup. The characterization for the deterministic setup follows as a corollary. To characterize list rationality, the main task is to identify when we can conclude that x unambiguously follows y in the considerations of a list-rational decision maker from the random choice 11 A recency effect emerges when people consider the last alternative in a list as more favorable than the others. Evidence for the recency effect has been found in contests where competitors are evaluated one after another; for example, see Bruine de Bruin (2006) and Glejser and Heyndels (2001). 12 Debreu (1960) proposes this example to highlight a shortcoming of the well known Luce rule. This probability assignment is incompatible with the Luce rule, since the existence of two very similar items outweighs the total choice probability of these items. This phenomenon is later referred to as the duplicates effect. Although list-rational random choice fails to accommodate the general duplicates effect, for Debreu's example, we observe that the natural choice behavior can be retrieved by following a particular list. See, for example, Gul et al. (2014) for a model that accommodates the general duplicates effect.
data. To define the revealed-to-follow relation that paves the way to this end, first we formulate a stochastic version of the path independence condition (Plott 1973) for deterministic choice functions. 13 Stochastic Path Independence (SPI): An r.c.f. C satisfies SPI if for each S ∈ such that x ∈ S and y / ∈ S, Equivalently, C satisfies SPI if for each S ∈ and each S 1 S 2 ⊂ S such that S 1 ∪ S 2 = S and S 1 ∩ S 2 = {x}, we have C x (S) = C x (S 1 ) · C x (S 2 ).
Definition 3. For a given r.c.f. C and for each distinct x y ∈ X, x is revealed-to-follow y, denoted by x f C y, if SPI is violated between x and y, i.e., for some S ∈ such that x ∈ S and y / ∈ S, we have

Proposition 1. An r.c.f. C is list-rational if and only if f C is acyclic. Moreover, the identified list is unique up to the completions of the transitive closure of f C .
Proof. Only-if part: Suppose C is a list-rational r.c.f. described by f. We will show that f C is acyclic. To see this, first we show that for each x y ∈ X, if x f C y, then x f y. We proceed by contradiction and suppose that y f x. Since x f C y, SPI should be violated between x and y. We will obtain the contradiction by showing that this is impossible. For each S ∈ such that x ∈ S and y / ∈ S, let S = S ∪ {y}. If y is the last alternative in S according to f, then by (2) of the list-rationality definition, we get C x (S ) = C x (S \ y) · C x (x y). It directly follows that SPI holds between x and y.
Next, suppose y is the last but one alternative in S according to f. Let z be the last alternative in S . By (2) we have C x (S ) = C x (S \ z) · C x (x z). Now consider the set S \ z. Since y is the last alternative in this set, by (2) we have C x (S \ z) = C x (S \{z y}) · C x (x y). Now substitute C x (S \ z) in the previous equation. Next consider the set S \ {y}. Since z is the last alternative in this set, by (2) we have C x (S \ y) = C x (S \ {z y}) · C x (x z). It follows that C x (S ) = C x (S \ y) · C x (x y); thus SPI holds between x and y. By proceeding similarly, one can show that SPI holds between x and y as far as y follows x in S . So far we have shown that if x f C y, then x f y. Since f is transitive, it follows that f C is acyclic.
If part: Given an r.c.f. C consider the relation f C . Denote the transitive closure of f C by Tr(f C ). Since f C is acyclic, Tr(f C ) is asymmetric. Let f be any completion of Tr(f C ). Note that f is an ordering on X.
In the rest of the proof we show that f rationalizes the given C. To see this, consider any S ∈ . Suppose x is the last alternative in S according to f. Next, we show that conditions (1) and (2) from Definition 2 hold. First, note that since x is the last element in the list, for each y ∈ S \ x, x f y. Since f nests f C and x f y, we cannot have y f C x. It follows that SPI holds between y and x.
(1) Note that we can simply write C x (S) = 1 − y∈S\x C y (S). Since SPI holds between each y ∈ S \ x and x, we have C y (S) = C y (S \ x) · (1 − C x (x y)). Once we substitute these expressions into the former, we obtain (1).
(2) Consider any y ∈ S \ x. Since SPI holds between y and x, C y (S) = C y (S \ x) · C y (x y). Hence we conclude that f rationalizes C.
Definition 4. For a given choice function c and for each distinct x y ∈ X, x is revealedto-follow y, denoted by x F c y, if for some S ∈ , we have either Proof. As noted above, any choice function can be thought of as an r.c.f. C such that for each S ∈ and x ∈ S, C x (S) ∈ {0 1}. Next, note that once the f C relation is written for a choice function c, we obtain the F c relation. Hence, the conclusion directly follows from Proposition 1.

List rationality and two-stage choice procedures
In this section, we relate list rationality to two-stage choice procedures. We consider the two-stage procedure, referred to as shortlisting, in which the decision maker has two binary relations defined over the alternative set such that the first relation P 1 is transitive but possibly incomplete, and the second relation P 2 is a preference relation. Given a choice set, the decision maker first commits to the set of undominated alternatives with respect to the first relation. Then from this set he chooses the best alternative according to the second relation. From each choice set S, shortlisting singles out the alternative max(max(S P 1 ) P 2 ). Shortlisting is more restrictive than the rational shortlist method (Manzini and Mariotti 2007) in which both binary relations are only required to be asymmetric. 14 One can easily check that the set of choice functions that can be represented as shortlisting and the set of list-rational choice functions are nonnested. In Example 2, we argue that list rationality can be equivalently formulated in the language of choice by game trees. Similarly, in the next example we introduce a choice procedure formulated in the language of choice by game trees and argue that this procedure is observationally equivalent to shortlisting. These observational equivalences point out the connection between list rationality and shortlisting that does not directly follow from their formulations. Example 4 (Choice by a Stackelberg game). The primitive of this choice procedure is a Stackelberg game, an extensive form game with two players{a leader with a preference relation 1 and a follower with a preference relation 2 . First, the leader chooses an action from his action space A 1 . Then, informed of the leader's choice, the follower chooses an action from his action space A 2 (a 1 ). Suppose each alternative is the outcome of a unique joint action of the players. For each choice set S, consider the reduced extensive form game G|S derived from G by retaining only the paths that lead to terminal nodes having outcomes in S. From each choice set S, the decision maker chooses the Stackelberg equilibrium 15 outcome of the game G|S.
To see that this procedure can be represented as shortlisting, first let P 1 = 2 . To define P 2 , for each x y ∈ X, if both are obtained by the same action of the leader, then let x P 2 y if x 1 y; otherwise let them be incomparable by P 2 . Now one can easily verify that a shortlisting procedure with (P 1 P 2 ) retrieves the same choice function. To see the converse, consider a shortlisting procedure described by (P 1 P 2 ). To construct the game G, let 1 = P 2 and 2 be any completion of P 1 . Next, design A 1 and {A 2 (a 1 )} a 1 ∈A 1 such that if the leader takes an action a 1 , then the resulting outcomes, depending on the actions of the follower, coincide with a maximal set of alternatives over which P 1 is complete. 16 It follows that for each choice set S, the Stackelberg equilibrium outcome of the game G|S is the max(max(S P 1 ) P 2 ). ♦ To motivate our characterization to follow, consider a shortlisting procedure described by (P 1 P 2 ). Note that if x is preferred to y according to the first binary relation, then y is never chosen from any choice set that contains x. So we can read x P 1 y as x dominates y. Next consider a list-rational choice procedure described by the list f. Note that if x is chosen when compared to y and y follows x in the list f, then y is never chosen from any choice set that contains x. So whenever this is the case, we can conclude that x dominates y. We illustrate a formal account of this connection by characterizing shortlisting in terms of acyclicity of a binary relation that is similar to the revealed-to-follow relation. 17 Definition 5. For a given choice function c and for each distinct x y ∈ X, x is related to y, denoted by x R c y, if for some S ∈ , we have (i) x = c(S ∪ y) and x = c(S), or (ii) y = c(S ∪ x) and x = c(x y), or (iii) y = c(S ∪ x) and [y = c(x y) and y = c(S)].

Proposition 2. A choice function c is a shortlisting if and only if R c is acyclic.
15 See Osborne and Rubinstein (1994) for related definitions. 16 That is, P 1 behaves as a preference relation over each A 2 (a 1 ). Since P 1 is transitive and any transitive relation can be decomposed into maximal chains, we can construct {A 2 (a 1 )} a 1 ∈A 1 as described. 17 To see the connection between R c and F c , note that if x R c i y, then we have x F c y; if x R c ii y or x R c iii y, then we have y F c x.
In the literature, Au andKawai (2011), Lleras et al. (2010), and Horan (2012) provide different characterizations of shortlisting. Among these, the closest to our characterization is by Au and Kawai (2011), who require acyclicity of another binary relation. The difference is that we formulate our R c relation with a minimal deviation from the revealedto-follow relation to facilitate the comparison of shortlisting with list rationality. 18 In the rest of this section we prove Proposition 2.
Lemma 1. For a given choice function c, if R c is acyclic, then for each S ∈ and x ∈ S, we have x = c(S) whenever for each y ∈ S \ x, x = c(x y).
Proof. Consider a choice function c such that R c is acyclic. First we show that for each S ∈ and distinct x y ∈ S, if x = c(S) and y = c(S \ x), then x = c(x y). Call this property weak path independence (WPI). 19 Suppose WPI does not hold. Then it follows that for some S ∈ and distinct x y ∈ X, we have x = c(S ∪ y) and y = c(S), but y = c(x y). Since x = c(S ∪ y) and y = c(x y), we have y R c ii x. Since y = c(S ∪ x), and y = c(x y) and y = c(S), we have x R c iii y. It follows that we have x R c y R c x, which contradicts R c is acyclic.
Next consider any S ∈ and x ∈ S such that for each y ∈ S \ x, x = c(x y). Now we show that x = c(S). If S has only two alternatives, then we are done. Suppose S = {x x 1 x n } and consider the choice set {x x 1 x 2 }. Note that since x = c(x x 1 ) and x = c(x x 2 ), it follows from WPI that x = c({x x 1 x 2 }). Next, supposing that S has at least four alternatives, consider the set {x x 1 x 2 x 3 }. Since x = c({x x 1 x 2 }) and x = c(x x 3 ), by WPI we have x = c({x x 1 x 2 x 3 }). By proceeding similarly, we obtain x = c(S).
Proof of Proposition 2. If part: Suppose c is a shortlisting described by (P 1 P 2 ). We will show that R c is acyclic. To see this, we first show that R c ⊆ P 2 . Since P 2 is acyclic, it will follow that R c is also acyclic.
To show that R c ⊆ P 2 , first note that for each x y ∈ X, if x R c i y, then for some S ∈ , we have x = c(S ∪ y) and x = c(S). For this case, first we show that y ∈ max(S ∪ y P 1 ). To see this, since x = c(S ∪y), we have x ∈ max(S ∪y P 1 ). It follows that we can have x = c(S) only if there is w ∈ max(S P 1 ) such that w P 2 x. Since x = c(S ∪ y), this is possible only if y P 1 w. Suppose there is z ∈ S such that z P 1 y. Since P 1 is transitive and z P 1 y P 1 w, we have z P 1 w. So we cannot have w ∈ max(S P 1 ). We obtain a contradiction and it follows that y ∈ max(S ∪ y P 1 ). Finally, since x = c(S ∪ y), we must have x P 2 y.
Next note that for each x y ∈ X, if x R c ii y, then for some S ∈ , we have y = c(S ∪ x) and x = c(x y). Since x = c(x y), either x P 1 y or x P 2 y. Since y = c(S ∪ x), we cannot have x P 1 y, so x P 2 y. Finally we argue that there is no x y ∈ X such that x R c iii y. To see this, since y = c(x y), either y P 1 x or y P 2 x. Since P 1 is transitive, we have max(S ∪ x P 1 ) ⊆ max(S P 1 ) ∪ x. If y P 1 x, then max(S ∪ x P 1 ) = max(S P 1 ), and we get y = c(S ∪ x). If y P 2 x, then y = max(max(S P 1 ) ∪ x P 2 ), and it follows that y = c(S ∪ x).
Only-if part: Let P 2 be any completion of the transitive closure of R c . Let P 1 = {(x y)|y P 2 x and x = c(x y)}. Since R c is acyclic, P 2 is a preference relation.
Next we show that P 1 is transitive. Considering any x y z ∈ X such that x P 1 y P 1 z, we show that x P 1 z. It follows from the construction of P 1 that z P 2 y P 2 x. Since P 2 is transitive, we have z P 2 x. Now we argue that x = c(x z). First, we show that x = c(x y z). By contradiction, first suppose y = c(x y z). Since x P 1 y, we have x = c(x y), so we get x R c ii y. This contradicts y P 2 x. Next suppose z = c(x y z). Since y P 1 z, we have y = c(y z). It follows that y R c ii z. This contradicts z P 2 y. Hence, we obtain x = c(x y z). Since y P 2 x, we cannot have x R c i y. Since x = c(x y z), we must have x = c(x z); otherwise we have x R c i y. Since x = c(x z), either x P 1 z or x P 2 z. Since z P 2 x, we have x P 1 y. Hence, we conclude that P 1 is transitive.
Finally, for each S ∈ such that x = c(S), we show that x = max(max(S P 1 ) P 2 ). First we show that x ∈ max(S P 1 ). By contradiction, suppose there is y ∈ S such that y P 1 x. It follows from the construction of P 1 that x P 2 y and y = c(x y). However, since x = c(S) and y = c(x y), we have y R c ii x. This contradicts x P 2 y. Next, we show that there is no y ∈ max(S P 1 ) such that y P 2 x. By contradiction, suppose there is such an alternative y. Since y = c(S), by Lemma 1, there exists z 1 ∈ S such that z 1 = c(y z 1 ). Since x = c(S), if x = c(S \ z 1 ), then we have x R c i z 1 . If x = c(S \ z 1 ), by the same reasoning, there exists z 2 ∈ (S \ z 1 ) such that z 2 = c(y z 2 ). Since S is finite, by proceeding similarly we find z ∈ S such that x R c i z and z = c(y z). Since P 2 is transitive and y P 2 x P 2 z, we have y P 2 z. Since z = c(y z), we obtain z P 1 y. This contradicts y ∈ max(S P 1 ). Hence, we obtain x = max(max(S P 1 ) P 2 ).