# Algorithmic Decision Processes

C. Baldassi F. Maccheroni M. Marinacci M. Pirazzini

###### Abstract

We develop a full-fledged analysis of an algorithmic decision process that, in
a multialternative choice problem, produces computable choice probabilities
and expected decision times.

##  1 Introduction

##### An algorithmic decision procedure

In a multialternative choice problem, decision units aim to find the best
alternatives within a finite choice set $A$ of available ones. Had they
unlimited resources allowing them to make an unconstrained number of exact
judgments between alternatives, they could proceed by standard revision. This
brute force comparison-and-elimination algorithm sequentially analyzes pairs
of alternatives and permanently discards the inferior ones. If the unit
preferences are complete and transitive, after $\left|A\right|-1$ comparisons
the incumbent solution of this algorithm is an optimal choice. Implicit in
traditional choice theory is an underlying algorithm of this kind.

Yet, decision units’ resources are typically too limited to implement a
standard revision procedure. Indeed, binary comparisons are typically costly,
time-consuming and subject to error (so inexact). This happens because the
decision unit may only imperfectly know the relative desirability of the
competing alternatives. As a result, deliberation over them consumes resources
(economic or physiological), requires time and is subject to error.111Here we
are abstracting from inescapable non-decision times. In choice episodes
involving the same pair of alternatives, different decision times and choices
may be then observed. Binary choice behavior can be described only in
probabilistic terms, with stochastic decision times and choice probabilities.

The well-known limits of working memory suggest a sequential structure for the
multialternative choice problem. Costly, time-consuming and inexact binary
comparisons unfold one after the other through a stochastic exploration
process, with alternatives playing the roles of proposals and incumbents in
each binary comparison. An iterative choice process then operates. The
decision unit limited resources constrain this process by limiting the number
of executable binary comparisons, with a (possibly random) cap on the number
of affordable iterations. When the process is terminated, an alternative is
selected. The inexact nature of comparisons and the stochasticity of the
exploration process make this selection random.

We formalize this schema through a decision procedure, the Neural Metropolis
Algorithm, that parsimoniously adapt standard revision by building on
sequential binary comparisons between proposals and incumbents, explicitly
modelled as time-consuming and subject to errors (so stochastic), that unfold
through a Markovian exploration of the choice set $A$. A stopping number,
determined by the decision unit resources, terminates the iterations of the
algorithm and thus makes the algorithm select an alternative. Different
iterations of the algorithm may result in different selections of alternatives
because of the stochastic nature of binary comparisons and of Markovian
exploration.

To the best of our knowledge, this is the first full-fledged analysis of an
algorithmic decision process over a choice set. We are able to derive both the
choice probabilities and expected decision times that the Neural Metropolis
Algorithm generates, with closed forms in some noteworthy cases (Section 4.2).
We are also able to provide a value representation for the algorithm, which
proceeds as if governed by some underlying utility judgements over
alternatives (Section 4.4). In so doing, we generalize and extend to pairs of
choice probabilities and decision times some basic results of traditional
stochastic choice.

This value foundation makes it possible to interpret our algorithmic decision
unit as the neural system of a decision maker that confronts a decision
problem. In particular, traditional choice analysis can be implemented by the
Neural Metropolis Algorithm when the resource constraint is relaxed, as it is
the case in the traditional choice analysis sketched at the outset. On the
other hand, our algorithm may incorporate neuroscience binary choice models,
like the Drift Diffusion Model (DDM), which thus get embedded in a sequential
multialternative decision process.

##### Outline of the analysis

We begin the analysis by generalizing traditional stochastic choice by
introducing binary choice probabilities $\rho\left(i\mid j\right)$ to model
binary comparisons that, in a sequential setting, involve alternatives $i$ and
$j$ playing the distinct roles of proposals and incumbents, respectively (a
distinction that stochastic choice does not make). In our first main result,
Theorem 4, we show that binary choice probabilities have a value
representation through a Fechnerian scaling $v:A\rightarrow\mathbb{R}$ when
they satisfy a basic transitivity property, thus extending to our setting
classic results of traditional deterministic choice theory and of traditional
stochastic choice theory. Indeed, our analysis includes as special cases both
deterministic traditional choice, where $\rho$ is $0$-$1$ valued, and
traditional stochastic choice, where $\rho$ is strictly positive.

Besides choice probabilities, the other key element of the analysis are the
expected decision times $\tau\left(i\mid j\right)$ that account for the
average duration of comparisons between proposal $i$ and incumbent $j$. We
introduce them formally and consider pairs $\left(\rho,\tau\right)$ to study
their interplay with binary choice probabilities. We propose a value
representation also for these pairs. Such a representation is behaviorally
characterized in our Theorem 5. Theorem 6 captures the special case of
symmetric expected decision times which result from a classical speed/accuracy
relation: faster decisons corresponding to smaller error rates.

With this, we move to the analysis of the Neural Metropolis Algorithm. It
sequentially compares pairs of alternatives, playing the roles of incumbents
and proposals. These comparisons use a binary choice model
$\left(\mathrm{C},\mathrm{RT}\right)$ consisting of choice variables and
response times that determine the frequency $\rho_{\mathrm{C}}\left(i\mid
j\right)$ with which proposal $i$ is accepted over incumbent $j$ and the mean
response time $\tau_{\mathrm{RT}}\left(i\mid j\right)$ required by the
comparison. To the pair $\left(\rho_{\mathrm{C}},\tau_{\mathrm{RT}}\right)$ we
can apply the value analysis previously developed, with a Fechnerian scaling
$v_{\mathrm{C}}:A\rightarrow\mathbb{R}$ for the stochastic binary comparisons
(featuring a positive $\rho_{\mathrm{C}}$) and a Paretian utility function
$w_{\mathrm{C}}:A\rightarrow\mathbb{R}$ for the deterministic ones (featuring,
instead, a $0$-$1$ valued $\rho$). An initial random condition $\mu$ and an
exploration matrix $Q$ complete the description of the constituent elements of
the Neural Metropolis Algorithm. A stopping time $N$ terminates the algorithm,
which thus selects an alternatives.

The algorithm thus generated a choice probability $p_{N}$ over alternatives,
where $p_{N}\left(i,A\right)$ is the probability that the algorithm selects
alternative $i$ from the choice set $A$, as well as a mean response time
$\tau_{N}\geq 0$, the average time that the algorithm takes to select an
alternative from $A$. We obtain closed forms for both $p_{N}$ and $\tau_{N}$
in the important case of negative binomial stopping times, which includes the
geometric ones.

Our value analysis shows that, as the stopping number allows more and more
iterations, the Neural Metropolis Algorithm has noteworthy optimality
properties. It selects optimal alternatives when all binary comparisons are
deterministic, thus implementing traditional choice behavior. When, instead,
deterministic and stochastic binary comparisons coexist, the algorithm first
selects alternatives $i$ that are best across the deterministic comparisons,
so belong to $\arg\max_{A}w_{\mathrm{C}}$, and then choose over them according
to a logit a rule

$\frac{e^{v_{\mathrm{C}}\left(i\right)}}{\sum_{j\in\arg\max_{A}w_{\mathrm{C}}}e^{v_{\mathrm{C}}\left(j\right)}}$

where $v_{\mathrm{C}}$ and $w_{\mathrm{C}}$ are the Fechnerian scaling and
Paretian utility previously mentioned.

##### Limitations of the analysis

In our analysis the stopping number, which accounts for the decision unit
limited resources, is exogenous. It is a convenient assumption in a first
analysis of an algorithmic decision process, but a topic for future research
is the study of a decision problem that would endogenously deliver it.

Relatedly, we take the Markovian stochastic exploration as exogenous, though
the decision unit may want to adjust it as exploration progresses. The study
of more sophisticated exploration strategies is another topic for future
research.

The sequential structure of the Neural Metropolis Algorithm appears to be
natural in view of the limitations of working memory. It would interesting,
however, to understand its optimality status by making explicit the working
memory constraints that impede the parallel, rather than sequential,
consideration of all competing alternatives in the choice set.

##### Related literature

The Neural Metropolis Algorithm has the Metropolis DDM Algorithm of Baldassi
et al. (2020) and Cerreia-Vioglio et al. (2022) as special cases in which
binary comparisons are performed according the DDM of Ratcliff (1978), as
adapted by Krajbich et al. (2010) and Milosavljevic et al. (2010) to value-
based binary choices. The generalization is significant, moving from a
specific binary comparison model to virtually all of them. Moreover, our
results are novel even when binary comparisons are DDM based.

The Neural Metropolis Algorithm differs from most neuro-computational models
of neuroscience that typically consider simultaneous evidence accumulation for
all the alternatives in the choice set $A$. See, e.g., Roe et al. (2001),
Anderson et al. (2004), McMillen and Holmes (2006), Bogacz et al. (2007),
Ditterich (2010), and Krajbich and Rangel (2011). This simultaneity
assumption, although efficient per se, is at odds with the known limits of
attention and working memory, as previously mentioned.

An important exception is Reutskaja et al. (2011), who present three two-stage
models in which subjects randomly search through the feasible set during an
initial search phase and, when this phase is concluded, select the best item
that was encountered during the search (up to some noise). This approach can
be called quasi-exhaustive search in that time pressure may terminate the
search phase before all alternatives have been evaluated and introduces an
error probability.

Although different from the models considered by Krajbich and Rangel (2011)
and Reutskaja et al. (2011), our model is consistent with some of their
experimental findings about the exploration process of choice sets and with
the conclusions of the seminal eye fixation study of Russo and Rosen (1975).

##  2 Preliminaries

###  2.1 Mathematics

##### Stochastic matrices

A square matrix $B$ is (_left_) _stochastic_ if the sum of the entries of each
column is $1$. Its powers are the stochastic matrices $B^{0}=I$ and
$B^{n}=BB^{n-1}$, with entry $b_{ij}^{(n)}$ for each $i,j$ in the index set of
$B$. A stochastic matrix $B$ is:

  1. (i)

_positive_ if its entries are strictly positive;

  2. (ii)

_quasi-positive_ if its off diagonal entries are strictly positive;

  3. (iii)

_primitive_ if there exists $n\geq 1$ such that $B^{n}$ is positive;

  4. (iv)

_irreducible_ if, for each $i,j$ in its index set, there exists $n\geq 1$ such
that $b_{ij}^{(n)}>0$;

  5. (v)

_non-traceless_ if, it has at least one strictly positive element on its
diagonal;

  6. (vi)

_nice_ if it is symmetric and quasi-positive;

  7. (vii)

_reversible_ if there exists a probability vector $p\gg\mathbf{0}$ such that

$b_{ij}p_{j}=b_{ji}p_{i}$ (1)

for each off diagonal entry $b_{ij}$.

This terminology is standard, except (vi). Clearly, a positive matrix is
quasi-positive, a quasi-positive matrix is primitive if at least of order $3$.
An irreducible and non-traceless matrix is primitive. Given a stochastic
matrix $B$, the matrix $I-\zeta B$ is invertible when
$\zeta\in\left(-1,1\right)$ because $\left\|\zeta
B\right\|_{1}=\left|\zeta\right|<1$. Instead, the matrix $I-B$ is not
invertible because, by Markov’s Theorem, there exists a probability vector $p$
such that

$Bp=p$

Such a vector is called a _stationary distribution_ of $B$.

##### Stopping number

A _stopping number_ (or _rule_) is a $\mathbb{N}$-valued random variable with
finite mean $\mathbb{E}\left[N\right]$ defined on an underlying probability
space featuring a probability measure $\mathbb{P}$. Two important functions
are associated with a stopping number $N$. The _probability generating
function_ $f_{N}:\left[0,1\right]\rightarrow\mathbb{R}$ is defined by

$f_{N}\left(z\right)={\displaystyle\sum_{n=0}^{\infty}}\mathbb{P}\left[N=n\right]z^{n}$

while the _survival generating function_
$g_{N}:\left[0,1\right]\rightarrow\mathbb{R}$ is defined by

$g_{N}\left(z\right)={\displaystyle\sum\limits_{n=0}^{\infty}}\mathbb{P}\left[N>n\right]z^{n}$

These two functions are related as follows (Feller, 1968, p. 265):

$g_{N}\left(z\right)=\dfrac{1-f_{N}\left(z\right)}{1-z}\qquad\forall
z\in\left[0,1\right]$

under the limit convention

$g_{N}\left(1\right)=\lim_{z\rightarrow
1^{-}}\dfrac{1-f_{N}\left(z\right)}{1-z}=\mathbb{E}\left[N\right]$ (2)

Probability generating functions are widely used and several formulas are
available for them (see, e.g., Johnson et al. 2005).

Let $\mathcal{B}$ be the collection of all stochastic matrices. Given a
stochastic matrix $B\in\mathcal{B}$, we denote by $f_{N}\left(B\right)$ and
$g_{N}\left(B\right)$ the square matrices of the same order of $B$ defined by

$f_{N}\left(B\right)={\displaystyle\sum_{n=0}^{\infty}}\mathbb{P}\left[N=n\right]B^{n}\quad\text{and\quad}g_{N}\left(B\right)={\displaystyle\sum\limits_{n=0}^{\infty}}\mathbb{P}\left[N>n\right]B^{n}$
(3)

It is easy to check that the matrix power series on the r.h.s. converges entry
by entry, and so the matrix $f_{N}\left(B\right)$ is well defined.222See
Section B.2.2 for more details. As $B\in\mathcal{B}$ varies, via (3) one
defines the matrix generating function on $\mathcal{B}$, still denoted by
$f_{N}$, induced by a probability generating function $f_{N}$.333On matrix
functions see, e.g., Rinehart (1955) and Higham (2008).

There is a natural partial order on stopping numbers: we say that stopping
number $N$ _stochastically dominates_ stopping number $N^{\prime}$, written
$N\geq N^{\prime}$, if

$\mathbb{P}\left[N>n\right]\geq\mathbb{P}\left[N^{\prime}>n\right]\qquad\forall
n\geq 0$

Intuitively, $N$ is a less tight stopping number than $N^{\prime}$. At the
limit, we say that a sequence $N_{k}$ of stopping numbers _diverges_ , written
$N_{k}\rightarrow\infty$, if

$\lim_{k\rightarrow\infty}\mathbb{P}\left(N_{k}>n\right)=1\qquad\forall n\geq
0$

This means, as easily checked, that the probability of stopping at any finite
$n$ vanishes as $k\rightarrow\infty$, that is,
$\lim_{k\rightarrow\infty}\mathbb{P}\left(N_{k}=n\right)=0$ for each $n\geq
0$.

###  2.2 Stochastic choice

Let $A$ be a finite choice set, with at least three alternatives,444In this
paper we do not carry out comparative statics exercises across menus. For this
reason, we develop the analysis in terms of an arbitrarily fixed menu $A$.
called _menu_. Its typical elements are $i$, $j$, $h$ and $k$. We denote by
$\Delta\left(A\right)$ the set of all probability distributions on $A$, viewed
as $\left|A\right|$-dimensional vectors. In other words,
$\Delta\left(A\right)$ is the standard simplex in the Euclidean space
$\mathbb{R}^{\left|A\right|}$.

A _choice probability_ $p\left(\cdot,A\right)\in\Delta\left(A\right)$ assigns
to each alternative $i$ the probability $p\left(i,A\right)$ that the decision
unit chooses $i$ within $A$. Formally, $p\left(i,A\right)$ is the component
$i$ of the $\left|A\right|$-dimensional vector $p\left(\cdot,A\right)$.

##  3 Binary choice

As discussed in the Introduction, our algorithmic decision process considers a
sequence of binary choices between an incumbent and a proposal. To model these
binary choices, in this section we generalize traditional stochastic choice to
account for the distinction between the roles of incumbents and proposals that
alternatives may play in binary choices. In the next section we will apply
this generalized framework to observed binary choice behavior.

###  3.1 Binary choice probabilities

A neural system, our decision unit,555Throughout we use the terms “decision
unit” and “neural system” interchangeably. compares two alternatives $i$ and
$j$ in a menu $A$ of alternatives through a _probability kernel_ a function
$\rho:A^{2}\rightarrow\left[0,1\right]$. For distinct $i$ and $j$,

$\rho\left(i\mid j\right)$

denotes the probability with which _proposal_ $i$ is accepted when $j$ is the
_incumbent_ (or _status quo_). So, $1-\rho\left(i\mid j\right)$ is the
probability with which the proposal is rejected and the incumbent maintained.
Next we introduce the class of kernels that we will study.

###### Definition 1

A probability kernel $\rho:A^{2}\rightarrow\left[0,1\right]$ is a _binary
choice probability_ if

$\rho\left(i\mid j\right)=1\Longleftrightarrow\rho\left(j\mid i\right)=0$ (4)

with the convention $\rho\left(i\mid i\right)=\varepsilon>0$.

We thus assume throughout that when an alternative is chosen for sure over
another alternative, this happens regardless of the roles that they play. With
this, we now introduce some basic properties.

###### Definition 2

A binary choice probability $\rho$ is:

  * •

_(status-quo) unbiased_ if

$\underset{\text{prob. }i\text{ if proposal}}{\underbrace{\rho\left(i\mid
j\right)}}=\underset{\text{prob. }i\text{ if
incumbent}}{\underbrace{1-\rho\left(j\mid i\right)}}$

for all distinct alternatives $i\ $and $j$;

  * •

_positive_ if $\rho\left(i\mid j\right)>0$ for all distinct alternatives $i\
$and $j$;

  * •

_Dirac_ if $\rho\left(i\mid j\right)\in\left\\{0,1\right\\}$ for all distinct
alternatives $i\ $and $j$.

These properties have a simple interpretation: a binary choice probability is
unbiased when gives the incumbent alternative no special status, it is
positive when selects either alternative with strictly positive probability,
and it is Dirac when selects either alternative deterministically.666If a
binary choice probability is positive, then for all distinct $i$ and $j$,
$\rho\left(i\mid j\right)>0$ and $\rho\left(j\mid i\right)>0$, then neither of
them can be $1$ (otherwise the other would be $0$). Thus we have
$0<\rho\left(i\mid j\right)<1$ for all $i$ and $j$.

Traditional stochastic choice usually considers unbiased (and often positive)
binary choice probabilities, where $\rho\left(i\mid
j\right)=p\left(i,\left\\{i,j\right\\}\right)$ describes the probability of
choosing $i$ from the doubleton $\left\\{i,j\right\\}$. General, possibly
biased, binary choice probabilities account for the incumbent and proposal
distinct roles that are peculiar to a sequential analysis.

###### Definition 3

A binary choice probability $\rho$ is _transitive_ if

$\rho\left(j\mid i\right)\rho\left(k\mid j\right)\rho\left(i\mid
k\right)=\rho\left(k\mid i\right)\rho\left(j\mid k\right)\rho\left(i\mid
j\right)$ (5)

for all distinct alternatives $i$, $j$ and $k$.

In words, a binary choice probability is transitive when violations of
transitivity in the choices that it determines are due only to the presence of
noise.777Cf. Luce and Suppes (1965) p. 341. Also note that if two alternatives
are not distinct, then condition (5) is automatically satisfied. Indeed,
condition (5) amounts to require the intransitive cycles

$i\rightarrow j\rightarrow k\rightarrow i\text{\quad and\quad}i\rightarrow
k\rightarrow j\rightarrow i$

to be equally likely (over independent choices). Transitivity ensures that
systematic intransitivities, a violation of a basic rationality tenet, cannot
occur. We expect that a viable neural system satisfies this property.

###  3.2 Binary value analysis

The binary choice probability $\rho$ induces two binary relations
$\succ^{\ast}$ and $\succsim$ defined by

$i\succ^{\ast}j\Longleftrightarrow\rho\left(i\mid
j\right)=1\quad\text{and\quad}i\succsim j\Longleftrightarrow\rho\left(i\mid
j\right)\geq\rho\left(j\mid i\right)$

for all alternatives $i$ and $j$. We interpret $\succ^{\ast}$ as a clear-cut,
deterministic, strict preference over the alternatives that the decision unit
is able to perfectly discriminate in value. It is a standard notion in
traditional (non-stochastic) utility theory.888See Fishburn (1970) and Kreps
(1988). Since

$i\succ^{\ast}j\Longleftrightarrow\rho\left(i\mid
j\right)=1\Longleftrightarrow\rho\left(j\mid i\right)=0$ (6)

a strict preference holds irrespective of the alternatives’ roles as
incumbents or proposals.999To further elaborate, $\rho\left(i\mid j\right)=1$
means that $i$ is accepted for sure when proposed, while $\rho\left(j\mid
i\right)=0$, that is, $1-\rho\left(j\mid i\right)=1$, means that $i$ is
maintained for sure when it is the incumbent. We write $i\parallel^{\ast}j$
when there is no strict preference over the two alternatives, i.e.,

$i\parallel^{\ast}j\Longleftrightarrow i\not\succ^{\ast}j\text{ and
}j\not\succ^{\ast}i$

by (6) this is equivalent to $\rho\left(i\mid j\right)\in\left(0,1\right)$,
and also to $\rho\left(j\mid i\right)\in\left(0,1\right)$. That is when choice
is truly stochastic (again irrespective of the alternatives’ roles).

In contrast, we interpret $\succsim$ as a weak notion of preference that
extends the strict preference $\succ^{\ast}$ by allowing for the stochastic
rankings that occur over alternatives that the decision unit only imperfectly
discriminates in value. The consistency property

$i\succ^{\ast}j\Longrightarrow i\succ j$ (7)

shows that, as natural, a strict preference is preserved by (the asymmetric
part of $\succsim$). Finally, the binary relation $\succsim^{{{}^{\circ}}}$
defined by

$i\succsim^{{{}^{\circ}}}j\Longleftrightarrow i\succsim j\text{ and
}i\parallel^{\ast}j$

describes the rankings that are stochastic. Indeed,

$i\succsim^{{{}^{\circ}}}j\Longleftrightarrow 1>\rho\left(i\mid
j\right)\geq\rho\left(j\mid i\right)>0$

The next lemma substantiates our interpretations.

###### Lemma 1

If the binary choice probability $\rho$ is transitive, then

  1. (i)

$\succ^{\ast}$ is asymmetric and negatively transitive;

  2. (ii)

$\parallel^{\ast}$ is an equivalence relation;

  3. (iii)

$\succsim$ is complete and transitive;

  4. (iv)

$\succsim^{{{}^{\circ}}}$ is reflexive and transitive as well as complete on
each equivalence class of $\parallel^{\ast}$.

The two preferences $\succsim^{{{}^{\circ}}}$ and $\succ^{\ast}$ complement
each other by accounting for the stochastic and deterministic comparisons that
occur, respectively, with imperfect and perfect discrimination in value.
Jointly, they rank all pairs of alternatives.101010Set-theoretically, we have
$\succ^{\ast}\cap\succsim^{{{}^{\circ}}}=\emptyset$ and
$\succ^{\ast}\cup\succsim^{{{}^{\circ}}}=\succsim$. In view of this, we focus
our analysis on them.

###### Definition 4

A binary choice probability $\rho:A^{2}\rightarrow\left[0,1\right]$ has a
_binary_ _value_ _representation_ if there exist $v,w:A\rightarrow\mathbb{R}$
and a symmetric $s:A^{2}\rightarrow\left(0,\infty\right)$ such that

$\rho\left(i\mid j\right)=\left\\{\begin{array}[c]{ll}1\vskip 6.0pt plus 2.0pt
minus 2.0pt&\qquad\text{if }w\left(i\right)>w\left(j\right)\\\
s\left(i,j\right)\dfrac{e^{v\left(i\right)}}{e^{v\left(i\right)}+e^{v\left(j\right)}}\vskip
6.0pt plus 2.0pt minus 2.0pt&\qquad\text{if
}w\left(i\right)=w\left(j\right)\\\ 0&\qquad\text{if
}w\left(i\right)<w\left(j\right)\end{array}\right.$ (8)

for all $i$ and $j$.

It is readily seen that, in this case

$i\succ^{\ast}j\Longleftrightarrow
w\left(i\right)>w\left(j\right)\quad\text{;\quad}i\parallel^{\ast}j\Longleftrightarrow
w\left(i\right)=w\left(j\right)$ (9)

and, when $w\left(i\right)=w\left(j\right)$,

$i\succsim^{{{}^{\circ}}}j\Longleftrightarrow v\left(i\right)\geq
v\left(j\right)$ (10)

Thus, we interpret $w$ as a utility function for $\succ^{\ast}$ and $v$ as a
utility function for $\succsim^{{{}^{\circ}}}$. Moreover, we interpret $s$ as
a status quo bias index. These interpretations are corroborated by the next
result. In reading it, keep in mind that $v$ and $s$ are relevant only for
stochastic rankings (as identified by the equivalence classes of
$\parallel^{\ast}$, so by the level sets of $w$).

###### Lemma 2

If a binary choice probability admits a binary value representation, then,

  1. (i)

the utility function $w$ is unique up to a strictly increasing transformation;

  2. (ii)

the utility function $v$ is, on each level set of $w$, unique up to an
additive constant;

  3. (iii)

the status quo bias index $s$ is, on each level set of $w$, unique with

$\displaystyle\rho\left(i\mid j\right)$ $\displaystyle<1-\rho\left(j\mid
i\right)\Longleftrightarrow s\left(i,j\right)<1$ $\displaystyle\rho\left(i\mid
j\right)$ $\displaystyle=1-\rho\left(j\mid i\right)\Longleftrightarrow
s\left(i,j\right)=1$ (11) $\displaystyle\rho\left(i\mid j\right)$
$\displaystyle>1-\rho\left(j\mid i\right)\Longleftrightarrow
s\left(i,j\right)>1$

The relations in the last point of the lemma clarify the interpretation of $s$
as a status quo bias index for the comparison of proposal $i$ and incumbent
$j$. In particular, bias favors the incumbent when $s\left(i,j\right)<1$, the
proposal when $s\left(i,j\right)>1$, and it is absent otherwise. Thus, the
binary choice probability $\rho$ is unbiased if and only if $s$ is constant to
$1$.

The utility $w$ is a traditional Paretian utility function that, by ranking
alternatives in an ordinal manner, represents the strict preference
$\succ^{\ast}$. This Paretian utility is constant, so irrelevant in (8), if
and only if $\rho$ is positive, i.e., when all rankings are stochastic. When
$\rho$ is both positive and unbiased, the binary value representation (8)
reduces to

$\rho\left(i\mid
j\right)=\dfrac{e^{v\left(i\right)}}{e^{v\left(i\right)}+e^{v\left(j\right)}}\vskip
6.0pt plus 2.0pt minus 2.0pt$

This is the strict utility representation of Marschak (1960) and Luce and
Suppes (1965),111111Luce (1959) and Block and Marschak (1960) study a stronger
non-binary version of strict utility. which our binary value representation
thus extends to general, possibly biased and partly deterministic, binary
choice probabilities. As well-known, using the logistic function $\xi$ we can
write:

$\dfrac{e^{v\left(i\right)}}{e^{v\left(i\right)}+e^{v\left(j\right)}}\vskip
6.0pt plus 2.0pt minus 2.0pt=\xi\left(v\left(i\right)-v\left(j\right)\right)$
(12)

The binary choice probability $\rho\left(i\mid j\right)$ thus depends, in a
Fechnerian way, on the utility difference
$v\left(i\right)-v\left(j\right)$.121212Cf. Luce and Suppes (1965) p. 334. The
logistic function $\xi:\mathbb{R}\rightarrow\mathbb{R}$ is given by
$\xi\left(x\right)=1/\left(1+e^{-x}\right)$.

In our extension, $v\ $continues to be a _bona fide_ utility function on the
level sets of $w$, as (10) shows. We call it a _Fechnerian utility_
_function_. When $w\left(i\right)=w\left(j\right)$, it holds

$\rho\left(i\mid j\right)\geq\rho\left(j\mid i\right)\Longleftrightarrow
v\left(i\right)\geq v\left(j\right)\iff 1-\rho\left(j\mid i\right)\geq
1-\rho\left(i\mid j\right)$ (13)

Alternatives with a higher Fechnerian utility thus have a higher probability
to be selected, regardless of their roles as proposals or incumbents. When
$\rho$ is both positive and unbiased, (13) takes the form

$v\left(i\right)\geq v\left(j\right)\Longleftrightarrow\rho\left(i\mid
j\right)\geq\frac{1}{2}$

familiar from traditional stochastic choice. The Fechnerian utility function
is immaterial when $\rho$ is Dirac, i.e., when all rankings of distinct
alternatives are deterministic.

###### Lemma 3

A binary choice probability $\rho$ is Dirac and transitive if and only if
$\succ^{\ast}$ is weakly complete and transitive.131313The strict preference
$\succ^{\ast}$ is _weakly complete_ if, for each $i\neq j$, either
$i\succ^{\ast}j$ or $j\succ^{\ast}i$ (cf. Fishburn, 1970). Under weak
completeness, we do not have to worry about indifferences, a notoriously
delicate issue.

The transitivity of a binary choice probability thus generalizes the
transitivity of a strict preference of traditional utility theory. In this
case, the binary value representation (8) reduces to

$\rho\left(i\mid j\right)=\left\\{\begin{array}[c]{ll}1\vskip 6.0pt plus 2.0pt
minus 2.0pt&\qquad\text{if }w\left(i\right)>w\left(j\right)\\\
\dfrac{1}{2}\vskip 6.0pt plus 2.0pt minus 2.0pt&\qquad\text{if
}w\left(i\right)=w\left(j\right)\\\ 0&\qquad\text{if
}w\left(i\right)<w\left(j\right)\end{array}\right.$

The next representation theorem, our first main result, shows that
transitivity characterizes the binary choice probabilities having a binary
value representation.

###### Theorem 4

A binary choice probability has a binary value representation __ if and only
if it is transitive.

This theorem generalizes standard utility representations in stochastic choice
(e.g., Luce and Suppes, 1965, p. 350) as well as, in view of Lemma 3, in
traditional utility theory.

We conclude by observing that the preference $\succsim$ has, in terms of the
binary value representation (8), a lexicographic representation via the
Fechnerian utility $v$ and the Paretian utility $w$. Indeed, it is easy to see
that, for each $i$ and $j$,

$i\succsim
j\Longleftrightarrow\left(w\left(i\right),v\left(i\right)\right)\geq_{lex}\left(w\left(j\right),v\left(j\right)\right)$

where $\geq_{lex}$ is the lexicographic order on the plane.

###  3.3 Expected response times

Besides the choice probability $\rho\left(i\mid j\right)$, the other quantity
featured in sequential binary choice is the expected time

$\tau\left(i\mid j\right)$

that the decision unit takes to choose between distinct proposal $i$ and
incumbent $j$. We represent it with a function
$\tau:A^{2}\rightarrow\left[0,\infty\right)$.

###### Definition 5

A pair $\left(\rho,\tau\right)$ of a binary choice probability and an expected
response time forms a _tandem_ if, for each $i\neq j$,

$\rho\left(i\mid
j\right)\in\left\\{0,1\right\\}\Longleftrightarrow\tau\left(i\mid j\right)=0$
(14)

and

$\tau\left(i\mid j\right)=\tau\left(j\mid
i\right)\Longrightarrow\rho\left(i\mid j\right)=1-\rho\left(j\mid i\right)$
(15)

A tandem provides a thorough description of the binary choices of our decision
unit in the menu $A$. In such a description, the consistency condition (14)
ensures that deterministic choices are the ones that take no time (so we
abstract from non-decision times). In particular, since $\rho$ is a binary
choice probability,

$\tau\left(i\mid j\right)=0\iff\tau\left(j\mid i\right)=0$

The consistency condition (15), instead, requires that the absence of a status
quo bias manifests itself primarily in the symmetry of response times.

###### Definition 6

A tandem $\left(\rho,\tau\right)$ has a _binary_ _value_ _representation_ if
there exist $v,w:A\rightarrow\mathbb{R}$, a symmetric
$s:A^{2}\rightarrow\left(0,\infty\right)$, and a strictly quasiconcave and
unimodal $\varphi:\mathbb{R}\rightarrow\left(0,\infty\right)$ such that (8)
holds and

$\tau\left(i\mid j\right)=\left\\{\begin{array}[c]{ll}0\vskip 6.0pt plus 2.0pt
minus 2.0pt&\qquad\text{if }w\left(i\right)\neq w\left(j\right)\\\
\varphi\left(v\left(i\right)-v\left(j\right)\right)&\qquad\text{if
}w\left(i\right)=w\left(j\right)\end{array}\right.$ (16)

for all $i$ and $j$.

A strictly quasiconcave and unimodal
$\varphi:\mathbb{R}\rightarrow\left[0,\infty\right)$ is a function that first
strictly increases to a strong maximum and then strictly decreases. This
pattern is motivated by the standard psychophysical assumption that the
stimulus strength determines response times with stronger stimuli inducing
faster responses. Since here the stimulus strength corresponds to the
preference intensity represented by utility differences
$v\left(i\right)-v\left(j\right)$, this standard assumption requires that
large (positive) differences and small (negative) differences command short
response times. This is exactly what is captured by the shape of $\varphi$.

To give an observable counterpart of this standard assumption we need to
introduce the following observables:

$\ell_{ij}=\ln\frac{\rho\left(i\mid j\right)}{\rho\left(j\mid i\right)}$

Using these log-odds we can introduce a class of tandems:

###### Definition 7

A tandem $\left(\rho,\tau\right)$ is _chronometric_ if $\rho$ is transitive
and there exists a threshold $l$ such that,

$\displaystyle\left.\ell_{ij}=\ell_{hk}\right.$
$\displaystyle\implies\tau\left(i\mid j\right)=\tau\left(h\mid k\right)$ (17)
$\displaystyle\left.l\leq\ell_{ij}<\ell_{hk}\right.$
$\displaystyle\implies\tau\left(i\mid j\right)>\tau\left(h\mid k\right)$ (18)
$\displaystyle\left.\ell_{ij}<\ell_{hk}\leq l\right.$
$\displaystyle\implies\tau\left(i\mid j\right)<\tau\left(h\mid k\right)$ (19)

for all pairs of alternatives $i,j$ and $h,k$ with nonzero response times.

We can now state our second representation theorem that characterizes tandems
having a binary value representation.

###### Theorem 5

A tandem has a binary value representation __ if and only if it is
chronometric.

Another standard psychophysical assumption is that stimulus strength
determines error rates, with stronger stimuli inducing lower error rates.
Consistency of this assumption with the previous one requires shorter response
times to correspond to lower error rates. Surprisingly this leads to unbiased
tandems.

Specifically, observe that when comparing a proposal $i$ and an incumbent $j$
(or viceversa) we may make errors of two types: we may reject a superior
proposal or accept an inferior one. In analogy with standard terminology, we
call them _first-type_ and _second-type errors_ , respectively. Their
probabilities are

$\mathrm{ER}_{i,j}^{\mathrm{I}}=\min\left\\{1-\rho\left(i\mid
j\right),1-\rho\left(j\mid
i\right)\right\\}\quad\text{;}\quad\mathrm{ER}_{i,j}^{\mathrm{II}}=\min\left\\{\rho\left(i\mid
j\right),\rho\left(j\mid i\right)\right\\}$ (20)

Next we introduce a basic error-monotonicity property.

###### Definition 8

A tandem $\left(\rho,\tau\right)$ is _psychometric_ if $\rho$ is transitive
and

$\tau\left(i\mid j\right)<\tau\left(h\mid
k\right)\Longrightarrow\mathrm{ER}_{i,j}^{\mathrm{I}}<\mathrm{ER}_{h,k}^{\mathrm{I}}\quad\text{and\quad}\mathrm{ER}_{i,j}^{\mathrm{II}}<\mathrm{ER}_{h,k}^{\mathrm{II}}$

and

$\tau\left(i\mid j\right)\leq\tau\left(h\mid
k\right)\Longrightarrow\mathrm{ER}_{i,j}^{\mathrm{I}}\leq\mathrm{ER}_{h,k}^{\mathrm{I}}\quad\text{and\quad}\mathrm{ER}_{i,j}^{\mathrm{II}}\leq\mathrm{ER}_{h,k}^{\mathrm{II}}$

for all pairs of alternatives $i,j$ and $h,k$ with nonzero response times.

In words, shorter binary expected response times correspond to lower errors of
both types, a property that regards as easier to make the choices between
alternatives with larger utility differences. The next representation theorem
shows that psychometricity characterizes chronometric tandems with symmetric
expected response times, thus featuring no status quo biases.

###### Theorem 6

A tandem has a binary value representation __ with an even $\varphi$ if and
only if it is psychometric.

It is noteworthy that psychometricity implies chronometricity since the two
definitions are not obviously related. With this theorem, our third main
result, we conclude the general analysis of binary choices.

##  4 An algorithmic decision process

###  4.1 Binary choice behavior

It is time to turn to observed binary choice behavior and apply to it the
general binary choice framework just introduced.

###### Definition 9

A _binary choice model_(_BCM_) is a pair of random matrices
$\left(\mathrm{C},\mathrm{RT}\right)$ where:

  1. (i)

$\mathrm{C}=\left[\mathrm{C}_{i,j}\right]$ consists of the random _choice
variables_ $\mathrm{C}_{i,j}$ that describe the random outcome of the
comparison between proposal $i$ and status quo $j$, with

$\mathrm{C}_{i,j}=\left\\{\begin{array}[c]{ll}i&\text{if }i\text{
accepted}\vskip 6.0pt plus 2.0pt minus 2.0pt\\\ j&\text{if }i\text{
rejected}\end{array}\right.$

  2. (ii)

$\mathrm{RT}=\left[\mathrm{RT}_{i,j}\right]$ consists of random _response
times_ $\mathrm{RT}_{i,j}$ required by the comparison.141414Throughout we
assume that random response times (say measured in seconds) have finite mean
and variance.

The distributions of $\mathrm{C}$ and $\mathrm{RT}$ are, in principle, both
observable in choice behavior. By equating probabilities and frequencies, they
induce a pair $\left(\rho_{\mathrm{C}},\tau_{\mathrm{RT}}\right)$ where

$\rho_{\mathrm{C}}\left(i\mid
j\right)=\mathbb{P}\left[\mathrm{C}_{i,j}=i\right]$

is the frequency with which proposal $i$ is accepted over incumbent $j$, and

$\tau_{\mathrm{RT}}\left(i\mid
j\right)=\mathbb{E}\left[\mathrm{RT}_{i,j}\right]$

is the mean response time required by the comparison.

When $\left(\rho_{\mathrm{C}},\tau_{\mathrm{RT}}\right)$ has a binary value
representation, we denote by

$\left(s_{\mathrm{C}},v_{\mathrm{C}},w_{\mathrm{C}},\varphi_{\mathrm{RT}}\right)$

its elements. The most basic example of a BCM
$\left(\mathrm{C},\mathrm{RT}\right)$ occurs in traditional utility theory
when the choices of the decision unit are deterministic. In this case, the
pair $\left(\rho_{\mathrm{C}},\tau_{\mathrm{RT}}\right)$ has the binary value
representation of the Dirac form:

$\rho_{\mathrm{C}}\left(i\mid j\right)=\left\\{\begin{array}[c]{ll}1\vskip
6.0pt plus 2.0pt minus 2.0pt&\qquad\text{if
}w_{\mathrm{C}}\left(i\right)>w_{\mathrm{C}}\left(j\right)\\\
\dfrac{1}{2}\vskip 6.0pt plus 2.0pt minus 2.0pt&\qquad\text{if
}w_{\mathrm{C}}\left(i\right)=w_{\mathrm{C}}\left(j\right)\\\ 0&\qquad\text{if
}w_{\mathrm{C}}\left(i\right)<w_{\mathrm{C}}\left(j\right)\end{array}\right.$

and $\tau_{\mathrm{RT}}$ is typically undefined.

A popular stochastic binary choice model is the _Drift Diffusion Model_(_DDM_)
introduced by Ratcliff (1978). In its value version, developed by Krajbich et
al. (2010) and Milosavljevic et al. (2010), the comparison of two alternatives
$i$ and $j$ is governed by their _neural utilities_ $\nu\left(i\right)$ and
$\nu\left(j\right)$ about which the decision unit learns, for instance via
memory retrieval, during the deliberation that precedes the choice between the
two alternatives.151515To ease the analysis, we assume that the neural utility
$\nu:A\rightarrow\mathbb{R}$ is injective. Evidence accumulation in favor of
either alternative is represented by the two Brownian motions with drift
$\mathrm{V}_{i}\left(t\right)=\nu\left(i\right)t+\mathrm{W}_{i}\left(t\right)$
and
$\mathrm{V}_{j}\left(t\right)=\nu\left(j\right)t+\mathrm{W}_{j}\left(t\right)$.
Each accumulation experiences independent white noise fluctuations modeled by
the uncorrelated Wiener processes $\mathrm{W}_{i}$ and $\mathrm{W}_{j}$. With
this,

  * •

the net evidence in favor of $i$ over $j$ is given, at each $t>0$, by the
difference

$\mathrm{Z}_{i,j}\left(t\right)=\mathrm{V}_{i}\left(t\right)-\mathrm{V}_{j}\left(t\right)=\left[\nu\left(i\right)-\nu\left(j\right)\right]t+\sqrt{2}~{}\mathrm{W}\left(t\right)$
(21)

where $\mathrm{W}$ is the Wiener difference process
$\left(\mathrm{W}_{i}-\mathrm{W}_{j}\right)/\sqrt{2}$;

  * •

comparison ends when $\mathrm{Z}_{i,j}\left(t\right)$ reaches either the
barrier $\lambda>0$ or $-\beta<0$; so the response time is

$\mathrm{RT}_{i,j}=\min\left\\{t:\mathrm{Z}_{i,j}\left(t\right)=\lambda\text{
or }\mathrm{Z}_{i,j}\left(t\right)=-\beta\right\\}$

  * •

proposal $i$ is accepted when the upper barrier $\lambda$ is reached, while
incumbent $j$ is maintained (so proposal $i$ is rejected) when the lower
barrier $-\beta$ is reached; so the choice variable is

$\mathrm{C}_{i,j}=\left\\{\begin{array}[c]{ll}i&\qquad\text{if
}\mathrm{Z}_{i,j}\left(\mathrm{RT}_{i,j}\right)=\lambda\vskip 6.0pt plus 2.0pt
minus 2.0pt\\\ j&\qquad\text{if
}\mathrm{Z}_{i,j}\left(\mathrm{RT}_{i,j}\right)=-\beta\end{array}\right.$

A different net evidence, $\lambda$ and $\beta$, accounts for the different
roles of alternatives as proposal and status quo. A DDM is pinned down by its
elements $\nu$, $\lambda$ and $\beta$. We thus write it as DDM
$\left(\nu,\lambda,\beta\right)$. When $\lambda=\beta$ we say that the DDM is
_symmetric_.

###### Proposition 7

The pair $\left(\rho_{\mathrm{C}},\tau_{\mathrm{RT}}\right)$ generated by a
DDM $\left(\nu,\lambda,\beta\right)$ is a chronometric tandem, with
$\rho_{\mathrm{C}}$ positive (and transitive). It has a binary value
representation with

$v_{\mathrm{C}}=\lambda\nu\quad\text{;}\quad
s_{\mathrm{C}}\left(i,j\right)=1+\dfrac{e^{\lambda\left|\nu\left(i\right)-\nu\left(j\right)\right|}-e^{\beta\left|\nu\left(i\right)-\nu\left(j\right)\right|}}{1-e^{\left(\lambda+\beta\right)\left|\nu\left(i\right)-\nu\left(j\right)\right|}}\quad\text{;}\quad
w_{\mathrm{C}}\text{ constant}$ (22)

and

$\varphi_{\mathrm{RT}}\left(x\right)=\frac{\lambda^{2}}{x}\left[\frac{1-e^{\frac{\beta}{\lambda}x}}{e^{-x}-e^{\frac{\beta}{\lambda}x}}\left(1+\frac{\beta}{\lambda}\right)-\frac{\beta}{\lambda}\right]$
(23)

for all $x\in\mathbb{R}$.

Thus, in the DDM case the pair
$\left(\rho_{\mathrm{C}},\tau_{\mathrm{RT}}\right)$ is a tandem with binary
value representation

$\rho_{\mathrm{C}}\left(i\mid
j\right)=s_{\mathrm{C}}\left(i,j\right)\xi\left(v_{\mathrm{C}}\left(i\right)-v_{\mathrm{C}}\left(j\right)\right)=s_{\mathrm{C}}\left(i,j\right)\frac{e^{v_{\mathrm{C}}\left(i\right)}}{e^{v_{\mathrm{C}}\left(i\right)}+e^{v_{\mathrm{C}}\left(j\right)}}$

and

$\tau_{\mathrm{RT}}\left(i\mid
j\right)=\varphi_{\mathrm{RT}}\left(v_{\mathrm{C}}\left(i\right)-v_{\mathrm{C}}\left(j\right)\right)=\lambda\frac{\lambda\rho_{\mathrm{C}}\left(i\mid
j\right)-\beta\left(1-\rho_{\mathrm{C}}\left(i\mid
j\right)\right)}{v_{\mathrm{C}}\left(i\right)-v_{\mathrm{C}}\left(j\right)}$

In particular, we have a decomposition of the Fechnerian utility
$v_{\mathrm{C}}=\lambda\nu$ in terms of neural utility function $\nu$ and
acceptance threshold $\lambda$. Accordingly,

$v_{\mathrm{C}}\left(i\right)-v_{\mathrm{C}}\left(j\right)=\lambda\left(\nu\left(i\right)-\nu\left(j\right)\right)$

The Fechnerian utility difference is decomposed in the neural utility
difference $\nu\left(i\right)-\nu\left(j\right)$ weighted by the coefficient
$\lambda$. The higher the neural utility difference, the higher can be viewed
the intensity of the neural value for $i$ over $j$. The higher $\lambda$, the
higher the DM ability to perceive this value difference, so to discriminate
the alternatives’ subjective values. In other words, $\lambda$ acts as a
magnification lens for neural utility differences.

The next result gives a sharp empirical content to the DDM case. It is
convenient to state it using the log-odds

$\ell_{ij}=\log\frac{\rho_{\mathrm{C}}\left(i\mid
j\right)}{\rho_{\mathrm{C}}\left(j\mid
i\right)}\quad\text{and\quad}\bar{\ell}_{ij}=\log\frac{1-\rho_{\mathrm{C}}\left(j\mid
i\right)}{1-\rho_{\mathrm{C}}\left(i\mid j\right)}$

###### Proposition 8

The elements of a DDM $\left(v,\lambda,\beta\right)$ are uniquely identified
by the tandem $\left(\rho_{\mathrm{C}},\tau_{\mathrm{RT}}\right)$ that it
generates. In particular, if $\ell_{ij}\neq 0$,

$\lambda=\left|\ell_{ij}\right|\sqrt{\frac{\tau_{ij}}{\ell_{ij}\rho_{ij}+\bar{\ell}_{ij}\left(\rho_{ij}-1\right)}}$

and

$\beta=\lambda\frac{\bar{\ell}_{ij}}{\ell_{ij}}\quad;\quad\nu\left(i\right)=\frac{1}{\lambda}\log
r_{\mathrm{C}}\left(i,j^{\ast}\right)$

under the normalization $v\left(j^{\ast}\right)=0$ for some alternative
$j^{\ast}$.

Finally, we characterize symmetric DDMs by showing that symmetry is equivalent
to an unbiased $\rho_{\mathrm{C}}$ as well as to a symmetric
$\tau_{\mathrm{RT}}$.

###### Proposition 9

For a tandem $\left(\rho_{\mathrm{C}},\tau_{\mathrm{RT}}\right)$ generated by
a DDM $\left(\nu,\lambda,\beta\right)$, the following conditions are
equivalent:

  1. (i)

the tandem is psychometric;

  2. (ii)

$\beta=\lambda$;

  3. (iii)

$\tau_{\mathrm{RT}}\left(i\mid j\right)=\tau_{\mathrm{RT}}\left(j\mid
i\right)$ for some (all) $i\neq j$;

  4. (iv)

$\rho_{\mathrm{C}}\left(i\mid j\right)=1-\rho_{\mathrm{C}}\left(j\mid
i\right)$ for some (all) $i\neq j$.

In this case,

$\varphi_{\mathrm{RT}}\left(x\right)=\frac{\lambda^{2}}{x}\tanh\frac{x}{2}$

for all $x\in\mathbb{R}$.

We conclude this section by observing that a broad family of BCMs is given by
_evidence threshold models_. They encompass integration models, like the DDM
just studied, as well as the extrema detection models discussed by Stine et
al. (2020). In Appendix A we discuss this family of BCMs in some detail.

###  4.2 Neural Metropolis Algorithm

The protagonist of our analysis is an algorithmic decision process that a
neural system might implement when facing a multialternative menu $A$. This
process consists of a sequence of pairwise comparisons conducted via a BCM,
whose contestants are selected by a Markovian mechanism in the sense of
Metropolis et al. (1953). This sequential structure is motivated, as discussed
in the Introduction, by the well-known limits of working memory and is
supported by classic and recent eye-tracking studies.161616See Russo and Rosen
(1975), Krajbich and Rangel (2011) and Reutskaja et al. (2011) as well as the
discussion in Cerreia-Vioglio et al. (2022).

In broad strokes, this algorithmic decision process:

  1. 1.

starts from an arbitrary element $j$ of the menu, the _incumbent_ ;

  2. 2.

selects a candidate alternative $i$ in the menu, the _proposal_ ;

  3. 3.

compares them via a BCM and makes the winner the new incumbent;

  4. 4.

repeats steps 1-3 until deliberation time comes, with the last incumbent being
the chosen alternative in the menu.

More in detail, the algorithm starts by selecting a first incumbent $j$
according to an initial distribution $\mu\in\Delta\left(A\right)$ that, for
example, may describe the “first fixation” of the decision unit. It proceeds
through an _exploration_(_stochastic_)_matrix_

$Q=\left[Q\left(i\mid j\right):i,j\in A\right]$

of order $\left|A\right|$ that describes how the algorithm navigates through
alternatives. In particular, given the incumbent $j$, a proposal $i$ is
selected with probability $Q\left(i\mid j\right)$. Incumbent and proposal are
then compared via a BCM $\left(\mathrm{C},\mathrm{RT}\right)$. After
$\mathrm{RT}_{i,j}$ seconds, the new incumbent is
$j^{\prime}=\mathrm{C}_{i,j}$; a new proposal $i^{\prime}$ is then selected
with probability $Q\left(i^{\prime}\mid j^{\prime}\right)$, and so on so
forth.

The algorithm terminates according to a posited random _stopping_ _number_ $N$
that limits the number of allowed iterations because of exogenously
constrained computational resources (for instance, this number may have a
cost, say economic or physiological, for the decision unit). The last
incumbent is the algorithm output, so what the algorithm chooses from menu
$A$.

After this preliminary discussion, next we formalize the _Neural Metropolis
Algorithm_ , our algorithmic decision process. Its constitutive elements are a
BCM $\left(\mathrm{C},\mathrm{RT}\right)$ and an exploration strategy
$\left(\mu,Q\right)$, summarized in the quartet

$\left(\mathrm{C},\mathrm{RT},\mu,Q\right)$ (24)

For mathematical convenience we start the algorithm at time $-1$.

Neural Metropolis Algorithm

Input:  _Given a stopping number_ $N$_._

Start: _Draw_ $i\ $_from_ $\emph{\ }A$_according to_ $\mu$ _and_

$\bullet$ _set_ $t_{-1}=0$_,_

$\bullet$_set_ $j_{-1}=i$_._

Repeat: _Draw_ $i_{n}\ \emph{from\ }A$_according to_ $Q\left(\cdot\mid
j_{n-1}\right)$_and compare it to_ $j_{n-1}$_:_

$\bullet$ _set_ $t_{n}=t_{n-1}+\mathrm{RT}_{i_{n},j_{n-1}}$_,_

$\bullet$_set_ $j_{n}=\mathrm{C}_{i_{n},j_{n-1}}$_;_

until $n=N$_._

Stop: _Set_ $k=j_{n-1}$_._

Output: _Choose_ $k$_from_ $A$_._

Along with stopping number $N$, the Neural Metropolis Algorithm (24) selects
alternative $j_{n-1}$ when $N=n$, where $n$ is the iteration at which the
decision process is interrupted by the stopping number. The Neural Metropolis
Algorithm generalizes the Metropolis-DDM Algorithm of Cerreia-Vioglio et al.
(2022), which is the special case when the underlying BCM is generated by a
DDM, the exploration matrix $Q\left(i\mid j\right)$ is inversely proportional
to the mean of $\mathrm{RT}_{i,j}$ and a hard deadline is given.

###  4.3 Algorithmic properties

The Neural Metropolis Algorithm (24) generates a Markov chain of incumbents

$J=\left\\{J_{-1},J_{0},J_{1},...\right\\}$ (25)

with $\mathbb{P}\left[J_{-1}=j\right]=\mu\left(j\right)$ for all alternatives
$j$ in $A$ and, for each $n\geq 0$,

$\mathbb{P}\left[J_{n}=i\mid J_{n-1}=j\right]=\underset{\text{prob. }i\text{
proposed}}{\underbrace{Q\left(i\mid j\right)}}\times\underset{\text{prob.
}i\text{ accepted}}{\underbrace{\rho_{\mathrm{C}}\left(i\mid
j\right)}}=:M\left(i\mid j\right)$

for all distinct alternatives $i$ and $j$ in $A$. The stochastic matrix $M$ is
the _transition matrix_ of the incumbents’ Markov chain $J$. In particular, we
say that the Neural Metropolis Algorithm is _reversible_ when its transition
matrix is reversible and so the incumbents’ Markov chain (25) is reversible.

The Neural Metropolis Algorithm induces, for each stopping number $N$, a:

  1. (i)

_choice probability_ $p_{N}\in\Delta\left(A\right)$,171717Recall that $p_{N}$
is an $\left|A\right|$-dimensional vector. where $p_{N}\left(i,A\right)$ is
the probability that alternative $i$ is selected from menu $A$ by the
algorithm;

  2. (ii)

_mean response time_ $\tau_{N}\in\left[0,\infty\right)$, the average time that
the algorithm takes to select an alternative from $A$.

The possibility of computing these quantities in explicit form is what makes
the Neural Metropolis Algorithm empirically relevant. To this end, next we
introduce a class of stopping numbers amenable to computations.

###### Definition 10

A stopping number $N$ is _simple_ within a Neural Metropolis Algorithm (24) if
it is independent of the realizations of incumbents, proposals and response
times.

Next we compute the choice probabilities and mean response times for a Neural
Metropolis Algorithm with a simple stopping number. A piece of notation: we
denote by

$\bar{\tau}_{j}={\displaystyle\sum\limits_{i\in A}}Q\left(i\mid
j\right)\tau_{\mathrm{RT}}\left(i\mid j\right)$ (26)

the average duration of an iteration when $j$ is the incumbent.

###### Proposition 10

For a Neural Metropolis Algorithm (24) with a simple stopping number
$N$,181818The r.h.s. of both formulas in (27) involve standard matrix-vector
multiplications: $\mu$ and $\bar{\tau}$ are $\left|A\right|$-dimensional
vectors, while $f_{N}\left(M\right)$ and $g_{N}\left(M\right)$ are the square
matrices of order $\left|A\right|$ defined by (3).

$p_{N}=f_{N}\left(M\right)\mu\quad\text{and\quad}\tau_{N}=\bar{\tau}\cdot
g_{N}\left(M\right)\mu$ (27)

Using the definitions of probability and survival generating functions, we can
rewrite the choice probabilities and mean response times (27) as

$p_{N}=\left({\displaystyle\sum\limits_{n=0}^{\infty}}\mathbb{P}\left[N=n\right]M^{n}\right)\mu\quad\text{and\quad}\tau_{N}=\bar{\tau}\cdot\left({\displaystyle\sum\limits_{n=0}^{\infty}}\mathbb{P}\left[N>n\right]M^{n}\right)\mu$
(28)

An immediate consequence of this rewriting is that

$N\geq N^{\prime}\Longrightarrow\tau_{N}\geq\tau_{N^{\prime}}$

A less tight stopping number results, as natural, in a longer mean decision
time.

In the following important case we can compute the choice probabilities and
mean response times in closed form.

###### Definition 11

Given two coefficients $\zeta\in\left(0,1\right)$ and $r\geq 1$, the _negative
binomial stopping number_ $N_{r}\left(\zeta\right)$ is defined by

$\mathbb{P}\left[N=n\right]=\binom{n+r-1}{r-1}\zeta^{n}\left(1-\zeta\right)^{r}\qquad\forall
n\geq 0$

Under this distribution, the decision unit receives a “search” signal with
probability $\zeta$ and a “stop” signal with probability $1-\zeta$; it then
proceeds to compare the alternatives when a search signal is received, while
it stops searching after $r$ stop signals.191919For the first $r-1$ stop
signals it just freezes, restarting in the next round. When $r=1$, it reduces
to a _geometric stopping number_

$\mathbb{P}\left[N_{1}\left(\zeta\right)=n\right]=\zeta^{n}\left(1-\zeta\right)\qquad\forall
n\geq 0$

Now, the decision unit stops as soon as it receives the first stop signal.

###### Proposition 11

It holds

$f_{N_{r}\left(\zeta\right)}\left(M\right)=\left(1-\zeta\right)^{r}\left(1-\zeta
M\right)^{-r}$

and

$g_{N_{r}\left(\zeta\right)}\left(M\right)=-\left(\sum_{k=0}^{r}\binom{r}{k}\left(-\zeta\right)^{k}\sum_{j=0}^{k-1}M^{j}\right)\left(1-\zeta
M\right)^{-r}$ (29)

By Proposition 10, for a simple negative binomial stopping number __ we thus
have

$p_{N_{r}\left(\zeta\right)}=\left(1-\zeta\right)^{r}\left(1-\zeta
M\right)^{-r}\mu\quad\text{and\quad}\tau_{N_{r}\left(\zeta\right)}=-\bar{\tau}\cdot\left(\sum_{k=0}^{r}\binom{r}{k}\left(-\zeta\right)^{k}\sum_{j=0}^{k-1}M^{j}\right)\left(1-\zeta
M\right)^{-r}\mu$

In particular, in the geometric case $r=1$ we get

$p_{N_{1}\left(\zeta\right)}=\left(1-\zeta\right)\left(1-\zeta
M\right)^{-1}\mu\qquad\text{and}\qquad\tau_{N_{1}\left(\zeta\right)}=\bar{\tau}\cdot\zeta\left(1-\zeta
M\right)^{-1}\mu$

The formula for $p_{N_{1}\left(\zeta\right)}$ was first proved in Valkanova
(2020), all other formulas appear to be novel.

###  4.4 Algorithmic value analysis

Earlier in the paper we discussed the value underpinning of binary choice
probabilities. Next we consider a similar concept for Neural Metropolis
Algorithms.

###### Definition 12

A Neural Metropolis Algorithm (24) is _value based_ if its binary choice
probability $\rho_{\mathrm{C}}$ has a binary value representation
$\left(s_{\mathrm{C}},v_{\mathrm{C}},w_{\mathrm{C}}\right)$.

This notion is the algorithmic counterpart of the binary value representation
of a binary choice probability. By Theorem 4, value-based Neural Metropolis
Algorithms are characterized by transitive binary choice probabilities.

###### Theorem 12

If a value-based Neural Metropolis Algorithm has a nice exploration matrix,
then

$\lim_{n\rightarrow\infty}\Pr\left[J_{n}=i\right]=\lim_{N_{k}\rightarrow\infty}p_{N_{k}}\left(i,A\right)=\left\\{\begin{array}[c]{ll}\vskip
6.0pt plus 2.0pt minus
2.0pt\frac{e^{v_{\mathrm{C}}\left(i\right)}}{\sum_{j\in\arg\max_{A}w_{\mathrm{C}}}e^{v_{\mathrm{C}}\left(j\right)}}&\qquad\text{if
}i\in\arg\max_{A}w_{\mathrm{C}}\\\ 0&\qquad\text{else}\end{array}\right.$ (30)

for all sequences of divergent simple stopping rules $N_{k}$.

This result clarifies the nature of a value-based Neural Metropolis Algorithm.
To appreciate it, observe that $\Pr\left[J_{n}=i\right]$ is the probability
that, unstopped, the algorithm chooses alternative $i$ after $n$ iterations,
while $\arg\max_{A}w_{\mathrm{C}}$ is the set of alternatives that are maximal
under $\succ^{\ast}$. Thus,

$\lim_{n\rightarrow\infty}\Pr\left[J_{n}=i\right]$

indicates the inherent tendency of the Neural Metropolis Algorithm to choose a
maximal alternative $i$, regardless of the exogenously posited stopping
number. As a result, it can be seen as representing the underlying value of
alternative $i$. When the algorithm satisfies (30), we have, for alternatives
$i$ and $j$ that are maximal under $\succ^{\ast}$,

$v_{\mathrm{C}}\left(i\right)\geq
v_{\mathrm{C}}\left(j\right)\Longleftrightarrow\lim_{n\rightarrow\infty}\Pr\left[J_{n}=i\right]\geq\lim_{n\rightarrow\infty}\Pr\left[J_{n}=i\right]$

The inherent tendency of the algorithm is thus consistent with the Fechnerian
utility function $v_{\mathrm{C}}$, which in the limit governs the choices
between maximal alternatives (be they incumbents or proposals). The equality

$\lim_{N_{k}\rightarrow\infty}p_{N_{k}}\left(i,A\right)=\lim_{n\rightarrow\infty}\Pr\left[J_{n}=i\right]$

shows that this limit behavior occurs when the stopping number is less and
less tight. This means, _inter alia_ , that the limit behavior is unaffected
by status quo biases, so $s_{\mathrm{C}}$ plays no role. Implicit here is the
view that these biases arise under external pressure, here embodied by the
posited stopping number, so they vanish when this pressure relaxes.

Finally, formula (30) ensures that

$\lim_{n\rightarrow\infty}\Pr\left[J_{n}=i\right]=\lim_{N_{k}\rightarrow\infty}p_{N_{k}}\left(i,A\right)=0$

for all alternatives $i$ in $A$ that are not maximal under $\succ^{\ast}$. In
other words, at the limit these alternatives have no chance to be selected –
as $\lim_{N_{k}\rightarrow\infty}p_{N_{k}}\left(i,A\right)=0$ – and in any
event the algorithm has no tendency to select them – as
$\lim_{n\rightarrow\infty}\Pr\left[J_{n}=i\right]=0$. This optimality property
ensures that, as stopping numbers are less and less tight, the algorithm
select alternatives that are maximal under $\succ^{\ast}$. Among them,
stochastic comparisons are then governed by the Fechnerian utility. In sum, at
the limit the Neural Metropolis Algorithm hard-maximizes $w_{\mathrm{C}}$ and
soft-maximizes $v_{\mathrm{C}}$.

A first important consequence of the previous theorem concerns the case in
which $\succ^{\ast}$ features a single maximal element.

###### Corollary 13

A value-based Neural Metropolis Algorithm (24), with nice exploration matrix
$Q$, satisfies

$\lim_{n\rightarrow\infty}\Pr\left[J_{n}=i\right]=\lim_{N_{k}\rightarrow\infty}p_{N_{k}}\left(i,A\right)=\left\\{\begin{array}[c]{ll}\vskip
6.0pt plus 2.0pt minus 2.0pt1&\qquad\text{if
}i\in\arg\max_{A}w_{\mathrm{C}}\\\ 0&\qquad\text{else}\end{array}\right.$

if and only if $\arg\max_{A}w_{\mathrm{C}}$ is a singleton.

For instance, in the deterministic case of a transitive Dirac binary choice
probability the Neural Metropolis Algorithm selects, at the limit, the best
alternative.202020Recall that a Dirac and transitive $\rho_{\mathrm{C}}$
corresponds to a weakly complete and transitive $\succ^{\ast}$ (cf. Lemma 3).
So. $\arg\max_{A}w_{\mathrm{C}}$ is a singleton consisting of the best
alternative under $\succ^{\ast}$. This limit analysis is much in line with the
traditional assumption of unconstrained computational resources. Traditional
choice behavior is thus implemented computationally by the Neural Metropolis
Algorithm.

In the traditional case just considered, $\arg\max_{A}w_{\mathrm{C}}$ is a
singleton in $A$. In contrast, $\arg\max_{A}w_{\mathrm{C}}$ coincides with the
whole set $A$ when, like in the DDM case, the binary choice probability
$\rho_{\mathrm{C}}$ is positive. In this case, $w_{\mathrm{C}}$ is constant,
so all alternatives are maximal under $\succ^{\ast}$. We thus have a second
noteworthy special case of the last representation theorem.

###### Corollary 14

A value-based Neural Metropolis Algorithm (24), with nice exploration matrix
$Q$, satisfies

$\lim_{n\rightarrow\infty}\Pr\left[J_{n}=i\right]=\lim_{N_{k}\rightarrow\infty}p_{N_{k}}\left(i,A\right)=\frac{e^{v_{\mathrm{C}}\left(i\right)}}{\sum_{j\in
A}e^{v_{\mathrm{C}}\left(j\right)}}\qquad\forall i\in A$ (31)

if and only if its binary choice probability $\rho_{\mathrm{C}}$ is positive.

By Proposition 7, in the DDM special case we have $v_{\mathrm{C}}=\lambda\nu$
in (31) and so multinomial logit behavior

$\frac{e^{\lambda\nu\left(i\right)}}{\sum_{j\in
A}e^{\lambda\nu\left(j\right)}}$ (32)

emerges at the limit, like in Baldassi et al. (2020) and Cerreia-Vioglio et
al. (2022), even though here the assumptions on the stopping numbers are
different.

In the positive $\rho_{\mathrm{C}}$ case, value-based Neural Metropolis
Algorithms have a remarkable computational property, as the next theorem, our
last main result, shows.

###### Theorem 15

A Neural Metropolis Algorithm (24) with positive $\rho_{\mathrm{C}}$ and nice
exploration matrix $Q$, is value based if and only if its transition matrix
$M$ is reversible.212121If and only if $\rho_{\mathrm{C}}$ is transitive.

At a computational level, reversibility ensures that the transition matrix $M$
is diagonalizable with real eigenvalues. Therefore,

$M=U\operatorname*{diag}\left(\lambda_{1},\lambda_{2},...,\lambda_{\left|A\right|}\right)U^{-1}$

where $\operatorname*{diag}\left(\cdot\right)$ is the diagonal matrix of the
eigenvalues $\lambda_{i}$ of $M$, each repeated according to its multiplicity,
and the columns of $U$ form a basis of the respective eigenvectors. In turn,
this readily implies

$f_{N}\left(M\right)=U\operatorname*{diag}\left(f_{N}\left(\lambda_{1}\right),f_{N}\left(\lambda_{2}\right),...,f_{N}\left(\lambda_{\left|A\right|}\right)\right)U^{-1}$
(33)

and

$g_{N}\left(M\right)=U\operatorname*{diag}\left(\dfrac{1-f_{N}\left(\lambda_{1}\right)}{1-\lambda_{1}},\dfrac{1-f\left(\lambda_{2}\right)}{1-\lambda_{2}},...,\dfrac{1-f\left(\lambda_{\left|A\right|}\right)}{1-\lambda_{\left|A\right|}}\right)U^{-1}$
(34)

with the limit convention (2). These formulas permit to compute choice
probabilities and mean response times for simple stopping numbers, as in
formulas (28). This computational achievement concludes the analysis of value-
based Neural Metropolis Algorithms.

##  5 Discussion: temporal constrains

In our analysis we considered constrained resources as modelled by a stopping
number on iterations, which may have an economic or physiological cost for the
decision unit. For perspective, in this final section we consider a different
type of constraint, namely, a temporal constraint in the form of a hard time
constraint $t$. This deadline induces a stopping number $N_{t}$ with $N_{t}=n$
if $t\in\left[t_{n-1},t_{n}\right)$. In words, the decision unit cannot
conclude the $n$-th comparison when the duration $t_{n}$ of that comparison
exceeds the deadline $t$. To see how this stopping number affects the
analysis, observe that, if unstopped, a Neural Metropolis Algorithm realizes a
stochastic process

$\left(J,I,T\right)=\left(J_{-1},I_{0},T_{0},J_{0},I_{1},T_{1},...,J_{n-1},I_{n},T_{n},J_{n},I_{n+1},...\right)$
(35)

where the realization $j_{n-1}$ of $J_{n-1}$ is the incumbent at the end of
iteration $n-1$, the realization $i_{n}$ of $I_{n}$ is the proposal at
iteration $n$, and the realization $t_{n}$ of $T_{n}$ is the duration of
iteration $n$. The stopping number $N_{t}$ acts as follows:

$N_{t}=n\iff T_{-1}+T_{0}+\cdot\cdot\cdot+T_{n-1}\leq
t<T_{-1}+T_{0}+\cdot\cdot\cdot+T_{n-1}+T_{n}$

where $T_{-1}=0$. In this case, a closed form representation of $p_{N_{t}}$ is
not achievable in general and, by definition, $\tau_{N_{t}}=t$. Yet, we can
give a limit result, in the spirit of Theorem 12, under the following
assumption.

Regularity A binary choice model $\left(\mathrm{C},\mathrm{RT}\right)$ is
_regular_ if $\rho_{\mathrm{C}}$ is positive and transitive,
$\tau_{\mathrm{RT}}$ is positive and
$\mathrm{RT}=\left[\mathrm{RT}_{i,j}\right]$ consists of random response times
$\mathrm{RT}_{i,j}$ with a continuous distribution at $0$ and with no singular
part.222222These two conditions on the distributions of response times are
automatically satisfied when they all admit density.

We can now state the limit result.232323In this discussion section we focus on
the positive case, leaving the more general case to an in-depth future
analysis.

###### Proposition 16

If a Neural Metropolis Algorithm (24) with irreducible exploration matrix $Q$
is based on a regular BCM $\left(\mathrm{C},\mathrm{RT}\right)$, then

$\lim_{t\rightarrow\infty}p_{N_{t}}\left(i,A\right)=\frac{e^{v_{\mathrm{C}}\left(i\right)}\bar{\tau}_{i}}{\sum_{j\in
A}e^{v_{\mathrm{C}}\left(j\right)}\bar{\tau}_{j}}\qquad\forall i\in A$

As time pressure diminishes, the limit probability of choosing alternative $i$
becomes proportional to the limit probability with which $i$ is an incumbent
times the average duration of the comparisons in which $i$ is the incumbent.
The intuition is natural: the longer the time spent in comparing an
alternative with the other alternatives, the higher the probability of
choosing that alternative at the deadline $t$.

In the DDM special case, we get

$\lim_{t\rightarrow\infty}p_{N_{t}}\left(i\right)=\frac{e^{\lambda\nu\left(i\right)}\bar{\tau}_{i}}{{\displaystyle\sum\limits_{j\in
A}}e^{\lambda\nu\left(j\right)}\bar{\tau}_{j}}=\frac{e^{\lambda\nu\left(i\right)+\alpha\left(i\right)}}{{\displaystyle\sum\limits_{j\in
A}}e^{\lambda\nu\left(j\right)+\alpha\left(j\right)}}\qquad\forall i\in A$
(36)

Thus, the limit probability is softmax with neural utility $\nu$ and
alternative specific bias

$\alpha\left(i\right)=\log\bar{\tau}_{i}\qquad\forall i\in A$

If, in addition, the DDM is symmetric and the off diagonal entries of the
exploration matrix $Q$ are inversely proportional to mean response times (as
in Cerreia-Vioglio et al. 2022, Section 2), then the $\bar{\tau}_{i}$’s are
approximately constant and multinomial logit behavior (32) emerges.242424See
Appendix B.4 for details.

##  Appendix A Appendix: Evidence threshold models

As it will soon become clear, evidence threshold models are best introduced in
discrete time. For each pair $i,j$ of alternatives in $A$, let
$\left\\{\mathrm{Z}_{i,j}\left(t\right)\right\\}_{t=0}^{\infty}$ be a
discrete-time stochastic process in which each variable
$\mathrm{Z}_{i,j}\left(t\right)$ represents the net evidence – accumulated or
instantaneous – in favor of $i$ over $j$ that the neural system takes into
account at time $t$. Given two evidence thresholds $\lambda,\beta>0$, a
decision is taken when either the evidence in favor of $i$ reaches level
$\lambda$ or the evidence in favor of $j$ reaches level $\beta$. This happens
at (stochastic) time

$\mathrm{RT}_{i,j}=\min\left\\{t:\mathrm{Z}_{i,j}\left(t\right)\geq\lambda\text{
or }\mathrm{Z}_{i,j}\left(t\right)\leq-\beta\right\\}$ (37)

With this, the choice variable is

$\mathrm{C}_{i,j}=\left\\{\begin{array}[c]{ll}i&\qquad\text{if
}\mathrm{Z}_{i,j}\left(\mathrm{RT}_{i,j}\right)\geq\lambda\vskip 6.0pt plus
2.0pt minus 2.0pt\\\ j&\qquad\text{if
}\mathrm{Z}_{i,j}\left(\mathrm{RT}_{i,j}\right)\leq-\beta\end{array}\right.$
(38)

Evidence threshold models encompass integration models, like a discrete-time
version of the DDM, as well as the extrema detection models discussed by Stine
et al. (2020). To see why, consider the discrete-time Ornstein-Uhlenbeck
process

$\mathrm{Z}_{i,j}\left(t\right)=\underset{\text{past
evidence}}{\underbrace{\left(1-\eta\right)\mathrm{Z}_{i,j}\left(t-1\right)}}+\underset{\text{new
evidence}}{\underbrace{\zeta_{i,j}\left(t\right)}}\qquad\forall t\geq 1$

with initial condition $\mathrm{Z}_{i,j}\left(0\right)=0$. The scalar
$\eta\in\left[0,1\right]$ captures past evidence deterioration and the
variable

$\zeta_{i,j}\left(t\right)=\left[\nu\left(i\right)-\nu\left(j\right)\right]\mu\left(t-1\right)+\sigma\varepsilon\left(t\right)\qquad\forall
t\geq 1$ (39)

is the instantaneous noisy evidence gathered at time $t$ in favor of either
alternative.252525Evidence is in favor of $i$ over $j$ when
$\zeta_{i,j}\left(t\right)\geq 0$ and in favor of $j$ over $i$ when
$\zeta_{i,j}\left(t\right)\leq 0$. The possible dependence of $\mu$ on $t-1$
allows for urgency signals. The shock $\varepsilon$ is a Gaussian white noise
process – i.e., it consists of i.i.d. Gaussian random variables
$\varepsilon\left(t\right)\sim N\left(0,1\right)$; like in the DDM,
$\nu\left(i\right)$ is the value of alternative $i$. When

$\eta=0\quad\text{,\quad}\mu=1\quad\text{and\quad}\sigma=\sqrt{2}$ (40)

process (39) reduces to the following discrete-time version of the DDM

$\mathrm{Z}_{i,j}\left(t\right)-\mathrm{Z}_{i,j}\left(t-1\right)=\left[\nu\left(i\right)-\nu\left(j\right)\right]+\sqrt{2}\,\varepsilon\left(t\right)\qquad\forall
t\geq 1$

Through the discrete-time Wiener process
$w\left(t\right)=\sum_{s=1}^{t}\varepsilon\left(s\right)$, it is immediate to
see that $\mathrm{Z}_{i,j}\left(t\right)$ represents accumulated noisy
evidence:

$\mathrm{Z}_{i,j}\left(t\right)=\sum_{s=1}^{t}\zeta_{i,j}\left(s\right)=\left[\nu\left(i\right)-\nu\left(j\right)\right]t+\sqrt{2}w\left(t\right)$

In contrast, when $\eta=1$ the process (39) takes the _extrema detection_ form

$\mathrm{Z}_{i,j}\left(t\right)=\zeta_{i,j}\left(t\right)=\left[\nu\left(i\right)-\nu\left(j\right)\right]\mu\left(t-1\right)+\sigma\varepsilon\left(t\right)\qquad\forall
t\geq 1$ (41)

Now $\mathrm{Z}_{i,j}\left(t\right)$ represents instantaneous noisy evidence,
as opposed to the DDM accumulated one.

In continuous time, the Ornstein-Uhlenbeck process becomes

$\mathrm{dZ}_{i,j}\left(t\right)=-\eta\mathrm{Z}_{i,j}\left(t\right)\mathrm{d}t+\left[\nu\left(i\right)-\nu\left(j\right)\right]\mu\left(t\right)\mathrm{d}t+\sigma\mathrm{dW}$

with solution

$\mathrm{Z}_{i,j}\left(t\right)=\left[\nu\left(i\right)-\nu\left(j\right)\right]\mu\left(t\right)\frac{1-e^{-\eta
t}}{\eta}+\int_{0}^{t}e^{-\eta\left(t-s\right)}\sigma\mathrm{dW}\left(s\right)$
(42)

The DDM (21) is still the special case (40). More difficult is to identify the
continuous counterpart of the extrema detection model (41) because of the
technical issues that arise with continuous time white noise. As these issues
do not appear to have a substantive neural underpinning, we introduced
evidence threshold models in discrete time.262626The accumulated evidence used
by integration models like the DDM is properly formalized by Wiener processes.
The instantaneous evidence featured by extrema detection models would rely on
a notion of “derivative” for Wiener processes, a notoriously subtle issue as
their paths are nowhere differentiable.

Be that as it may, Bogacz et al. (2006) report formulas for the continuous
time Ornstein-Uhlenbeck process that generalize the DDM ones upon which
Proposition 7 is based. It is unclear, however, whether this generalized
formulas deliver a sharp Ornstein-Uhlenbeck extension of this proposition.
Nevertheless, (42) is a significant generalization of the DDM that, via the
obvious continuous time versions of (37) and (38), can play the role of a BCM.

##  Appendix B Appendix: Proofs and related analysis

###  B.1 Section 3

In this section it is sometimes convenient to use the exponential
transformation $u=e^{v}$ of the Fenchel utility $v$. We call $u$ _strict
utility_.

####  B.1.1 Proof of Lemma 1

(i) Asymmetry is easily checked. Assume _per contra_ that $\succ^{\ast}$ is
not negatively transitive. Then, there exist $i$, $j$ and $k$ such that
$i\nsucc^{\ast}k\nsucc^{\ast}j$ but $i\succ^{\ast}j$. Alternatives $i$, $k$
and $j$ must be distinct: $i\succ^{\ast}j$ implies $i\neq j$, while $i=k$
would imply $i\nsucc^{\ast}j$ and so would $k=j$. Moreover,

  1. (a)

$i\nsucc^{\ast}k$ implies $\rho\left(i\mid k\right)<1$ and $\rho\left(k\mid
i\right)>0$,

  2. (b)

$k\nsucc^{\ast}j$ implies $\rho\left(k\mid j\right)<1$ and $\rho\left(j\mid
k\right)>0$,

  3. (c)

$i\succ^{\ast}j$ implies $\rho\left(i\mid j\right)=1$ and$\ \rho\left(j\mid
i\right)=0$.

Therefore,

$\rho\left(j\mid i\right)\rho\left(k\mid j\right)\rho\left(i\mid
k\right)=0\quad\text{and\quad}\rho\left(k\mid i\right)\rho\left(j\mid
k\right)\rho\left(i\mid j\right)\neq 0$

which contradicts the transitivity of $\rho$. We conclude that $\succ^{\ast}$
is negatively transitive.

(ii) In view of (i), it follows from Fishburn (1970) p. 13.

(iii) Completeness is easily established. Assume _per contra_ that $\succsim$
is not transitive. Then there exist $i$, $j$ and $k$ such that $i\succsim
k\succsim j$ but $i\not\succsim j$. Alternatives $i$, $k$ and $j$ must be
distinct: $i\not\succsim j$ implies $i\neq j$, while $i=k$ would imply
$i\succsim j$, and so would $k=j$. Moreover,

  1. (a)

$i\succsim k$ implies $\rho\left(i\mid k\right)\geq\rho\left(k\mid i\right)$,

  2. (b)

$k\succsim j$ implies $\rho\left(k\mid j\right)\geq\rho\left(j\mid k\right)$,

  3. (c)

$i\not\succsim j$ implies $\rho\left(j\mid i\right)>\rho\left(i\mid j\right)$.

It holds $\rho\left(i\mid k\right)>0$. Indeed, $\rho\left(i\mid k\right)=0$
would imply $\rho\left(k\mid i\right)=1$, contradicting (a). Similarly,
$\rho\left(k\mid j\right)>0$. Then,

$\rho\left(i\mid k\right)\rho\left(k\mid j\right)\geq\rho\left(k\mid
i\right)\rho\left(j\mid k\right)\quad\text{;\quad}\rho\left(j\mid
i\right)>\rho\left(i\mid j\right)\quad\text{;\quad}\rho\left(i\mid
k\right)\rho\left(k\mid j\right)>0$

If $\rho\left(i\mid k\right)\rho\left(k\mid j\right)=\rho\left(k\mid
i\right)\rho\left(j\mid k\right)$, then both terms are strictly positive, and

$\rho\left(i\mid k\right)\rho\left(k\mid j\right)\rho\left(j\mid
i\right)>\rho\left(k\mid i\right)\rho\left(j\mid k\right)\rho\left(i\mid
j\right)$

Else $\rho\left(i\mid k\right)\rho\left(k\mid j\right)>\rho\left(k\mid
i\right)\rho\left(j\mid k\right)$, and then

$\rho\left(i\mid k\right)\rho\left(k\mid j\right)\rho\left(j\mid
i\right)>\rho\left(k\mid i\right)\rho\left(j\mid k\right)\rho\left(j\mid
i\right)\geq\rho\left(k\mid i\right)\rho\left(j\mid k\right)\rho\left(i\mid
j\right)$

In both cases the transitivity of $\rho$ is contradicted. We conclude that
$\succsim$ is transitive.

(iv) Reflexivity of $\succsim^{\circ}$ is obvious. Let
$i\succsim^{{{}^{\circ}}}j$ and $j\succsim^{{{}^{\circ}}}k$. By definition,
$i\succsim j$ and $i\parallel^{\ast}j$ as well as $j\succsim k$ and
$j\parallel^{\ast}k$. As both $\succsim$ and $\parallel^{\ast}$ are
transitive, it follows that $i\succsim k$ and $i\parallel^{\ast}k$, that is,
$i\succsim^{{{}^{\circ}}}k$. We conclude that $\succsim^{{{}^{\circ}}}$ is
transitive. Finally, assume $i\parallel^{\ast}j$, and note that also
$j\parallel^{\ast}i$. Since $\succsim$ is complete, then either $i\succsim j$
or $j\succsim i$, thus either $i\succsim^{{{}^{\circ}}}j$ or
$j\succsim^{{{}^{\circ}}}i$. $\blacksquare$

####  B.1.2 Proof of Lemma 2

Point (i) is obvious.

(ii) Let $i$ and $j$ be any two alternatives with
$w\left(i\right)=w\left(j\right)$, and let
$\tilde{u}:A\rightarrow\left(0,\infty\right)$ be such that

$\rho\left(i\mid
j\right)=s\left(i,j\right)\dfrac{\tilde{u}\left(i\right)}{\tilde{u}\left(i\right)+\tilde{u}\left(j\right)}$

We have

$\frac{\rho\left(i\mid j\right)}{\rho\left(j\mid
i\right)}=\frac{s\left(i,j\right)\dfrac{\tilde{u}\left(i\right)}{\tilde{u}\left(i\right)+\tilde{u}\left(j\right)}}{s\left(j,i\right)\dfrac{\tilde{u}\left(j\right)}{\tilde{u}\left(i\right)+\tilde{u}\left(j\right)}}=\dfrac{\tilde{u}\left(i\right)}{\tilde{u}\left(j\right)}$

Similarly,

$\frac{\rho\left(i\mid j\right)}{\rho\left(j\mid
i\right)}=\frac{s\left(i,j\right)\dfrac{u\left(i\right)}{u\left(i\right)+u\left(j\right)}}{s\left(j,i\right)\dfrac{u\left(j\right)}{u\left(i\right)+u\left(j\right)}}=\dfrac{u\left(i\right)}{u\left(j\right)}$

Therefore, for any $j^{\ast}\in A$,

$\tilde{u}\left(i\right)=\frac{\tilde{u}\left(j^{\ast}\right)}{u\left(j^{\ast}\right)}u\left(i\right)$

for all $i\in A$. We conclude that $u$ is unique up to a positive scalar
multiple.

(iii) Let $i$ and $j$ be any two alternatives with
$w\left(i\right)=w\left(j\right)$. By the symmetry of $s$,

$\rho\left(i\mid j\right)+\rho\left(j\mid
i\right)=s\left(i,j\right)\dfrac{u\left(i\right)}{u\left(i\right)+u\left(j\right)}+s\left(j,i\right)\dfrac{u\left(j\right)}{u\left(i\right)+u\left(j\right)}=s\left(i,j\right)$
(43)

Then $s$ is unique on the level set of $w\left(i\right)$. The relations in
(11) follow. $\blacksquare$

####  B.1.3 Proof of Lemma 3

Let $\rho$ be a binary choice probability. Suppose that $\rho$ is Dirac and
transitive. Let $i\neq j$. As $\rho$ is Dirac, $\rho\left(i\mid
j\right)\in\left\\{0,1\right\\}$. If $\rho\left(i\mid j\right)=1$, then
$i\succ^{\ast}j$. If $\rho\left(i\mid j\right)=0$, then $\rho\left(j\mid
i\right)=1$ and so $j\succ^{\ast}i$. We conclude that $\succ^{\ast}$ is weakly
complete.

Let $i\succ^{\ast}j$ and $j\succ^{\ast}k$. Hence, we have that
$j\not\succ^{\ast}i$, $k\not\succ^{\ast}j$, and $k\neq i$. As $\rho$ is
transitive, $\succ^{\ast}$ is negatively transitive by Lemma 1. Hence,
$k\not\succ^{\ast}i$ thus $\rho\left(i\mid k\right)\neq 0$. By the definition
of Dirac and since $i\neq k$, we have that $\rho\left(i\mid k\right)=1$, thus
$i\succ^{\ast}k$. We conclude that $\succ^{\ast}$ is transitive.

As to the converse, let $\succ^{\ast}$ be weakly complete and transitive. Let
$i\neq j$. As $\succ^{\ast}$ is weakly complete, either $i\succ^{\ast}j$ or
$j\succ^{\ast}i$. If $i\succ^{\ast}j$, then $\rho\left(i\mid j\right)=1$; if
$j\succ^{\ast}i$, then $\rho\left(j\mid i\right)=1$ and so $\rho\left(i\mid
j\right)=0$. We conclude that $\rho\left(i\mid
j\right)\in\left\\{0,1\right\\}$. This proves that $\rho$ is Dirac. Suppose,
_per contra_ , that $\rho$ is not transitive. Then, there exist three distinct
alternatives $i$, $j$ and $k$ such that

$\rho\left(j\mid i\right)\rho\left(k\mid j\right)\rho\left(i\mid
k\right)\neq\rho\left(k\mid i\right)\rho\left(j\mid k\right)\rho\left(i\mid
j\right)$

It is impossible that both sides contain a zero factor. Since $\rho$ is Dirac,
then either

$\rho\left(j\mid i\right)\rho\left(k\mid j\right)\rho\left(i\mid k\right)=1$

or

$\rho\left(k\mid i\right)\rho\left(j\mid k\right)\rho\left(i\mid j\right)=1$

In the former case, $i\succ^{\ast}k\succ^{\ast}j\succ^{\ast}i$ and so
$\succ^{\ast}$ is not transitive. In the latter case,
$i\succ^{\ast}j\succ^{\ast}k\succ^{\ast}i$ and so, again, $\succ^{\ast}$ is
not transitive. We conclude that $\rho$ must be transitive. $\blacksquare$

####  B.1.4 Theorem 4

We prove a more general result that provides a utility representation
$\bar{u}:A\rightarrow\mathbb{R}$ for the preference $\succsim$.

###### Theorem 17

Given a binary choice probability $\rho$, the following conditions are
equivalent:

  1. (i)

$\rho$ is transitive;

  2. (ii)

there exist $w,u:A\rightarrow\left(0,\infty\right)$ and a symmetric
$s:A^{2}\rightarrow\left(0,\infty\right)$ such that

$\rho\left(i\mid j\right)=\left\\{\begin{array}[c]{ll}1\vskip 6.0pt plus 2.0pt
minus 2.0pt&\qquad\text{if }w\left(i\right)>w\left(j\right)\\\
s\left(i,j\right)\dfrac{u\left(i\right)}{u\left(i\right)+u\left(j\right)}\vskip
6.0pt plus 2.0pt minus 2.0pt&\qquad\text{if
}w\left(i\right)=w\left(j\right)\\\ 0&\qquad\text{if
}w\left(i\right)<w\left(j\right)\end{array}\right.$

for all $i,j\in A$;

  3. (iii)

there exist $\bar{u}:A\rightarrow\left(0,\infty\right)$,
$f:\operatorname{Im}\bar{u}\rightarrow\left(0,\infty\right)$ increasing, and a
symmetric $s:A^{2}\rightarrow\left(0,\infty\right)$ such that

$\rho\left(i\mid j\right)=\left\\{\begin{array}[c]{ll}1\vskip 6.0pt plus 2.0pt
minus 2.0pt&\qquad\text{if
}f\left(\bar{u}\left(i\right)\right)>f\left(\bar{u}\left(j\right)\right)\\\
s\left(i,j\right)\dfrac{\bar{u}\left(i\right)}{\bar{u}\left(i\right)+\bar{u}\left(j\right)}\vskip
6.0pt plus 2.0pt minus 2.0pt&\qquad\text{if
}f\left(\bar{u}\left(i\right)\right)=f\left(\bar{u}\left(j\right)\right)\\\
0&\qquad\text{if
}f\left(\bar{u}\left(i\right)\right)<f\left(\bar{u}\left(j\right)\right)\end{array}\right.$

for all $i,j\in A$.

By setting $v=\log u$ we recover Theorem 4 (note that since $w$ is ordinally
unique we can always assume it to be strictly positive).

Proof (i) implies (iii). Since $A$ is finite there exists
$w:A\rightarrow\left(0,\infty\right)$ that represents $\succ^{\ast}$ in the
sense of (9). Then,

$\displaystyle w\left(i\right)$ $\displaystyle>w\left(j\right)\iff
i\succ^{\ast}j\iff\rho\left(i\mid j\right)=1$ $\displaystyle w\left(i\right)$
$\displaystyle<w\left(j\right)\iff j\succ^{\ast}i\iff\rho\left(i\mid
j\right)=0$ $\displaystyle w\left(i\right)$ $\displaystyle=w\left(j\right)\iff
i\parallel^{\ast}j\iff\rho\left(i\mid j\right)\in\left(0,1\right)$

By Lemma 1, $\parallel^{\ast}$ is an equivalence relation on $A$. Since $w$ is
unique up to a strictly increasing transformation, if
$\left|\operatorname{Im}w\right|=m$ we can assume
$\operatorname{Im}w=\left\\{1,2,...,m\right\\}$. For all $h=1,2,...,m$ we can
choose $i_{h}^{\ast}\in w^{-1}\left(h\right)$. With this,
$\left[i_{1}^{\ast}\right],...,\left[i_{m}^{\ast}\right]$ is the partition of
$A$ induced by $\parallel^{\ast}$. For each $h=1,...,m$, set

$u_{h}^{\ast}\left(j\right)=\dfrac{\rho\left(j\mid
i_{h}^{\ast}\right)}{\rho\left(i_{h}^{\ast}\mid j\right)}\qquad\forall
j\in\left[i_{h}^{\ast}\right]$

The ratio is well defined because $w\left(j\right)=w\left(i_{h}^{\ast}\right)$
implies $\rho\left(j\mid i_{h}^{\ast}\right),\rho\left(i_{h}^{\ast}\mid
j\right)\in\left(0,1\right)$. With this,

$\frac{u_{h}^{\ast}\left(j\right)}{u_{h}^{\ast}\left(k\right)}=\frac{\dfrac{\rho\left(j\mid
i_{h}^{\ast}\right)}{\rho\left(i_{h}^{\ast}\mid
j\right)}}{\dfrac{\rho\left(k\mid
i_{h}^{\ast}\right)}{\rho\left(i_{h}^{\ast}\mid
k\right)}}=\dfrac{\rho\left(j\mid
i_{h}^{\ast}\right)}{\rho\left(i_{h}^{\ast}\mid
j\right)}\dfrac{\rho\left(i_{h}^{\ast}\mid k\right)}{\rho\left(k\mid
i_{h}^{\ast}\right)}\qquad\forall j,k\in\left[i_{h}^{\ast}\right]$

By transitivity, we have that

$\rho\left(j\mid i\right)\rho\left(k\mid j\right)\rho\left(i\mid
k\right)=\rho\left(k\mid i\right)\rho\left(j\mid k\right)\rho\left(i\mid
j\right)$

for all $i,$ $j,$ $k\in A$,272727As previously observed, transitivity implies
the above “product rule” for all triplets of alternatives in $A$ and not only
triplets of distinct ones. and

$\dfrac{\rho\left(j\mid i_{h}^{\ast}\right)}{\rho\left(i_{h}^{\ast}\mid
j\right)}\dfrac{\rho\left(i_{h}^{\ast}\mid k\right)}{\rho\left(k\mid
i_{h}^{\ast}\right)}=\frac{\rho\left(j\mid k\right)}{\rho\left(k\mid
j\right)}$

for all $j,k\in\left[i_{h}^{\ast}\right]$. Therefore,

$\frac{u_{h}^{\ast}\left(j\right)}{u_{h}^{\ast}\left(k\right)}=\dfrac{\rho\left(j\mid
i_{h}^{\ast}\right)}{\rho\left(i_{h}^{\ast}\mid
j\right)}\dfrac{\rho\left(i_{h}^{\ast}\mid k\right)}{\rho\left(k\mid
i_{h}^{\ast}\right)}=\frac{\rho\left(j\mid k\right)}{\rho\left(k\mid
j\right)}\qquad\forall j,k\in\left[i_{h}^{\ast}\right]$

for all $h=1,...,m$.

Set $\sigma_{1}=1$ and for each $h=2,...,m$, choose a strictly positive
constant $\sigma_{h}$ such that

$\max_{j\in\left[i_{h-1}^{\ast}\right]}\sigma_{h-1}u_{h-1}^{\ast}\left(j\right)<\min_{j\in\left[i_{h}^{\ast}\right]}\sigma_{h}u_{h}^{\ast}\left(j\right)$

that is,

$\sigma_{h}>\sigma_{h-1}\frac{\max_{j\in\left[i_{h-1}^{\ast}\right]}u_{h-1}^{\ast}\left(j\right)}{\min_{j\in\left[i_{h}^{\ast}\right]}u_{h}^{\ast}\left(j\right)}$

Define

$\bar{u}\left(j\right)=\sigma_{h}u_{h}^{\ast}\left(j\right)\qquad\forall
j\in\left[i_{h}^{\ast}\right],\forall h=1,...,m$

Note that for all $h=2,...,m$, all $j_{h-1}\in\left[i_{h-1}^{\ast}\right]$ and
all $j_{h}\in\left[i_{h}^{\ast}\right]$

$\bar{u}\left(j_{h-1}\right)<\bar{u}\left(j_{h}\right)$

that is,

$\bar{u}\left(j_{1}\right)<\bar{u}\left(j_{2}\right)<\cdot\cdot\cdot<\bar{u}\left(j_{m}\right)$

whenever $j_{h}\in\left[i_{h}^{\ast}\right]$ for all $h=1,2,...,m$. Then, if
$\bar{u}\left(k\right)\geq\bar{u}\left(j\right)$, with
$k\in[i_{h_{k}}^{\ast}]$ and $j\in[i_{h_{j}}^{\ast}]$, it cannot be the case
that

$h_{j}>h_{k}$

Thus, $h_{k}\geq h_{j}$, $w\left(i_{h_{k}}^{\ast}\right)\geq
w\left(i_{h_{j}}^{\ast}\right)$, and $w\left(k\right)\geq w\left(j\right)$.
Therefore there exists
$f:\bar{u}\left(A\right)\rightarrow\left(0,\infty\right)$ increasing and such
that

$f\circ\bar{u}=w$

Thus,

$\displaystyle f\left(\bar{u}\left(i\right)\right)$
$\displaystyle>f\left(\bar{u}\left(j\right)\right)\iff\rho\left(i\mid
j\right)=1\quad\text{;\quad}f\left(\bar{u}\left(i\right)\right)=f\left(\bar{u}\left(j\right)\right)\iff\rho\left(i\mid
j\right)\in\left(0,1\right)$ $\displaystyle
f\left(\bar{u}\left(i\right)\right)$
$\displaystyle<f\left(\bar{u}\left(j\right)\right)\iff\rho\left(i\mid
j\right)=0$

For all $j\neq k$ in $A$ such that
$f\left(\bar{u}\left(j\right)\right)=f\left(\bar{u}\left(k\right)\right)$, we
have $\rho\left(j\mid k\right)\in\left(0,1\right)$, and so
$j\parallel^{\ast}k$, then there exists $h=1,...,m$ such that, for each
$j,k\in\left[i_{h}^{\ast}\right]$,

$\frac{\bar{u}\left(j\right)}{\bar{u}\left(j\right)+\bar{u}\left(k\right)}=\frac{1}{1+\frac{\bar{u}\left(k\right)}{\bar{u}\left(j\right)}}=\frac{1}{1+\frac{\sigma_{h}u^{\ast}\left(k\right)}{\sigma_{h}u^{\ast}\left(j\right)}}=\frac{1}{1+\frac{\rho\left(k\mid
j\right)}{\rho\left(j\mid k\right)}}=\frac{\rho\left(j\mid
k\right)}{\rho\left(j\mid k\right)+\rho\left(k\mid j\right)}$

and

$\rho\left(j\mid
k\right)=\,\underset{=s\left(j,k\right)}{\underbrace{(\rho\left(j\mid
k\right)+\rho\left(k\mid
j\right))}}\frac{\bar{u}\left(j\right)}{\bar{u}\left(j\right)+\bar{u}\left(k\right)}$

By setting $s\left(j,k\right)=1$ if $f\left(\bar{u}\left(i\right)\right)\neq
f\left(\bar{u}\left(j\right)\right)$ we conclude the argument.

Since (iii) trivially implies (ii), it remains to prove that (ii) implies (i).
Let $u$, $w$ and $s$ represent $\rho$ as in (ii). We have already observed
that $w$ represents $\succ^{\ast}$.

For any triplet $i,j,k$ of distinct elements of $A$, consider the two products

$\rho\left(j\mid i\right)\rho\left(k\mid j\right)\rho\left(i\mid
k\right)\qquad\text{and}\qquad\rho\left(k\mid i\right)\rho\left(j\mid
k\right)\rho\left(i\mid j\right)$

Suppose first that $i,j,k$ do not belong to the same level set of $w$. Without
loss of generality, we can then set $\rho\left(j\mid i\right)=0$. Hence,
$\rho\left(i\mid j\right)=1$ and so $i\succ^{\ast}j$, that is,
$w\left(i\right)>w\left(j\right)$. There are two cases to consider.

  1. (1)

If $w\left(k\right)\geq w\left(i\right)$, then
$w\left(k\right)>w\left(j\right)$ and so $\rho\left(j\mid k\right)=0$.

  2. (2)

Else $w\left(i\right)>w\left(k\right)$, then $\rho\left(k\mid i\right)=0$.

In both cases, the two products are null, so equal. Next suppose that $i,j,k$
belong to the same level set of $w$. Then,

$\displaystyle\rho\left(j\mid i\right)\rho\left(k\mid j\right)\rho\left(i\mid
k\right)$
$\displaystyle=s\left(j,i\right)\dfrac{u\left(j\right)}{u\left(j\right)+u\left(i\right)}s\left(k,j\right)\dfrac{u\left(k\right)}{u\left(k\right)+u\left(j\right)}s\left(i,k\right)\dfrac{u\left(i\right)}{u\left(i\right)+u\left(k\right)}$
$\displaystyle=s\left(k,i\right)\dfrac{u\left(i\right)}{u\left(k\right)+u\left(i\right)}s\left(j,k\right)\dfrac{u\left(k\right)}{u\left(j\right)+u\left(k\right)}s\left(i,j\right)\dfrac{u\left(j\right)}{u\left(i\right)+u\left(j\right)}$
$\displaystyle=s\left(k,i\right)\dfrac{u\left(k\right)}{u\left(k\right)+u\left(i\right)}s\left(j,k\right)\dfrac{u\left(j\right)}{u\left(j\right)+u\left(k\right)}s\left(i,j\right)\dfrac{u\left(i\right)}{u\left(i\right)+u\left(j\right)}$
$\displaystyle=\rho\left(k\mid i\right)\rho\left(j\mid k\right)\rho\left(i\mid
j\right)$

We conclude that $\rho$ is transitive. $\blacksquare$

####  B.1.5 Theorem 5

“Only if.” If a tandem has a binary value representation
$\left(v,w,s,\varphi\right)$, then $\rho$ is transitive (see Theorem 4).
Consider the set

$\displaystyle\mathbb{D}$
$\displaystyle=\left\\{\left(i,j\right):\tau\left(i\mid j\right)\neq
0\right\\}=\left\\{\left(i,j\right):\rho\left(i\mid
j\right)\in\left(0,1\right)\right\\}$
$\displaystyle=\left\\{\left(i,j\right):i\parallel^{\ast}j\right\\}=\left\\{\left(i,j\right):w\left(i\right)=w\left(j\right)\right\\}$

Note that for all $\left(i,j\right)\in\mathbb{D}$,

$\ell_{ij}=\ln\frac{\rho\left(i\mid j\right)}{\rho\left(j\mid
i\right)}=v\left(i\right)-v\left(j\right)$

thus (16) delivers

$\ell_{ij}=\ell_{hk}\implies
v\left(i\right)-v\left(j\right)=v\left(h\right)-v\left(k\right)\implies\tau\left(i\mid
j\right)=\tau\left(h\mid k\right)$

for all $\left(i,j\right),\left(h,k\right)\in\mathbb{D}$. Thus (17) is
satisfied.

Since $\varphi$ is strictly quasiconcave and unimodal, then there exists a
unique $l\in\mathbb{R}$ such that $\varphi$ is strictly increasing on
$\left(-\infty,l\right]$ and strictly decreasing on $\left[l,\infty\right)$,
then

$\displaystyle l$ $\displaystyle\leq\ell_{ij}<\ell_{hk}\implies l\leq
v\left(i\right)-v\left(j\right)<v\left(h\right)-v\left(k\right)$
$\displaystyle\implies\varphi\left(v\left(i\right)-v\left(j\right)\right)>\varphi\left(v\left(h\right)-v\left(k\right)\right)\implies\tau\left(i\mid
j\right)>\tau\left(h\mid k\right)$

and

$\displaystyle\ell_{ij}$ $\displaystyle<\ell_{hk}\leq l\implies
v\left(i\right)-v\left(j\right)<v\left(h\right)-v\left(k\right)\leq l$
$\displaystyle\implies\varphi\left(v\left(i\right)-v\left(j\right)\right)<\varphi\left(v\left(h\right)-v\left(k\right)\right)\implies\tau\left(i\mid
j\right)<\tau\left(h\mid k\right)$

for all $\left(i,j\right),\left(h,k\right)\in\mathbb{D}$. Thus (18) and (19)
are satisfied, as desired.

“If.” If a tandem is chronometric then $\rho$ is transitive and there exist
$v,w:A\rightarrow\mathbb{R}$ and a symmetric
$s:A^{2}\rightarrow\left(0,\infty\right)$ such that (8) holds. Consider the
set

$\displaystyle\mathbb{D}$
$\displaystyle=\left\\{\left(i,j\right):\tau\left(i\mid j\right)\neq
0\right\\}=\left\\{\left(i,j\right):\rho\left(i\mid
j\right)\in\left(0,1\right)\right\\}$
$\displaystyle=\left\\{\left(i,j\right):i\parallel^{\ast}j\right\\}=\left\\{\left(i,j\right):w\left(i\right)=w\left(j\right)\right\\}$

Note that for all $\left(i,j\right)\in\mathbb{D}$,

$\ell_{ij}=\ln\frac{\rho\left(i\mid j\right)}{\rho\left(j\mid
i\right)}=v\left(i\right)-v\left(j\right)$

and set
$L=\left\\{\ell_{ij}:\left(i,j\right)\in\mathbb{D}\right\\}=\left\\{v\left(i\right)-v\left(j\right):\left(i,j\right)\in\mathbb{D}\right\\}$.
With this, (17) implies that there exists
$\psi:L\rightarrow\left(0,\infty\right)$ such that

$\tau\left(i\mid
j\right)=\psi\left(\ell_{ij}\right)=\psi\left(v\left(i\right)-v\left(j\right)\right)$

for all $\left(i,j\right)\in\mathbb{D}$. Moreover, by (18), if $x,y\in L$ are
such that $l\leq x<y$, taking $\left(i,j\right)$ and $\left(h,k\right)\ $in
$\mathbb{D}$ such that $x=\ell_{ij}$ and $y=\ell_{hk}$, it follows that

$l\leq\ell_{ij}<\ell_{hk}\implies\tau\left(i\mid j\right)>\tau\left(h\mid
k\right)\implies\psi\left(\ell_{ij}\right)>\psi\left(\ell_{hk}\right)\implies\psi\left(x\right)>\psi\left(y\right)$

Analogously, by (19), if $x,y\in L$ are such that $x<y\leq l$, taking
$\left(i,j\right)$ and $\left(h,k\right)\ $in $\mathbb{D}$ such that
$x=\ell_{ij}$ and $y=\ell_{hk}$, it follows that

$\ell_{ij}<\ell_{hk}\leq l\implies\tau\left(i\mid j\right)<\tau\left(h\mid
k\right)\implies\psi\left(\ell_{ij}\right)<\psi\left(\ell_{hk}\right)\implies\psi\left(x\right)<\psi\left(y\right)$

Summing up, $L$ is a finite subset of $\mathbb{R}$ and
$\psi:L\rightarrow\left(0,\infty\right)$ is such that there exists
$l\in\mathbb{R}$ for which

$\displaystyle l$ $\displaystyle\leq
x<y\implies\psi\left(x\right)>\psi\left(y\right)$ $\displaystyle x$
$\displaystyle<y\leq l\implies\psi\left(x\right)<\psi\left(y\right)$

for all $x,y\in L$.

This allows to extend $\psi$ to a function
$\varphi:\mathbb{R}\rightarrow\left(0,\infty\right)$ such that $\varphi$ is
strictly increasing on $\left(-\infty,l\right]$ and strictly decreasing on
$\left[l,\infty\right)$. Thus there exists a strictly quasiconcave and
unimodal $\varphi:\mathbb{R}\rightarrow\left(0,\infty\right)$ such that

$\tau\left(i\mid j\right)=\varphi\left(v\left(i\right)-v\left(j\right)\right)$

if $w\left(i\right)=w\left(j\right)$.

Finally, if $w\left(i\right)\neq w\left(j\right)$, by (8), $\rho\left(i\mid
j\right)\in\left\\{0,1\right\\}$ and by definition of tandem $\tau\left(i\mid
j\right)=0$. $\blacksquare$

####  B.1.6 Theorem 6

Note that if either $\left(\rho,\tau\right)$ has a binary value representation
or it is psychometric, then $\rho$ is transitive and there exist
$v,w:A\rightarrow\mathbb{R}$ and a symmetric
$s:A^{2}\rightarrow\left(0,\infty\right)$ such that (8) holds. Therefore the
set of pairs of alternatives with nonzero response time is

$\displaystyle\mathbb{D}$
$\displaystyle=\left\\{\left(i,j\right):\tau\left(i\mid j\right)\neq
0\right\\}=\left\\{\left(i,j\right):\rho\left(i\mid
j\right)\in\left(0,1\right)\right\\}$
$\displaystyle=\left\\{\left(i,j\right):i\parallel^{\ast}j\right\\}=\left\\{\left(i,j\right):w\left(i\right)=w\left(j\right)\right\\}$

Arbitrarily choose $\left(i,j\right)\in\mathbb{D}$, since
$i\parallel^{\ast}j$, by Lemma 1, we can assume, without loss of generality,
that $i\succsim^{{{}^{\circ}}}j$, thus

$\rho\left(i\mid j\right)\geq\rho\left(j\mid
i\right)\quad\text{and\quad}1-\rho\left(j\mid i\right)\geq 1-\rho\left(i\mid
j\right)$

A second-type error is the probability of accepting an inferior proposal, that
is,

$\mathrm{ER}_{i,j}^{\mathrm{II}}=\rho\left(j\mid
i\right)=\min\left\\{\rho\left(i\mid j\right),\rho\left(j\mid
i\right)\right\\}$

A first-type error is the probability of rejecting a superior proposal, that
is,

$\mathrm{ER}_{i,j}^{\mathrm{I}}=1-\rho\left(i\mid
j\right)=\min\left\\{1-\rho\left(i\mid j\right),1-\rho\left(j\mid
i\right)\right\\}$

Since (8) holds, $i\succsim^{{{}^{\circ}}}j$ if and only if
$v\left(i\right)\geq v\left(j\right)$. Therefore:

$\displaystyle\mathrm{ER}_{i,j}^{\mathrm{II}}$ $\displaystyle=\rho\left(j\mid
i\right)=s\left(j,i\right)\frac{1}{1+e^{-\left(v\left(j\right)-v\left(i\right)\right)}}=s\left(j,i\right)\frac{1}{1+e^{\left|v\left(j\right)-v\left(i\right)\right|}}$
$\displaystyle=s\left(i,j\right)\frac{1}{1+e^{\left|v\left(i\right)-v\left(j\right)\right|}}$
$\displaystyle\mathrm{ER}_{i,j}^{\mathrm{I}}$ $\displaystyle=1-\rho\left(i\mid
j\right)=1-s\left(i,j\right)\frac{1}{1+e^{-\left(v\left(i\right)-v\left(j\right)\right)}}=1-s\left(i,j\right)\frac{1}{1+e^{-\left|v\left(i\right)-v\left(j\right)\right|}}$
$\displaystyle=1-\mathrm{ER}_{i,j}^{\mathrm{II}}\frac{1+e^{\left|v\left(i\right)-v\left(j\right)\right|}}{1+e^{-\left|v\left(i\right)-v\left(j\right)\right|}}$

Summing up, for each $\left(i,j\right)\in\mathbb{D}$,

$\displaystyle\mathrm{ER}_{i,j}^{\mathrm{II}}$
$\displaystyle=s\left(i,j\right)\frac{1}{1+e^{\left|v\left(i\right)-v\left(j\right)\right|}}$
$\displaystyle\mathrm{ER}_{i,j}^{\mathrm{I}}$
$\displaystyle=1-\mathrm{ER}_{i,j}^{\mathrm{II}}\frac{1+e^{\left|v\left(i\right)-v\left(j\right)\right|}}{1+e^{-\left|v\left(i\right)-v\left(j\right)\right|}}$

But then, for all $\left(i,j\right)$ and $\left(h,k\right)$ in $\mathbb{D}$
such that $\mathrm{ER}_{i,j}^{\mathrm{I}}<\mathrm{ER}_{h,k}^{\mathrm{I}}\ $and
$\mathrm{ER}_{i,j}^{\mathrm{II}}<\mathrm{ER}_{h,k}^{\mathrm{II}}$, it follows
that

$\displaystyle
1-\mathrm{ER}_{i,j}^{\mathrm{II}}\frac{1+e^{\left|v\left(i\right)-v\left(j\right)\right|}}{1+e^{-\left|v\left(i\right)-v\left(j\right)\right|}}<1-\mathrm{ER}_{h,k}^{\mathrm{II}}\frac{1+e^{\left|v\left(h\right)-v\left(k\right)\right|}}{1+e^{-\left|v\left(h\right)-v\left(k\right)\right|}}$
$\displaystyle\mathrm{ER}_{h,k}^{\mathrm{II}}\frac{1+e^{\left|v\left(h\right)-v\left(k\right)\right|}}{1+e^{-\left|v\left(h\right)-v\left(k\right)\right|}}<\mathrm{ER}_{i,j}^{\mathrm{II}}\frac{1+e^{\left|v\left(i\right)-v\left(j\right)\right|}}{1+e^{-\left|v\left(i\right)-v\left(j\right)\right|}}$
$\displaystyle\frac{\frac{1+e^{\left|v\left(h\right)-v\left(k\right)\right|}}{1+e^{-\left|v\left(h\right)-v\left(k\right)\right|}}}{\frac{1+e^{\left|v\left(i\right)-v\left(j\right)\right|}}{1+e^{-\left|v\left(i\right)-v\left(j\right)\right|}}}<\frac{\mathrm{ER}_{i,j}^{\mathrm{II}}}{\mathrm{ER}_{h,k}^{\mathrm{II}}}<1$
$\displaystyle\frac{1+e^{\left|v\left(h\right)-v\left(k\right)\right|}}{1+e^{-\left|v\left(h\right)-v\left(k\right)\right|}}<\frac{1+e^{\left|v\left(i\right)-v\left(j\right)\right|}}{1+e^{-\left|v\left(i\right)-v\left(j\right)\right|}}$
$\displaystyle\left|v\left(h\right)-v\left(k\right)\right|<\left|v\left(i\right)-v\left(j\right)\right|$

in other words

$\mathrm{ER}_{i,j}^{\mathrm{I}}<\mathrm{ER}_{h,k}^{\mathrm{I}}\quad\text{and\quad}\mathrm{ER}_{i,j}^{\mathrm{II}}<\mathrm{ER}_{h,k}^{\mathrm{II}}\Longrightarrow\left|v\left(i\right)-v\left(j\right)\right|>\left|v\left(h\right)-v\left(k\right)\right|$
(44)

A similar argument shows that

$\mathrm{ER}_{i,j}^{\mathrm{I}}\leq\mathrm{ER}_{h,k}^{\mathrm{I}}\quad\text{and\quad}\mathrm{ER}_{i,j}^{\mathrm{II}}\leq\mathrm{ER}_{h,k}^{\mathrm{II}}\Longrightarrow\left|v\left(i\right)-v\left(j\right)\right|\geq\left|v\left(h\right)-v\left(k\right)\right|$
(45)

“If.” If $\left(\rho,\tau\right)$ is psychometric, then (44) and (45) imply

$\tau\left(i\mid j\right)<\tau\left(h\mid
k\right)\Longrightarrow\left|v\left(i\right)-v\left(j\right)\right|>\left|v\left(h\right)-v\left(k\right)\right|$
(46)

and

$\tau\left(i\mid j\right)\leq\tau\left(h\mid
k\right)\Longrightarrow\left|v\left(i\right)-v\left(j\right)\right|\geq\left|v\left(h\right)-v\left(k\right)\right|$
(47)

for all $\left(i,j\right)$ and $\left(h,k\right)$ in $\mathbb{D}$. As a result

$\left|v\left(i\right)-v\left(j\right)\right|\geq\left|v\left(h\right)-v\left(k\right)\right|\Longleftrightarrow\tau\left(i\mid
j\right)\leq\tau\left(h\mid k\right)$

Therefore, setting
$M=\left\\{\left|v\left(i\right)-v\left(j\right)\right|:\left(i,j\right)\in\mathbb{D}\right\\}$,
there is a strictly decreasing function
$\psi:M\rightarrow\left(0,\infty\right)$ such that $\tau\left(i\mid
j\right)=\psi\left(\left|v\left(i\right)-v\left(j\right)\right|\right)$. We
can first extend $\psi$ from $M$ to $\left[0,\infty\right)$ as a strictly
decreasing function and then set
$\varphi\left(x\right)=\psi\left(\left|x\right|\right)$ for all
$x\in\mathbb{R}$. With this, there exists a strictly quasiconcave, unimodal,
and even $\varphi:\mathbb{R}\rightarrow\left(0,\infty\right)$ such that

$\tau\left(i\mid j\right)=\varphi\left(v\left(i\right)-v\left(j\right)\right)$

if $w\left(i\right)=w\left(j\right)$.

Finally, if $w\left(i\right)\neq w\left(j\right)$, by (8), $\rho\left(i\mid
j\right)\in\left\\{0,1\right\\}$ and by definition of tandem $\tau\left(i\mid
j\right)=0$.

“Only if.” If a tandem has a binary value representation
$\left(v,w,s,\varphi\right)$, then $\rho$ is transitive (see Theorem 4). Now
$\varphi$ is strictly quasiconcave, unimodal, and even
$\varphi:\mathbb{R}\rightarrow\left(0,\infty\right)$, with strong maximum at
$0$ and strictly decreasing on $\left[0,\infty\right)$. In particular,

$\tau\left(i\mid j\right)=\tau\left(j\mid i\right)$

for all alternatives $i$ and $j$. But then $\rho$ is unbiased, and so
$s\left(i,j\right)=1$ for all $\left(i,j\right)\in\mathbb{D}$, and so

$\mathrm{ER}_{i,j}^{\mathrm{I}}=\mathrm{ER}_{i,j}^{\mathrm{II}}=\frac{1}{1+e^{\left|v\left(i\right)-v\left(j\right)\right|}}$

Moreover, for all $\left(i,j\right)$ and $\left(h,k\right)$ in $\mathbb{D}$,

$\displaystyle\left.\tau\left(i\mid j\right)<\tau\left(h\mid k\right)\right.$
$\displaystyle\iff\varphi\left(\left|v\left(i\right)-v\left(j\right)\right|\right)<\varphi\left(\left|v\left(h\right)-v\left(k\right)\right|\right)$
$\displaystyle\iff\left|v\left(i\right)-v\left(j\right)\right|>\left|v\left(h\right)-v\left(k\right)\right|$
$\displaystyle\iff\mathrm{ER}_{i,j}<\mathrm{ER}_{h,k}$

This proves that $\left(\rho,\tau\right)$ is psychometric. $\blacksquare$

###  B.2 Section 4

####  B.2.1 Subsection 4.1

To ease notation, we set $\Lambda_{ij}=\nu\left(i\right)-\nu\left(j\right)$ as
well as

$\rho_{\mathrm{C}}\left(i\mid
j\right)=\rho_{ij}\quad\text{;}\quad\rho_{\mathrm{C}}\left(j\mid
i\right)=\rho_{ji}\quad\text{;}\quad\tau_{\mathrm{RT}}\left(i\mid
j\right)=\tau_{ij}\quad\text{;}\quad\tau_{\mathrm{RT}}\left(j\mid
i\right)=\tau_{ji}\quad\text{;}\quad s_{\mathrm{C}}\left(i,j\right)=s_{ij}$

By Theorems 8.1 and 8.2 of Pinsky and Karlin (2011),

$\rho_{ij}=\frac{1-e^{\beta\Lambda_{ij}}}{e^{-\lambda\Lambda_{ij}}-e^{\beta\Lambda_{ij}}}\quad\text{and\quad}\tau_{ij}=\frac{1}{\Lambda_{ij}}\left[\rho_{ij}\left(\lambda+\beta\right)-\beta\right]$
(48)

also note that

$\rho_{ij}=\frac{1-e^{-\beta\Lambda_{ij}}}{1-e^{-\left(\lambda+\beta\right)\Lambda_{ij}}}$

We begin with a few preliminary lemmas.

###### Lemma 18

For each $\left(i,j\right)\in A^{2}$, it holds

$\lambda\Lambda_{ij}=\ln\frac{\rho_{ij}}{\rho_{ji}}\quad\text{;}\quad\beta\Lambda_{ij}=\ln\frac{1-\rho_{ji}}{1-\rho_{ij}}$
(49)

Proof Let $\left(i,j\right)\in A^{2}$. We have

$\frac{\rho_{ij}}{\rho_{ji}}=\frac{\frac{1-e^{\beta\Lambda_{ij}}}{e^{-\lambda\Lambda_{ij}}-e^{\beta\Lambda_{ij}}}}{\frac{1-e^{-\beta\Lambda_{ij}}}{e^{\lambda\Lambda_{ij}}-e^{-\beta\Lambda_{ij}}}}=e^{\lambda\Lambda_{ij}}$

and so $\lambda\Lambda_{i,j}=\ln\rho_{ij}/\rho_{ji}$. We also have

$\frac{1-\rho_{ji}}{1-\rho_{ij}}=\frac{1-\frac{1-e^{-\beta\Lambda_{ij}}}{e^{\lambda\Lambda_{ij}}-e^{-\beta\Lambda_{ij}}}}{1-\frac{1-e^{\beta\Lambda_{ij}}}{e^{-\lambda\Lambda_{ij}}-e^{\beta\Lambda_{ij}}}}=\frac{\frac{e^{\lambda\Lambda_{ij}}-1}{e^{\lambda\Lambda_{ij}}-e^{-\beta\Lambda_{ij}}}}{\frac{1-e^{-\lambda\Lambda_{ij}}}{e^{\beta\Lambda_{ij}}-e^{-\lambda\Lambda_{ij}}}}=e^{\beta\Lambda_{ij}}$

and so
$\beta\Lambda_{i,j}=\ln\left(1-\rho_{ji}\right)/\left(1-\rho_{ij}\right)$.
$\blacksquare$

###### Lemma 19

Let $\left(i,j\right)\in A^{2}$ with $\Lambda_{ij}\neq 0$. It holds

$\tau_{ij}=\frac{\lambda^{2}}{\ln\rho_{ij}-\ln\rho_{ji}}\left[\rho_{ij}+\frac{\ln\left(1-\rho_{ji}\right)-\ln\left(1-\rho_{ij}\right)}{\ln\rho_{ij}-\ln\rho_{ji}}\left(\rho_{ij}-1\right)\right]$
(50)

Proof By (49),

$\frac{\beta}{\lambda}=\frac{\beta\Lambda_{ij}}{\lambda\Lambda_{ij}}=\frac{\ln\frac{1-\rho_{ji}}{1-\rho_{ij}}}{\ln\frac{\rho_{ij}}{\rho_{ji}}}=\frac{\ln\left(1-\rho_{ji}\right)-\ln\left(1-\rho_{ij}\right)}{\ln\rho_{ij}-\ln\rho_{ji}}$
(51)

Hence,

$\displaystyle\tau_{ij}$
$\displaystyle=\frac{1}{\Lambda_{ij}}\left[\rho_{ij}\left(\lambda+\beta\right)-\beta\right]=\frac{\lambda^{2}}{\lambda\Lambda_{ij}}\left[\rho_{ij}\left(1+\frac{\beta}{\lambda}\right)-\frac{\beta}{\lambda}\right]=\frac{\lambda^{2}}{\lambda\Lambda_{ij}}\left[\rho_{ij}+\frac{\beta}{\lambda}\left(\rho_{ij}-1\right)\right]$
$\displaystyle=\frac{\lambda^{2}}{\ln\rho_{ij}-\ln\rho_{ji}}\left[\rho_{ij}+\frac{\ln\left(1-\rho_{ji}\right)-\ln\left(1-\rho_{ij}\right)}{\ln\rho_{ij}-\ln\rho_{ji}}\left(\rho_{ij}-1\right)\right]$

as desired. $\blacksquare$

###### Lemma 20

Let $\left(i,j\right)\in A^{2}$ with $\Lambda_{ij}\neq 0$. If
$\tau_{ij}=\tau_{ji}$, then $\beta=\lambda$.

Proof To further ease notation, set $x=\rho_{ij}$ and $y=\rho_{ji}$. Since
$\Lambda_{ij}\neq 0$, by (49) we have $x\neq y$. By (50), we have

$\displaystyle\tau_{ij}$ $\displaystyle=\tau_{ji}$
$\displaystyle\Longleftrightarrow\frac{\lambda^{2}}{\ln\frac{x}{y}}\left[x+\frac{\ln\frac{1-y}{1-x}}{\ln\frac{x}{y}}\left(x-1\right)\right]=\frac{\lambda^{2}}{\ln\frac{y}{x}}\left[y+\frac{\ln\frac{1-x}{1-y}}{\ln\frac{y}{x}}\left(y-1\right)\right]$
$\displaystyle\Longleftrightarrow\frac{\ln\frac{y}{x}}{\ln\frac{x}{y}}\left[x+\frac{\ln\frac{1-y}{1-x}}{\ln\frac{x}{y}}\left(x-1\right)\right]=y+\frac{\ln\frac{1-x}{1-y}}{\ln\frac{y}{x}}\left(y-1\right)$
$\displaystyle\Longleftrightarrow-x-\frac{\ln\frac{1-y}{1-x}}{\ln\frac{x}{y}}\left(x-1\right)=y+\frac{\ln\frac{1-x}{1-y}}{\ln\frac{y}{x}}\left(y-1\right)$
$\displaystyle\Longleftrightarrow\frac{\ln\frac{1-y}{1-x}}{\ln\frac{y}{x}}\left(y-1\right)+\frac{\ln\frac{1-y}{1-x}}{\ln\frac{y}{x}}\left(x-1\right)=y+x\Longleftrightarrow\frac{2}{x+y}+\frac{\ln\frac{y}{x}}{\ln\frac{1-y}{1-x}}=1$

The locus of pairs
$\left(x,y\right)\in\left(0,1\right)\times\left(0,1\right)$, with $x\neq y$,
that solve this equation is

$\left\\{\left(x,y\right)\in\left(0,1\right)_{\neq}^{2}:x=1-y\right\\}$

Thus, $\rho_{ij}=1-\rho_{ji}$. By (49),

$\frac{\beta}{\lambda}=\frac{\beta\Lambda_{ij}}{\lambda\Lambda_{ij}}=\frac{\ln\frac{1-\rho_{ji}}{1-\rho_{ij}}}{\ln\frac{\rho_{ij}}{\rho_{ji}}}=\frac{\ln\frac{\rho_{ij}}{\rho_{ji}}}{\ln\frac{\rho_{ij}}{\rho_{ji}}}=1$

We conclude that $\beta=\lambda$. $\blacksquare$

##### Proof of Proposition 7

Positivity of $\rho=\rho_{\mathrm{C}}$ follows immediately from (48) and hence
$\rho$ is a binary choice probability. So, to establish whether
$\left(\rho,\tau\right)$ is a tandem we need to check only condition (15).
When $\beta=\lambda$, this condition trivially holds because $\rho$ is
unbiased and $\tau$ is symmetric. Since $\nu$ is injective, we have
$\Lambda_{ij}\neq 0$ for all distinct $i$ and $j$ in $A$. By Lemma 20, it must
then be the case that $\tau_{ij}\neq\tau_{ji}$; so, condition (15) now
vacuously holds. We conclude that $\left(\rho,\tau\right)$ is a tandem.
Finally, the transitivity of $\rho$ follows by Theorem 15 because Baldassi et
al. (2020) show that, given any nice exploration matrix $Q$, the transition
matrix $M$ is reversible.282828Of course, it can also be verified by brute
force from (48).

We now turn to the binary value representation. By positivity,
$w_{\mathrm{C}}$ is constant. For all $i\ $and $j$ in $A$,

$s_{ij}=\rho_{ij}+\rho_{ji}=\dfrac{1-e^{-\beta\Lambda_{ij}}}{1-e^{-\left(\lambda+\beta\right)\Lambda_{ij}}}+\dfrac{1-e^{\beta\Lambda_{ij}}}{1-e^{\left(\lambda+\beta\right)\Lambda_{ij}}}=1+\dfrac{e^{\lambda\Lambda_{ij}}-e^{\beta\Lambda_{ij}}}{1-e^{\left(\lambda+\beta\right)\Lambda_{ij}}}$

by symmetry

$s_{ij}=s_{ji}=1+\dfrac{e^{\lambda\left(-\Lambda_{ij}\right)}-e^{\beta\left(-\Lambda_{ij}\right)}}{1-e^{\left(\lambda+\beta\right)\left(-\Lambda_{ij}\right)}}$

and so

$s_{\mathrm{C}}\left(i,j\right)=s_{ij}=1+\dfrac{e^{\lambda\Lambda_{ij}}-e^{\beta\Lambda_{ij}}}{1-e^{\left(\lambda+\beta\right)\Lambda_{ij}}}=1+\dfrac{e^{\lambda\left|\Lambda_{ij}\right|}-e^{\beta\left|\Lambda_{ij}\right|}}{1-e^{\left(\lambda+\beta\right)\left|\Lambda_{ij}\right|}}$

Moreover,

$s_{ij}\frac{1}{1+e^{-\lambda\Lambda_{ij}}}=\left(1+\dfrac{e^{\lambda\Lambda_{ij}}-e^{\beta\Lambda_{ij}}}{1-e^{\left(\lambda+\beta\right)\Lambda_{ij}}}\right)\frac{1}{1+e^{-\lambda\Lambda_{ij}}}=\dfrac{1-e^{-\beta\Lambda_{ij}}}{1-e^{-\left(\lambda+\beta\right)\Lambda_{ij}}}=\rho_{ij}$

This proves that $v_{\mathrm{C}}=\lambda\nu$, thus completing the proof of
(22).

As to (23),

$\displaystyle\tau_{ij}$
$\displaystyle=\frac{\lambda^{2}}{\lambda\Lambda_{ij}}\left[\rho_{ij}\left(1+\frac{\beta}{\lambda}\right)-\frac{\beta}{\lambda}\right]=\frac{\lambda^{2}}{\lambda\Lambda_{ij}}\left[\frac{1-e^{\beta\Lambda_{ij}}}{e^{-\lambda\Lambda_{ij}}-e^{\beta\Lambda_{ij}}}\left(1+\frac{\beta}{\lambda}\right)-\frac{\beta}{\lambda}\right]$
$\displaystyle=\frac{\lambda^{2}}{\lambda\Lambda_{ij}}\left[\frac{1-e^{\frac{\beta}{\lambda}\lambda\Lambda_{ij}}}{e^{-\lambda\Lambda_{ij}}-e^{\frac{\beta}{\lambda}\lambda\Lambda_{ij}}}\left(1+\frac{\beta}{\lambda}\right)-\frac{\beta}{\lambda}\right]$

but
$\lambda\Lambda_{ij}=v_{\mathrm{C}}\left(i\right)-v_{\mathrm{C}}\left(j\right)$.
We can then define $\varphi_{\mathrm{RT}}:\mathbb{R}\rightarrow\mathbb{R}$ by

$\varphi_{\mathrm{RT}}\left(x\right)=\frac{\lambda^{2}}{x}\left[\frac{1-e^{\frac{\beta}{\lambda}x}}{e^{-x}-e^{\frac{\beta}{\lambda}x}}\left(1+\frac{\beta}{\lambda}\right)-\frac{\beta}{\lambda}\right]$

and obtain
$\tau_{ij}=\varphi_{\mathrm{RT}}\left(v_{\mathrm{C}}\left(i\right)-v_{\mathrm{C}}\left(j\right)\right)$.
$\blacksquare$

##### Proof of Proposition 8

By (50),

$\tau_{ij}=\frac{\lambda^{2}}{\ell_{ij}}\left[\rho_{ij}+\frac{\bar{\ell}_{ij}}{\ell_{ij}}\left(\rho_{ij}-1\right)\right]=\frac{\lambda^{2}}{\ell_{ij}^{2}}\left[\ell_{ij}\rho_{ij}+\bar{\ell}_{ij}\left(\rho_{ij}-1\right)\right]$

thus

$\lambda=\left|\ell_{ij}\right|\sqrt{\frac{\tau_{ij}}{\ell_{ij}\rho_{ij}+\bar{\ell}_{ij}\left(\rho_{ij}-1\right)}}$

as desired. By (51), $\beta=\lambda\bar{\ell}_{ij}/\ell_{ij}$. Finally, set
$\nu\left(j^{\ast}\right)=0$ for some alternative $j^{\ast}$. By (49), for
each $i$ we have

$\nu\left(i\right)=\nu\left(i\right)-\nu\left(j^{\ast}\right)=\Lambda_{ij^{\ast}}=\frac{1}{\lambda}\ell_{ij^{\ast}}$

concluding the proof. $\blacksquare$

##### Proof of Proposition 9

By Proposition 7, the tandem
$\left(\rho_{\mathrm{C}},\tau_{\mathrm{RT}}\right)$ is chronometric.

(i) implies (iii) If $\varphi_{\mathrm{RT}}$ is even, then

$\tau_{\mathrm{RT}}\left(i\mid
j\right)=\varphi_{\mathrm{RT}}\left(v_{\mathrm{C}}\left(i\right)-v_{\mathrm{C}}\left(j\right)\right)=\varphi_{\mathrm{RT}}\left(v_{\mathrm{C}}\left(j\right)-v_{\mathrm{C}}\left(i\right)\right)=\tau_{\mathrm{RT}}\left(j\mid
i\right)$

for all $i\neq j$.

(iii) implies (ii). If $\tau_{\mathrm{RT}}\left(i\mid
j\right)=\tau_{\mathrm{RT}}\left(j\mid i\right)$ for some $i\neq j$, since
$\nu$ is injective, then $\Lambda_{ij}\neq 0$ and so, by Lemma 20,
$\beta=\lambda$.

(ii) implies (iv). Indeed if $\beta=\lambda$, then

$s_{\mathrm{C}}\left(i,j\right)=1+\dfrac{e^{\lambda\left|\nu\left(i\right)-\nu\left(j\right)\right|}-e^{\beta\left|\nu\left(i\right)-\nu\left(j\right)\right|}}{1-e^{\left(\lambda+\beta\right)\left|\nu\left(i\right)-\nu\left(j\right)\right|}}=1$

for all $i\ $and $j$, and so $\rho_{\mathrm{C}}$ is unbiased.

(iv) implies (i) If $\rho_{\mathrm{C}}\left(i\mid
j\right)=1-\rho_{\mathrm{C}}\left(j\mid i\right)$ for some $i\neq j$, then
$\rho_{\mathrm{C}}\left(j\mid i\right)=1-\rho_{\mathrm{C}}\left(i\mid
j\right)$, and, by Lemma 18,

$\lambda\Lambda_{ij}=\beta\Lambda_{ij}$

Since $\nu$ is injective, then $\Lambda_{ij}\neq 0$ and $\beta=\lambda$. In
particular,

$\varphi_{\mathrm{RT}}\left(x\right)=\frac{\lambda^{2}}{x}\left(2\frac{1-e^{x}}{e^{-x}-e^{x}}-1\right)=\frac{\lambda^{2}}{x}\tanh\left(\frac{x}{2}\right)$

is even. $\blacksquare$

####  B.2.2 Stochastic matrices

A sequence $a=\left\\{a_{n}\right\\}$ of non-negative scalars is _summable_ if
${\displaystyle\sum\limits_{n=0}^{\infty}}a_{n}<\infty$. Its _generating
function_ given by

$f_{a}\left(z\right)={\displaystyle\sum\limits_{n=0}^{\infty}}a_{n}z^{n}$ (52)

is defined where the power series on the right hand side converges.
Summability of $\left\\{a_{n}\right\\}$ guarantees that the radius of
convergence $R$ satisfies $R\geq 1$ and that $f_{a}\left(z\right)$ is defined
and continuous on the unit disk$\mathbb{\
}\left\\{z\in\mathbb{C}:\left|z\right|\leq 1\right\\}$.

###### Lemma 21

If $a=\left\\{a_{n}\right\\}$ is a non-negative and summable sequence, then
the matrix power series ${\displaystyle\sum\limits_{n=0}^{\infty}}a_{n}B^{n}$
converges (entry by entry) for all stochastic matrices $B$.

Proof The $\left(i,j\right)$-th entry $b_{ij}^{(n)}$ of the matrix $B^{n}$
belongs to $\left[0,1\right]$ because $B^{n}$ is a stochastic matrix too. Then
$\sum_{n=0}^{\infty}a_{n}b_{ij}^{(n)}$ is a non-negative series such that
$0\leq a_{n}b_{ij}^{(n)}\leq a_{n}$ and it converges because
$\sum_{n=0}^{\infty}a_{n}$ does. $\blacksquare\vskip 12.0pt plus 4.0pt minus
4.0pt$

As a consequence the function

$f_{a}\left(B\right)={\displaystyle\sum\limits_{n=0}^{\infty}}a_{n}B^{n}$

is well defined in the strong sense of Weyr (see e.g. Rinehart, 1955), for all
stochastic matrices $B$.

Denote by $Q$ and $M$ the exploration and transition matrices defined in the
main text, which, as observed, are stochastic.

###### Lemma 22

Let $\rho_{\mathrm{C}}$ be positive. If $Q$ is irreducible (quasi-positive),
then $M$ is primitive (positive).

Proof To ease notation we write $\rho$ in place of $\rho_{\mathrm{C}}$. Let
$Q$ be irreducible. Recall that

$M\left(i\mid j\right)=Q\left(i\mid j\right)\rho\left(i\mid
j\right)\qquad\forall i\neq j$ (53)

and $M\left(j\mid j\right)=1-{\displaystyle\sum\limits_{k\neq j}}Q\left(k\mid
j\right)\rho\left(k\mid j\right)$, for all $j\in A$. Given any $j\in A$, since
$Q$ is irreducible, then it cannot be the case that $Q\left(k\mid j\right)=0$
for all $k\neq j$. Positivity of the BCM implies that

$M\left(j\mid j\right)=1-{\displaystyle\sum\limits_{k\neq j}}Q\left(k\mid
j\right)\rho\left(k\mid j\right)>1-{\displaystyle\sum\limits_{k\neq
j}}Q\left(k\mid j\right)\geq 1-{\displaystyle\sum\limits_{k\in A}}Q\left(k\mid
j\right)=0$

and so $M\left(j\mid j\right)>0$ for all $j\in A$.

Moreover, if $i\neq j$, then there exist $n\geq 1$ and $k_{0},...,k_{n}$ in
$A$, with $k_{0}=i$, $k_{n}=j$, and $k_{h}\neq k_{h-1}$ for all $h=1,...,n$,
such that

$Q\left(k_{1}\mid k_{0}\right)Q\left(k_{2}\mid k_{1}\right)\cdot\cdot\cdot
Q\left(k_{n}\mid k_{n-1}\right)>0$

and positivity of the BCM implies that

$M\left(k_{1}\mid k_{0}\right)M\left(k_{2}\mid k_{1}\right)\cdot\cdot\cdot
M\left(k_{n}\mid k_{n-1}\right)>0$

Together with positivity of $M$ on the diagonal, this yields primitivity of
$M$ itself.292929Because $M$ is then irreducible and non-traceless.

Finally, if $Q$ is quasi-positive, the argument above shows that $M$ is
positive on the diagonal, and (53) shows that $M$ is positive also off the
diagonal. $\blacksquare$

####  B.2.3 Proof of Proposition 10

By Lemma 21 the two matrix power series

$\sum_{n=0}^{\infty}\mathbb{P}\left[N=n\right]M^{n}\qquad\text{and\qquad}\sum_{n=0}^{\infty}\mathbb{P}\left[N>n\right]M^{n}$

converge (note that
$\sum_{n=0}^{\infty}\mathbb{P}\left[N>n\right]=\mathbb{E}\left[N\right]<\infty$).
Recall that, if the algorithm stops at iteration
$n\in\mathbb{N}=\left\\{0,1,...\right\\}$, it chooses the incumbent $j_{n-1}$.
By independence, the joint probability of stopping at iteration $n$ and
choosing $j\in A$ is

$\mathbb{P}\left[N=n,J_{n-1}=j\right]=\mathbb{P}\left[N=n\right]\mathbb{P}\left[J_{n-1}=j\right]$

Now, for $n=0$ we have

$\mathbb{P}\left[J_{-1}=j\right]=\mu_{j}=\left(M^{0}\mu\right)_{j}$

Assume that for $n=m$ we have

$\mathbb{P}\left[J_{m-1}=j\right]=\left(M^{m}\mu\right)_{j}$

Then, for $n=m+1$ we have

$\displaystyle\mathbb{P}\left[J_{\left(m+1\right)-1}=j\right]$
$\displaystyle=\mathbb{P}\left[J_{m}=j\right]=\sum_{i\in
A}\mathbb{P}\left[J_{m}=j,J_{m-1}=i\right]=\sum_{i\in
A}\mathbb{P}\left[J_{m}=j\mid
J_{m-1}=i\right]\mathbb{P}\left[J_{m-1}=i\right]$ $\displaystyle=\sum_{i\in
A}m_{ji}\left(M^{m}\mu\right)_{i}=\left(M\left(M^{m}\mu\right)\right)_{j}=\left(M^{m+1}\mu\right)_{j}$

We have proved by induction that

$\mathbb{P}\left[J_{n-1}=j\right]=\left(M^{n}\mu\right)_{j}\qquad\forall
n\in\mathbb{N}$

It follows that the probability of choosing $j$ is

${\displaystyle\sum\limits_{n=0}^{\infty}}\mathbb{P}\left[N=n,J_{n-1}=j\right]={\displaystyle\sum\limits_{n=0}^{\infty}}\mathbb{P}\left[N=n\right]\mathbb{P}\left[J_{n-1}=j\right]={\displaystyle\sum\limits_{n=0}^{\infty}}\mathbb{P}\left[N=n\right]\left(M^{n}\mu\right)_{j}$

Then

$\displaystyle p_{N}$
$\displaystyle={\displaystyle\sum\limits_{n=0}^{\infty}}\mathbb{P}\left[N=n\right]\left(M^{n}\mu\right)=\lim_{k\rightarrow\infty}{\displaystyle\sum\limits_{n=0}^{k}}\mathbb{P}\left[N=n\right]\left(M^{n}\mu\right)=\lim_{k\rightarrow\infty}\left(\left[{\displaystyle\sum\limits_{n=0}^{k}}\mathbb{P}\left[N=n\right]M^{n}\right]\mu\right)$
$\displaystyle=\left(\lim_{k\rightarrow\infty}\left[{\displaystyle\sum\limits_{n=0}^{k}}\mathbb{P}\left[N=n\right]M^{n}\right]\right)\mu$

and so $p_{N}=f_{N}\left(M\right)\mu$ holds. The average duration of an
iteration starting with incumbent $j$ is

$\tau_{j}={\displaystyle\sum\limits_{i\in A}}Q\left(i\mid
j\right)\tau_{\mathrm{RT}}\left(i\mid j\right)$

where to ease notation we write $\tau$ in place of $\bar{\tau}$. Since
$\mathbb{P}\left[J_{n-1}=j\right]=\left(M^{n}\mu\right)_{j}$, the average
duration of iteration $k$ (if it takes place, i.e., if $N>k$) is

${\displaystyle\sum\limits_{j\in
A}}\tau_{j}\mathbb{P}\left[J_{k-1}=j\right]={\displaystyle\sum\limits_{j\in
A}}\tau_{j}\left(M^{k}\mu\right)_{j}=\tau\cdot M^{k}\mu$

The average duration if $N=n$ is then

${\displaystyle\sum\limits_{k=0}^{n-1}}\tau\cdot
M^{k}\mu=\tau\cdot\left({\displaystyle\sum\limits_{k=0}^{n-1}}M^{k}\right)\mu$

with the convention ${\displaystyle\sum\limits_{k=0}^{-1}}M^{k}=0$ (the zero
matrix). Since the probability of stopping at $n$ is
$\mathbb{P}\left[N=n\right]$, it follows that

$\displaystyle\tau_{N}$
$\displaystyle={\displaystyle\sum\limits_{n=0}^{\infty}}\mathbb{P}\left[N=n\right]\tau\cdot\left({\displaystyle\sum\limits_{k=0}^{n-1}}M^{k}\right)\mu=\tau\cdot\left({\displaystyle\sum\limits_{n=0}^{\infty}}\mathbb{P}\left[N=n\right]\left({\displaystyle\sum\limits_{k=0}^{n-1}}M^{k}\right)\right)\mu$
(54)
$\displaystyle=\tau\cdot\left({\displaystyle\sum\limits_{n=1}^{\infty}}\mathbb{P}\left[N=n\right]\left({\displaystyle\sum\limits_{k=0}^{n-1}}M^{k}\right)\right)\mu$

because ${\displaystyle\sum\limits_{k=0}^{-1}}M^{k}=0$. Now

$\displaystyle{\displaystyle\sum\limits_{n=1}^{\infty}}\mathbb{P}\left[N=n\right]\left({\displaystyle\sum\limits_{k=0}^{n-1}}M^{k}\right)$
$\displaystyle={\displaystyle\sum\limits_{n=1}^{\infty}}\mathbb{P}\left[N=n\right]\left({\displaystyle\sum\limits_{k=1}^{n}}M^{k-1}\right)$
$\displaystyle={\displaystyle\sum\limits_{n=1}^{\infty}}{\displaystyle\sum\limits_{k=1}^{\infty}}1_{\left\\{k\leq
n\right\\}}\mathbb{P}\left[N=n\right]M^{k-1}={\displaystyle\sum\limits_{k=1}^{\infty}}{\displaystyle\sum\limits_{n=1}^{\infty}}1_{\left\\{k\leq
n\right\\}}\mathbb{P}\left[N=n\right]M^{k-1}$
$\displaystyle={\displaystyle\sum\limits_{k=1}^{\infty}}M^{k-1}{\displaystyle\sum\limits_{n=1}^{\infty}}1_{\left\\{k\leq
n\right\\}}\mathbb{P}\left[N=n\right]={\displaystyle\sum\limits_{k=1}^{\infty}}M^{k-1}{\displaystyle\sum\limits_{n=k}^{\infty}}\mathbb{P}\left[N=n\right]$
$\displaystyle={\displaystyle\sum\limits_{k=1}^{\infty}}\mathbb{P}\left[N\geq
k\right]M^{k-1}={\displaystyle\sum\limits_{n=0}^{\infty}}\mathbb{P}\left[N\geq
n+1\right]M^{n}={\displaystyle\sum\limits_{n=0}^{\infty}}\mathbb{P}\left[N>n\right]M^{n}$

This proves that $\tau_{N}=\tau\cdot g_{N}\left(M\right)\mu$ holds.
$\blacksquare$

####  B.2.4 Proof of Proposition 11

If $N$ is negative binomial, then

$\displaystyle f_{N}\left(z\right)$
$\displaystyle=\sum_{n=0}^{\infty}\binom{n+r-1}{r-1}\zeta^{n}\left(1-\zeta\right)^{r}z^{n}=\left(1-\zeta\right)^{r}\sum_{n=0}^{\infty}\binom{n+r-1}{r-1}\left(\zeta
z\right)^{n}=\frac{\left(1-\zeta\right)^{r}}{\left(1-\zeta z\right)^{r}}$
$\displaystyle g_{N}\left(z\right)$
$\displaystyle=\frac{1-f_{N}\left(z\right)}{1-z}=\frac{1-\frac{\left(1-\zeta\right)^{r}}{\left(1-\zeta
z\right)^{r}}}{1-z}=\frac{\frac{\left(1-\zeta z\right)^{r}}{\left(1-\zeta
z\right)^{r}}-\frac{\left(1-\zeta\right)^{r}}{\left(1-\zeta
z\right)^{r}}}{1-z}=\frac{\left(1-\zeta
z\right)^{r}-\left(1-\zeta\right)^{r}}{\left(1-z\right)\left(1-\zeta
z\right)^{r}}$

For $r=1$ it yields

$\displaystyle f_{N}\left(z\right)$
$\displaystyle=\left(1-\zeta\right)\left(1-\zeta z\right)^{-1}$ $\displaystyle
g_{N}\left(z\right)$ $\displaystyle=\frac{1-\zeta
z-1+\zeta}{\left(1-z\right)\left(1-\zeta z\right)}=\frac{\zeta-\zeta
z}{\left(1-z\right)\left(1-\zeta
z\right)}=\frac{\zeta\left(1-z\right)}{\left(1-z\right)\left(1-\zeta
z\right)}=\zeta\left(1-\zeta z\right)^{-1}$

In general, note that $z=1$ is a root of $\left(1-\zeta
z\right)^{r}-\left(1-\zeta\right)^{r}$. Thus, the ratio

$\frac{\left(1-\zeta z\right)^{r}-\left(1-\zeta\right)^{r}}{1-z}$

appearing above is a polynomial of degree $r-1$ in $z$. Next we compute it. It
holds

$\displaystyle\left(1-\zeta z\right)^{r}-\left(1-\zeta\right)^{r}$
$\displaystyle=\sum_{k=0}^{r}\binom{r}{k}\left(-\zeta
z\right)^{k}-\sum_{k=0}^{r}\binom{r}{k}\left(-\zeta\right)^{k}$
$\displaystyle=\sum_{k=0}^{r}\left(-1\right)^{k}\binom{r}{k}\zeta^{k}z^{k}-\sum_{k=0}^{r}\left(-1\right)^{k}\binom{r}{k}\zeta^{k}$
$\displaystyle=\sum_{k=0}^{r}\left(-1\right)^{k}\binom{r}{k}\zeta^{k}\left(z^{k}-1\right)=\sum_{k=0}^{r}\binom{r}{k}\left(-\zeta\right)^{k}\left(z-1\right)\sum_{j=0}^{k-1}z^{j}$

because

$z^{k}-1=\left(z-1\right)\left(1+z+\cdot\cdot\cdot+z^{k-1}\right)=\left(z-1\right)\sum_{j=0}^{k-1}z^{j}$

with the convention $\sum_{j=0}^{-1}z^{j}=0$. Then,

$\displaystyle g_{N}\left(z\right)$ $\displaystyle=\frac{\left(1-\zeta
z\right)^{r}-\left(1-\zeta\right)^{r}}{\left(1-z\right)\left(1-\zeta
z\right)^{r}}=\left(\sum_{k=0}^{r}\binom{r}{k}\left(-\zeta\right)^{k}\left(z-1\right)\sum_{j=0}^{k-1}z^{j}\right)\frac{1}{\left(1-z\right)\left(1-\zeta
z\right)^{r}}$
$\displaystyle=-\left(\sum_{k=0}^{r}\binom{r}{k}\left(-\zeta\right)^{k}\sum_{j=0}^{k-1}z^{j}\right)\left(1-\zeta
z\right)^{-r}$

showing that (29) holds.

####  B.2.5 Equations (33) and (34)

##### Preamble

A reversible matrix $B$ is diagonalizable with real eigenvalues. Indeed, from
the detailed balance condition (1) it readily follows that the matrix
$B^{\ast}$ with off diagonal entries $b_{ij}^{\ast}=b_{ij}\sqrt{p_{j}/p_{i}}$
is symmetric and has the same eigenvalues as $B$. A stochastic reversible
matrix $B$ has then a largest eigenvalue $\lambda_{1}$ equal to $1$ and all
its other eigenvalues have absolute values $\leq\lambda_{1}$, i.e., they
belong to $\left[-1,1\right]$. If, in addition, $B$ is primitive, by Perron’s
Theorem their absolute values are actually $<\lambda_{1}$, so they belong to
$\left(-1,1\right)$.

##### Equations

Let the transition matrix $M$ be diagonalizable (e.g., because it is
reversible) and let
$\Lambda=\operatorname*{diag}\left(\lambda_{1},\lambda_{2},...,\lambda_{m}\right)$
be the diagonal matrix of its eigenvalues, each repeated according to its
multiplicity. For any summable sequence $a=\left\\{a_{n}\right\\}$ of non-
negative scalars we then have

$\displaystyle f_{a}\left(M\right)$
$\displaystyle={\displaystyle\sum\limits_{n=0}^{\infty}}a_{n}M^{n}=\lim_{l\rightarrow\infty}{\displaystyle\sum\limits_{n=0}^{l}}a_{n}U\Lambda^{n}U^{-1}=\lim_{l\rightarrow\infty}\left[U\left({\displaystyle\sum\limits_{n=0}^{l}}a_{n}\Lambda^{n}\right)U^{-1}\right]$
$\displaystyle=U\left[\lim_{l\rightarrow\infty}\left({\displaystyle\sum\limits_{n=0}^{l}}a_{n}\Lambda^{n}\right)\right]U^{-1}=U\left[\operatorname*{diag}\left({\displaystyle\sum\limits_{n=0}^{\infty}}a_{n}\lambda_{1}^{n},{\displaystyle\sum\limits_{n=0}^{\infty}}a_{n}\lambda_{2}^{n},...,{\displaystyle\sum\limits_{n=0}^{\infty}}a_{n}\lambda_{m}^{n}\right)\right]U^{-1}$
$\displaystyle=U\left[\operatorname*{diag}\left(f_{a}\left(\lambda_{1}\right),f_{a}\left(\lambda_{2}\right),...,f_{a}\left(\lambda_{\left|A\right|}\right)\right)\right]U^{-1}$

This immediately yields (33) and (34).

###  B.3 Section 4.4

####  B.3.1 Proof of Theorem 12, Corollary 13, and Corollary 14

###### Proposition 23

If $\rho_{\mathrm{C}}$ is has a binary value representation and the
exploration matrix $Q$ is nice, then the probability distribution

$\pi\left(i\right)=\left\\{\begin{array}[c]{ll}\dfrac{u\left(i\right)}{\sum_{j\in\left.\arg\max\right._{A}w}u\left(j\right)}\vskip
6.0pt plus 2.0pt minus 2.0pt&\qquad\text{if }i\in\left.\arg\max\right._{A}w\\\
0&\qquad\text{else}\end{array}\right.$

is the only stationary distribution for $M$, and there exists
$\varepsilon\in\left(0,1\right)$ such that, for all $n\in\mathbb{N}$ and all
$\mu\in\Delta\left(A\right)$,

$\left\|M^{n}\mu-\pi\right\|_{1}\leq 2\left(1-\varepsilon\right)^{n}$ (55)

Moreover, if $\left\\{N_{k}\right\\}_{k=0}^{\infty}$ is a sequence of stopping
numbers that diverges, then, for all $\mu\in\Delta\left(A\right)$

$\left({\displaystyle\sum\limits_{n=0}^{\infty}}\mathbb{P}\left[N_{k}=n\right]M^{n}\right)\mu\rightarrow\pi\qquad\text{as
}k\rightarrow\infty$ (56)

In particular, (55) implies that

$\lim_{n\rightarrow\infty}\Pr\left[J_{n}=i\right]=\pi\left(i\right)$

and (56) implies that

$\lim_{N_{k}\rightarrow\infty}p_{N_{k}}=\pi$ (57)

when the stopping numbers are simple. Hence,

$\lim_{N_{k}\rightarrow\infty}p_{N_{k}}\left(i,A\right)=\lim_{n\rightarrow\infty}\Pr\left[J_{n}=i\right]=\left\\{\begin{array}[c]{ll}\dfrac{u\left(i\right)}{\sum_{j\in\left.\arg\max\right._{A}w}u\left(j\right)}\vskip
6.0pt plus 2.0pt minus 2.0pt&\qquad\text{if }i\in\left.\arg\max\right._{A}w\\\
0&\qquad\text{else}\end{array}\right.$

This proves Theorem 12. Corollaries 13 and 14 follow immediately.

Proof To ease notation we write $\rho$ in place of $\rho_{\mathrm{C}}$. We
first show that

$M\left(k\mid j\right)\pi\left(j\right)=M\left(j\mid
k\right)\pi\left(k\right)$ (58)

for all $j$ and $k$ in $A$. Denote, for brevity,
$W\left(A\right)=\left.\arg\max\right._{A}w$. If $j=k$, the equality is
trivial. Let $j\neq k$ in $A$.

  * •

If $j,k\in W\left(A\right)$, then

$\displaystyle M\left(k\mid j\right)\pi\left(j\right)$
$\displaystyle=Q\left(k\mid j\right)\rho\left(k\mid
j\right)\dfrac{u\left(j\right)}{\sum_{i\in W\left(A\right)}u\left(i\right)}$
$\displaystyle=Q\left(k\mid
j\right)s\left(k,j\right)\dfrac{u\left(k\right)}{u\left(k\right)+u\left(j\right)}\dfrac{u\left(j\right)}{\sum_{i\in
W\left(A\right)}u\left(i\right)}$ $\displaystyle=Q\left(j\mid
k\right)s\left(j,k\right)\dfrac{u\left(j\right)}{u\left(j\right)+u\left(k\right)}\dfrac{u\left(k\right)}{\sum_{i\in
W\left(A\right)}u\left(i\right)}=Q\left(j\mid k\right)\rho\left(j\mid
k\right)\pi\left(k\right)$ $\displaystyle=M\left(j\mid
k\right)\pi\left(k\right)$

  * •

If $j,k\notin W\left(A\right)$, then $\pi\left(j\right)=\pi\left(k\right)=0$
and

$M\left(k\mid j\right)\pi\left(j\right)=M\left(j\mid
k\right)\pi\left(k\right)$

  * •

If $j\in W\left(A\right)$ and $k\notin W\left(A\right)$, then
$w\left(j\right)>w\left(k\right)$ and so $\rho\left(k\mid
j\right)=0=\pi\left(k\right)$, thus

$M\left(k\mid j\right)\pi\left(j\right)=Q\left(k\mid j\right)\rho\left(k\mid
j\right)\dfrac{u\left(j\right)}{\sum_{i\in
W\left(A\right)}u\left(i\right)}=0=M\left(j\mid k\right)\pi\left(k\right)$

  * •

If $j\notin W\left(A\right)$ and $k\in W\left(A\right)$, then
$w\left(k\right)>w\left(j\right)$ and so $\rho\left(j\mid
k\right)=0=\pi\left(j\right)$, thus

$M\left(k\mid j\right)\pi\left(j\right)=0=Q\left(j\mid k\right)\rho\left(j\mid
k\right)\pi\left(k\right)=M\left(j\mid k\right)\pi\left(k\right)$

The “detailed balance” condition (58) implies that

${\displaystyle\sum\limits_{j\in A}}M\left(k\mid
j\right)\pi\left(j\right)={\displaystyle\sum\limits_{j\in A}}M\left(j\mid
k\right)\pi\left(k\right)=\pi\left(k\right){\displaystyle\sum\limits_{j\in
A}}M\left(j\mid k\right)=\pi\left(k\right)$

for all $k\in A$, then $M\pi=\pi$. Thus $\pi$ is a stationary distribution for
$M$.

Take $j_{0}\in W\left(A\right)$. Then, $w\left(j_{0}\right)\geq
w\left(i\right)$ for all $i\neq j_{0}$, and so

$M\left(j_{0}\mid i\right)=Q\left(j_{0}\mid i\right)\rho\left(j_{0}\mid
i\right)=\left\\{\begin{array}[c]{ll}Q\left(j_{0}\mid i\right)\vskip 6.0pt
plus 2.0pt minus 2.0pt&\qquad\text{if }w\left(j_{0}\right)>w\left(i\right)\\\
Q\left(j_{0}\mid
i\right)s\left(j_{0},i\right)\dfrac{u\left(j_{0}\right)}{u\left(j_{0}\right)+u\left(i\right)}&\qquad\text{if
}w\left(j_{0}\right)=w\left(i\right)\end{array}\right.$

For $i=j_{0}$, we have that $\rho\left(k\mid j_{0}\right)=0$ if $k\notin
W\left(A\right)$ and $\rho\left(k\mid j_{0}\right)\in\left(0,1\right)$ if
$k\in W\left(A\right)$ (provided $k\neq j_{0}$),

$M\left(j_{0}\mid j_{0}\right)=1-{\displaystyle\sum\limits_{k\neq
j_{0}}}Q\left(k\mid j_{0}\right)\rho\left(k\mid
j_{0}\right)>1-{\displaystyle\sum\limits_{k\neq j_{0}}}Q\left(k\mid
j_{0}\right)\geq 1-{\displaystyle\sum\limits_{k\in A}}Q\left(k\mid
j_{0}\right)=0$

By Doeblin’s Theorem, $\pi$ is the only stationary distribution for $M$ and
there exists $\varepsilon\in\left(0,1\right)$ such that

$\left\|M^{n}\mu-\pi\right\|_{1}\leq 2\left(1-\varepsilon\right)^{n}$

for all $n\in\mathbb{N}$ and all $\mu\in\Delta\left(A\right)$.

Given any $\mu\in\Delta\left(A\right)$, set, for each $k\in\mathbb{N}$,

$P_{k}\left(n\right)=\mathbb{P}\left[N_{k}=n\right]\qquad\forall
n\in\mathbb{N}$

and

$p_{k}=\left({\displaystyle\sum\limits_{n=0}^{\infty}}P_{k}\left(n\right)M^{n}\right)\mu$

Then

$p_{k}=\lim_{m\rightarrow\infty}{\displaystyle\sum\limits_{n=0}^{m}}P_{k}\left(n\right)M^{n}\mu\text{\quad
and\quad}\pi=\lim_{m\rightarrow\infty}{\displaystyle\sum\limits_{n=0}^{m}}P_{k}\left(n\right)\pi$

and so

$p_{k}-\pi=\lim_{m\rightarrow\infty}{\displaystyle\sum\limits_{n=0}^{m}}P_{k}\left(n\right)\left(M^{n}\mu-\pi\right)$

Thus,

$\displaystyle\left\|p_{k}-\pi\right\|_{1}$