# Decisions over Sequences

Bhavook<EMAIL_ADDRESS>[ Siddharth
<EMAIL_ADDRESS>[ Indian Statistical Institute  Indian
Statistical Institute

###### Abstract

This paper introduces a class of objects called decision rules that map
infinite sequences of alternatives to a decision space. These objects can be
used to model situations where a decision maker encounters alternatives in a
sequence such as receiving recommendations. Within the class of decision
rules, we study two natural subclasses —stopping and uniform-stopping rules.
Our main result establishes the equivalence of these two subclasses of
decision rules. Next, we introduce the notion of computability of decision
rules using Turing machines and show that computable rules can be implemented
using a simpler computational device—a finite automaton. We further show that
computability of choice rules —an important subclass of decision rules—is
implied by their continuity with respect to a natural topology. Finally, we
introduce some natural heuristics in this framework and provide their
behavioral characterization.

decision rules,

computability,

sequences,

revealed preference,

###### keywords:

We are extremely grateful to Arunava Sen and Debasis Mishra for their
invaluable guidance. We also benefitted from discussions with Rahul Deb,
Kalyan Chatterjee, Yves Sprumont, Pradeep Dubey and Rahul Roy. All errors are
our own.

##  1 Introduction

###  1.1 A brief overview

Imagine a decision maker (DM) who faces alternatives sequentially before she
decides to “stop" and make a decision. The alternatives keep on being
presented and the decision to stop may depend on the history of alternatives
examined thus far. A wide range of situations where decision making involves
seeking recommendations, receiving bitstreams of information, meeting people,
viewing alternatives on websites etc. fall under such a description. There has
been substantial evidence that the order in which alternatives are presented
to the DM affects the final decision. Incorporating this sequentiality, the
literature has introduced models of choice from finite lists i.e. ordered sets
(see [Rubinstein and Salant (2006)] and [Horan (2010)], among others).
However, since the alternatives could possibly be presented “forever" or the
DM could potentially go examining the alternatives as long as she “wishes" to
in the above mentioned situations, infinite sequences instead of finite lists
are a more appropriate modelling device. To that end, we propose a framework
of decision making from infinite sequences. We introduce a class of objects
called decision rules that generalize choice functions over lists in two ways:
(i) It allows the lists to be infinite (and allow for duplication); (ii) It
allows the choice to land in an arbitrary decision space making choice from
within the set of alternatives a special case.

The present paper focuses on two natural subclasses of decision rules, which
we term as stopping rules and uniform-stopping rules. These rules allow us to
capture the notion of bounded rationality in our framework and lend their
interpretation to commonly studied themes such as shortlisting, screening,
limited/bounded attention etc. As the name suggests, for any input i.e. a
sequence of alternatives, stopping rules decide within some finite amount of
time i.e. after inspecting a finite segment of alternatives. However, the
stopping point may depend on the input. On the other hand, in case of uniform-
stopping rules —which are a subclass of stopping rules—there is a fixed upper
bound on the stopping point. When the set of alternatives is finite, a fixed
upper bound ensures that the set of inputs is finite, thereby allowing one to
study various heuristics and provide testable restrictions for their axiomatic
characterization. On the other hand, one might suspect that no such guarantee
is assured in case of stopping rules even with a finite set of alternatives
since the set of infinite sequences is uncountably infinite. Hence, a
reasonable question to ask is what restrictions on the class of stopping rules
pin down the subclass of uniform-stopping rules? As it turns out, no further
restrictions are required i.e. every stopping rule is a uniform-stopping rule.
We believe that —due to the generality of our framework—this result might be
of independent interest to linguists, computer scientists and game theorists.
Our proof relies on the assumption that the set of alternatives is finite and
is established via a diagonalization argument.

We discuss the computational aspects of decision making in our framework using
two models of computation —a Turing machine and a finite automaton. While much
of the literature on computational aspects of choice uses a finite automaton
to model a decision maker, a more powerful and faithful model of computation
is that of a Turing machine. We define the class of computable decision rules
as the ones that can be “implemented" via a Turing machine and automaton-
computable rules as the ones which can be implemented via a finite automaton.
While it is straightforward to see that automaton-computable rules are
computable, we show that the converse is also true. This result is established
using the equivalence of stopping and uniform-stopping rules. The connection
between computable (automaton-computable) rules and stopping (uniform-
stopping) rules allows us to examine the procedural aspects of decision making
in our framework.

Next, we turn our attention to an important subclass of decision rules —choice
rules. These are the rules in which the decision space is restricted to be the
set of alternatives. Choice rules are the analogue of choice functions over
lists. We show that continuity of the choice rules with respect to a natural
topology—the product topology —on the set of sequences and the discrete
topology on the set of alternatives ensures that they are stopping rules,
thereby highlighting the link between continuity and computability. Within the
class of stopping choice rules, we introduce some natural heuristics and
provide their behavioral characterization. In particular, we adapt the idea of
satisficing and introduce two variants: ordinal satisficing and cardinal
satisficing. In contrast to the result on choice over sets ([Rubinstein
(2012)]), satisficing is behaviorally not equivalent to “rational" choice in
our framework. In fact, it turns out that rational behavior is a special case
of ordinal satisficing. Next, we introduce a broad class of heuristics called
configuration-dependent rules that can explain how position and frequency of
the alternatives in a sequence can affect choice. Finally, we provide a
topological foundation for our main equivalence result.

###  1.2 Computability and bounded rationality

Computational aspects of decision making have been an area of interest to
economic theorists. As has been pointed out in [Richter and Wong (1999)]),
computability-based economic theories also provide foundations for complexity
analysis. The idea of bounded rationality has been closely linked to
computational limitations of an economic agent (see [Futia (1977)]). For
instance, in the analysis of repeated games, the strategies of players are
implemented using finite automata ([Rubinstein (1986)]). Further, this
implementation of strategies is also assumed to be costly in the state
complexity of the automata implementing them ([Abreu and Rubinstein (1988)]).
In the context of finitely repeated games, the imposition of bounds on the
complexity of strategies of the players is shown to justify cooperation (see
[Neyman (1985)]).

The discussion of the role of computational constraints in individual decision
making goes back to [Simon (1955)]. He remarks “…limits on computational
capacity may be important constraints entering into the definition of rational
choice under particular circumstances". To capture the finite informational
processing capacity, [Kramer (1967)] models the DM as a finite automaton and
shows the incongruence of rational decision making given this behavioral
restriction on the DM. On the other hand, [Salant (2003)] shows that with the
finite automaton model of decision making, implementation of rational choice
functions over menus (sets of alternatives) is computationally efficient. He
further shows that implementation of other choice functions is much more
computationally demanding.
In our framework, decision rules can be implemented by a finite automaton. We
call such rules automaton-computable rules. For instance, the decision rule in
Example 2 is an automaton-computable rule and can be implemented using a
finite automaton with six states if the number of alternatives is 2, both of
them having a score of 1 and the threshold score is 2 (see Figure 1).

$q_{o}$start$1_{x}$$1_{y}$$2_{x}$$2_{y}$$1_{x}1_{y}$
$x$$y$$x$$x$$y$$x$$y$$y$$x,y$$x,y$ Figure 1: An automaton-computable decision
rule

While modeling DMs using automaton has been a popular approach to model
aspects of bounded rationality, to model the computational aspects of decision
making, the Turing machine is a more appropriate device. It is a more powerful
model of computation than a finite automaton and can be thought of as a
precise way of mathematically describing an algorithm. According to the
Church-Turing thesis, any realisable computer can be simulated as a Turing
machine. Therefore, Turing machines embody the idea of computability in the
truest sense. [Richter and Wong (1999)] use the idea of a Turing machine to
define computable preferences and show that computable preferences have
computable utility representations. [Camara (2021)] models the DM as a Turing
machine in the environment of decision making under risk. He introduces the
notion of computational tractability. A decision problem is intractable if it
cannot be implemented by an algorithm in a “reasonable" amount of time. He
shows that expected utility maximization is intractable unless the utility
function satisfies a strong separable property. Dropping the requirement of
tractability and retaining the aspect of computability in our framework, we
call a decision rule computable if it can be implemented by a Turing machine.
Our main result shows equivalence of computable and simply-computable rules,
thereby highlighting the relationship between the notions of computability and
bounded rationality.

###  1.3 Choice rules

An important subclass of decision rules are the rules whose decision space is
restricted to be the set of all alternatives itself. These are called choice
rules. These are the analogue of choice functions over lists and choice
functions over menus in classical abstract choice theory. The idea that a DM
may observe alternatives in the form of a list i.e. an ordered set was first
introduced in [Rubinstein and Salant (2006)]. Based on their framework, a
variety of models incorporating order effects in choice have been introduced
in the literature (see for instance [Guney (2014)] and [Dimitrov et al.
(2016)]).

Satisficing, first introduced by [Simon (1955)] has been an influential idea
in choice theory and many adaptations have been done in the literature. The
list setup provides a natural framework to study satisficing behavior. [Kovach
and Ülkü (2020)] introduced one such model. In their model, the DM makes her
choice in two stages. In the first stage, she searches through the list till
she sees k alternatives. In the second stage, she chooses from the
alternatives she has seen. Another adaptation of satisficing was introduced in
[Manzini et al. (2019)]. Their model is interpreted as one of approval as
against choice. Since our framework is a generalization of lists, satisficing
heuristics are a natural choice of study. To behaviorally characterize the
satisficing models in our framework, we introduce the informational notions of
sufficiency and minimal sufficiency of finite segments of a sequence. The
underlying idea is that a DM “makes up" his mind after viewing a certain
minimum number of alternatives in a given sequence. Such segments are
“sufficient" to implement the choice from the sequence. These notions form the
basis of our axioms that characterize the satisficing models in our framework.

As discussed above, an important application of our framework is when
alternatives come in the form of streams of recommendations. The idea that
recommendations influence choices has been widely accepted. [Cheung and
Masatlioglu (2021)] have introduced a model of decision making under
recommendation. However, in their setup, the decision maker observes sets of
alternatives and hence is different from our setup. Our object of interest-
infinite sequences- in the context of choices has been previously studied by
[Caplin and Dean (2011)]. Our model differs from their model in terms of
incorporating sequences in the domain of choice functions whereas they enrich
the observable choice data by incorporating sequences as the output of the
choice function and interpret these sequences as provisional choices of the DM
with contemplation time.

###  1.4 Examples

Our framework is general in its scope and provides fruitful avenues to study
many situations as the following examples might indicate.

Example 1 (Language processing). Let $X=\\{0,1\\}$. Consider a computer
program that receives bitstreams or sequences of symbols from $X$. The
bitstreams represent expressions in a natural language (for instance, English)
encoded in binary expression i.e. $0^{\prime}s$ and $1^{\prime}s$. For every
input bitstream, the program declares it as “TRUE" if it contains a
grammatically correct sentence. It outputs “FALSE" otherwise.

Example 2 (Cardinal satisficing). Let $X$ be a set of movies and
$\\{X_{i}\\}^{N}_{i=1}$ denote a partition of the movies into $N$ genres for
some $N\in\mathbb{N}$. A DM wishes to watch a movie and relies on
recommendations. She attaches a “weight" to each genre which indicates the
value she attaches to each genre i.e. there exists a function
$w:N\to\mathbb{R}_{+}$ such that every movie in the $i^{th}$ genre is given
the same weight. Her decision procedure involves seeking recommendations
sequentially from different sources such as peer groups, websites etc. She has
a threshold score in her mind and the first movie in the sequence of
recommendations whose cumulative score (due to repetitions) crosses the
threshold value is selected by her.

Example 3 (Ordinal satisficing). A DM has to choose a partner based on
repeated interactions with a set of potential partners. She has a fixed
attention span i.e. finite first-$k$ interactions. She attaches a “utility"
number to each alternative and has some threshold in her mind. She chooses the
first potential partner within the first-$k$ interaction whose utility number
exceeds the threshold. Otherwise she chooses the partner with the maximum
utility value from the first-$k$ interactions.

Example 4 (Investment strategy). A company wishes to invest in a fund based on
inputs provided by a fund rating agency. Let $X$ be a finite set of possible
performances of the fund (often denoted as $A_{+},B_{++}$ etc.). The inputs
are in the form of a sequence of performances of the fund i.e. at every time
period $t\in\mathbb{N}$, the agency announces the performance of the fund. Let
$Y=\mathbb{R}\times\mathbb{N}$. The company uses an “algorithm" that —based on
the input of performances—decides the amount of money and the time period for
which to invest i.e. $y\in Y$.

Example 6 (Stochastic choice) Let $X$ be a set of alternatives and $\sigma$ be
a probability distribution over $\mathbb{N}$. Faced with an input sequence,
the DM first draws the “depth" parameter $k\in\mathbb{N}$ according to
$\sigma$ and then chooses the $k^{th}$ alternative in the sequence.

Example 7 (Two-stage choice) A DM relies on a shortlisting procedure to make
choice and is endowed with two objects: a shortlisting function $\Gamma$ that
selects, for every input sequence, a finite initial segment and an output
function, $O$, that selects an output from the shortlisted segment.

The outline of the paper is as follows. In the next section, we formally
introduce stopping and uniform stopping rules and provide the main result.
Section 3 introduces the notions of computability of decision making in our
framework. Section 4 focuses on choice rules and within the class of choice
rules, two variants of satisficing are introduced and behaviorally
characterized. Further a broad subclass of choice rules called configuration-
dependent rules are introduced and behaviorally characterized. Section 5
discusses the topological approach to our main result and section 6 concludes.

##  2 Main result

Let $X$ be a finite set of alternatives. The objects of interest are
$X$-valued infinite sequences i.e. sequences whose terms are the alternatives
in $X$. These are the analogue of “menus" of classical abstract choice theory
in our framework. Let $\mathcal{S}$ be the collection of all such sequences
i.e. $\mathcal{S}=\\{S\ |\ S:\mathbb{N}\to X\\}$. Denote by $S(i)$, the
$i^{th}$ element of the sequence $S$. Let $S|_{k}$ denote the segment of $S$
that comprises of the first-$k$ elements of the sequence $S$ and by $S|_{k}.T$
a “concatenation" of the segment $S|_{k}$ with some sequence $T\in\mathcal{S}$
i.e. $S|_{k}.T\in\mathcal{S}$ with $[S|_{k}.T](i)=S(i)$ for
$i\in\\{1,2,\ldots,k\\}$ and $[S|_{k}.T](k+i)=T(i)$ for $i\in\mathbb{N}$. Let
$Y$ be any abstract set which we call the decision space. The DM in our
framework is endowed with a decision rule, $d$, which gives a unique decision
in the decision space for any given input sequence.

######  Definition 1.

A decision rule on sequences is a map $d:\mathcal{S}\to Y$ .

Consider the following decision rule: Let $Y=\\{0,1\\}$ and $\\{x^{*},y,z\\}$.
For any input $S\in\mathcal{S}$, $d(S)=1$ if $x^{*}=S(i)$ for some
$i\in\mathbb{N}$ and $d(S)=0$ otherwise. If the input is examined by the DM
sequentially —in discrete time for instance —such a decision rule looks
implausible since for the inputs that do not feature $x^{*}$, the DM would
have to wait “forever" to make a decision. To preclude such decision rules, we
restrict our attention to a subclass which we term stopping rules. To define
stopping rules formally, we first introduce the following useful object

$k_{d}(S)\coloneqq\inf\big{\\{}k\in\mathbb{N}:d(S)=d(S|_{k}\cdot T)\text{ for
all }T\in\mathcal{S}\big{\\}}.$

The function $k_{d}(\cdot)$ captures the smallest truncation of a sequence $S$
beyond which the terms of the sequence do not affect decisions. In other
words, for any “tail" appended beyond $k_{d}(S)$, the decision of the sequence
is unaffected. Now, we can formally define stopping rules as follows

######  Definition 2.

A decision rule $d$ is a stopping rule if for every $S\in\mathcal{S}$

$k_{d}(S)<\infty$

Stopping rules capture the idea that for any given input sequence, the DM does
not wait indefinitely and “makes up its mind" by a finite amount of time i.e.
after viewing a finite initial segment and the subsequent alternatives of the
sequence do not affect the decision. It is important to note the stopping time
or the “relevant" finite segment can depend on the i.e. input sequence. Since
the set of inputs is infinite (uncountably), stopping “times" may not have a
finite upper bound. A subclass of stopping rules for which the stopping times
have a finite upper bound are called uniform-stopping rules. They are formally
defined as

######  Definition 3.

A decision rule $d$ is a uniform-stopping rule if

$\sup\big{\\{}k_{d}(S):S\in\mathcal{S}\big{\\}}<\infty$

Consider a simple uniform-stopping rule: The DM is endowed with a strict
preference order $\succ$ over $X$, and for any input sequence, she considers
only the first 10 alternatives and picks the $\succ$-maximal alternative from
them. While it is clear that every uniform-stopping rule is a stopping rule,
we show below the converse is also true.

######  theorem 1.

Every stopping rule is a uniform-stopping rule

###### Proof.

Let $d:\mathcal{S}\rightarrow X$ be a stopping rule. Suppose, for the sake of
contradiction, $d$ is not a uniform stopping rule. The proof is organized in
steps which are as follows.

Step 1: We iteratively define a sequence of pairs
$\\{(k_{j},\mathcal{A}_{j})\\}_{j\in\mathbb{N}}$, where $k_{j}\in\mathbb{N}$
and $\mathcal{A}_{j}\subseteq\mathcal{S}$, as follows:

  1. 1.

Let $k_{1}\coloneqq\inf\\{k_{d}(S):S\in\mathcal{S}\\}$ and
$\mathcal{A}_{1}\coloneqq\\{S\in\mathcal{S}:k_{d}(S)=k_{1}\\}$.

  2. 2.

For any $j\in\mathbb{N}\setminus\\{1\\}$, assuming $(k_{l},\mathcal{A}_{l})$
have already been defined for every $l\in\\{1,\ldots,j-1\\}$, let

$\displaystyle k_{j}$
$\displaystyle\coloneqq\inf\\{k_{d}(S):S\in\mathcal{S}\setminus\cup_{l=1}^{j-1}\mathcal{A}_{l}\\}\text{,
and }$ $\displaystyle\mathcal{A}_{j}$
$\displaystyle\coloneqq\\{S\in\mathcal{S}\setminus\cup_{l=1}^{j-1}\mathcal{A}_{l}:k_{d}(S)=k_{j}\\}.$

The sets $\mathcal{A}_{j}$ refer to the set of all the sequences for which the
stopping time is $k_{j}$. From our supposition that $d$ is stopping rule and
$d$ does not have a uniform stopping time, the following properties are
immediate:

  1. [(a)]

  2. 1.

For each $j\in\mathbb{N}$, $k_{j}\in\mathbb{N}$ and
$\mathcal{A}_{j}\neq\varnothing$.

  3. 2.

$k_{1}<k_{2}<\ldots<k_{j}<\ldots$ and so on.

  4. 3.

$\\{\mathcal{A}_{j}:j\in\mathbb{N}\\}$ is a partition of $\mathcal{S}$.

These properties shall be referred to in the rest of the argument.

Step 2: Pick an arbitrary $S_{j}\in\mathcal{A}_{j}$ for every
$j\in\mathbb{N}$. This generates a sequence of sequences
$(S_{1},S_{2},\ldots)$ such that the stopping time for each $S_{j}$ is
$k_{j}$. Now, we construct a subsequence of this sequence
$(\bar{S}_{1},\bar{S}_{2},\ldots)$ that “converges" to some
$S^{*}\in\mathcal{S}$. We do this inductively i.e. we show that for any
$N\in\mathbb{N}$, there exists infinitely many sequences
$(S_{N_{1}},S_{N_{2}},\ldots)$ in $(S_{1},S_{2},\ldots)$ that “agree" on the
first $N$ terms. For the base case, note that since $X$ is finite, there must
exist at least one alternative in $X$ that appears in the first position in
infinitely many terms of the sequence $(S_{1},S_{2},\ldots)$ i.e. in
infinitely many sequences. There may be multiple such terms. We pick any one
arbitrarily. Consider all such sequences which have the same first term. This
forms a subsequence of $(S_{1},S_{2}\ldots)$. We can write this subsequence as
$(S_{11},S_{12},\ldots)$ where $S_{1i}=S_{m_{i}}$ for some $m_{i}\geq i$. Note
that all sequences in $(S_{11},S_{12}...)$ have the same first term. Let
$\bar{S}_{1}=S_{11}$. For the inductive step, suppose we have found out a
subsequence $(S_{k1},S_{k2},\ldots)$ of $(S_{(k-1)1},S_{(k-1)2},\ldots)$ (and
consequently of $(S_{1},S_{2},\ldots)$) such that all sequences (i.e. terms)
in the subsequence “agree" on the first $k$ terms. Let $\bar{S}_{k}=S_{k1}$.
Now, to show that it must be true for $k+1$ i.e. we can find a subsequence of
$(S_{k1},S_{k2},\ldots)$ such that all sequences agree on the first $k+1$
terms, note that since $X$ is finite, there must exist at least one
alternative in $X$ that occurs at the $(k+1)^{th}$ position in infinitely many
sequences i.e. infinitely many terms of $(S_{k1},S_{k2},\ldots)$. Let that
subsequence be $(S_{(k+1)1},S_{(k+1)2},\ldots)$ and
$\bar{S}_{k+1}=S_{(k+1)1}$. Therefore, we have shown that there exists a
subsequence $(\bar{S}_{1},\bar{S}_{2},\ldots)$ of $(S_{1},S_{2},\ldots)$ such
that for any $k\in\mathbb{N}$, we have

$\bar{S}_{k}|_{k}=\bar{S}_{j}|_{k}\ \ \forall\ j\geq k$

Therefore $(\bar{S}_{1},\bar{S}_{2},\ldots)$ is a convergent subsequence that
converges to some $S^{*}\in\mathcal{S}$.

Step 3: Since $d$ is a stopping rule, there must exist $k^{*}\in\mathbb{N}$
such that

$d(S^{*})=d(S^{*}|_{k^{*}}.T)\ \ \forall\ \ T\in\mathcal{S}$ (1)

Note that we can write $(\bar{S}_{1},\bar{S}_{2}\ldots)$ as
$(S_{11},S_{21},\ldots)$ such that $S_{i1}=S_{n_{i}}$ for some $n_{i}\geq i$
where each $S_{n_{i}}$ is an element of the initial sequence
$(S_{1},S_{2},\ldots)$ for all $i\in\mathbb{N}$. Consider $n_{i}>k^{*}$. Note
that by construction, $S_{n_{i}}\in\mathcal{A}_{n_{i}}$ i.e. for any
$k<n_{i}$, there exists some $T^{\prime}\in\mathcal{S}$ such that
$d(S_{n_{i}})\neq d(S_{n_{i}}|_{k}.T^{\prime})$. Let $k=k^{*}$. We know that
$S_{n_{i}}|_{k^{*}}=S^{*}|_{k^{*}}$ which implies that
$S_{n_{i}}=S^{*}|_{k^{*}}.T"$, where $T"\in\mathcal{S}$ and
$T"(i)=S_{n_{i}}(k^{*}+i)$ for all $i\in\mathbb{N}$. By (1), we know that
$d(S^{*})=d(S_{n_{i}})$. However, since $d(S_{n_{i}})\neq
d(S_{n_{i}}|_{k}^{*}.T^{\prime})$ for some $T^{\prime}\in\mathcal{S}$ , we get

$d(S_{n_{i}}|_{k^{*}}.T^{\prime})=d(S^{*}|_{k^{*}}.T^{\prime})\neq d(S^{*})$

which contradicts (1). So, there does not exist $k^{*}\in\mathbb{N}$ such that
(1) holds i.e. there is no finite stopping time for the sequence $S^{*}$, a
contradiction to $d$ being a stopping rule. Therefore our supposition is wrong
and $d$ must be a uniform-stopping rule. ∎

Stopping rules —and consequently uniform stopping rules—serve a dual purpose
in our framework. First, they encompass various notions of bounded
rationality. For instance, they capture the notion of bounded attention. The
finite upper bound on the stopping times can be interpreted as the attention
span of the DM within which she makes her decision. Alternatively, the
“relevant" finite initial segment of a given input sequence can be thought of
as a consideration set or a shortlisted set that the DM considers before
making the decision. Second, since the set of alternatives is assumed to be
finite, the equivalence of stopping and uniform-stopping rules enables us to
provide testable restrictions to characterize specific subclasses of stopping
decision rules. In section 4, we introduce some natural subclasses of stopping
rules and introduce some useful concepts that form the basis of their
axiomatic characterization.

##  3 Computability

A natural constraint on decision making is the limited information processing
capability of DMs. While the standard notion of rationality assumes no such
constraints, there are a variety of settings where the assumption of infinite
processing capabilities is an unrealistic one. The theories of individual
decision-making have incorporated such constraints by modelling the decision
maker as a finite information-processing device. For instance, [Kramer
(1967)], shows that when the DM suffers from computational constraints, it is
impossible to display fully rational behavior. While modelling the decision
maker as a finite information-processing device, much of the literature has
resorted to the finite automaton model (see [Salant (2003)], among others).
However, a more general model of computation is that of the Turing machine.
[Richter and Wong (1999)] define the computability of preferences using a
Turing machine. More recently, [Camara (2021)] has modelled the DM as a Turing
machine and examined the computational tractability of choice under
uncertainty.

Our framework also allows us to study computable aspects of decision making.
We study the implementation of a decision rule using Turing machines and
finite automaton. We first formally define a Turing machine.

######  Definition 4.

A Turing machine is a tuple $TM=(Q,\Sigma,\delta)$, where $Q$ is a finite set
of states, $\Sigma$ is a finite set of symbols called the alphabet and
$\delta:Q\times\Sigma^{2}\to Q\times\Sigma\times\\{L,S,R\\}^{2}$ is a
transition function

Our formulation of a Turing machine contains two tapes which are infinite one
directional line of “cells". We denote the two tapes as input and output
tapes. Each tape is equipped with a tape head. The tape head of the input tape
reads the symbols on the tape one cell at a time whereas the tape head of the
output tape can potentially write symbols to the tape one cell at a time. Both
the tapes contain $\triangleleft\in\Sigma$ in its first position, the start
symbol that initializes the machine. It contains a “register" that holds a
single element of $Q$ at a time with the intial state being $q_{0}$. The
transition function maps the current state and the symbol on the current
entries of the tapes to a new state and instructions for the heads. The input
head can move to the next entry of the tape, or move to the previous entry of
the tape, or stay in case a terminal state is reached. The machine stops when
a terminal state is reached and the output of the machine, denoted by $TM(I)$
where $I$ is the input sequence, is the entry under head on the output tape.
Let $\mathcal{I}$ denote a set of possible inputs and $TM_{\mathcal{I}}$ be
any Turing machine that stops in finite time for all $I\in\mathcal{I}$ i.e.
for every $I\in\mathcal{I}$, $TM(I)$ is computed in finite number of steps.
Using this notion of a Turing machine, a computable rule is defined as
follows.

######  Definition 5.

A decision rule $d$ is computable, if there exists a Turing machine
$TM_{\mathcal{S}}$ such that $d(S)=TM(S)$ for all $S\in\mathcal{S}$

Next, we define the notion of automaton-computability using a finite
automaton. A finite automaton is formally defined as follows.

######  Definition 6.

A finite automaton is a tuple $A=(Q,\Sigma,\delta)$ where $Q$ is a finite set
of states, $\Sigma$ is a finite set of symbols called the input alphabet and
$\delta:Q\times\Sigma\to Q$ is a transition function.

An automaton starts in an initial state $q_{0}\in Q$ and reads elements of
$\Sigma$ one at a time (in some order). For every input element and the
current state, the transition function determines the next state of the
automaton. Within the set of states are the terminal or absorbing states,
denoted by $F$. Once the automaton enters one of these states, it remains in
that state irrespective of the subsequent inputs. [Salant (2011)] describes
implemention of a choice function on lists using an automaton with an output
function. It reads the elements of a list in order and stops either at end of
the list or at some intermediate step, depending on the choice function it is
implementing. Once it reaches its terminal state i.e. it stops, the output
function determines the decision from the decision space (which is the set of
alternatives appearing in the list). In our framework, we can denote such an
automaton by $A_{O}$ where for every input sequence, a terminal state is
reached in finite number of steps and $O:F\to Y$ is the output function
mapping terminal states to a decision. Using this, we can define
implementablilty of a decision rule on sequences by an automaton in a fairly
straightforward manner

######  Definition 7.

A decision rule $d$ is automaton-computable if there exists an automaton
$A_{O}$ such that for any input $S\in\mathcal{S}$, the output generated by it
is $d(S)$.

Our notions of computable and automaton-computable rules are closely linked to
stopping and uniform stopping rules. Upon closer examination, one can see that
if a decision rule is computable, then it must be a stopping rule. This is
because of the fact that since for every input $S$, the Turing machine halts
in finite time i.e. after observing a finite initial segment. The sequence
beyond this halting point is irrelevant for the output and hence it
corresponds to $k_{d}(S)$ of that input. On the other hand, it is easy to see
that uniform stopping rules are implementable using a finite automaton. Our
main result therefore establishes the equivalence of computable and automaton-
computable rules as well.

######  Corollary 1.

A decision rule is computable if and only if it is automaton-computable

The above equivalence collapses when we admit only finite inputs of i.e.
finite segments of arbitrary length as against infinite sequences. Consider
the following example from: Let $X=\\{a,b,\emptyset\\}$,
$Y=\\{\text{yes},\text{no}\\}$ and $\mathcal{S}$ be the set of all finite
strings that comprise of $a$ and $b$ with the last element being $\emptyset$
(indicating the end of the segment). The decision rule outputs “yes" for any
$S\in\\{a^{n}b^{n}\emptyset:n\in\mathbb{N}\\}$ i.e. any segment that comprises
of $n$ number of $a^{\prime}$s followed by $n$ number of $b^{\prime}$s for any
$n\in\mathbb{N}$ and it outputs “no" otherwise. Such a decision rule can be
implemented using a Turing machine. However, it cannot be implemented by a
finite automaton.

##  4 Choice Rules and Satisficing

An important subclass of decision rules are choice rules. As discussed
earlier, since the decision space is restricted to be the set of alternatives,
these can be thought of as the analogue of choice functions over lists and
choice function over sets. These are formally defined as

######  Definition 8.

A decision rule is a choice rule if $d(S)=S(i)$ for some $i\in\mathbb{N}$ and
for all $S\in\mathcal{S}$

Now, we will characterize the class of stopping choice rules. As it turns out,
the only condition we require is continuity with respect to the the discrete
topology on $X$ and the induced product topology defined on the set of all
sequences111This result goes through even when the decision space is some
finite set $Y$. The product topology here has a behavioral interpretation. It
says that a DM considers two sequences “close" or “similar" if their initial
segments are the same. Continuity of the choice rule then implies that she
cannot display “jumps" in choices for close enough choice problems. This
translates into the observation that after a certain finite segment has been
observed by the DM, the “tail" of a sequence cannot affect the choice.

######  theorem 2.

Assume $\mathcal{S}$ and $X$ are endowed with the product topology and the
discrete topology respectively. Then, a choice rule $d:\mathcal{S}\to X$ is a
stopping rule if and only if it is continuous.

###### Proof.

First, we show what the product topology on $\mathcal{S}$ looks like. We know
that $\Pi_{\mathcal{S}}$, the product topology, is the smallest topology with
respect to which the projection maps are continuous. Consider any map
$M:\\{1,\dots,N\\}\to X$ where $N\in\mathbb{N}$ and define the set $B(M)$ as:

$B(M)=\\{S\in\mathcal{S}:\ \text{for all}\ i\in\\{1,\dots,N\\},\ S(i)=M(i)\\}$

Let $\mathcal{B}_{\mathcal{S}}$ be the class of all such sets. Note that a for
any $N\in\mathbb{N}$, the number of possible maps $M:\\{1,\ldots N\\}\to X$ is
$|X|^{N}$. These sets are what can be interpreted as “open balls" in
$\mathcal{S}$. Let $\mathscr{T}_{\mathcal{S}}$ be the class of unions of
arbitrary subcollections of $\mathcal{B}_{\mathcal{S}}$.

######  Lemma 1.

$\mathscr{T}_{\mathcal{S}}$ is the product topology on $\mathcal{S}$

###### Proof.

First, we show that $\mathscr{T}_{\mathcal{S}}$ is indeed a topology over
$\mathcal{S}$. Notice that $\mathscr{T}_{\mathcal{S}}$ is closed under
arbitrary unions by definition. To show that it is closed under finite
intersections, let $\bigcap_{i=1}^{K}B_{i}$ be a finite intersection such that
$B_{i}\in\mathscr{T}_{\mathcal{S}}$ for all $i\in\\{1,\ldots K\\}$. Note that
each $B_{i}$ is a union of some subcollection of $\mathcal{B}_{\mathcal{S}}$
and therefore we can write
$B_{i}=\bigcup_{j_{i}\in\mathcal{J}_{i}}B_{i}^{j_{i}}$, with $\mathcal{J}_{i}$
being some indexed set, where each $B_{i}^{j_{i}}$ corresponds to an “open
ball" i.e. is a set of the form $B(M)$ for some $M:\\{1,\ldots,N\\}\to X$ and
$N\in\mathbb{N}$. Using the definition of $B(M)$, we know that there exist
sets $A_{1}^{i},A^{i}_{2}\ldots$ with $A^{i}_{j}\subseteq X$ for all
$j\in\mathbb{N}$ such that

$B_{i}=\\{S\in\mathcal{S}:\ \text{for all}\ j\in\mathbb{N},S(j)\in
A^{i}_{j}\\}$

So, we can write $\bigcap_{i=1}^{K}B_{i}$ as

$\bigcap_{i=1}^{K}B_{i}=\\{S\in\mathcal{S}:\ \text{for all}\
j\in\mathbb{N},S(j)\in\bigcap_{i=1}^{K}A^{i}_{j}\\}$

Clearly, $\bigcap_{i=1}^{K}B_{i}=\bigcup_{M\in\mathcal{M}_{i}}B(M)$ for some
collection of maps $\mathcal{M}_{i}$. Therefore, $\mathscr{T}_{\mathcal{S}}$
is closed under finite intersection. Finally, $\mathscr{T}_{\mathcal{S}}$
contains $\mathcal{S}$ and $\varnothing$ as its elements. That
$\varnothing\in\mathscr{T}_{\mathcal{S}}$ holds follows from the fact that
$\varnothing$ is the union of elements from the empty subcollection of
$\mathcal{B}_{\mathcal{S}}$. Further, $\mathcal{S}$ is the union of elements
from the full collection $\mathcal{B}_{\mathcal{S}}$. Thus,
$\mathscr{T}_{\mathcal{S}}$ is a topology over $\mathcal{S}$.
Now, we argue: $\Pi_{\mathcal{S}}\subseteq\mathscr{T}_{\mathcal{S}}$. For
this, fix an arbitrary $i_{\ast}\in\mathbb{N}$ and $A\subseteq X$. If
$A=\varnothing$, then $\pi_{i_{\ast}}^{-1}(A)=\varnothing$. As
$\varnothing\in\mathscr{T}_{\mathcal{S}}$,
$\pi_{i_{\ast}}^{-1}(A)\in\mathscr{T}_{\mathcal{S}}$ if $A=\varnothing$.
However, if $A\neq\varnothing$, then observe:

$\pi_{i_{\ast}}^{-1}(A)=\bigcup\big{\\{}B(M):M\in
X^{\\{1,\ldots,i_{\ast}\\}}\;;\;M(i_{\ast})\in A\big{\\}}.$

Thus, if $A\neq\varnothing$, then
$\pi_{i\ast}^{-1}(A)\in\mathscr{T}_{\mathcal{S}}$. That is,
$\pi_{i}^{-1}(A)\in\mathscr{T}_{\mathcal{S}}$ for every $A\subseteq X$. Hence,
$\\{\pi_{i}^{-1}(A):i\in\mathbb{N}\;;\;A\subseteq
X\\}\subseteq\mathscr{T}_{\mathcal{S}}$ and we have already shown that
$\mathscr{T}_{\mathcal{S}}$ is a topology over $\mathcal{S}$. Further, by
definition, $\Pi_{\mathcal{S}}$ is the smallest topology that satisfies
$\\{\pi_{i}^{-1}(A):i\in\mathbb{N}\;;\;A\subseteq X\\}\in\Pi_{\mathcal{S}}$.
Therefore, we obtain: $\Pi_{\mathcal{S}}\subseteq\mathscr{T}_{\mathcal{S}}$.
Finally, we argue: $\mathscr{T}_{\mathcal{S}}\subseteq\Pi_{\mathcal{S}}$. For
this, fix an arbitrary $I\in\mathbb{N}$ and consider an arbitrary map
$M:\\{1,\ldots,I\\}\rightarrow X$. For each $i\in\\{1,\ldots,I\\}$, let
$A_{i}\coloneqq\\{M(i)\\}$. Then, we have the following:

$B(M)=\bigcap\big{\\{}\pi_{i}^{-1}(A_{i}):i=1,\ldots,I\big{\\}}.$

Since $\Pi_{\mathcal{S}}$ is a topology and
$\\{\pi_{i}^{-1}(A):i\in\mathbb{N}\;;\;A\subseteq
X\\}\subseteq\Pi_{\mathcal{S}}$, it follows that $B(M)\in\Pi_{\mathcal{S}}$.
Thus, $\Pi_{\mathcal{S}}$ is a topology over $\mathcal{S}$ such that
$\mathcal{B}_{\mathcal{S}}\subseteq\Pi_{\mathcal{S}}$. Moreover,
$\mathscr{T}_{\mathcal{S}}$ is the smallest topology over $\mathcal{S}$ such
that $\mathcal{B}_{\mathcal{S}}\subseteq\mathscr{T}_{\mathcal{S}}$. Hence, we
conclude: $\mathscr{T}_{\mathcal{S}}\subseteq\Pi_{\mathcal{S}}$.
∎

Now to show $d$ is a stopping rule if and only if it is continuous, first,
assume that $d:\mathcal{S}\rightarrow X$ is continuous. Fix an arbitrary
$S_{\ast}\in\mathcal{S}$ and let $y_{S_{\ast}}\coloneqq d(S_{\ast})$. Now, we
know that $\\{y_{S_{\ast}}\\}$ is open in the discrete topology over $X$. By
continuity of the map $d$, the following set:

$d^{-1}(\\{y_{S_{\ast}}\\})\coloneqq\\{S\in\mathcal{S}:d(S)=y_{S_{\ast}}\\}$

satisfies $d^{-1}(\\{y_{S_{\ast}}\\})\in\Pi_{\mathcal{S}}$. By the lemma above
and the definition of $\mathscr{T}_{\mathcal{S}}$, there exists
$M:\\{1,\ldots,k\\}\rightarrow X$ such that $S_{\ast}\in B(M)\subseteq
d^{-1}(\\{y_{S_{\ast}}\\})$. Now, $S_{\ast}\in B(M)$ implies:
$M=S_{\ast}|_{k}$ and $B(M)=\\{S_{\ast}|_{k}\cdot T:T\in\mathcal{S}\\}$. Since
$B(M)\subseteq d^{-1}(\\{y_{S_{\ast}}\\})$, it follows: $d(S_{\ast}|_{k}\cdot
T)=y_{S_{\ast}}$ for all $T\in\mathcal{S}$. Since $y_{S_{\ast}}=d(S_{\ast})$
and $S_{\ast}$ was arbitrary, we have established: if the map
$d:\mathcal{S}\rightarrow X$ is continuous, then it is a stopping rule.
Now, assume that $d:\mathcal{S}\rightarrow X$ is a stopping rule. Since $X$
has the topology $2^{X}$, we must argue that
$d^{-1}(A)\coloneqq\\{S\in\mathcal{S}:d(S)\in A\\}\in\Pi_{\mathcal{S}}$ for
any $A\subseteq X$. Since $d^{-1}$ preserves arbitrary unions and
$\Pi_{\mathcal{S}}$ is closed under arbitrary unions, it is enough to argue
that $d^{-1}(\\{y\\})\in\Pi_{\mathcal{S}}$ for any $y\in X$. So, fix an
arbitrary $y_{\ast}\in X$. If $d^{-1}(\\{y_{\ast}\\})=\varnothing$, then we
have nothing more to argue as $\varnothing\in\Pi_{\mathcal{S}}$. Hence, assume
that $d^{-1}(\\{y_{\ast}\\})\neq\varnothing$. Consider an arbitrary
$S_{\ast}\in d^{-1}(\\{y_{\ast}\\})$. Since $d$ is a stopping rule, there
exists $k(S_{\ast})\in\mathbb{N}$ such that: $d(S)=y_{\ast}$ for every $S\in
B(S_{\ast}|_{k(S_{\ast})})$. This is because
$B(S_{\ast}|_{k(S_{\ast})})=\\{S_{\ast}|_{k(S_{\ast})}\cdot
T:T\in\mathcal{S}\\}$. Thus, we have:

$\bigcup\big{\\{}B(S|_{k(S)}:S\in
d^{-1}(\\{y_{\ast}\\}))\big{\\}}=d^{-1}(\\{y_{\ast}\\}).$

Hence, $d^{-1}(\\{y_{\ast}\\})\in\mathscr{T}_{\mathcal{S}}$ by definition of
$\mathscr{T}_{\mathcal{S}}$. By the lemma above, it follows that
$d^{-1}(\\{y_{\ast}\\})\in\Pi_{\mathcal{S}}$. Since $y_{\ast}\in Y$ was
arbitrary, we have: $d^{-1}(A)\in\Pi_{\mathcal{S}}$ for any $A\in 2^{X}$.
Thus, if the $D:\mathcal{S}\rightarrow X$ is a stopping rule, then it is
continuous. ∎

###  4.1 Satisficing Rules

Satisficing, first introduced by Herbert Simon (see [Simon (1955)]), has been
a hugely influential model of decision making and has been studied widely in
the literature (see [Kovach and Ülkü (2020)], [Aguiar et al. (2016)], [Tyson
(2015)] and [Papi (2012)], among others). Satisficing behavior incorporates
search of the DM until a “good enough” alternative is observed. While some
existing models endogenize the search order of the DM (see [Aguiar et al.
(2016)]), others treat it as observable in the form of a list and vary the
threshold (see [Kovach and Ülkü (2020)]). In this section, we propose two
models similar in spirit and provide their behavioral characterization.

####  4.1.1 Preliminaries

There is a large literature on limited attention and a variety of modeling
approaches have been used (see [Masatlioglu et al. (2012)], [Caplin and Dean
(2015)] and [Manzini and Mariotti (2014)]). As mentioned in the above section,
our notion of stopping rules also indicate a limited attention span of the DM.
From the informational aspect of decision making, we argue that there exists a
point by which the DM makes up her mind regarding what to choose. We capture
this idea using the concepts of sufficiency and minimal sufficiency of finite
segments in a sequence. Let $\mathcal{S}_{k}$ be the set of all segments of
length $k$. Then we define a sufficient segment as follows

######  Definition 9.

A segment $M\in\mathcal{S}_{m}$ is sufficient if $d(M.T)=d(M.T^{\prime})$ for
all $T,T^{\prime}\in\mathcal{S}$

The intuitive content of the above definition is as follows. As the DM faces a
sequence $S\in\mathcal{S}$, there comes a point $k\in\mathbb{N}$ when the
segment $S|_{k}$ has enough information for the decision maker to have made up
her mind about the choice i.e. $S|_{k}$ is informationally “sufficient" to
enforce a decision. However, the acquired information will not be sufficient
until a certain point in time. This motivates the notion of minimal
sufficiency. Formally,

######  Definition 10.

A segment $M\in\mathcal{S}_{m}$ is minimal sufficient if it is sufficient and
for any $k<m$, $M|_{k}$ is not sufficient

Minimal sufficiency captures the idea of “critical" length of a segment to
enforce a decision. By critical, we mean that if the segment is smaller than
that length, it can no longer guarantee the same choice irrespective of the
tail. Note that the definition of stopping rules indicates that every sequence
must have a corresponding minimal sufficient segment that “implements" the
choice. Let us denote the class of sufficient and minimal sufficient segments
as $\mathbb{S}$ and $\mathbb{MS}$ respectively. If $M=S|_{k}$ for some
$k\in\mathbb{N}$ and $M\in\mathbb{S}\cup\mathbb{MS}$, then we will abuse
notation and denote the choice of $S$ by $d(M)$ i.e. $d(S)=d(M)$. Also denote
by $M(X)$ the set of alternatives that appear in the segment in $M$.

To illustrate the idea of sufficiency and minimal sufficiency, let us consider
Example 2 of the introduction. Let $X=\\{a,b,c\\}$ and $s(a)=s(b)=s(c)=1$.
Suppose the DM has a threshold value of 3 and consider the sequence $S=(a\ b\
c\ a\ b\ c..)$ i.e. it consist of “cycles" of alternatives $a$, $b$ and $c$.
Here, the minimal sufficient segment is of length 7 i.e. where $a$ is the
first alternative to appear 3 times. Any segment of length less than 7 is not
minimal sufficient and any segment of length more than 7 is sufficient.

####  4.1.2 Cardinal Satisficing

We formalize the idea of Example 2 and equip the DM with two objects. The
first one is a weight function $w:X\to\mathbb{R}_{+}$ that assigns a number to
every alternative. The weights can be thought of as some scores the DM assigns
to the alternatives that are indicative of the relative importance of
alternatives. For instance, a DM may give a higher score to “action" movies
over the ones belonging to the genre “drama". The second object that the DM is
endowed with is a threshold number $v\in\mathbb{R}_{+}$. The threshold can be
thought of as the satisficing component or the cutoff that the DM uses to make
decisions. In what we term as the Cardinal Satisficing Rule (CSR), the DM
parses through a sequence and selects the first alternative whose “cumulative"
weight crosses the threshold. Since in this heuristic, the “intensity" of the
weights can affect the choice, it is termed as “cardinal". For any given
sequence $S\in\mathcal{S}$ and a position $N\in\mathbb{N}$, we define the
cumulative weight of an alternative $x$ as

$W^{N}_{S}(x)=|\\{i\in\\{1,\ldots N\\}:S(i)=x\\}|.w(x)$

Now, we can define CSR formally as follows

######  Definition 11.

A stopping rule $d$ is a Cardinal Satisficing Rule if there exists
$v\in\mathbb{R}_{+}$ and $w:X\to\mathbb{R}_{+}$ such that for any
$S\in\mathcal{S}$,

$d(S)=\\{x:W^{N}_{S}(x)\geq v>W^{N}_{S}(y)\\}$

for all $y\neq x$ and some $N\in\mathbb{N}$

Before we state our axioms, we will introduce two concepts: favorable deletion
and favorable shift. For any sequence $S\in\mathcal{S}$ and $k\in\mathbb{N}$,
let $\hat{S}^{k}\in\mathcal{S}$ be the sequence which is defined as follows:

$\hat{S}^{k}(i)\coloneqq\begin{cases}S(k+1)&\text{ if }i=k;\\\ S(k)&\text{ if
}i=k+1;\\\ S(i)&\text{ otherwise.}\end{cases}$

That is, the sequence $\hat{S}^{k}$ is obtained from $S$ by interchanging its
$k^{th}$ and $k+1^{th}$ elements. We call $\hat{S}^{k}$ a favorable shift of
$S$ with respect to an alternative $x$ if $S(k+1)=x$.

For any $S\in\mathcal{S}$ and $k\in\mathbb{N}$ define $\tilde{S}^{k}$ as

$\tilde{S}^{k}(i)\coloneqq\begin{cases}S(i)&\text{ if }i<k;\\\ S(i-1)&\text{
if }i>k\end{cases}$

The sequence $S^{k}$ is obtained from $S$ by dropping the alternative located
at the $k^{th}$ position. We call $\tilde{S}^{k}$ as a favorable deletion $S$
with respect to an alternative $x$ if $S(k)\neq x$. The notions of favorable
shift and favorable deletion with respect to an alternative capture the idea
of bringing it “closer" to the DM. In other words, lowering the position in
which an alternative appears in a sequence is considered as “favorable" for
it.

Let the class of all favorable shifts of $S$ with respect to $x$ be denoted by
$\mathcal{FS}(S,x)$. Further, the class of all favorable deletions of $S$ with
respect to $x$ be denoted by $\mathcal{FD}(S,x)$. For any $S\in\mathcal{S}$
and $x\in X$, a favorable transformation of $S$ with respect to $x$ is any
favorable shift or favorable deletion. The class of all favorable
transformations of $S$ with respect to $x$ shall be denoted by
$\mathcal{F}(S,x)$. Therefore,
$\mathcal{F}(S,x)=\mathcal{FS}(S,x)\cup\mathcal{FD}(S,x)$ by definition. Now,
we are ready to state the axioms that characterize CSR.

####  4.1.3 Axioms

Our characterization of CSR relies upon two axioms. Our first axiom is an
adaptation of the idea of monotonicity to the setting of sequences.

######  Axiom 1 (Monotonicity).

Let $S\in\mathcal{S}$ and $d(S)=x$. Then $d(S^{\prime})=x$ for all
$S^{\prime}\in\mathcal{F}(S,x)$ .

Intuitively, the axiom captures the idea of primacy effect. It requires the DM
to make the same choice if the chosen alternative is brought “closer" to him
in the sequence i.e. if a new sequence is more favorable for an alternative
that was previously chosen, then it should continue to chosen in the new
sequence. Our second axiom relies on the above defined notions of sufficient
and minimal sufficient segments.

######  Axiom 2 (Informational Dominance).

Let $M\in\mathbb{MS}$ and $N\in\mathbb{S}$ such that $d(M)=x,\ d(N)=z$ and
$x\notin N(X)$. Then $d([M|_{k}.N].T)\neq x$ for any $k<m$ and all
$T\in\mathcal{S}$ .

This axiom states that if a minimal sufficient segment $M$ “implements" an
alternative $x$ and another sufficient segment $N$ that does not contain $x$
implements some other alternative $z$, then concatenating any truncation of
$M$ with $N$ prevents $x$ from being chosen. In other words, it asserts that a
sufficient segment not containing an alternative can “dominate" a non-minimal
sufficient segment in an informational sense. To illustrate, consider the
example discussed above. We showed that for a threshold of 3, the minimal
sufficient segment for the sequence $S=(a\ b\ c\ a\ b\ c\ a\ b\ c\ldots)$ is
$M=(a\ b\ c\ a\ b\ c\ a)$. Consider another sequence $S^{\prime}=(b\ b\ c\ b\
b\ c\ldots)$. It is easy to see that the segment $N=(b\ b\ c\ b\ b)$ is
sufficient. Informational dominance says that for any sequence which contains
any truncation of $M$ concatenated with the segment $N$ as its initial
segment, the choice cannot be equal to $a$. Now, we are ready to state our
result.

a x w . . . . $M=$ b c z . . . . $N=$ a x w . . . . b c z . . . . $M|_{k}.N=$
Figure 2: Informational Dominance

######  theorem 3.

A stopping choice rule $d$ is a Cardinal Satisficing Rule if and only if it
satisfies Monotonicity and Informational Dominance

###### Proof.

(Necessity): Given a a choice function is a Cardinal Satisficing Rule, we know
that there exists a $v\in\mathbb{R}_{+}$ and $w:X\to\mathbb{R}_{+}$ such that
for any $S\in\mathcal{S}$, we have $d(S)=\\{x:W^{N}_{S}(x)\geq
v>W^{N}_{S}(y)\\}$ for some $N\in\mathbb{N}$ and for all $y\neq x$. To show it
satisfies Monotonicity consider any $S$ and its favourable deletion with
respect to $d(S)$, say $S^{\prime}$. Let $N_{1}\in\mathbb{N}$ be the position
of $S$ where $W^{N_{1}}_{S}(d(S))\geq v>W^{N}_{S}(y)$ for all $y\neq d(S)$.
Note that $S^{\prime}$ is generated by “deleting" a term of $S$ that is not
equal to $d(S)$, for $N_{2}=N_{1}-1$ we have $W^{N_{2}}_{S}(d(S))\geq
v>W^{N}_{S}(y)$ for all $y\neq d(S)$ and therefore $d(S^{\prime})=d(S)$. By
similar argument, we can see that $d(S)=d(S^{\prime})$ where $S^{\prime}$ is a
favorable shift of $S$ with respect to $d(S)$. To show that $d$ satisfies
Informational Dominance, consider a minimal sufficient segment $M$ of length
$m$ such that $d(M)=x$ and a sufficient segment $N$ of length $n$ such that
$d(N)=y$ and $x\notin N(X)$. Assume for contradiction $d([M|k.N].T)=x$ for
some $k<m$. Then there exists $N_{1}\in N$ such that $W^{N_{1}}_{T}(x)\geq
v>W^{N}_{S}(y)$. Note that since $M|k$ is not minimal suffcient and $x\notin
N(X)$, we must have $N_{1}>k+n$. But, since the segment $N$ is sufficient, we
must have $W^{N_{2}}_{S}(y)\geq v$ for some $N_{2}<N_{1}$, a contradiction.

(Sufficiency): Let $d$ be a stopping rule that satisfies Monotonicity and
Informational Dominance. First, we construct the “revealed" critical frequency
of each alternative. Fix $x\in X$. Note that $x$ is chosen from the constant
sequence $S^{x}=(x,x\ldots)$ i.e. $d(S^{x})=x$. Now, by the definition of a
stopping rule, there exists $k\in\mathbb{N}$ such that
$d(S^{x})=d([S^{x}|_{k}].T)$ for all $T\in\mathcal{S}$. Let
$n_{x}=\inf\\{k:d(S^{x})=d(S^{x}|_{k})\\}$. Since $\mathbb{N}$ is well
ordered, we know that $n_{x}\in\mathbb{N}$.

Consider any non-constant sequence $S$ such that $d(S)=x$ (we do not need to
prove anything for the case of constant sequences). Denote by
$\\#x(S|_{i})=|\\{j\in\\{1,\ldots,i\\}:[S|_{i}](j)=x\\}|$, i.e. the number of
appearances of $x$ in a segment $S|_{i}$ of $S$. Now, denote by
$i(S,a)=\\{i\in\mathbb{N}:\\#a(S|_{i})=n_{a}\\}$ i.e. the position at which an
alternative $a$ reaches $n_{a}$ appearances in $S$. We show that
$i(S,x)<i(S,y)$ for all $y\neq x$. Assume for contradiction that
$i(S,y)<i(S,x)$ for some $y\neq x$. Let $S^{\prime}$ be a sequence generated
from $S$ by deleting all the first terms in the first $i(S,x)$ positions that
are not equal to $x$ or $y$ i.e. finitely many favorable deletions with
respect to $x$ and $y$. By Monotonicity, $d(S^{\prime})=x$. Note that first
$i(S^{\prime},x)$ terms contain $n\geq n_{y}$ number of $y$’s and $n_{x}$
terms of $x$’s ($n+n_{x}=i(S^{\prime},x)$ ). Now, consider finitely many
favourable shifts of $S^{\prime}$ with respect to $x$ to generate
$S^{\prime\prime}$ such that its first $n_{x}$ terms are all $x$ followed by
$n$ terms that are $y$. Again, by Monotonicity, we have
$d(S^{\prime\prime})=x$.

Denote this segment of $y$’s as $N$ and the segment of $x$’s as $Mx$ where $M$
is $(n_{x}-1)$ long segment of $x$’s. So, we can write
$S^{\prime\prime}=[Mx.N].T$ where $T\in\mathcal{S}$ and
$T(j)=S(i(S^{\prime},x)+j)$ for all $j\in\mathbb{N}$. By the definition of
$n_{x}$ we know that there exists some $T\in\mathcal{S}$ such that $d(M.T)\neq
x$. Also, by the definition of $n_{y}$, we know that $d(N.T)=y$ for all
$T\in\mathcal{S}$. In other words, $Mx$ is a minimal sufficient segment and
$N$ is a sufficient segment. Using Informational Dominance, we know that
$d(MNxT)\neq x$ for all $T\in\mathcal{S}$. It must be that $d(MNxT)=y$ for all
$T\in\mathcal{S}$. Suppose not i.e. $d(MNxT)=z$ for some $z\neq x,y$ and
$T\in\mathcal{S}$. Then, by Monotonicity, it must be that $d(NxT)=z$, a
contradiction since $N$ contains $n_{y}$ first $y$’s. Therefore $d(MNxT)=y$
for all $T\in\mathcal{S}$. Now, notice that we can generate the earlier
sequence $S^{\prime}$ by successively moving $y$’s to the left i.e. a finitely
many favourable shifts with respect to $y$ and by Monotonicity, we must have
$d(S^{\prime})=y$, a contradiction. Therefore $i(S,x)<i(S,y)$.

Let $v=1$ and $w(x)=\frac{1}{n_{x}}$ for all $x\in X$. Consider a stopping
rule $d^{*}$ such that $d^{*}(S)=\\{x:W^{N}_{S}(x)\geq v>W^{N}_{S}(y)\\}$ for
all $S\in\mathcal{S}$. We will show that $d^{*}$ and $d$ coincide. Consider
any arbitrary $S\in\mathcal{S}$ and let $d(S)=z$. We know that $i(S,z)<i(S,y)$
for all $y\neq z$. Let $i(S,z)=N$. By construction, we know that
$W_{S}^{N}(z)\geq v>W_{S}^{N}(y)$ for all $y\neq z$ and therefore
$d^{*}(S)=z$. Since $S$ was chosen arbitrarily, we have shown that $d^{*}=d$.
∎

####  4.1.4 Ordinal satisficing

In this section we introduce another variation of satisficing which we term
ordinal satisficing. We use the term “ordinal" because the DM in this model is
endowed with a strict preference ordering $\succ$ over the set of
alternatives, $X$. She has a threshold alternative, say $a^{*}\in X$ that
reflects the satisficing component. For any sequence, she considers a fixed
number of alternatives—her bounded attention span—and picks the first
alternative that is ranked above $a^{*}$. If no such alternative exists in her
attention span, she chooses the $\succ$-maximal element among the alternatives
considered. This is in contrast with the satisficing model discussed in
[Rubinstein (2012)] where a DM chooses the last alternative from the list if
it contains no alternative ranked above the threshold. To illustrate, consider
an example where $X=\\{a,b,c\\}$ with $a\succ b\succ c$, $a^{*}=b$ and $k=2$.
For the sequence $S=(b\ c\ a\ a\dots)$, the choice is $b$ whereas the choice
from the sequence $S^{\prime}=(a\ b\ c\ c\ldots)$ is $a$. Now, we formally
define the heuristic.

######  Definition 12.

A choice rule $d$ is a Ordinal Satisficing Rule (OSR) if there exists
$(\succ,a^{*},k)$ with $a^{*}\in X$, $\succ$ a linear order222A linear order
is an asymmetric, complete and transitive binary relation. over $X$ and
$k\in\mathbb{N}$ such that $d(S)=x$ if

  * (i)

If $x\succ a^{*}$ and $x$ is the first such alternative in the first $k$
positions; or

  * (ii)

$x$ is the $\succ$-maximal element in the first $k$ positions

Before we state the axioms, we need to define the concept of a decisive
element.

######  Definition 13.

A set $D\subseteq X$ is the set of decisive alternatives of $X$ if $D=\\{x\in
X:(\forall M\in\mathbb{MS})[x\in X(M)\implies d(M)=x\\}]$. Let
$D^{\prime}=X\setminus D.$

The idea behind a “decisive" alternative is that whenever it is present in a
minimal sufficient segment, it is chosen. Intuitively, it dominates attention
of the DM and enforces its choice. For a given choice function, the set of
decisive alternatives may be empty. However, we will show that in the case of
OSR, it turns out to be non-empty. Further, in the special case where the DM
is an attention-constrained preference maximizer i.e. she chooses the
$\succ$-maximal alternative after viewing a fixed length of alternatives, this
set will be a singleton. Based on the notion of a decisive alternative, we can
partition the set of minimal sufficient segments into ones that contain at
least one decisive alternative and the ones that do not.

######  Definition 14.

$\mathbb{MS_{D^{\prime}}}\coloneqq\\{M\in\mathbb{MS}:X(M)\subseteq
D^{\prime}\\}\\}$ and
$\mathbb{MS_{D}}\coloneqq\mathbb{MS}\setminus\mathbb{MS_{D^{\prime}}}$

####  4.1.5 Axioms

######  Axiom 3 (Replacement).

Let $M\in\mathbb{MS}_{D^{\prime}}$. Consider any
$M^{\prime}=(M\setminus\\{x\\})\cup\\{y\\}$ such that $y\in D^{\prime}$. Then
$M^{\prime}\in\mathbb{S}$.

The above axiom is related to the informational implications of replacing a
non-decisive alternative with another non-decisive alternative. It says that
such a replacement does not affect the informational content of a segment. In
other words, the new segment generated by replacing one alternative retains
its “sufficiency".

######  Axiom 4 (Sequential-$\boldsymbol{\alpha}$).

Consider any $M,M^{\prime}\in\mathbb{MS}_{D^{\prime}}$ such that
$M(X)\subseteq M^{\prime}(X)$ and $d(M^{\prime})\in M(X)$. Then
$d(M^{\prime})=d(M)$.

This axiom is the related to the classic condition-$\alpha$ ([Sen (1969)])
that characterizes rational choice functions on sets. Here, it is restricted
to the sequences that contain only non-decisive alternatives. Intuitively, it
says that if a non-decisive alternative is revealed “superior" to another non-
decisive alternative, then the reverse cannot hold true for those
alternatives.

######  Axiom 5 (Sequential-No Binary Cycles (S-NBC)).

Let $x,y,z\in X$ and
$M,M^{\prime},M^{\prime\prime}\in\mathbb{MS}_{D^{\prime}}$ such that
$X(M)=\\{x,y\\},X(M^{\prime})=\\{y,z\\}$ and $X(M^{\prime\prime})=\\{x,z\\}$.
If $d(M)=x$ and $d(M^{\prime})=y$, then $d(M^{\prime\prime})\neq z$

This is a mild condition related to the no binary cycles condition of [Manzini
and Mariotti (2007)]. It says that the minimal sufficient segments that
contain pairs of alternatives cannot display cycles in choices. Now, we are
ready to state our result.

######  theorem 4.

A stopping choice rule $d$ is an OSR if and only if it satisfies Replacement,
Sequential-$\alpha$ and Sequential-NBC.

###### Proof.

Necessity is easy to establish. So we prove the sufficiency. Suppose $d$
satisfies Replacement, Sequential-$\alpha$ and Sequential NBC. We will use the
following two lemmas in establishing that $d$ is an OSR.

######  Lemma 2.

$|M|=|M^{\prime}|$ for any $M,M^{\prime}\in\mathbb{MS_{D^{\prime}}}$.

###### Proof.

Suppose not. W.L.O.G let $|M|>|M^{\prime}|$. Since $d$ is a stopping rule, $M$
and $M^{\prime}$ are finite. Therefore, the restriction of $M$ to
$|M^{\prime}|$ i.e. $M|_{|M^{\prime}|}$ is also finite. So, we can reach from
$M^{\prime}$ to $M|_{|M^{\prime}|}$ in finite number of “steps" of replacement
i.e. there exists a chain of segments $M_{1},\ldots,M_{n}$ with
$M_{1}=M^{\prime}$ and $M_{n}=M|_{|M^{\prime}|}$ such that $|\\{i:M_{j}(i)\neq
M_{j+1}(i)\\}|=1$ for all $j\in\\{1,\ldots n-1\\}$. In other words $M_{j}$ and
$M_{j+1}$ differ only in one position for all segments in the chain. By
Replacement, we know all the segments in the chain are sufficient and
therefore $M|_{|M^{\prime}|}\in\mathcal{S}$. Since $|M_{|M^{\prime}|}|<|M|$
and $[M|_{|M^{\prime}|}](i)=M(i)$ for all $i$, this is a contradiction to
$M\in\mathbb{MS}$. ∎

We have established that all minimal sufficient segments that do not contain
any decisive alternatives are of the same length. Let that length be denoted
by $i^{D^{\prime}}$.

######  Lemma 3.

Consider any $M\in\mathbb{MS_{D}}$ and let
$i^{D}=\inf\\{i\in\mathbb{N}:M(i)\in D\\}$. Then $|M|\leq i^{D^{\prime}}$ and
$|M|=i^{D}$

###### Proof.

Suppose not i.e. there exists a $M\in\mathbb{MS_{D}}$ such that
$|M|>i^{D^{\prime}}$. Since $d$ is a stopping rule, we know that $M$ is
finite. Consider any $M^{\prime}\in\mathbb{MS_{D^{\prime}}}$. By lemma 2, we
know that $|M^{\prime}|=i^{D^{\prime}}$. As in lemma 2, consider a chain of
segments $M_{1}\ldots,M_{n}$ such that $M_{1}=M^{\prime}$ and
$M_{n}=M|_{|M^{\prime}|}$ such that every successive element in the chain
differs by an alternative in exactly one position. By Replacement, we know
that $M_{n}$ is a sufficient segment. Since $|M_{n}|<M$ and $M_{n}(i)=M(i)$
for all $i$, this is a contradiction to $M\in\mathbb{MS}$. Therefore, $|M|\leq
i^{D^{\prime}}$. Now, we will show that $|M|=i^{D}$. Assume for contradiction
that $|M|>i^{D}$ (note that the argument for the case $|M|<i^{D}$ is trivial
by the definition of $\mathbb{MS_{D^{\prime}}}$). W.L.O.G let $M(i^{D})=x$. By
definition of $D$, we know that $d(M)=x$. Since $M\in\mathbb{MS}$, there
exists a sequence $T$ such that $d([M|_{|M|-1}].T)\neq d(M)=x$. Let $\bar{M}$
be the minimal sufficient segment of the sequence $[M|_{|M|-1}].T$. By
definition of $D$, $|\bar{M}|<i^{D}$. Since $|\bar{M}|<|M|$ and
$\bar{M}(i)=M(i)$ for all $i$, this is a contradiction to
$M\in\mathbb{MS_{D}}$. Therefore $|M|=i^{D}$. ∎

Remark. The above lemmas show that all the minimal sufficient segments that do
not contain any decisive alternatives have the same length. The DM considers
all alternatives in his attention span and then decides. Whereas any occurence
of a decisive alternative in a minimal sufficient segment makes the DM stop
and pick that alternative.

By Theorem 1, we know that $d$ is a uniform stopping rule and there exists a
$k\in\mathbb{S}$, such that for all $S\in\mathbb{S}$,
$d([S|_{k}].T)=d(S[S|_{k}].T^{\prime})$ for all $T,T^{\prime}\in\mathcal{S}$.
Now, we consider the following cases:

  * (i)

$k=1$. This implies that size of any minimal sufficient segment is 1.
Therefore $D=X$. Consider any linear order $\succ$ on $X$ and
$a^{*}=\min(X,\succ)$. We can show that $(k,\succ,a^{*})$ explain the choice
data.

  * (ii)

$k\geq 2$ . Consider any $x,y\in D^{\prime}$. Define $\succ$ as follows:
$x\succ y$ if there exists $M\in\mathbb{MS_{D^{\prime}}}$ such that
$\\{x,y\\}\in X(M)$ and $c(M)=x$. We first show that $\succ$ is a linear order
over $D^{\prime}$. Assume for contradiction that $\succ$ is not asymmetric.
Then there exists $M,M^{\prime}\in\mathbb{MS_{D^{\prime}}}$ such that $x,y\in
X(M)\cap X(M^{\prime})$, $d(M)=x$ and $d(M^{\prime})=y$. Consider
$M^{\prime\prime}$ such that $X(M^{\prime\prime})=\\{x,y\\}$ (such
$M^{\prime\prime}$ exists due to the assumption that $k\geq 2$). By
Sequential-$\alpha$, $d(M^{\prime\prime})=x$ and $d(M^{\prime\prime})=y$, a
contradiction. Therefore $\succ$ is asymmetric. Now, consider any $x,y\in
D^{\prime}$ and $M\in\mathbb{MS_{D^{\prime}}}$ such that $X(M)=\\{x,y\\}$. By
definition of $\succ$ we have either $x\succ y$ or $y\succ x$. Therefore
$\succ$ is weakly connected. To show $\succ$ is transitive, we consider two
cases:

    * (a)

$k=2$. This implies $|M|=2$ for all $M\in\mathbb{MS_{D^{\prime}}}$. Consider
any $x,y,z\in D^{\prime}$ and suppose $x\succ y$ and $y\succ z$. Therefore, we
know that there exists $M,M^{\prime}\in\mathbb{MS_{D^{\prime}}}$ such that
$X(M)=\\{x,y\\}$, $d(M)=x$ and $X(M^{\prime})=\\{y,z\\}$, $d(M^{\prime})=y$.
Consider $M^{\prime\prime}\in\mathbb{MS_{D^{\prime}}}$ such that
$X(M^{\prime\prime})=\\{x,z\\}$. By Sequential-NBC, we know that
$d(M^{\prime\prime})\neq z$, implying $d(M^{\prime\prime})=x$.

    * (b)

$k>2$. Consider any $x,y,z\in D^{\prime}$ . Let $x\succ y$ and $y\succ z$.
Consider $M\in\mathbb{MS_{D^{\prime}}}$ such that $X(M)=\\{x,y,z\\}$. By
sequential-$\alpha$, we know that $d(M)\neq z$ and $d(M)\neq y$. Therefore
$d(M)=x$ implying $x\succ z$.

We have shown that $\succ$ is a linear order over $D^{\prime}$. Now, let
$a^{*}=\max(D^{\prime},\succ)$ and consider any linear order $\bar{\succ}$ on
X such that $\succ\subset\bar{\succ}$ and $x\ \bar{\succ}\ y$ for all $x\in D$
and $y\in D^{\prime}$.

Before showing that this linear order and threshold alternative rationalize
the choie data, we first we show that there exists at least one decisive
alternative

######  Lemma 4.

$D$ is non-empty

###### Proof.

Assume for contradiction that $D$ is empty i.e. $X=D^{\prime}$ By lemma 1, all
minimal sufficient segments are of the same length i.e. $M=M^{\prime}$ for all
$M\in\mathbb{MS}$. Since $\succ$ is a linear order over $X$, we have a unique
maximal element. W.L.O.G let it be $x$. By Sequential-$\alpha$, we know that
$d(M)=x$ for all $M\in\mathbb{MS}$ such that $d\in X(M)$. By defintion of $D$,
we must have $x\in D$ , a contradiction. ∎

Now, we will show that $(k,\bar{\succ},a^{*})$ explains the choice data. Let
$d(S)=x$. There are two possible cases: (i) The segment of $S_{k}$ does not
contain any alternative from $D$. In this case, by construction, $x$ is the
$\succ$-maximal element of $X(S_{k})$. (ii) The initial segment $S_{k}$
contains at least one alternative from $D$. By lemma 2, $x\in D$ and is the
first alternative from $D$ to feature in $S_{k}$

∎

It is interesting to note that rational behavior within the limited attention
span is a special case of our satisficing model i.e. when $D$ is a singleton.
This is in contrast with satisficing over sets where satisficing is equivalent
to preference maximization (See [Rubinstein (2012)]). Note that in the case
where $|D|>1$, the identified preference order is not unique i.e. any ordering
between the alternatives of $D$ can explain the choice data.

###  4.2 Configuration Dependent rules

In this section, we define a broad class of choice rules that we call
configuration dependent rules. The underlying idea is that the decision is
made using the “configuration" of the alternatives i.e. the pattern of their
occurence in an input sequence. Configuration dependent rules subsume many
possible behaviors. One can think of rules that utilise the information on
positioning of alternatives to make choices. Alternatively, one may be
interested in rules that focus on frequency of alternatives appearing in the
sequence. Rules that utilise any combination of the frequency and positioning
of alternatives can also be analysed under the umbrella of configuration
dependent rules.

Configuration dependent rules can be described by what we term a bitstream
processor. A bitstream is any sequence $b\in\\{0,1\\}^{\mathbb{N}}$ i.e. a
sequence of $0$’s and $1$’s. Let $b(i)$ denote the $i^{th}$ component of the
bitstream $b$. We call a collection of bitstreams $B$ feasible if it satisfies
the following condition

$|\\{b\in B|b(i)=1\\}|=1\ \ \forall i\in\mathbb{N}$

In other words for any arbitrary position $i\in\mathbb{N}$, there is exactly
one bitstream that contains $1$ at its $i^{th}$ position. Denote by
$\mathbb{B}$ the set of all bitstreams and $\mathscr{B}$ the set of all
feasible collections of bitstreams.

######  Definition 15.

A bitstream processor is a map $f:\mathscr{B}\to\mathbb{B}$ such that $f(B)\in
B$ for all $B\in\mathscr{B}$

A bitstream processor selects a bitstream from a feasible collection of
bitstreams. One can think of configuration dependent rules “encrypting" any
given sequence into a feasible collection sequences of $0$’s and $1$’s and
feeding it into a bitstream processor which then selects one bitstream out of
the ones fed into it. This selected bitstream is then “ decrypted" into an
alternative which is the final choice.

Let $x(S)=\\{a\in\\{0,1\\}^{\mathbb{N}}:a(i)=1\ \text{if}\ S(i)=x,\ 0\
\text{otherwise}\\}$. This corresponds to the “configuration" of the
alternative $x$ in sequence $S$. Note that any sequence $S$ corresponds to a
feasible collection of bitstreams. Denote by $B(S)$ the feasible collection of
bitstreams generated by $S$ where $|B(S)|=|X(S)|$ i.e. the number of
bitstreams is equal to the number of alternatives appearing in $S$. To
illustrate, consider the sequence $S=(a\ b\ c\ a\ b\ c...)$ i.e. the sequence
of cycles of $a,b$ and $c$. This will generate three bitstreams: $b_{1}=(1\ 0\
0\ 1\ 0\ 0\ldots)$, $b_{2}=(0\ 1\ 0\ 0\ 1\ 0\ldots)$ and $b_{3}=(0\ 0\ 1\ 0\
0\ 1\ldots)$. Note that $\\{b_{1},b_{2},b_{3}\\}$ form a feasible collection
of bitstreams. Now, we can formally define configuration dependent rules.

######  Definition 16.

A choice rule $d$ is a configuration dependent rule if there exists a
bitstream processor $f$ such that $d(S)=x$ if and only if $f(B(S))=x(S)$ for
all $S\in\mathcal{S}$

Intuitively, the choice is made “as if" the input sequence is viewed as a
feasible collection of bitstreams and fed into a bitstream processor. The
choice of the processor, which is a sequence of 0’s and 1’s corresponds to one
of the alternatives of the sequence. Configuration dependent rules are
characterized by a Neutrality axiom that is stated as follows.

######  Axiom 6 (Neutrality).

Consider any bijection $\sigma:X\to X$ and $S,S^{\prime}\in\mathcal{S}$.

$[S^{\prime}(i)=\sigma(S(i))\ \forall
i\in\mathbb{N}]\implies[d(S^{\prime})=\sigma(d(S))]$

This axiom states that if a sequence is “transformed" into a new sequence by
relabelling the alternatives, then the choice from the new sequence must
respect this transformation. In other words, the choice rule is “neutral" with
respect to the identity of the alternatives.

######  theorem 5.

A choice rule is a configuration dependent rule if and only if it satisfies
Neutrality

###### Proof.

Suppose $d$ is a configuration dependent rule. Then there exists an $f$ such
that $d(S)=x\iff f(B(S))=x(S)$. Consider any $S,S^{\prime}$ such that $d(S)=x$
and for all $i\in\mathbb{N}$, $S^{\prime}(i)=\sigma(S(i))$. We know that
$B(S)=B(S^{\prime})$ and $\sigma(x)(S^{\prime})=x(S)$. Therefore
$f(B(S^{\prime}))=\sigma(x)(S^{\prime})$ which implies
$d(S^{\prime})=\sigma(x)=\sigma(d(S))$.

To show the other direction, consider a choice rule $d$ that satisfies
Neutrality. Define the relation $\sim_{\sigma}$ as follows:
$S\sim_{\sigma}S^{\prime}$ if and only if there exists a bijection
$\sigma:X\to X$ such that $S^{\prime}(i)=\sigma(S(i))\ \ \forall
i\in\mathbb{N}$. Note that $\sim_{\sigma}$ is an equivalence relation and
hence partitions $\mathcal{S}$. Now, consider any arbitrary $S\in\mathcal{S}$
such that $d(S)=y$ for some $y\in X$. Define $f$ as $f(B(S))=y(S)$. Consider
any $S^{\prime}$ such that $S\sim_{\sigma}S^{\prime}$, for some bijection
$\sigma:X\to X$. By Neutrality, we know that $d(S^{\prime})=\sigma(c(S))$.
Also, since $B(S)=B(S^{\prime})$ and $y(S)=\sigma(y)(S^{\prime})$, we have
$f(B(S^{\prime}))=\sigma(y)(S^{\prime})$, by construction. Hence we have
defined an $f$ such that $d(S)=x$ if and only if $f(B(S))=x(S)$. Therefore $d$
is a configuration dependent rule.

∎

###  4.3 Rational Configuration Dependent Rules

In this section, we provide and characterize a class of rules that are the
analogue of rational choice functions over sets. We term them as rational
configuration dependent rules. The idea behind rational configuration
dependent rules is that the DM has a preference over the patterns or
configurations of the alternatives. This is captured by endowing her with a
linear order333A linear order over a set is a complete, transitive and
antisymmetric binary relation over the set $\\{0,1\\}^{\mathbb{N}}$ which she
uses to make choices. The heuristic can be formally defined as follows

######  Definition 17.

A choice rule $d$ is a rational configuration dependent rule if there exists a
linear order $\triangleright$ over $\\{0,1\\}^{\mathbb{N}}$ such that for all
$S\in\mathcal{S}$

$d(S)=\\{x:x(S)\triangleright y(S)\ \text{for all}\ y\neq x,y\in X(S)\\}$

As mentioned above, configuration dependent rules can be used to describe
behavior where the information about location of alternatives can be used to
make choices. Rational configuration-dependent rules, in particular, are
useful to this effect. For instance, consider a DM that always picks the first
alternative from a sequence. To describe this behavior, let us denote by $O$
the set of all $\\{0,1\\}^{\mathbb{N}}$ sequences. Let $O_{1}$ and $O_{2}$
form a partition of $O$ where $O_{1}=\\{a\in O:a(1)=1\\}$ i.e. the set of all
$0,1$ sequences that have $1$ at its first position and $O_{2}=O\setminus
O_{1}$. Such behavior can be explained as a rational configuration dependent
rule by a linear order $\triangleright$ over $O$ with $x\triangleright y$ for
any $x\in O_{1}$ and $y\in O_{2}$.

Rational configuration-dependent rules are characterized using a condition
that resembles the well-known Strong Axiom of Revealed Preference (SARP). To
state our axiom, we need the notion of an equivalence relation between two
sequences with respect to an alternative.

######  Definition 18.

For any $x\in X$, let $\sim_{x}\in\mathcal{S}\times\mathcal{S}$ such that
$S\sim_{x}S^{\prime}$ if and only if $S(i)=x\implies S^{\prime}(i)=x$ for all
$i\in\mathbb{N}$

The above defined binary relation says that two sequences are related via the
relation $\sim_{x}$ if the configuration of the alternative $x$ is the same
for both. Now, we are ready to state our axiom.

######  Axiom 7 (Acylicity).

For any $x_{1},x_{2}\ldots x_{n}$ such that $x_{i}\in X$ and
$S_{1},S_{2}\ldots S_{n}$ such that $S_{j}\sim_{x_{j+1}}S_{j+1}$ for all
$j\in\\{1,\ldots n-1\\}$, $S_{n}\sim_{x_{1}}S_{1}$

$[d(S_{1})=x_{1}\dots d(S_{n-1})=x_{n-1}]\implies d(S_{n})\neq x_{n}$

This axiom is closely related to SARP and it says that if an alternative
$x_{1}$’s configuration is directly or indirectly “revealed" preferred to
another alternative $x_{n}$’s configuration, then the converse cannot hold.
Now, we state our result.

######  theorem 6.

A choice function $d$ is a rational configuration-dependent rule if and only
if it satisfies Neutrality and Acyclicity.

###### Proof.

Necessity is easy to establish, so we prove the sufficiency. Define the
following “revealed" relation over configurations $\triangleright^{c}$ as
follows: For any $a,b\in\\{0,1\\}^{\mathbb{N}}$, $a\ \triangleright^{c}\ b$ if
there exists a sequence $S$ with $x(S)=a$ and $y(S)=b$ for some $x,y,\in X$
and $d(S)=x$. First, we show that $\triangleright^{c}$ is asymmetric. Suppose
not, then there exist $a,b\in\\{0,1\\}^{\mathbb{N}}$ such that
$a\triangleright^{c}b$ and $b\triangleright^{c}a$, i.e. there exist
$S,S^{\prime}\in\mathcal{S}$ and $x,y,w,z\in X$ with $x(S)=w(S^{\prime})=a$,
$d(S)=x$ and $y(S)=z(S^{\prime})=b$, $d(S^{\prime})=z$. There are four
possible cases:

  * (i)

$x=w$ and $y=z$. Note that $S\sim_{y}S^{\prime}$ and $S^{\prime}\sim_{x}S$. By
Acylicity, $d(S^{\prime})\neq y$.

  * (ii)

$x\neq w$ and $y=z$. Let $\sigma:X\to X$ be such that $\sigma(x)=w$ and
$\sigma(a)=a$ for all $a\neq x$. Let $S^{\prime\prime}$ be such that
$S^{\prime\prime}(i)=\sigma(S(i))$ for all $i\in\mathbb{N}$. By Neutrality,
$d(S^{\prime\prime})=w$. Note that $S^{\prime\prime}\sim_{y}S^{\prime}$ and
$S^{\prime}\sim_{w}S^{\prime\prime}$. By Acylicity, $d(S^{\prime})\neq y=z$.

  * (iii)

$x=w$ and $y\neq z$. Let $\sigma:X\to X$ be such that $\sigma(z)=y$ and
$\sigma(a)=a$ for all $a\neq x$. Let $S^{\prime\prime}$ be such that
$S^{\prime\prime}(i)=\sigma(S^{\prime}(i))$ for all $i\in\mathbb{N}$. By
Neutrality, $d(S^{\prime\prime})=y$. Note that $S^{\prime\prime}\sim_{y}S$ and
$S\sim_{x}S^{\prime\prime}$. By Acylicity, $d(S)\neq x$

  * (iv)

$x\neq w$ and $y\neq z$. Let $\sigma:X\to X$ be such that $\sigma(z)=y$,
$\sigma(w)=x$ and $\sigma(a)=a$ for all $a\neq z,w$. Let $S^{\prime\prime}$ be
such that $S^{\prime\prime}(i)=\sigma(S^{\prime}(i))$ for all
$i\in\mathbb{N}$. By Neutrality, $d(S^{\prime\prime})=y$. Note that
$S\sim_{y}S^{\prime\prime}$ and $S^{\prime\prime}\sim_{x}S$. By Acylicity,
$d(S)\neq x$

Similarly, by Acyclicity and Neurality, we can show that the “revealed"
relation $\triangleright^{c}$ is also acyclic. Now, define an indirect
“revealed" relation $a\ \triangleright^{i}\ b$ as follows: For any
$a,b\in\\{0,1\\}^{\mathbb{N}}$, $a\ \triangleright^{i}\ b$ if there exists a
chain of alternatives $a_{1},\ldots a_{n}\in\\{0,1\\}^{\mathbb{N}}$ with
$a=a_{1}$ and $a_{n}=b$ such that
$a\triangleright^{c}a_{1}\triangleright^{c}\ldots a_{n}\triangleright^{c}b$.
Note that by construction $\triangleright^{i}$ is asymmetric and transitive
i.e. a partial order. Consider a exists a linear order $\triangleright$ such
that $\triangleright^{i}\subseteq\triangleright$. Now, define
$\tilde{d}(S)=\\{x:x(S)\triangleright y(S)\ \text{for all}\ y\neq x\\}$ for
all $S\in\mathcal{S}$ . Consider any $S$ and W.L.O.G. let $d(S)=x$. Let
$x(S)=a$ and now it is easy to see that $d(S)=\tilde{d}$

∎

##  5 Topological approach

In this section, we discuss a topological approach to our main result. Having
already introduced the product topology on the set of all inputs
$\mathcal{S}$, we now explicitly describe convergence with respect to the
product topology. The following definition is standard.

Definition 3: Suppose, $(Z,\mathscr{T})$ is a topological space. A $Z$–valued
sequence $(z_{n})$ converges in $\mathscr{T}$ to $z_{\ast}$ if, for every
$U\in\mathscr{T}$ with $z_{\ast}\in U$, there exists $n_{U}\in\mathbb{N}$ such
that $z_{n}\in U$ for all $n\geq n_{U}$.

The phrase “$(z_{n})$ converges in $\mathscr{T}$ to $z_{\ast}$” shall often be
abbreviated as “$z_{n}\longrightarrow z_{\ast}$ in $\mathscr{T}$”. In
particular, the meaning of any $X$–valued sequence $(S)$ converges in the
product topology $\Pi_{\mathcal{S}}$ to some $S_{\ast}\in\mathcal{S}$ stands
specified. Now, consider the following proposition.

######  Proposition 1.

Let $(S_{n})$ be an $X$–valued sequence and $S_{\ast}\in\mathcal{S}$. Then,
$S_{n}\longrightarrow S_{\ast}$ in $\Pi_{\mathcal{S}}$, if and only if, for
every $k\in\mathbb{N}$, there exists $n_{k}\in\mathbb{N}$ such that
$S_{n}|_{k}=S_{\ast}|_{k}$ if $n\geq n_{k}$.

###### Proof.

First, we assume: $S_{n}\longrightarrow S_{\ast}$ in $\Pi_{\mathcal{S}}$. Fix
an arbitrary $k\in\mathbb{N}$ and define $M:\\{1,\ldots,k\\}\rightarrow X$ as
follows: $M(i)\coloneqq S_{\ast}(i)$ for all $i\in\\{1,\ldots,k\\}$; that is,
$M=S_{\ast}|_{k}$. Now, $\Pi_{\mathcal{S}}=\mathscr{T}_{\mathcal{S}}$ by
proposition $1$ and recall
$\mathcal{B}_{\mathcal{S}}\subseteq\mathscr{T}_{\mathcal{S}}$ by definition of
$\mathscr{T}_{\mathcal{S}}$. Thus, $B(M)\in\Pi_{\mathcal{S}}$. Then, by
definition $3$, $S_{n}\longrightarrow S_{\ast}$ in $\Pi_{\mathcal{S}}$
implies: there exists $n_{B(M)}\in\mathbb{N}$ such that $S_{n}\in B(M)$ if
$n\geq n_{B(M)}$. Let $n_{k}\coloneqq n_{B(M)}$. Finally, note that $S_{n}\in
B(M)$ and $M=S_{\ast}|_{k}$ implies: $S_{n}|_{k}=S_{\ast}|_{k}$.
Now, we prove the converse. For this, consider an arbitrary
$U\in\Pi_{\mathcal{S}}$ with $S_{\ast}\in U$. By proposition $1$,
$U\in\mathscr{T}_{\mathcal{S}}$. By definition of $\mathscr{T}_{\mathcal{S}}$,
there exists $k\in\mathbb{N}$ and a map $M:\\{1,\ldots,k\\}\rightarrow X$ such
that $S_{\ast}\in B(M)\subseteq U$. Also, there exists $n_{k}\in\mathbb{N}$
such that $S_{n}|_{k}=S_{\ast}|_{k}$ if $n\geq n_{k}$. However, $S_{\ast}\in
B(M)$ implies $S_{\ast}|_{k}=M$. Thus, $S_{n}\in S_{\ast}|_{k}$ implies
$S_{n}\in B(M)$. Therefore, $S_{n}\in B(M)$ for all $n\geq n_{k}$. Since
$B(M)\subseteq U$, we have: $S_{n}\in U$ if $n\geq n_{k}$. Thus, let
$n_{U}\coloneqq n_{k}$ to complete the proof. ∎

In addition to the topology over the domain $\mathcal{S}$, we must formalize a
certain continuity property associated with any stopping rule. For this, we
associate to each decision rule $d:\mathcal{S}\rightarrow Y$ a natural map
$k_{d}:\mathcal{S}\rightarrow\mathbb{N}\cup\\{0\,,\infty\\}$ which was defined
as:

$k_{d}(S)\coloneqq\inf\\{k\in\mathbb{N}:(\forall
T\in\mathcal{S})[d(S|_{k}\cdot T)=d(S)]\\}$

for all $S\in\mathcal{S}$. Assuming that $d:\mathcal{S}\rightarrow Y$ is not a
constant function, the fact that it is a stopping rule is equivalent to
asserting that $k_{d}$ is $\mathbb{N}$–valued. Also, we consider the set
$\mathbb{N}$ to be endowed with the discrete topology $2^{\mathbb{N}}$. Note,
this topology is the restriction to $\mathbb{N}$ of the standard topology on
$\mathbb{R}$. A basic result is as follows.

######  Proposition 2.

Let $\mathcal{S}$ and $\mathbb{N}$ be endowed with the topologies
$\Pi_{\mathcal{S}}$ and $2^{\mathbb{N}}$, respectively. If
$d:\mathcal{S}\rightarrow Y$ is a non–constant stopping rule, then the
associated map $k_{d}:\mathcal{S}\rightarrow\mathbb{N}$ is continuous.

###### Proof.

Let $d:\mathcal{S}\rightarrow Y$ be a non–constant stopping rule. Fix an
arbitrary $A\subseteq\mathbb{N}$. We shall argue:
$k_{d}^{-1}(A)\in\Pi_{\mathcal{S}}$. If $A=\varnothing$, then
$k_{d}^{-1}(A)=\varnothing$. This is because $k_{d}$ is $\mathbb{N}$–valued
since $d$ is a non–constant stopping rule. Thus,
$k_{d}^{-1}(A)\in\Pi_{\mathcal{S}}$ if $A=\varnothing$. Henceforth, we assume
that $A\neq\varnothing$. By definition of the map $k_{d}$, we have:

$k_{d}^{-1}(A)=\bigcup\big{\\{}B(S|_{k_{d}(S)}):k_{d}(S)\in A\big{\\}}.$

Thus, $k_{d}^{-1}(A)\in\mathscr{T}_{\mathcal{S}}$ by definition of
$\mathscr{T}_{\mathcal{S}}$. Since proposition $1$ requires that
$\mathscr{T}_{\mathcal{S}}=\Pi_{\mathcal{S}}$, we obtain:
$k_{d}^{-1}(A)\in\Pi_{\mathcal{S}}$. ∎

With this background in place, we are ready to prove Theorem $1$ via
topological methods. The first of these proofs is as follows.

###### Proof 2.

Since $X$ is finite, the topology $2^{X}$ makes $X$ compact. Thus, by
Tychonoff’s theorem, the product topology $\Pi_{\mathcal{S}}$ makes
$\mathcal{S}$ compact. Since the continuous image of a compact set is compact,
it follows that $k_{d}(\mathcal{S})\coloneqq\\{k_{d}(S):S\in\mathcal{S}\\}$ is
a compact subset of $\mathbb{N}$ endowed with the topology $2^{\mathbb{N}}$.
Now, $2^{\mathbb{N}}$ is the restriction of the standard topology of
$\mathbb{R}$ to $\mathbb{N}$. Thus, $k_{d}(\mathcal{S})$ is a compact subset
of $\mathbb{R}$. Since compact subsets of $\mathbb{R}$ must be bounded, there
exists $k_{\ast}\in\mathbb{N}$ such that $k_{d}(S)\leq k_{\ast}$ for all
$S\in\mathcal{S}$. Thus, the decision rule $d:\mathcal{S}\rightarrow Y$ has a
uniform stopping time. ∎

While the above argument is short, it rests in large measure on the abstract
result that continuous maps over compact set have a compact range. The
following argument, however, removes the role of this result in furnishing a
proof of Theorem $1$.

###### Proof 3.

Let $d:\mathcal{S}\rightarrow X$ be a non–constant stopping rule. Thus, the
map $k_{d}$ is $\mathbb{N}$–valued. For each $k\in\mathbb{N}$, let
$\mathcal{A}_{k}\coloneqq\\{S\in\mathcal{S}:k_{d}(S)=k\\}$. Since $k_{d}$ is
$\mathbb{N}$–valued, we have:
$\mathcal{S}=\cup_{k\in\mathbb{N}}\mathcal{A}_{k}$. Then,
$\\{\mathcal{A}_{k}:k\in\mathbb{N}\\}$ is an open cover of $\mathcal{S}$ if we
can argue: $\mathcal{A}_{k}\in\Pi_{\mathcal{S}}$ for every $k\in\mathbb{N}$.
For this, fix an arbitrary $k\in\mathbb{N}$ and observe:

$\big{\\{}S\in\mathcal{S}:k_{d}(S)=k\big{\\}}=\bigcup\big{\\{}B(S|_{k}):k_{d}(S)=k\big{\\}}.$

Thus, $\mathcal{A}_{k}\in\mathscr{T}_{\mathcal{S}}$ by definition of
$\mathscr{T}_{\mathcal{S}}$. Then, proposition $1$ implies that
$\mathcal{A}_{k}\in\Pi_{\mathcal{S}}$. That is,
$\\{\mathcal{A}_{k}:k\in\mathbb{N}\\}$ is an open cover of $\mathcal{S}$ in
the topology $\Pi_{\mathcal{S}}$. However, $\Pi_{\mathcal{S}}$ makes
$\mathcal{S}$ compact by Tychonoff’s theorem (see [Munkres (2000)]). Thus,
there exists $L\in\mathbb{N}$ and $k_{1}<\ldots<k_{L}$ such that:

$\mathcal{S}=\bigcup_{l=1}^{L}\big{\\{}S\in\mathcal{S}:k_{d}(S)=k_{l}\big{\\}}.$

Define $k_{\ast}\coloneqq\max\\{k_{l}:l=1,\ldots,L\\}$. Thus, $k_{d}(S)\leq
k_{\ast}$ for all $S\in\mathcal{S}$. ∎

A direct comparison of proofs $2$ and $3$ suggests that the essential
ingredient for Theorem $1$ to hold is the compactness of $\mathcal{S}$ under
the product topology. This was the point of step $2$ in the elementary proof
(i.e., proof $1$). However, only the sequential compactness of $\mathcal{S}$
was established there which is weaker than compactness. Further, this was done
by a direct argument rather than appealing to the theorem of Tychonoff. The
next proof essentially casts the elementary proof via the compactness of
various subsets of $\mathcal{S}$ under $\Pi_{\mathcal{S}}$.

###### Proof 4.

Suppose, $d:\mathcal{S}\rightarrow Y$ is a stopping rule that does not have a
uniform stopping time. Thus, for each $j\in\mathbb{N}$, there exists
$k_{j}\in\mathbb{N}$ such that $(1)$ $k_{j}<k_{j+1}$ for all $j\in\mathbb{N}$,
and $(2)$ the image of the map $k_{d}$, which is the set
$k_{d}(\mathcal{S})\coloneqq\\{k_{d}(S):S\in\mathcal{S}\\}$, is
$\\{k_{j}:j\in\mathbb{N}\\}$. Then, for each $j\in\mathbb{N}$, define
$\mathcal{A}_{j}\coloneqq\\{S\in\mathcal{S}:k_{d}(S)\geq k_{j}\\}$. From $(1)$
and $(2)$, we have: $\mathcal{A}_{j}\neq\varnothing$ for every
$j\in\mathbb{N}$. Further, $\mathcal{A}_{j+1}\subseteq\mathcal{A}_{j}$ for
every $j\in\mathbb{N}$. Thus, $\\{\mathcal{A}_{j}:j\in\mathbb{N}\\}$ satisfies
the finite–intersection property.
We now argue that, if $\mathcal{A}_{j}$ is compact for every $j\in\mathbb{N}$,
then the claim of Theorem $1$ holds. This is because the collection
$\\{\mathcal{A}_{j}:j\in\mathbb{N}\\}$ satisfies the finite–intersection
property. Thus, by Cantor’s theorem:

$\bigcap\big{\\{}\mathcal{A}_{j}:j\in\mathbb{N}\big{\\}}\neq\varnothing.$

Thus, there exists $S_{\ast}\in\mathcal{S}$ such that
$S_{\ast}\in\mathcal{A}_{j}$ for all $j\in\mathbb{N}$. Then, by definition of
$\mathcal{A}_{j}$, we have: $k_{d}(S_{\ast})\geq k_{j}$ for every
$j\in\mathbb{N}$. Since $k_{j}<k_{j+1}$ and $k_{j}\in\mathbb{N}$ for all
$j\in\mathbb{N}$, we have: $k_{d}(S_{\ast})=\infty$. This contradicts the fact
that $d$ is a stopping rule. Thus, our supposition that the stopping rule $d$
does not have a uniform stopping time must be wrong.
Therefore, it only remains to argue: $\mathcal{A}_{j}$ is compact for each
$j\in\mathbb{N}$. For this, fix an arbitrary $j\in\mathbb{N}$. Notice,
$\mathcal{A}_{1}=\mathcal{S}$ which is compact under $\Pi_{\mathcal{S}}$ by
Tychonoff’s theorem. Hence, we assume $j\geq 2$. For any map
$f:\\{1,\ldots,L\\}\rightarrow X$ and $L_{\ast}\leq L$, we shall denote the
map $l\in\\{1,\ldots,L_{\ast}\\}\mapsto M(l)$ by $M|_{L_{\ast}}$. That is,
$M|_{L_{\ast}}$ is the truncation of the map $M$ at $L_{\ast}$. Now, define:

$\mathcal{M}_{j}\coloneqq\big{\\{}M\in X^{\\{1,\ldots,k_{j}\\}}:\neg(\exists
S\in\mathcal{S})[k_{d}(S)<k_{j}\;;\,S|_{k_{d}(S)}=M|_{k_{d}(S)}]\big{\\}}.$

Thus, $\mathcal{M}_{j}$ is precisely the collection of maps
$M:\\{1,\ldots,k_{j}\\}\rightarrow X$ such that444Recall, $M\cdot T$ is the
concatenation of the map $T$ to the map $M$. $k_{d}(M\cdot T)\geq k_{j}$ for
any $T\in\mathcal{S}$. That is:

$\mathcal{A}_{j}=\bigcup\big{\\{}B(M):M\in\mathcal{M}_{j}\big{\\}}.$

Since $X$ is finite, it follows that $\mathcal{M}_{j}$ is finite. Thus, to
show that $\mathcal{A}_{j}$ is compact it is enough to argue that
$B(M_{\ast})$ is compact for any $M_{\ast}:\\{1,\ldots,K_{\ast}\\}\rightarrow
X$.555Here, $B(M_{\ast})$ is endowed with the topology $\Pi_{\mathcal{S}}\cap
B(M_{\ast})$. However, the map $f_{M_{\ast}}:\mathcal{S}\rightarrow
B(M_{\ast})$, defined by $f_{M_{\ast}}(T)\coloneqq M_{\ast}\cdot T$ for all
$T\in\mathcal{S}$, is a homeomorphism. To see why, it is enough to argue that
the following holds:

$A\in\Pi_{\mathcal{S}}\iff\\{M_{\ast}\cdot T:T\in A\\}\in\Pi_{\mathcal{S}}\cap
B(M_{\ast}).$

This follows from the fact that666For
$M_{\ast}:\\{1,\ldots,K_{\ast}\\}\rightarrow X$ and
$M:\\{1,\ldots,K\\}\rightarrow X$, the map $M_{\ast}\cdot
M:\\{1,\ldots,K_{\ast}+K\\}\rightarrow X$ is defined by: $[M_{\ast}\cdot
M](k)\coloneqq M_{\ast}(k)$ if $k\in\\{1,\ldots,K_{\ast}\\}$; otherwise,
$[M_{\ast}\cdot M](k)\coloneqq M(k-K_{\ast})$. $\\{M_{\ast}\cdot T:T\in
B(M)\\}=B(M_{\ast}\cdot M)$ for any map $M:\\{1,\ldots,K\\}\rightarrow X$ and
Lemma $1$. Since $\mathcal{S}$ is compact and $f_{M_{\ast}}$ is a
homeomorphism from $\mathcal{S}$ to $B(M_{\ast})$, it follows that
$B(M_{\ast})$ is compact. Thus, the set $\mathcal{A}_{j}$ is compact for each
$j\in\mathbb{N}$. ∎

##  6 Concluding remarks

In this paper, we introduced a new framework of decision making that considers
infinite sequences. Our framework provides a natural setting to study
decision-making si tuations where the DM faces alternatives sequentially and
provides a generalization of the framework on choice over lists introduced in
[Rubinstein and Salant (2006)]. We introduced a natural class of decision
rules called stopping rules that require the DM to decide after viewing a
finite segment of an input sequence. Our main result showed that stopping
rules are equivalent to its seemingly stricter subclass, uniform-stopping
rules. We introduced the notion of computability of a decision rule using
Turing machines and showed that any computable decision rule can be
implemented by a finite automaton —a less powerful model of computation than
the Turing machine.

While we have introduced some natural stopping choice heuristics in this
framework, one can think of more such heuristics. The notions of sufficiency
and minimal sufficiency of a segment are useful to provide testable axioms in
our framework. Future work involves studying stochastic choice rules and
examining potential applications of our main result.

## References

  * Abreu and Rubinstein (1988) Abreu, D. and A. Rubinstein (1988): “The structure of Nash equilibrium in repeated games with finite automata,” _Econometrica: Journal of the Econometric Society_ , 1259–1281.
  * Aguiar et al. (2016) Aguiar, V. H., M. J. Boccardi, and M. Dean (2016): “Satisficing and stochastic choice,” _Journal of Economic Theory_ , 166, 445–482.
  * Camara (2021) Camara, M. K. (2021): “Computationally Tractable Choice,” Tech. rep., Working Paper.
  * Caplin and Dean (2011) Caplin, A. and M. Dean (2011): “Search, choice, and revealed preference,” _Theoretical Economics_ , 6, 19–48.
  * Caplin and Dean (2015) ——— (2015): “Revealed preference, rational inattention, and costly information acquisition,” _American Economic Review_ , 105, 2183–2203.
  * Cheung and Masatlioglu (2021) Cheung, P. and Y. Masatlioglu (2021): “Decision Making with Recommendation,” .
  * Dimitrov et al. (2016) Dimitrov, D., S. Mukherjee, and N. Muto (2016): “‘Divide-and-choose’in list-based decision problems,” _Theory and Decision_ , 81, 17–31.
  * Futia (1977) Futia, C. (1977): “The complexity of economic decision rules,” _Journal of Mathematical Economics_ , 4, 289–299.
  * Guney (2014) Guney, B. (2014): “A theory of iterative choice in lists,” _Journal of Mathematical Economics_ , 53, 26–32.
  * Horan (2010) Horan, S. (2010): “Sequential search and choice from lists,” _Unpublished paper.[716]_.
  * Kovach and Ülkü (2020) Kovach, M. and L. Ülkü (2020): “Satisficing with a variable threshold,” _Journal of Mathematical Economics_ , 87, 67–76.
  * Kramer (1967) Kramer, G. H. (1967): “An impossibility result concerning the theory of decision-making,” .
  * Manzini and Mariotti (2007) Manzini, P. and M. Mariotti (2007): “Sequentially rationalizable choice,” _American Economic Review_ , 97, 1824–1839.
  * Manzini and Mariotti (2014) ——— (2014): “Stochastic choice and consideration sets,” _Econometrica_ , 82, 1153–1176.
  * Manzini et al. (2019) Manzini, P., M. Mariotti, and L. Ulku (2019): “Sequential Approval: A Model of “Likes”, Paper Downloads and Other Forms of Click Behaviour.” .
  * Masatlioglu et al. (2012) Masatlioglu, Y., D. Nakajima, and E. Y. Ozbay (2012): “Revealed attention,” _American Economic Review_ , 102, 2183–2205.
  * Munkres (2000) Munkres, J. R. (2000): _Topology_ , vol. 2, Prentice Hall Upper Saddle River.
  * Neyman (1985) Neyman, A. (1985): “Bounded complexity justifies cooperation in the finitely repeated prisoners’ dilemma,” _Economics letters_ , 19, 227–229.
  * Papi (2012) Papi, M. (2012): “Satisficing choice procedures,” _Journal of Economic Behavior & Organization_, 84, 451–462.
  * Richter and Wong (1999) Richter, M. K. and K.-C. Wong (1999): “Computable preference and utility,” _Journal of Mathematical Economics_ , 32, 339–354.
  * Rubinstein (1986) Rubinstein, A. (1986): “Finite automata play the repeated prisoner’s dilemma,” _Journal of economic theory_ , 39, 83–96.
  * Rubinstein (2012) ——— (2012): _Lecture notes in microeconomic theory_ , Princeton University Press.
  * Rubinstein and Salant (2006) Rubinstein, A. and Y. Salant (2006): “A model of choice from lists,” _Theoretical Economics_ , 1, 3–17.
  * Salant (2003) Salant, Y. (2003): “Limited computational resources favor rationality,” _NAJ Economics_ , 6.
  * Salant (2011) ——— (2011): “Procedural analysis of choice rules with applications to bounded rationality,” _American Economic Review_ , 101, 724–48.
  * Sen (1969) Sen, A. (1969): “Quasi-transitivity, rational choice and collective decisions,” _The Review of Economic Studies_ , 36, 381–393.
  * Simon (1955) Simon, H. A. (1955): “A behavioral model of rational choice,” _The quarterly journal of economics_ , 69, 99–118.
  * Tyson (2015) Tyson, C. J. (2015): “Satisficing behavior with a secondary criterion,” _Social Choice and Welfare_ , 44, 639–661.