Gradual pairwise comparison and stochastic choice
Abstract
EconStor is a publication server for scholarly economic literature, provided as a non-commercial public service by the ZBW.
Full text
Dutta, Rohan Article Gradual pairwise comparison and stochastic choice Theoretical Economics Provided in Cooperation with: The Econometric Society Suggested Citation: Dutta, Rohan (2020) : Gradual pairwise comparison and stochastic choice, Theoretical Economics, ISSN 1555-7561, The Econometric Society, New Haven, CT, Vol. 15, Iss. 4, pp. 1335-1364, https://doi.org/10.3982/TE3647 This Version is available at: https://hdl.handle.net/10419/253475 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by-nc/4.0/
Theoretical Economics 15 (2020), 1335–1364 1555-7561/20201335 Gradual pairwise comparison and stochastic choice Rohan Dutta Department of Economics, McGill University Guided by evidence from eye-tracking studies of choice, pairwise comparison is assumed to be the building block of the decision-making procedure. A decisionmaker with a rational preference may nevertheless consider the constituent pairwise comparisons gradually, easier comparisons preceding difficult ones. Facing a choice problem, she may be unable to complete all relevant comparisons and choose with equal odds from alternatives not found inferior. Stochastic choice data consistent with such behavior are characterized and used to infer the underlying preference relation and the order of pairwise comparisons. The choice procedure offers a novel rationale for behavioral phenomena such as the similarity effect and violations of stochastic transitivity and regularity. Keywords. Revealed preference, bounded rationality, stochastic choice. JEL classification. D01, D91. 1. Introduction The literature on eye-tracking analysis of multi-alternative choice, pioneered by Russo and Rosen (1975), offers evidence of the actual choice procedure that consists primarily of a sequence of pairwise comparisons.1For a rational agent capable of considering all relevant comparisons (those that shrink the set of options being considered) before making a choice, the simultaneity or sequentiality of such comparisons is irrelevant. This is untrue if the agent is often, for unobservable reasons, unable to complete all relevant comparisons. I study such a boundedly rational agent who considers the relevant pairwise comparisons of her underlying strict rational preference sequentially to remove inferior alternatives from a given choice set. This sequence is menu-independent in the particular sense that if two different pairwise comparisons are both relevant in two distinct choice problems, then they are considered in the same order in both. The set of relevant pairwise comparisons, however, is menu-dependent. Facing a choice problem, the agent may be forced to stop at different points along this sequence of relevant comparisons according to some unobserved and menu-dependent probability distribution. Rohan Dutta: [email protected] I thank Sean Horan, David Levine, Yusufcan Masatlioglu, Salvatore Modica, Paulo Natenzon, Pietro Ortoleva, and Anna Winterbottom for helpful comments. I also thank the three anonymous referees for the detailed reports. The paper has been helped immensely by their engagement. 1See also Russo and Leclerc (1994) and the review of eye-tracking research in Wedel and Pieters (2008). For more recent work, see Noguchi and Stewart (2014,2018). ©2020 The Author. Licensed under the Creative Commons Attribution-NonCommercial License 4.0. Available at https://econtheory.org.https://doi.org/10.3982/TE3647
1336 Rohan Dutta Theoretical Economics 15 (2020) While she is able to make all relevant comparisons with positive probability, it is not certain. Upon stopping she chooses from alternatives that have not been removed from the choice set with equal odds. Choice resulting from this procedure is called a gradual pairwise comparison rule (GPCR). The random nature of stopping along the sequence makes the choice behavior stochastic. Such boundedly rational behavior is consistent with a rich set of (stochastic) choice data, including deterministic rational choice, Luce rules (Luce 1959), and additive perturbed utility rules (Fudenberg et al. 2015), but also choice data where the order of choice probabilities across alternatives is menu-dependent. The assumption of menu independence of the order of relevant comparisons follows from a more basic assumption that the order reflects the agent’s relative ease of making such comparisons, with easier comparisons preceding difficult ones. This relative ease may be subjective and known to the agent alone. Nevertheless, it ensures that the order of comparison is menu-independent (see Section 5.2). This order can be inferred from choice data (Theorem 5). The random stopping could arise from different sources such as fatigue (from making multiple comparisons) or unobserved time constraints. Section 4 describes how GPCRs can exhibit violations of strong (and moderate) stochastic transitivity, the similarity effect, and regularity violations, thereby suggesting one avenue through which fatigue or time constraints could yield such nonstandard behavior. The primary objective of this study is to carefully analyze a simple decision procedure built upon the empirical finding that choice involves a sequence of pairwise comparisons and the idea that easier comparisons precede difficult ones.2,3Theexerciseis made more compelling by the ability of this procedure to explain disparate behavioral phenomena despite an underlying stable rational preference. The latter facilitates standard welfare analysis. The ordinal content of choice probabilities in a GPCR is essentially determined by the sequence of pairwise comparisons (Theorem 1). Changing the choice probabilities of a GPCR without changing the ordinal content leads to a new GPCR where only the random stopping specification needs changing (Theorem 2). As a result, checking whether some choice data are GPCR amounts to verifying if there exists a sequence of pairwise comparisons that can generate the required choice ranks. The model is characterized by three simple axioms (Theorem 3) and each GPCR is shown to correspond to a unique underlying strict preference (Theorem 4). The latter is easily identified with the agent strictly preferring ato bif and only if ahas the highest choice probability in some set containing b. Multiple sequences of pairwise comparisons can be consistent with the same GPCR. It may be, though, that in all such representations, certain pairwise comparisons must 2Ravid and Steverson (2018) also study a choice procedure involving pairwise comparisons, but with very different structure and implications, as discussed in Section 5.1. 3Using empirical guidance to derive appropriate properties of a choice procedure, instead of suitable restrictions on choice data, is less common in economics research, but has a tradition of its own. See, for instance, Simon (1955), Rubinstein (1988), and Manzini and Mariotti (2007).
Theoretical Economics 15 (2020) Pairwise comparison and stochastic choice 1337 be considered before some others. These are fully identified by using a revealed preference approach (Theorem 5). This study owes a considerable debt to Apesteguia and Ballester (2013)andManzini and Mariotti (2012). Not only did they introduce the framework of choice resulting from a sequence of pairwise comparisons on which the current model is built, they also made the valuable finding that identifying from choice data the first relevant pairwise comparison for any (collection of) choice set(s) is key to characterizing their sequential procedures. This idea is essential in the current setting too and is captured by one of the three axioms that characterize the model. The rest of the paper is as follows. Section 2 defines the gradual pairwise comparison (GPC) choice procedure and discusses an example. Section 3 contains all the characterization results. The proof of Theorem 1 is retained in the main body of the text to give the reader a better sense of how the model works. All other proofs are collected in the Appendix, along with a discussion on the independence of axioms. Section 4 discusses the specific ways in which GPCRs can accommodate violations of stochastic transitivity and other forms of menu-dependent choice. Section 5 discusses the key components of the GPC procedure and how they relate to other models of boundedly rational choice and stochastic choice. 2. Stochastic choice and procedures 2.1 Preliminaries Consider a nonempty finite set of alternatives Xand let Xbe the set of all nonempty subsets of X. These are the choice sets the decision-maker faces. The decision-maker is assumed to have a strict rational preference. This is captured by a binary relation, P⊆X×X,where(a b) ∈Pmeans that ais strictly preferred to b.4It will often be convenient to represent this binary relation by ,whereab≡(a b) ∈P.Denotethe set of all strict rational preferences over Xas P. Definition 1. A stochastic choice rule is a function p:X×X→[01]such that a∈Ap(aA) =1for all A∈Xand p(aA) =0for all a/∈A. Here p(a A) is the probability with which ais chosen when the decision-maker faces the choice set A. Stochastic choice rules are clearly more general than deterministic ones, which in addition require p(a A) ∈{01}. More importantly, they better accommodate observed choice data in that they can represent the relative observed choice frequencies obtained from repeated choices by the decision-maker. Let a stochastic choice rule without ties be a stochastic choice rule psuch that p(a A) = p(bA) for all ab ∈A∈X,witha= b. These choice rules turn out to be particularly useful in the characterization results that follow. 4As a strict rational preference, Pmust be asymmetric ((ab) ∈P⇒(b a) /∈P), complete (for all a b ∈X, if a= b, then either (a b) ∈Por (ba) ∈P), and transitive ((ab) ∈Pand (b c) ∈P⇒(a c) ∈P).
1338 Rohan Dutta Theoretical Economics 15 (2020) 2.2 Gradual pairwise comparison The choice procedure of gradual pairwise comparison (GPC) is as follows. The decisionmaker, endowed with a strict rational preference P, does not consider all the binary comparisons in Psimultaneously. Instead, she has an ordered partition P={Pi}I i=1of Pin that Pj∩Pk=∅for j= k,andiPi=Pand Pi= ∅for all 1≤i≤I.LetP0=∅. A pairwise comparison (a b) is relevant given a set of alternatives, Aif {a b}⊆A.Given a choice set, the agent considers all the relevant pairwise comparisons in P1simultaneously, eliminating all alternatives found inferior. With the alternatives that survive, she then considers the relevant comparisons (given the set of surviving alternatives) in P2and so on. For a given ordered partition Pof Pand a choice set A∈X, define the following sets recursively: MP 0(A) =A MP i(A) =x∈MP i−1(A)|∀y∈MP i−1(A)(yx) /∈Pi∀1≤i≤I (1) The set MP i(A) contains all alternatives that survive after the decision-maker has considered the ith cell of her ordered partition. For any choice set A,let ˜ IP(A) be the cell of the partition that finally reduces the surviving options to a singleton. Formally, ˜ IP(A) =i≤Isuch that |MP i(A)|=1and either |MP i−1(A)|>1or i=1.5The cell ˜ IPis well defined since Pis a partition of a strict rational preference P.6 If the decision-maker could complete all comparisons, her choice would coincide with deterministic rational choice. Her (possible) inability to do so is captured by a function π:(P∪{P0})×X→[01],suchthatPi∈Pπ(PiA) +π(P0A) =1and π(P˜ IP(A)A)>0for all A∈X, labeled stopping function.7For any choice set A,π(PiA) is the probability that the decision-maker stops at cell Piand is unable to complete the comparisons contained in subsequent cells; π(P0A)is the probability with which she is unable to complete any relevant comparison at all. While the premise of this study is that a decision-maker may be unable to make all relevant comparisons, assuming π(P˜ IP(A)A)>0for all A∈Xrequires that her ability to do so cannot be ruled out entirely either. It says that the decision-maker is able to make all relevant comparisons with positive probability. In deterministic rational choice, this probability would have to be 1. Conditional on stopping after considering cell Pi, the procedure entails the decisionmaker choosing with equal odds from among the alternatives that remain, MP i(A). Definition 2. A gradual pairwise comparison rule (GPCR) is a stochastic choice rule pPπ with an ordered partition Pof a strict rational preference Pand a stopping function 5The term |B|denotes the number of elements in the set B. 6For any i<I, by definition, |MP i(A)|≥|MP i+1(A)|,wherePbeing a partition of a strict rational preference Pimplies that MP I(A) is a singleton (containing the most preferred alternative in A). 7The obvious dependence of the stopping function on the partition Pis suppressed for notational convenience.
Theoretical Economics 15 (2020) Pairwise comparison and stochastic choice 1339 πsuch that for all A∈X, pPπ(aA) = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ {i|a∈MP i(A)} π(PiA) MP i(A) if a∈A 0otherwise. (2) Asimple pairwise comparison rule (SPCR) is a GPCR, pPπ , for which each cell of the ordered partition Pis a singleton. Formally, |Pi|=1for all Pi∈P. A stochastic choice rule pis rationalizable by gradual pairwise comparison if there exists an ordered partition P of a preference P∈Pand a stopping function πsuch that p=pPπ . To see how the procedure works, consider the following example. Example 1. There are three lotteries, a,b,andc: a(71001005;3 41 4) b(70001000;3 41 4) c(6650490;4 51 5) Read the table above as lottery ayields $7100 with probability 3/4and $1005 with probability 1/4, and so on. The agent’s underlying preference ranks aover bover c. Nevertheless, she is able to make the comparison between aand bthe earliest, followed by the comparison between aand c,andthenband c. Formally, X={a b c}. The decision-maker’s preference is abc.Inotherwords, P={(a b) (ac) (b c)}. The ordered partition Pis P0P1P2P3 (ab) (a c) (b c) Her stopping function is π(·A) A={a b}{ac}{b c}{abc} P002/32/30 P11004/5 P201/30 1/5 P3001/30 The resulting choice probabilities through gradual pairwise comparison are pPπ(·A) A={ab}{a c}{b c}{a b c} a12/30 3/5 b002/30 c01/31/32/5 For instance, pPπ(b{bc})=2/3and pPπ(c {a b c})=2/5. The stopping function captures the agent’s ability to complete the comparison (ab), whenever relevant. By contrast, the agent finds the comparison (a c) difficult.
1340 Rohan Dutta Theoretical Economics 15 (2020) The probability with which she is unable to complete this comparison when facing the choice set {a c}is captured by π(P0{a c}). With the choice set {ab c}, the agent again makes the comparison (ab) without fail. However, she is now unable to complete the (ac) comparison with higher probability, π(P1{a b c}). Such a stopping function specification therefore captures something akin to fatigue (or time constraints), where successfully carrying out one comparison reduces the chances of completing subsequent comparisons. ♦ Remark 1. Note that when choosing from {b c}, the only relevant comparison is (b c); the agent does not think of any other comparisons. When choosing from {abc},the relevant comparisons are (a b) followed by (a c), while (b c) is not considered. Clearly, the set of relevant comparisons is menu-dependent. Nevertheless, the order of relevant comparisons is menu-independent, in that if there were a larger choice set in which (ab) and (a c) were relevant comparisons, then (a b) would precede (a c).It is this menu independence of the order of relevant comparisons that allows for a menuindependent specification of the ordered partition, with the understanding that the agent, for a given choice set, considers only the relevant comparisons in each cell of the partition, sequentially.8 Remark 2. The model allows for a very general class of stopping rules. For instance, with the same ordered partition as in Example 1, the model allows an agent to stop with equal probability at every cell of the partition, irrespective of the choice set π(PiA)= 1/4for all A∈Xand all i∈{0123}. This specification makes little sense, since, for instance, when choosing from the set {b c}, the agent does not think about the comparisons (a b) and (a c); so stopping at P1or P2does not correspond to any literal description of the choice procedure. Indeed, the following subset of stopping functions captures more accurately the decision procedure: π:(P∪{P0})×X→[01]is an exact stopping function if it is a stopping function such that π(PiA)=0if MP i(A) =MP i−1(A) for all 1≤i≤I. It turns out, though, that the set of choice rules rationalizable by gradual pairwise comparison is identical to those rationalizable by GPC using exact stopping functions. Observation 1. A stochastic choice rule pis rationalizable by gradual pairwise comparison if and only if p=pPπ,whereπis an exact stopping function. Relying on this observation, the subsequent analysis continues to use the more general stopping functions, which are easier to describe in proofs. Exact stopping functions are used in all examples. Finally, choosing between these two classes of stopping functions has no impact on any of the results that follow. 8A similar feature is at work in the representation of strict rational preferences. The menu-independent ranking of any two available alternatives allows for a menu-independent representation of the entire preference ordering, with the understanding that the agent, for a given choice set, maximizes this preference only from among the available alternatives.
Theoretical Economics 15 (2020) Pairwise comparison and stochastic choice 1341 3. Characterization 3.1 Choice probabilities and choice rank The ordinal content of choice probabilities is labeled choice rank. This is the ranking of alternatives in a choice set generated by the choice probabilities, with a higher choice probability corresponding to a higher rank. Since the mapping from choice probabilities to choice rank is many-to-one, knowledge of choice rank alone cannot pin down the exact value of choice probabilities. The two key components of a GPC procedure—the ordered partition Pand the stopping function π—play very different roles in determining choice rank and choice probabilities. Choice rank is essentially determined by P, the sequence in which the constituent pairwise comparisons of the rational preference are considered (and therefore the underlying preference too). Theorem 1. Fix an ordered partition Pof some P∈P.Letπand πbe stopping functions on P. Then for any A∈Xand ab ∈X, pPπ(aA) > pPπ(bA) ⇒pPπ(a A) ≥pPπ(b A) Proof. It follows from the definition of these sets in (1)thatforanyP,MP j(A) ⊇MP k(A) for all j k ≤Iwith j<k.Alsoforanyab ∈A,oneofthesets{i|a∈MP i(A)}and {i|b∈ MP i(A)}must be a subset of the other. Therefore, pPπ(aA) = {i|a∈MP i(A)} π(PiA) MP i(A) > {i|b∈MP i(A)} π(PiA) MP i(A) =pPπ(bA) ⇒i|a∈MP i(A)⊃i|b∈MP i(A) ⇒pPπ(a A) = {i|a∈MP i(A)} π(PiA) MP i(A) ≥ {i|b∈MP i(A)} π(PiA) MP i(A) =pPπ(b A) In other words, changing the stopping function cannot reverse strict choice ranks. Further, any stochastic choice rule that always has a unique most probable alternative and is consistent with the choice ranks of some GPCR can be rationalized by choosing an appropriate stopping function while leaving the ordered partition of the original GPCR unchanged. Axiom 1 (Unique best). For all A∈X,thereexistsa∈Asuch that p(aA) > p(b A) ∀b∈A\{a} Theorem 2. Fix an ordered partition Pof some P∈Pand a stopping function π.Letp be a stochastic choice rule that satisfies Axiom 1, and for all A∈Xand ab ∈X, pPπ(aA) > pPπ(b A) ⇒p(a A) ≥p(b A) pPπ(aA) =pPπ(bA) ⇒p(a A) =p(b A) Then there exists πsuch that p=pPπ.
1342 Rohan Dutta Theoretical Economics 15 (2020) Taken together, the two theorems above show that the key step to rationalizing a stochastic choice rule by gradual pairwise comparison is to obtain an ordered partition of the underlying preference that generates the required choice ranks. It is then guaranteed that there exists an appropriate stopping function for the remaining task of matching the exact choice probabilities. 3.2 General characterization Deterministic rational choice is a particular case of the GPC procedure. Indeed, for any preference P∈Pand any ordered partition Pof it, setting π(P˜ IP(A)A)=1ensures that pPπ(aA) =1if ais the most preferred element in Aaccording to Pand pPπ(aA) =0 otherwise. This is unsurprising, since setting π(P˜ IP(A)A)=1implies that the agent is able to make all relevant comparisons before making her decision. More interestingly, the GPC procedure can rationalize choice reversals. For instance, in Example 1, adding the alternative ato the choice set {b c}, increases the probability of cbeing selected from 1/3to 2/5while reducing that of bfrom 2/3to 0.Commonly used stochastic choice rules such as the Luce rule cannot allow such choice reversals. In fact, the increased probability of cviolates regularity, a property that requires p(aA) ≥p(a B) for all a∈A⊆B. This puts the GPC choice procedure outside the scope of random utility models, which necessarily satisfy regularity. It is natural, then, to wonder whether the GPC procedure has any empirical content. Indeed, it does and it can be characterized. Start by defining an appropriate notion of revealed preference. Definition 3. Given a stochastic choice rule pand a b ∈X,ais stochastically revealed preferred to bif ∃A∈Xsuch that ab ∈Aand p(aA) ≥p(d A) ∀d∈A Note that it is not enough for ato simply have a higher choice probability than bto be revealed preferred to it; amust be the most probable alternative in the presence of b. This leads to the most immediate testable implication of the GPC procedure, labeled stochastic weak axiom of revealed preference (sWARP). Axiom 2 (sWARP). For all ab ∈X,ifais stochastically revealed preferred to b,thenbis not stochastically revealed preferred to a. In words, alternatives that were not the most probable in a given set cannot become the most probable in the presence of the original most probable alternative. Given the assumption of strict preferences, an immediate implication of Axiom 2 is that for any choice set there is a unique alternative with the highest choice probability. Axiom 2 relates entirely to how the most probable alternative varies across choice sets. It imposes no restriction on the choice probabilities or even the choice rank of alternatives that are not the most probable. The testable implications of GPC on these are more subtle.
Theoretical Economics 15 (2020) Pairwise comparison and stochastic choice 1349 Figure 1. Violation of regularity. similarity effect obtains with blosing a larger proportion of its probability compared to a(inequality (4)), improving the odds ratio in favor of a. The rationale behind the result is simple. The only effect of adding cto Ais cjoining all survivor sets MP ithat contain b(except the one following the comparison (b c)), leaving all else unchanged. This makes ctake away more probability from bthan a,either directly as in part (i), where the set of survivor sets containing ais a strict subset of those containing b, or proportionally as in part (ii), where the survivor sets containing a and those containing b, which are affected by c,arethesame,butais chosen with the higher probability in A. 4.3 Violation of regularity through fatigue The regularity property, which requires p(a A) ≥p(aB) for all a∈A⊆Band satisfied by random utility models, is often violated in choice data (see the review in Reiskamp et al. 2006). The GPC procedure captures how fatigue may lead to regularity violations. Consider the choice environment described in Figure 1. The decision-maker chooses from among alternatives defined by a pair of attributes. She prefers more to less of each attribute. Suppose her underlying preference is abc. The fact that alternative cis clearly dominated by bbut not by amakes it natural then that the decisionmaker makes the comparison (bc) before any other. Consider the order of comparison P0P1P2 (bc) (a b) (ac) The resulting choice violates regularity with p(b{ab c}) > p(b{a b})if π(P0{a b c})/3+π(P1{a b c})/2>π(P 0{ab})/2. Given the obvious nature of the comparison (b c), it is reasonable to expect π(P0{a b c})to be negligibly small, if not 0. Therefore, the violation occurs as long as having to make an additional comparison increases the chance of giving up before completing a tougher comparison. The phenomenon of decision fatigue, in which making multiple decisions negatively affects the quality of subsequent decisions, is now well documented (see, for instance,
1350 Rohan Dutta Theoretical Economics 15 (2020) Levav et al. 2010 and Hirshleifer et al. 2019). The example above shows that even in a single decision problem, fatigue may worsen choices. Indeed, even adding alternatives that are relatively easily found to be inferior may nevertheless make it less probable that the decision-maker completes the more difficult comparisons. This phenomenon is distinct from the attraction effect. In the latter, the increased probability of choosing bupon adding cdoes not depend on the preference between a and b. By contrast, in the argument above, it matters that ais preferred to b.Herethe earlier comparison (bc) helps the inferior alternative bin the later comparison (a b). 5. Discussion 5.1 Sequence of pairwise comparisons An essential ingredient of the GPC procedure is that choice involves a sequence of pairwise comparisons. Ravid and Steverson (2018) study a model of choice that also contains this feature but is otherwise very different in both structure and implication. In their model labeled “focus, then compare” (FTC), an agent focuses on an available alternative (with equal odds) and sequentially compares it in a pairwise manner to all other alternatives in a random order. The focal alternative is selected if all comparisons are favorable. Otherwise, a new alternative is selected (with replacement) as focal, again with equal odds, and the procedure is repeated. The most important difference with GPC is that the result of each binary comparison in FTC is random. Requiring these comparisons to reflect a stable rational preference (as in GPC) would reduce the model to deterministic rational choice. So, to the extent that FTC can rationalize context-dependent choice or even nondegenerate stochastic choice, it must depart from rational preferences. Further, in contrast to GPC, the sequentiality of pairwise comparisons (for a given focal option) plays no important procedural role in FTC. Since what matters is whether all the pairwise comparisons are favorable, changing the order of these comparisons while holding their outcomes constant would lead to the same decision. The FTC procedure shows how the random nature of what catches an agent’s attention can interact with random (pairwise) choice mistakes to generate contextdependent choice. By contrast, in GPC, context-dependent choice is the result of the differential ease of making these pairwise comparisons (hence the sequential structure), which interacts with the random number of comparisons the agent is able to make. While not directly addressed in the paper, to the best of my understanding, FTC cannot accommodate the similarity effect. The simple premise behind choosing an alternative in the GPC procedure is that it is not found to be inferior in any relevant pairwise comparison. Based on this alone, the agent has no reason to further discriminate among surviving alternatives. This is the logic behind the agent randomizing uniformly across these alternatives. There exist more involved variants of the procedure where the agent uses additional information to randomize non-uniformly across surviving alternatives.12 It is beyond the scope of this 12For instance, the agent could keep track of the number of successful comparisons for each surviving alternative. Indeed, different successful comparisons could be weighted differently as well, depending on the identity of the dominated alternative, and so on.
Theoretical Economics 15 (2020) Pairwise comparison and stochastic choice 1351 study to consider and compare such variants. Hopefully, subsequent theoretical and empirical work such as Reutskaja et al. (2011) will identify the interesting variants. 5.2 Menu (in)dependence The menu independence of the order of relevant comparisons follows from the assumption that easier comparisons precede more difficult ones. Consider Example 1 again. The agent finds the comparison (ab) easier to make than (ac). Since this relative ease depends directly on a,b,andc, adding another lottery to the menu should have no effect on it. Note, however, that adding a new lottery could make one or both of these comparisons irrelevant.13 But if (a b) and (a c) continue to be relevant upon adding another lottery, then the comparison (a b) must continue to precede (bc). While the menu-dependent choice described in Section 4 is not an example of framing effects, the GPC procedure can accommodate the latter in a natural way. Framing an alternative differently while leaving its payoff-relevant features the same does not change the preference ordering, but typically changes the order of relevant pairwise comparisons, thereby affecting choice. The key driver of context-dependent choice in the GPC procedure is the menudependent nature of the set of relevant pairwise comparisons. This interacts with the menu-independent order of relevant comparisons to generate a highly menudependent sequence of actual comparisons the decision-maker makes. 5.3 Random attention models Recent work has focused on a different source of bounded rationality.14 Only a strict subset of all available alternatives may catch the decision-maker’s attention. Despite a rational preference, her chosen alternative could then be worse than an available option that did not catch her attention. The stochastic nature of what catches the agent’s attention for a given choice set leads to stochastic choice behavior. As for choice data it can rationalize; none of the random attention models nests GPC and vice versa. For instance, the model in Manzini and Mariotti (2014) must satisfy regularity (unlike a GPCR), but allows violations of sWARP. The following example, studied in Cattaneoetal.(2020), is of a GPCR that violates the acyclicity condition that characterizes the most general random attention model. Example 3 (Violation of RAM acyclicity). The ordered partition of the underlying preference abcdis P1P2P3P4P5 (c d) (a b) (a d) (ac) (bc) (bd) 13For instance, if lottery d,whichpays$10,000 with probability 1, were added to the menu, then perhaps the comparisons (d a),(d b), and (d c) would precede all others, making the comparisons (a b) and (a c) irrelevant for the choice set {ab c d}. 14See Manzini and Mariotti (2014), Brady and Rehbeck (2016), and Cattaneo et al. (2020).
1352 Rohan Dutta Theoretical Economics 15 (2020) The stopping function is π(·A) A={a c}{abc}{a bd}{a b cd} P10001/5 P201/31/32/5 P3002/30 P412/30 2/5 P50000 This results in pPπ(c {ac})=0and pPπ(c {a bc})=1/6,whichinCattaneoetal. (2020) means that cis revealed preferred to b.ButwithpPπ(b{ab d})=0and pPπ(b{ab c d})=1/15,bis revealed preferred to c, violating acyclicity. ♦ More importantly, the random attention model and the GPC constitute fundamentally different choice procedures. This often leads to the same choice behavior despite vastly different underlying preferences, making inference about such preferences while ignoring the specific source of bounded rationality extremely tenuous.15 Take, for instance, Example 1, in which the underlying preference in the GPC procedure was abc. The choice data in the example are rationalizable by random access memory (RAM), but the only inferences about preference under RAM would be caand cb. 5.4 Luce’s model and related work In Luce’s model, if the underlying preference is a strict order, as in this study, then the alternatives can be assigned values u(x) ∈R++,∀x∈X,suchthatu(x) = u(y) if x= y and p(xA) =u(x)/(y∈Au(y)). All such choice rules are rationalizable by GPC. Consider the following construction that rationalizes any choice rule where, given the function u(·)above, p(x A) > p(y A) if and only if u(x) > u(y).16 Luce’s model is a particular case of this more general class of choice rules. Order the nalternatives in X as {xi}n i=1,wherei<j⇔u(xi)>u(x j). The ordered partition is Pi=(xjxn−i+1)|j<n−i+1∀i≤n In words, the first element of the ordered partition contains all pairwise comparisons in which the alternative with the lowest value under uis the inferior alternative. The second element contains all pairwise comparisons in which the alternative with the second lowest value under uis the inferior alternative and so on. Let πbe such that π(Pi·)>0 for all i≤n. It then follows that pPπ(xA) > pPπ(yA) ⇔u(x) > u(y) ∀A∈X{xy}⊆A Matching the exact choice probabilities then follows from Theorem 2.AlsobyTheorem 2,thek(A) lowest ranked alternatives in choice set Acan be assigned 0probability. 15Masatlioglu et al. (2012) and Dutta and Horan (2015) make a similar argument against the model-free approach suggested in Bernheim and Rangel (2009) for deterministic choice. 16This includes any choice rule without ties that has an additive perturbed utility representation as in Fudenberg et al. (2015).
Theoretical Economics 15 (2020) Pairwise comparison and stochastic choice 1353 This formulation, in a natural way, allows for zero probabilities in choice, while staying consistent with the order independence axiom.17 Finally, to match the choice probabilities to the Luce rule exactly, the following stopping rule π(along with the ordered partition above) is sufficient. Fix A∈X.Letxiand xkbe two alternatives in Awith adjacent choice ranks, and let xkbe the worse of the two, where iand kcorrespond to the order described in the previous paragraph. Set π(Pn−k+1A)= {xm∈A|m≤i} u(xi)−u(xk) xj∈A u(xj) and π(Pn−q+1A)=|A|u(xq)/(xj∈Au(xj)),wherexqis the worst choice ranked option in A. Appendix Lemma 1. For any GPCR pPπ,thereexistsanSPCRpPπsuch that pPπ =pPπ. Proof. Consider a GPCR pPnπnand let Pkbe the first cell in Pnthat is not a singleton. Since Pis a strict rational preference, there must exist some (xy) ∈Pksuch that (y c) /∈Pkfor any c∈X.Let(ab) ∈Pksatisfy this condition. Define a new ordered partition Pn+1={P j}and stopping function πn+1in the following way: P i=Pifor all i<k,P k=(ab),P k+1=Pk\{(a b)},P i+1=Pifor all i>k,πn+1(P i·)=πn(Pi·)for all i<k,πn+1(P k·)=0,andπn+1(P i+1·)=πn(Pi·)for all i≥k.Itiseasytoconfirmthat pPnπn=pPn+1πn+1. So setting P1=Pand π1=πgenerates a finite sequence {pPnπn}m n=1 using the construction above, such that pPmπmis an SPCR. Setting Pm=Pand πm=π concludes the proof. Lemma 2. For any GPCR pPπ , there exists a GPCR without ties pPπ, such that for all A∈Xand ab ∈X, pPπ(a A) > pPπ(b A) ⇒pPπ(aA) ≥pPπ(bA) Proof.FixaGPCRpPπ .ThenbyLemma 1 there exists an SPCR, say pPπ , such that pPπ =pPπ.SetP=P. Pick any stopping function πon Psuch that π(Pi·)>0for all Pi∈P.ThenpPπis a GPCR without ties. Also, pPπ(a A) > pPπ(b A) ⇒pPπ(aA) ≥pPπ(aA) ⇔pPπ(aA) ≥pPπ(bA) The first implication is because P=Pand Theorem 1. 17See Echenique and Saito (2019), Ahumada and Ulku (2018), and Horan (2018) for work on extending the Luce model to better incorporate choice with 0probabilities.
1354 Rohan Dutta Theoretical Economics 15 (2020) Proof of Observation 1. It is sufficient to show that given a GPCR pPπ , it follows that pPπ =pPπ,whereπis an exact stopping function. Let Z(A) ={i≤I|MP i(A) = MP i−1(A)}∪{0}.Foranyj∈Z(A),letk(j) be the smallest number in the set Z(A) that is larger than j.Ifjis the highest number in Z(A), then let k(j) =I+1.Set π(PjA)=j≤i≤k(j)−1π(PiA) if j∈Z(A). Otherwise set π(PjA)=0. Therefore, π is an exact stopping function. Now fix some A∈Xand a∈A. Observe that pPπ(a A) = {j∈Z(A)|a∈MP j(A)} π(PjA) MP j(A) = {j∈Z(A)|a∈MP j(A)} j≤i≤k(j)−1 π(PiA) MP j(A) = {j∈Z(A)|a∈MP j(A)} j≤i≤k(j)−1 π(PiA) MP i(A) = {i|a∈MP i(A)} π(PiA) MP i(A) =pPπ(aA) Proof of Theorem 2.GivenPand some A∈X, define the sequence of sets {Ei(A)}I i=1, where Ei(A) ={a∈A|a/∈MP i(A) and a∈MP i−1(A)}.Ei(A) contains all alternatives in A that are eliminated by the GPC choice procedure at the ith cell of P. It follows from (2) that if aand bboth belong to Ei(A),thenpPπ(a A) =pPπ(b A). By the premise of the theorem, it follows that p(a A) =p(b A).Letp(αjA) denote the choice probability under pof an element (if any) in Ej(A).IfpPπ(a A) < pPπ(b A),thenagainfrom (2), it follows that a∈Ej(A) and b∈Ek(A) with j<k. Further, by the premise of the theorem, p(aA) ≤p(b B). In what follows, πis selected so that π(PiA) ≥0for all 0≤i≤I.Letjbe the smallest number ifor which Ei(A) is nonempty. Set πsuch that j−1 i=0π(PiA) = |A|p(αjA). Subsequently, for any jand kwith j<ksuch that Ej(A) and Ek(A) are nonempty and Eq(A) =∅for all j<q<k,setπsuch that k−1 i=j π(PiA)= MP k−1(A) p(αkA)−p(αjA) Finally if jis the largest number ifor which Ei(A) is nonempty, then set π(PjA)= p(αjA) −p(αhA),wherehis the second largest number ifor which Ei(A) is nonempty. So defined, πis a stopping function. Indeed, the selections ensure that π(PiA)≥0 for all 0≤i≤I.Also,ifjis the largest number ifor which Ei(A) is nonempty, then it must be that j=˜ IP(A).Soπ(P ˜ IP(A)A)>0.LetZ(A) ={i|Ei(A) > 0and Ek(A) > 0for some k>i}.Forj∈Z(A),letjbe the next highest element in Z(A) (formally,
Theoretical Economics 15 (2020) Pairwise comparison and stochastic choice 1355 j>jand k∈Z(A) with j<k<j ). Then I i=0 π(PiA)=|A|p(αjA)+ j∈Z(A) MP j−1(A) p(αjA)−p(αjA)+p(α ˜ IP(A)A) = j Ej(A) p(αjA)+p(α ˜ IP(A)A)= a∈A p(aA) =1 Since psatisfies unique best, |A|−j|Ej(A)|=1. This is what ensures that the third equality above holds. It is now straightforward to verify that pPπ(a A) =p(αjA), where a∈Ej(A). Lemma 3. We have MP i(A) =B⇒MP i(B) =B. Proof. The relationship MP i(A) =Bimplies that for all a b ∈B,(a b) /∈Pjfor all j≤i. This in turn implies that MP j(B) =Bfor all j≤i. Lemma 4. If a∈MP ˜ IP(A)(A),then(a c) ∈Pfor all c∈A\{a}. Proof. Suppose, by contradiction, there exists b∈Asuch that (b a) ∈P. Since Pis a strict rational preference, there must be a P-maximal element in A,sayd∈A.If(b a) ∈ P, then d= a. Since by definition MP ˜ IP(A)(A) is a singleton, d/∈MP ˜ IP(A)(A) ⇒(cd) ∈P for some c∈A. This contradicts dbeing P-maximal in A. Proof of Theorem 3.Necessity. It is sufficient to show that if pPπ is a simple comparison rule (SCR) without ties, then it satisfies sWARP (Axiom 2), s-reducibility (Axiom 4), and ITR (Axiom 3). It turns out that any pPπ (not just those without ties) satisfies sWARP. sWARP. Suppose under the SCR pPπ that ais stochastically revealed preferred to b. So for some A∈Xwith {a b}⊆A, pPπ(aA) ≥pPπ(cA) ∀c∈A ⇒ {i|a∈MP i(A)} π(PiA) MP i(A) ≥ {i|c∈MP i(A)} π(PiA) MP i(A) ∀c∈A ⇒i|a∈MP i(A)⊇i|c∈MP i(A)∀c∈A ⇒i|a∈MP i(A)⊃i|c∈MP i(A)∀c∈A\{a} The final implication obtains because MP ˜ IP(A)(A) is a singleton by definition and so it must contain a. This means that (a c) ∈P∀c∈A\{a}by Lemma 4. Now suppose by contradiction there exists B∈Xsuch that a b ∈Band pPπ(bB) ≥ pPπ(cB) for all c∈B. Then exactly by the argument above it must be that MP ˜ IP(B)(B) = {b}.AgainbyLemma 4, this implies that (ba) ∈P, a contradiction. s-reducibility. By Lemma 1,pPπ can be assumed to be an SPCR without loss of generality. Fix a collection of sets B⊆˜ X.GivenP,letPkbe the first cell to contain a pairwise
1356 Rohan Dutta Theoretical Economics 15 (2020) comparison (a b) such that {a b}⊆Bfor some B∈B. Formally, for all Piwith i<k, (xy) ∈Pi⇒{xy}A∀A∈Band (a b) ∈Pkis such that {a b}⊆Bfor some B∈B. Since pPπ is an SPCR, (ab) is the only element in Pk. So if {ab}⊆A∈B,thenMP i(A) =Afor all i<k. Since (a b) ∈Pkit must be that MP k(A) =MP k−1(A) \{b}. This implies {i|b∈MP i(A)}⊂{i|c∈MP i(A)}for all c∈A.Therefore, since pPπ is an SPCR without ties, pPπ(c A) > pPπ(bA) ∀c∈A\{b}. ITR. Suppose D∈AT(pPπ)for some A∈˜ X. ThenitmustbethatMP k(A) =Dfor some k.Lemma 3 then ensures that MP k(D) =D. This implies that MP j(A) =MP j(D) for all j≥k.So{i|c∈MP i(A)}={i|c∈MP i(D)}for all c∈D. Therefore, pPπ(aA) > pPπ(bA) ⇔pPπ(aD) > pPπ(b D) for all a b ∈D. Observing that this is true for all A∈˜ Xwith D∈AT(pPπ)concludes the argument. Sufficiency. Let pbe a stochastic choice rule without ties that satisfies sWARP, ITR, and s-reducibility. The proof is by construction and relies on defining a sequence of sets in a recursive manner. For any nonempty Ci⊆˜ X, the subsequent set Ci+1will be constructed along with Pi. Fix some nonempty Ci⊆˜ X. Since psatisfies s-reducibility, there exists D∈Ciwith {x y}⊂Dsuch that if {xy}⊂A∈Ci,thenp(c A) > p(y A) for all c∈A\{y}. There may be multiple pairs {x y}that satisfy this condition. Simply pick one, say {aibi}.SetPi={(aibi)}and let Ci+1=Ci\Ei,whereEi={A∈Ci|{aibi}⊆A}. Setting C1=˜ Xyields a sequence {Pi}I i=1.LetP={Pi}I i=1.Alsoletπbe a stopping function on Psuch that π(Pi·)>0for all 1≤i≤I. It will now be shown that Pso defined is a partition of a strict rational preference. By construction, if (a b) ∈Pi,then {ab}Afor any A∈Cjwith j>i. Therefore, (ba) /∈Pjfor j>i. This proves asymmetry. Next, by s-reducibility, as long as Ciis nonempty, Ci+1⊂Ci. So for a given pair a,b, either {ab}∈Cjfor some jsuch that A/∈Cjfor any A⊃{ab},or(a b) ∈Pior (b a) ∈Pi for some i<j. In the first case it must be that either (a b) ∈Pior (b a) ∈Pifor some j≤i≤I. This proves completeness. Finally, to prove transitivity, note that by construction, (xiyi)∈Pi⇒p(xi{xiyi})>p(y i{xiyi}). Suppose by contradiction there exists asequence{xiyi}n i=1such that for each 1≤i≤n,(xiyi)∈Pj(i),yi=xi+1∀i<nand x1=yn. Since psatisfies sWARP, there must be a unique most probable alternative under pin the set A=∪ n i=1{xiyi},saya. But then there must exist some 1≤i≤nfor which a=yi. This contradicts the assumption that psatisfies sWARP. Therefore pPπ is a well defined SPCR. Further, by construction, pPπ is an SCR withoutties. Toseewhy,notefirstthatsincepPπ is an SPCR, for any A∈˜ Xand ab ∈A, one of the two sets {i|a∈MP i(A)}and {i|b∈MP i(A)}must be a strict subset of the other. Now since π(Pi·)>0for all 1≤i≤I,itmustbethateitherpPπ(aA) > pPπ(b A) or pPπ(aA) < pPπ(b A). To complete the proof it is sufficient to show that for all A∈Xand a b ∈X, pPπ(aA) > pPπ(bA) ⇒p(a A) > p(b A).Theorem 2 then guarantees the existence of a πsuch that pPπ=p, since sWARP implies unique best. Suppose by contradiction there exists an A∈˜ Xsuch that the condition above does not hold. Consider the choice ranks defined by pPπ and pon the alternatives in A.In particular, start with the lowest ranked alternative (smallest choice probability) according to each and if they are the same, then move one rank up. If there exists x y ∈Asuch that pPπ(xA) > pPπ(y A) but p(y A) > p(xA), then eventually this process must
Theoretical Economics 15 (2020) Pairwise comparison and stochastic choice 1357 end with the mth ranked alternative according to pPπ being different from that according to p,withm>1, while all lower ranked alternatives are identical. Let Bbe the set of all alternatives in Aranked mor better by pPπ . By construction, Bis also the set of alternatives in Aranked mor better by p.SoBis both a p-truncation and a pPπ-truncation of A. Suppose ais the mth ranked alternative in A(and, therefore, also B)underpPπ(·A) while it is bunder p(·A)with b= a. Since ais the lowest ranked alternative in Bunder pPπ(·A), it must be that the first pairwise comparison in Prelevant to Bis of the form (xa) for some x∈B\{a}. Suppose Pkis the cell of Pthat contains this (x a).Soforany yz ∈B,(y z) /∈Pjfor all j<k.ThenbyconstructionofPit must be that B∈Ck.Then (again by construction) (x a) ∈Pkimplies that since {x a}⊆B,wegetp(c B) > p(a B) for all c∈B\{a}. Finally by ITR it must be that if B∈AT(p),thenp(cA) > p(a A) for all c∈B\{a}. This contradicts the assertion that bis choice ranked last in Bunder p(·A). Theorem 6. A stochastic choice rule pis rationalizable by gradual pairwise comparison if and only if psatisfies unique best and there exists a stochastic choice rule without ties pthat satisfies sWARP, ITR, and s-reducibility such that for any A∈Xand ab ∈X, p(aA) > p(b A) ⇒p(a A) ≥p(bA) Proof of Theorem 6.Necessity. ItissufficienttoshowthatforanyGPCRpPπ , unique best is satisfied and that there exists a GPCR without ties pPπsuch that for all A∈X and ab ∈X,pPπ(a A) > pPπ(bA) ⇒pPπ(aA) ≥pPπ(bA). The latter follows directly from Lemma 2. As for the former, it has already been shown in the proof of Theorem 3 that a GPCR necessarily satisfies sWARP. It is easy to see that sWARP implies unique best. Sufficiency. Suppose psatisfies unique best and there exists an SCR without ties p that satisfies sWARP, ITR, and s-reducibility such that for all A∈Xand ab ∈X, p(aA) > p(b A) ⇒p(a A) ≥p(bA) (5) Since pis an SCR without ties and satisfies sWARP, ITR, and s-reducibility, by Theorem 3 there exists a GPCR pPπ such that pPπ =p. Moreover, since the (possible) ties in pare consistent with p=pPπ as in (5), by Theorem 2,thereexistsπsuch that p=pPπ. Proof of Theorem 4.⇒.If(a b) ∈P,thenpPπ(a{a b})>p Pπ(b{ab})since by assumption π(P˜ IP(A)A)>0for all A∈X. ⇐. The fact that ais stochastically revealed preferred to bimplies that there exists some A∈Xwith b∈Asuch that MP ˜ IP(A)(A) ={a}. The result then follows directly from Lemma 4. Lemma 5. Suppose pPπ is an SPCR with Pj=(a b),Pj+1=(x y),andπ(Pi·)>0for all Pi∈P.IfZMP j−1(A) for all A∈X,whereZ={ab}∪{x y},then pPπ(v B) > pPπ(wB) ⇔pPπ(v B) > pPπ(w B) ∀vw ∈B B ∈˜ X
1358 Rohan Dutta Theoretical Economics 15 (2020) where P i=Pifor all i<jand i>j+1,P j=(xy),andP j+1=(ab) and π(P i·)>0for all P i∈P. Proof.FixB∈˜ X. Suppose v∈Band v/∈Z. Then clearly v∈MP i(B) ⇔v∈MP i(B) for all 1≤i≤I.Further,ifv∈MP j−1(B),thenv∈MP j+1(B). If instead v∈B∩Z,then v∈MP i(B) ⇔v∈MP i(B) for all i<j. Now since ZMP j−1(B),itmustbethateitherMP j(B) =MP j−1(B) or MP j+1(B) = MP j(B),orboth.IfMP j(B) =MP j−1(B),thenitmustbethatMP j+1(B) =MP j(B).Further, since P j=Pj+1, it follows that MP j(B) =MP j+1(B) and, therefore, MP j+1(B) =MP j+1(B). Suppose now that MP j+1(B) =MP j(B), while MP j(B) may or may not be the same as MP j−1(B). Either way, it must be that MP j(B) =MP j−1(B). Thisinturnmeansthat MP j+1(B) =MP j(B). Therefore, again MP j+1(B) =MP j+1(B).Asaresult,ZMP j−1(B) implies that MP j+1(B) =MP j+1(B) and that no more than one element in MP j−1(B) could be missing from MP j+1(B), and this element must belong in Z. Note that MP j+1(B) =MP j+1(B) implies that MP i(B) =MP i(B) for all i≥j+1. In summary, MP i(B) =MP i(B) for all i= jand |MP j+1(B) \MP j−1(B)|≤1.So pPπ(v B) > pPπ(w B) ⇔v∈MP i(B) w /∈MP i(B) for some 1≤i≤I ⇔v∈MP k(B) w /∈MP k(B) for some 1≤k≤I ⇔pPπ(v B) > pPπ(w B) The only non-obvious component of the second implication above involves vw ∈ MP i(B) for all i<j and v∈MP j(B),butw/∈MP j(B). Then notice that |MP j+1(B) \ MP j−1(B)|≤1ensures that v∈MP j+1(B) while still w/∈MP j+1(B). The implication then follows from MP j+1(B) =MP j+1(B). Proof of Theorem 5.⇐. Suppose (ab) p(x y) and let p=pPπ.SothereexistsA∈ Xwith {xy}⊆A∪{a}such that p(b A) > p(zA) for some z∈Aand p(b A ∪{a})< p(w A ∪{a})for all w∈A∪{a},w= b. Without loss of generality suppose zis choice ranked last in A.Furtherlet1≤i≤Ibe the smallest number for which z/∈MP i(A) (by assumption, b∈MP i(A)). Therefore, (w v) /∈Pjfor all j<iand wv ∈A.Nowb being choice ranked last in A∪{a}implies that b/∈MP j(A ∪{a})for some j<i.This means (ab) ∈Pjfor some j<i.So(ab) precedes (wv) in the ordered partition for all wv ∈A. Further, since bis choice ranked last, (ab) precedes (av) in the ordered partition for all v∈A. Therefore, (ab) is revealed compared before (x y). By the transitivity of the revealed compared relation, it follows that if (ab) p(x y), then also (a b) is revealed compared before (x y). ⇒. Suppose p=pPπ .ByLemma 1,pPπ is assumed to be an SPCR without loss of generality. Further, since pis without ties, we can set π(Pi·)>0for all Pi∈P.Now suppose Pj=(ab) and Pj+1=(x y).Itwillbeshownthat(ab) p(x y) implies that ZMP j−1(A) for all A∈X,whereZ={a b}∪{x y}.ThenbyLemma 5 anewordered