# General Markov Chains: Cycles of Finitely Additive Measures and lassical
Cycles of States

Alexander I. Zhdanok 111Institute for Information Transmission Problems of the
Russian Academy of Science, Moscow, Russia; 222Tuvinian Institute for
Exploration of Natural Resources of the Siberian Branch RAS, Kyzyl, Republic
of Tuva, Russia; 333This work was supported by the Russian Foundation for
Basic Research (project No. 20-01-00575-a)
e-mail<EMAIL_ADDRESS>
Abstract. General Markov chains in an arbitrary phase space are considered in
the framework of the operator treatment. Markov operators continue from the
space of countably additive measures to the space of finitely additive
measures. Cycles of measures generated by the corresponding operator are
constructed, and algebraic operations on them are introduced. One of the main
results obtained is that any cycle of finitely additive measures can be
uniquely decomposed into the coordinate-wise sum of a cycle of countably
additive measures and a cycle of purely finitely additive measures.We have
proved theorems on the conditions and consequences of consistency cycles of
measures with cycles of sets of states of General Markov chains. A theorem is
proved (under certain conditions) that if a finitely additive cycle of a
Markov chain is unique, then it is countably additive.

Keywords.  General Markov chains, Markov operators, Finitely additive
measures, Cycles of measures, Decomposition of cycles.

MSC: 60J05, 28A33

##  1 Introduction

The considered general Markov chains (MC) are random processes with an
arbitrary phase space, with discrete time, and homogeneous in time. MCs are
given by the usual transition probability, countably additive in the second
argument, which generates two Markov operators $T$ and $A$ in the space of
measurable functions and in the space of countably additive measures,
respectively. Thus, we use the operator treatment in the theory of general
MCs, proposed in 1937 by N. Kryloff and N. Bogolyuboff, and developed in
detail in the article [1]. Later, in a number of works by different authors,
an extension of the Markov operator $A$ to the space of finitely additive
measures was carried out, which turned $A$ into an operator topologically
conjugate to the operator $T$, and opened up new possibilities in the
development of the operator treatment. Within the framework of such a scheme,
we carry out here the study of cycles of measures of general MC. In this case,
we use a number of information on the general theory of finitely additive
measures from the sources [2] and [3].

In the ergodic theory of MC, one usually distinguishes in the space of its
states ergodic classes and their cyclic subclasses, if such exist (see, for
example, [4]). However, in the general phase space, the study of such sets has
its natural limitations. Therefore, in some cases it is more convenient to use
not cycles of sets, but cycles of measures generated by the Markov operator A.

In this paper we propose a corresponding construction for cyclic finitely
additive measures of MC on an arbitrary measurable space. We also study cycles
of countably additive and purely finitely additive measures, and their
relationship with classical cycles of sets of States of an arbitrary Markov
chain. In the proof of the theorems presented here, we also use some results
of papers [5] and [6].

##  2 Finitely additive Measures and Markov operators

Let $X$ be an arbitrary infinite set and $\Sigma$ the sigma-algebra of its
subsets containing all one-point subsets from $X$. Let $B(X,\Sigma)$ denote
the Banach space of bounded $\Sigma$ -measurable functions $f:X\to R$ with
sup-norm.

We also consider Banach spaces of bounded measures $\mu:\Sigma\to R$, with the
norm equal to the total variation of the measure $\mu$ (but you can also use
the equivalent sup-norm):

$ba(X,\Sigma)$ is the space of finitely additive measures,

$ca(X,\Sigma)$ is the space of countably additive measures.

If $\mu\geq{0}$, then $||\mu||=\mu(X)$.

###### Definition 2.1

(see [2]). A finitely additive nonnegative measure $\mu$ is called purely
finitely additive (pure charge, pure mean) if any countably additive measure
$\lambda$ satisfying the condition $0\leq\lambda\leq\mu$ is identically zero.
An alternating measure $\mu$ is called purely finitely additive if both
components of its Jordan decomposition are purely finitely additive.

Any finitely additive measure $\mu$ can be uniquely expanded into the sum
$\mu=\mu_{1}+\mu_{2}$, where $\mu_{1}$ is countably additive and $\mu_{2}$ is
a purely finitely additive measure (the Alexandroff -Yosida-Hewitt
decomposition, see [2] and [3]).

Purely finitely additive measures also form a Banach space $pfa(X,\Sigma)$
with the same norm, $ba(X,\Sigma)=ca(X,\Sigma)\oplus pfa(X,\Sigma)$.

Examples 2.1. Here are two examples of purely finitely additive measures.

Let $X=[0,1]\subset\mathbb{R}$ ($\mathbb{R}=(-\infty;+\infty)$) and
$\Sigma=\mathfrak{B}$ ( $\mathfrak{B}$ \- Borel sigma algebra). There is
(proved) a finitely additive measure $\mu\colon\mathfrak{B}\to\mathbb{R}$,
$\mu\in S_{ba}$, such that for any $\varepsilon>0$ the following holds:

$\mu((0,\varepsilon))=1,\;\;\mu([\varepsilon,1])=0,\;\;\mu(\\{0\\})=0.$

We can say that the measure $\mu$ fixes the unit mass arbitrarily close to
zero (on the right), but not at zero. According to [2], such a measure is
purely finitely additive, but it is not the only one. It is known that the
cardinality of a family of such measures located ‘‘near zero (on the right)’’
is not less than $2^{2^{\aleph_{0}}}=2^{c}$ (hypercontinuum). And the same
family of purely finitely additive measures exists ‘‘near each point
$x_{0}\in[0,1]$ (to the right, or to the left, or both there, and there)’’.

Examples 2.2.

Let $X=\mathbb{R}=(-\infty;+\infty)$ and $\Sigma=\mathfrak{B}$. There is
(proved) a finitely additive measure $\mu\colon\mathfrak{B}\to\mathbb{R}$,
$\mu\in S_{ba}$, such that for any $x\in\mathbb{R}$ the following holds:

$\mu((x,\infty))=1,\;\;\mu((-\infty,x))=0,\;\;\mu(\\{x\\})=0.$

We can say that the measure $\mu$ fixes the unit mass arbitrarily far, ‘‘near
infinity’’. This measure is also purely finitely additive. And there are also
a lot of such measures.

We denote the sets of measures:

$S_{ba}=\\{\mu\in{ba(X,\Sigma)}:\mu\geq{0},||\mu||=1\\},$
$S_{ca}=\\{\mu\in{ca(X,\Sigma)}:\mu\geq{0},||\mu||=1\\},$

$S_{pfa}=\\{\mu\in{pfa(X,\Sigma)}:\mu\geq{0},||\mu||=1\\}.$

All measures from these sets will be called probabilistic.

Markov chains (MC) on a measurable space $(X,\Sigma)$ are given by their
transition function (probability) $p(x,E),x\in X,E\in\Sigma$, under the usual
conditions:

  1. 1.

$0\leq p(x,E)\leq{1},p(x,X)=1,\forall{x}\in{X},\forall{E}\in\Sigma$;

  2. 2.

$p(\cdot,E)\in{B(X,\Sigma)},\forall{E}\in\Sigma$;

  3. 3.

$p(x,\cdot)\in{ca(X,\Sigma)},\forall{x}\in{X}$.

We emphasize that our transition function is a countably additive measure in
the second argument, i.e. we consider classical MCs.

The transition function generates two Markov linear bounded positive integral
operators:

$T:B(X,\Sigma)\to{B(X,\Sigma)},(Tf)(x)=Tf(x)=\int\limits_{X}f(y)p(x,dy),$

$\forall{f\in{B(X,\Sigma)}},\forall{x}\in{X};$

$A:ca(X,\Sigma)\to{ca(X,\Sigma)},(A\mu)(E)=A\mu(E)=\int\limits_{X}p(x,E)\mu(dx),$

$\forall{\mu\in{ca(X,\Sigma)}},\forall{E}\in\Sigma.$

Let the initial measure be $\mu_{0}\in{S_{ca}}$. Then the iterative sequence
of countably additive probability measures
$\mu_{n}=A\mu_{n-1}\in{S_{ca}},n\in{N}$, is usually identified with the Markov
chain.

Topologically conjugate to the space $B(X,\Sigma)$ is the (isomorphic) space
of finitely additive measures: $B^{*}(X,\Sigma)=ba(X,\Sigma)$ (see, for
example, [3]). Moreover, the operator $T^{*}:ba(X,\Sigma)\to{ba(X,\Sigma)}$ is
topologically conjugate to the operator $T$:

$T^{*}\mu(E)=\int\limits_{X}p(x,E)\mu(dx),\forall{\mu\in{ba(X,\Sigma)}},\forall
E\in\Sigma.$

The operator $T^{*}$ is the only bounded continuation of the operator $A$ to
the entire space $ba(X,\Sigma)$ while preserving its analytic form. The
operator $T^{*}$ has its own invariant subspace $ca(X,\Sigma)$, i.e.
$T^{*}[ca(X,\Sigma)]\subset{ca(X,\Sigma)}$, on which it matches the original
operator $A$. The construction of the Markov operators $T$ and $T^{*}$ is now
functionally closed. We shall continue to denote the operator $T^{*}$ as $A$.

In such a setting, it is natural to admit to consideration also the Markov
sequences of probabilistic finitely additive measures
$\mu_{0}\in{S_{ba}},\mu_{n}=A\mu_{n-1}\in{S_{ba}},n\in{N}$, keeping the
countable additivity of the transition function $p(x,\cdot)$ with respect to
the second argument.

##  3 Cycles of Measures and their properties

###### Definition 3.1

If $A\mu=\mu$ holds for some positive finitely additive measure $\mu$, then we
call such a measure invariant for the operator $A$ (and for the Markov chain).

We denote the sets of all probability invariant measures for the operator $A$:

$\Delta_{ba}=\\{\mu\in{S_{ba}}:\mu=A\mu\\}$,

$\Delta_{ca}=\\{\mu\in{S_{ca}}:\mu=A\mu\\}$,
$\Delta_{pfa}=\\{\mu\in{S_{pfa}}:\mu=A\mu\\}$.

A classical countably additive Markov chain may or may not have invariant
countably additive probability measures, i. e. possibly $\Delta_{ca}=\O$ (for
example, for a symmetric walk on $Z$).

In [7, Theorem 2.2] Šidak proved that any countably additive MC on an
arbitrary measurable space $(X,\Sigma)$ extended to the space of finitely
additive measures has at least one invariant finitely additive measure, i.e.
always $\Delta_{ba}\neq\O$. Šidak in [7, Theorem 2.5] also established in the
general case that if a finitely additive measure $\mu$ is invariant
$A\mu=\mu$, and $\mu=\mu_{1}+\mu_{2}$ is its decomposition into are countably
additive and purely finitely additive components, then each of them is also
invariant: $A\mu_{1}=\mu_{1}$, $A\mu_{2}=\mu_{2}$. Therefore, it suffices to
study invariant measures from $\Delta_{ca}$ and from $\Delta_{pfa}$,
separately.

The study of questions of the existence and properties of invariant finitely
additive measures of general Markov chains is also carried out in the author’s
preprints [8], [9], [10].

###### Definition 3.2

A finite numbered set of pairwise different positive finitely additive
measures $K=\\{\mu_{1}$, $\mu_{2}$, … , $\mu_{m}\\}$ will be called a cycle
measures of an operator $A$ of a given Markov chain (or a cycle of measures MC
) if

$A\mu_{1}=\mu_{2},A\mu_{2}=\mu_{3},...,A\mu_{m-1}=\mu_{m},A\mu_{m}=\mu_{1}.$

Such cycles will be called finitely additive. The number $m\geq 1$ will be
called the cycle period, and the measures $\mu_{1},\mu_{2},...,\mu_{m}$ –
cyclic measures. Unnormalized cycles will also be used below.

If $K=\\{\mu_{1},\mu_{2},...,\mu_{m}\\}$ is a MC cycle, then, obviously,

$A^{m}{\mu_{1}}=\mu_{1},A^{m}{\mu_{2}}=\mu_{2},...,A^{m}{\mu_{m}}=\mu_{m},$

i.e. all cyclic measures $\mu_{i}$ are invariant for the operator $A^{m}$ and
$A^{m}(K)=K$.

The following well-known statement is obvious. Let
$K=\\{\mu_{1},\mu_{2},...,\mu_{m}\\}$ be a cycle of finitely additive
measures. Then the measure

$\mu=\frac{1}{m}\sum_{k=1}^{m}\mu_{k}=\frac{1}{m}\sum_{k=1}^{m}A^{k-1}\mu_{1}$

is invariant for the operator $A$, i.e. $A\mu=\mu$ (here $A^{0}$ is the
identity operator).

###### Definition 3.3

The measure constructed above will be called the mean cycle measure $K$.

###### Definition 3.4

We call each method of choosing a measure $\mu_{1}$ in $K$ an operation
renumbering a cycle $K$.

###### Definition 3.5

We say that two cycles of the same period $K^{1}$ and $K^{2}$are identical if
there is a renumbering of cycles $K^{1}$ or $K^{2}$ such that all their cyclic
measures with the same numbers match. In this case, we will write
$K^{1}=K^{2}$. Instead of the words ‘‘ identical cycles ’’, we will still say
the words ‘‘ equal cycles ’’.

Obviously, for the cycles to be equal, it is sufficient that their first
measures coincide.

Hereinafter, it is convenient to call cyclic measures $\mu_{i},i=1,...,m,$
cycle coordinates $K$.

###### Definition 3.6

By the operation of multiplying a cycle of measures
$K=\\{\mu_{1},\mu_{2},...,\mu_{m}\\}$ by a number $\gamma>0$ we mean the
construction of a cycle of measures $\gamma
K=\\{\gamma\mu_{1},\gamma\mu_{2},...,\gamma\mu_{m}\\}$.

Since the operator $A$ is isometric in the cone of positive measures, all
cyclic measures of one cycle $K=\\{\mu_{1}$, $\mu_{2}$, … , $\mu_{m}\\}$ have
the same norm $\|\mu_{1}\|=\|\mu_{2}\|=,...,=\|\mu_{m}\|=\|\mu\|$, which is
naturally called the norm $\|K\|$ of the cycle $K$ itself.

To give the cycle a probabilistic meaning, it is sufficient to multiply it
coordinatewise by the normalizing factor $\gamma=\frac{1}{\|\mu\|}$:
$\hat{K}=\gamma\cdot K=\\{\gamma\mu_{1}$, $\gamma\mu_{2}$, … ,
$\gamma\mu_{m}\\}$. We obtain a probability cycle with the norm
$\|\hat{K}\|=1,\hat{K}\subset S_{ba}$.

###### Definition 3.7

Let there be given two cycles of measures of the same MC
$K^{1}=\\{\mu^{1}_{1},\mu^{1}_{2},...,\mu^{1}_{m}\\}$ and
$K^{2}=\\{\mu^{2}_{1},\mu^{2}_{2},...,\mu^{2}_{m}\\}$ of the same period $m$.
We call the sum of cycles $K^{1}$ and $K^{2}$ the following set of measures
$K=K^{1}+K^{2}=\\{\mu^{1}_{1}+\mu^{2}_{1},...,\mu^{1}_{m}+\mu^{2}_{m}\\}$
derived from $K^{1}$ and $K^{2}$ coordinatewise addition.

The measure spaces are semi-ordered by the natural order relation. In them one
can introduce the notion of infimum
$inf\\{\mu_{1},\mu_{2}\\}=\mu_{1}\wedge\mu_{2}$ and supremum
$sup\\{\mu_{1},\mu_{2}\\}=\mu_{1}\vee\mu_{2}$, which are also contained in
these spaces. Thus, the measure spaces $ba(X,\Sigma),ca(X,\Sigma)$ and
$pfa(X,\Sigma)$ are lattices ($K$-lineals).

In [2], Theorem 1.11, due to S. Bochner and R. S. Phillips (1941), is given,
which states that the following construction corresponds to the natural order
in the space $ba(X,\Sigma)$ (and, therefore, in the subspaces $ca(X,\Sigma)$,
$pfa(X,\Sigma)$):

$(\mu_{1}\land\mu_{2})(E)=inf\\{\mu_{1},\mu_{2}\\}(E)=inf(\mu_{1}(C)+\mu_{2}(E\cap
C^{\prime})),C^{\prime}=X\setminus C,$

where the infimum is taken over all sets $C\subset E,C\in\Sigma$;

$(\mu_{1}\lor\mu_{2})=sup\\{\mu_{1},\mu_{2}\\}=-((-\mu_{1})\land(-\mu_{2})).$

In this case, $\mu_{1}\land\mu_{2},\mu_{1}\lor\mu_{2}\in ba(X,\Sigma)$.

###### Definition 3.8

Two positive measures $\mu_{1},\mu_{2}\in ba(X,\Sigma)$ are called disjoint if
$\mu_{1}\wedge\mu_{2}=0$.

###### Definition 3.9

Two positive measures $\mu_{1},\mu_{2}\in ba(X,\Sigma)$ are called singular if
there are two sets $D_{1},D_{2}\subset X$, $\;D_{1},D_{2}\in\Sigma$, such that
$\mu_{1}(D_{1})=\mu_{1}(X)$, $\;\mu_{2}(D_{2})=\mu_{2}(X)$ and $D_{1}\cap
D_{2}=\emptyset$.

We give in our notation Theorem 1.21 from [2].

###### Theorem 3.1

1\. Let two finitely additive positive measures $\mu_{1},\mu_{2}$ be disjunct.
Then for any numbers $\alpha,\beta>0$ there is a set $E\in\Sigma$ such that
$\mu_{1}(E)\leq\alpha$ and $\mu_{2}(X\setminus E)\leq\beta$. Here you can put
$\varepsilon=\alpha=\beta$ and consider $\varepsilon$ "as small as you like".

2\. If at least one of the two finitely additive measures $\mu_{1}$ and
$\mu_{2}$ is not countably additive, then their disjunctness does not imply a
singularity.

3\. Countably additive measures $\mu_{1},\mu_{2}$ are disjunct if and only if
they are singular.

If the measures $\mu_{1}$ and $\mu_{2}$ are singular, then they are also
disjoint (see [2]).

###### Definition 3.10

A cycle $K=\\{\mu_{1},\mu_{2},...,\mu_{m}\\}$ is called a cycle of disjoint
measures if all its cyclic measures are pairwise disjoint, i.e.
$\mu_{i}\wedge\mu_{j}=0$ for all $i\neq j$.

###### Definition 3.11

Two cycles of measures $K^{1},K^{2}$ are called disjoint, if each measure from
the cycle $K^{1}$ is disjoint with each measure from the cycle $K^{2}$.

If the cycle of disjoint measures $K=\\{\mu_{1},\mu_{2},...,\mu_{m}\\}$ is
countably additive, then all its cyclic measures are pairwise singular and
have pairwise disjoint supports (sets of full measure)
$D_{1},D_{2},...,D_{m}\in\Sigma$, that is, $\mu_{i}(D_{i})$, $i=1,...,m$, and
$D_{i}\cap D_{j}=\emptyset$ for $i\neq j$.

Now we give one of the versions of the classical definition of cycles of a MC
in the state space (see, for example, [4]).

###### Definition 3.12

A cycle in the set of states $(X,\Sigma)$ of an arbitrary Markov chain is a
system of pairwise distinct sets
$S=\\{D_{1},D_{2},...,D_{m}\\},D_{i}\in\Sigma$, $i=1,...,m$, such that
$p(x,D_{i+1})=1$ for all $x\in D_{i}$, $i=1,...,m-1$, and $p(x,D_{1})=1$ for
all $x\in D_{m}$. The sets $D_{i}$, $i=1,...,m$, are called cyclic, and the
number $m$ is the period of the cycle $S$.

If the sets $D_{i}$ do not intersect pairwise, that is, $D_{i}\cap
D_{j}=\emptyset$ for $i\neq j$, then such a cycle is called singular.

###### Remark 3.1

Many papers study Markov chains on a measurable set together with some
predetermined fixed measure $\mu$, that is, on $(X,\Sigma,\mu)$. Accordingly,
Markov operators are also constructed on function spaces
$L_{p}(X,\Sigma,\mu)$. With this approach, a refinement naturally appears in
the definition of cycles: $p(x,D_{i+1})=1$ almost everywhere relative to the
measure $\mu$ for $x\in D_{i}$, $i=1,...,m-1$, and $p(x,D_{2})=1$ almost
everywhere. Other measures may be used in such definitions. In such cases,
they usually write: [$\mu$] almost everywhere.

In the present work, we use another apparatus for studying the MC, and no a
priori fixed measure $\mu$ is assumed when specifying the MC. Therefore, there
is usually no need to introduce ‘‘almost surely’’ or ‘‘almost everywhere’’
annotations in the main statements and formulas. But sometimes we can’t do
without it, such a case will arise in Lemma 4.1 and in Theorem 4.6 at the end
of the article.

At the end of the next section, two theorems 4.5 and 4.6 will be proved that
show how the cycles of the sets of states of the MC and the cycles of its
measures are related.

If we do not require pairwise disjointness (singularity) of the measures of a
countably additive cycle, then new, somewhat unexpected objects may appear in
the state space of a MC. Let’s give a suitable simple example.

Example 3.1. Let the MC be finite, having exactly three states
$X=\\{x_{1},x_{2},x_{3}\\}$ with transition probabilities:

$p(x_{1},x_{1})=1,p(x_{2},x_{3})=1,p(x_{3},x_{2})=1.$

This means that the MC has in the state space $X$ one stationary state
$\\{x_{1}\\}$ (we can say that this is a cycle of period $m=1$) and one cycle
$\\{x_{2},x_{3}\\}$ of the period $m=2$. Within the framework of the operator
approach, it is more convenient for us to translate what has been said into
the language of measures as follows.

Let $x\in X$ and $E\subset X(E\in\Sigma=2^{X})$. Then
$p(x_{1},E)=\delta_{x_{1}}(E)$, $p(x_{2},E)=\delta_{x_{3}}(E)$,
$p(x_{3},E)=\delta_{x_{2}}(E)$, where $\delta_{x_{i}}(\cdot)$, $i=1,2,3$, are
the Dirac measures at the points $x_{1},x_{2},x_{3}$. For an operator $A$ such
a MC we have: $A\delta_{x_{1}}=\delta_{x_{1}}$,
$A\delta_{x_{2}}=\delta_{x_{3}}$, $A\delta_{x_{3}}=\delta_{x_{2}}$, i. e. the
family of measures $K=\\{\delta_{x_{2}},\delta_{x_{3}}\\}$ is a cycle
according to Definition 3.2, and the cyclic measures $\delta_{x_{2}}$ and
$\delta_{x_{3}}$ are singular.

Consider one more family of measures
$\tilde{K}=\\{\frac{1}{2}\eta_{1},\frac{1}{2}\eta_{2}\\}$, where
$\eta_{1}=\delta_{x_{1}}+\delta_{x_{2}}$,
$\eta_{2}=\delta_{x_{1}}+\delta_{x_{3}}$. Then
$A\eta_{1}=A(\delta_{x_{1}}+\delta_{x_{2}})$ =
$A\delta_{x_{1}}+A\delta_{x_{2}}=\delta_{x_{1}}+\delta_{x_{3}}=\eta_{2}$ and
similarly $A\eta_{2}=\eta_{1}$. Since the measures $\eta_{1}$ and $\eta_{2}$
are different, then by Definition 3.2, the family of measures $\tilde{K}$ is
also a MC cycle different from $K$. Moreover, the measures $\eta_{1}$ and
$\eta_{2}$ are not disjoint: $\eta_{1}\wedge\eta_{2}=\delta_{x_{1}}\neq 0$.
These measures are not singular: their supports $\\{x_{1},x_{2}\\}$
$\\{x_{1},x_{3}\\}$ intersect, i. e.
$\\{x_{1},x_{2}\\}\cap\\{x_{1},x_{3}\\}=\\{x_{1}\\}\neq\emptyset$.

###### Remark 3.2

Such cycles with intersecting cyclic sets of states, as in Example 3.1, are
usually not considered in the classical theory of MC.

However, we believe that the study of intersecting cycles of sets is very
useful in general theory. Research of such cycles is more productive for us in
terms of measure cycles. In this case, instead of intersecting sets of
measures, one should consider cycles of measures that are not disjoint. Our
Theorems 4.1, 4.2, 4.3, and 4.7 (proved in Section 4) do not require pairwise
disjointness (or singularity) of cyclic measures in measure cycles.

##  4  Main results

###### Theorem 4.1

Any finitely additive cycle of measures for an arbitrary MC is a linearly
independent set in the linear space $ba(X,\Sigma)$.

Proof. We prove by induction.

Consider first two arbitrary different measures $\mu_{1},\mu_{2}\in S_{ba}$
(not necessarily cyclic), for which $\|\mu_{1}\|=\|\mu_{2}\|=1$. They are
obviously linearly independent. In particular the cycle
$K=\\{\mu_{1},\mu_{2}\\}$ consisting of two different measures from $S_{ba}$,
is linearly independent.

Now let the cycle consist of three pairwise different measures:
$K=\\{\mu_{1},\mu_{2},\mu_{3}\\}\subset S_{ba}$. As we found out above, any
two measures of them are linearly independent.

Suppose that one of these three measures is linearly dependent on the other
two, let it be the measure $\mu_{3}$ (the number is not important here). Then
there exist numbers $\alpha_{1},\alpha_{2},0\leq\alpha_{1},\alpha_{2}\leq
1,\alpha_{1}+\alpha_{2}=1$, such that the measure $\mu_{3}$ is uniquely
representable as a linear combination
$\mu_{3}=\alpha_{1}\mu_{1}+\alpha_{2}\mu_{2}$.

Let $\alpha_{1}=0$.Then $\alpha_{2}=1$ and $\mu_{3}=\mu_{2}$ which contradicts
the pairwise difference of the three measures. Similarly for $\alpha_{1}=1$.
Therefore, we can assume that $0<\alpha_{1},\alpha_{2}<1$.

By cycle conditions

$\mu_{1}=A\mu_{3}=A(\alpha_{1}\mu_{1}+\alpha_{2}\mu_{2})=\alpha_{1}A\mu_{1}+\alpha_{2}A\mu_{2}=\alpha_{1}\mu_{2}+\alpha_{2}\mu_{3}.$

Since $\alpha_{2}\neq 0$ from this we get
$\mu_{3}=\frac{1}{\alpha_{2}}\mu_{1}-\frac{\alpha_{1}}{\alpha_{2}}\mu_{2}$.
Since the decomposition of $\mu_{3}$ is unique, we have
$\alpha_{1}=\frac{1}{\alpha_{2}},\alpha_{2}=-\frac{\alpha_{1}}{\alpha_{2}}<0$.
Since $\alpha_{1}$ and $\alpha_{2}$ are positive, we obtain a contradiction in
the second equality. Therefore, all three measures $\mu_{1},\mu_{2}$ and
$\mu_{3}$ are linearly independent.

We turn to the general case.

Let be a cycle of measures $K=\\{\mu_{1},\mu_{2},...,\mu_{m}\\}$ with an
arbitrary period $m\geq 3$. We assume that the sets of any $m-1$ pieces of
measures $\mu_{i}$ from $K$ are linearly independent. Assume that the measure
$\mu_{m}$ (the number is not important) depends linearly on the measures
$\mu_{1},\mu_{2},...,\mu_{m-1}$. Then the measure $\mu_{m}$ is uniquely
represented as

$\mu_{m}=\sum_{i=1}^{m-1}\alpha_{i}\mu_{i},$

where $0\leq\alpha_{i}\leq 1$ for $i=1,2,...,m$,
$\sum_{i=1}^{m-1}\alpha_{i}=1$.

Assume that for some $t\in\\{1,2,...,m-1\\}$, $\alpha_{t}=0$ is executed. Then
the measure $\mu_{m}$ is linearly expressed in terms of $m-2$ pieces of
measures $\mu_{i}$, all of them together with $\mu_{m}$ will be $m-1$ piece.
This contradicts the assumption that the sets of any $m-1$ pieces of measures
$\mu_{i}$ from $K$ are linearly independent. Therefore, all
$\alpha_{i}>0,\;\;i=1,2,...,m-1.$

Now let $t\in\\{1,2,...,m-1\\}$ be $\alpha_{t}=1$. Then all other
$\alpha_{i}=0\;(i\neq t)$ and $\mu_{m}=\alpha_{t}\cdot\mu_{t}=\mu_{t}$, which
contradicts the condition of pairwise difference of all measures from the
cycle.

So, for all coefficients in the linear decomposition of the measure $\mu_{m}$
we have $0<\alpha_{i}<1,\;\;i=1,2,...,m-1$.

We apply the operator $A$ to this decomposition of the measure $\mu_{m}$ and
obtain:

$\mu_{1}=A\mu_{m}=\sum_{i=1}^{m-1}\alpha_{i}A\mu_{i}=\sum_{i=1}^{m-1}\alpha_{i}\mu_{i+1}=\alpha_{1}\mu_{2}+\alpha_{2}\mu_{3}+...+\alpha_{m-1}\mu_{m}.$

Therefore, we have ($\alpha_{m-1}\neq 0$):

$\mu_{m}=\frac{1}{\alpha_{m-1}}\mu_{1}-\frac{1}{\alpha_{m-1}}\sum_{i=1}^{m-2}\alpha_{i}\mu_{i+1}.$

Since the representation for the measure $\mu_{m}$ is unique, here and above
we obtain the following relations for the coefficients of the measure
$\mu_{2}$:

$0<\alpha_{2}=-\frac{\alpha_{1}}{\alpha_{m-1}}<0.$

It follows from the contradiction obtained that the measure $\mu_{m}$ is
linearly independent of the other measures of the cycle. Consequently, any
other measure $\mu_{i}\in K$ is linearly independent of the other measures of
the cycle $K$. The theorem is proved.

###### Theorem 4.2

Let $K=\\{\mu_{1},\mu_{2},...,\mu_{m}\\}$ be a finitely additive cycle of
measures for an arbitrary MC. If at least one cyclic measure $\mu_{i}$ is
countably additive, then all other cyclic measures in $K$ and their mean
measures are also countably additive. Such cycles will be called countably
additive.

Proof.

Since $\mu_{i+1}=A\mu_{i},i=1,2,...,m-1$ and $\mu_{1}=A\mu_{m}$ then the
statement of the theorem follows from the fact that the operator $A$ has the
space $ca(X,\Sigma)$ as its invariant subspace in $ba(X,\Sigma)$, that is,
transforms countably additive measures into countably additive ones. The
countable additivity of the mean measure follows from the fact that
$ca(X,\Sigma)$ is a linear space, i. e. the sum of countably additive measures
is also countably additive and a countably additive measure multiplied by a
number is also countably additive.

The theorem is proved.

###### Proposition 4.1

There exist classical Markov chains with purely finitely additive cycles of
measures with period $m\geq 2$.

Example 4.1. An example of a classical MC is constructed, for which the
existence of a purely finitely additive cycle of measures is proved.

For simplicity, we take a deterministic MC generated by a point
transformation.

Let $X=(0,1)\cup(1,2)$, $\Sigma=\mathfrak{B}_{X}$ (Borel $\sigma$-algebra on
$X$). Denote $D_{1}=(0,1)$, $D_{2}=(1,2)$. Then $D_{1}\cup D_{2}=X$,
$D_{1}\cap D_{2}=\emptyset$..

Let’s define the transition function of the Markov chain according to the
rules:

$p(x,\\{1+x^{2}\\})=1$, if $x\in(0,1)$;

$p(y,\\{(y-1)^{2}\\})=1$, if $y\in(1,2)$.

Then $p(x,D_{2})=1$, if $x\in D_{1}$; $p(x,D_{1})=1$, if $x\in D_{2}$.

Therefore, the sets of states $D_{1}$ and $D_{2}$ are cyclic and form a
singular cycle $S=\\{D_{1},D_{2}\\}$ with period $m=2$.

The phase portrait of such a MC is given in Figure 1.

Figure 1: Phase portrait for MC with purely finitely additive cycles.

Note that for any trajectory of the Markov chain beginning at the point
$x_{0}\in(0,1)$, its subsequence with even numbers tends to zero from the
right:

$1+x_{0}^{2},\;1+x_{0}^{16},1+x_{0}^{64},...\to 1,$

and the subsequence with odd numbers tends to one from the right:

$x_{0},\;x_{0}^{4},x_{0}^{32},...\to 0$

(and vice versa, for $x_{0}\in(1,2)$).

By Šidak’s Theorem ([7, Theorem 2.2]) for a given MC there exists an invariant
finitely additive measure $\mu=A\mu\in S_{ba}$. It can be shown that for her
$\mu(D_{1})=\mu(D_{2})=\frac{1}{2}>0$.

We construct two new measures $\mu_{1}$ and $\mu_{2}$ as the restriction of
the measure $\mu$ to the sets $D_{1}$ and $D_{2}$: $\mu_{1}(E)=\mu(E\cap
D_{1})$, $\mu_{2}(E)=\mu(E\cap D_{2})$ for all $E\subset X$, $E\in\Sigma$, and
$\mu=\mu_{1}+\mu_{2}$. The measures $\mu_{1}$ and $\mu_{2}$ are singular and
have supports $D_{1}$ and $D_{2}$. It can be proved that $A\mu_{1}=\mu_{2}$
and $A\mu_{2}=\mu_{1}$. This means that the measures $\mu_{1}$ and $\mu_{2}$
form a disjoint cycle of finitely additive measures $K=\\{\mu_{1},\mu_{2}\\}$.

Let $0<\varepsilon<1$ and $D_{1}^{\varepsilon}=(0,\varepsilon)$,
$D_{2}^{\varepsilon}=(1,1+\varepsilon)$. We can get that for any
$\varepsilon$, $\mu_{1}(D_{1}^{\varepsilon})=1/2$,
$\mu_{2}(D_{2}^{\varepsilon})=1/2$. This means that the measures $\mu_{1}$ and
$\mu_{2}$ and their mean measure are purely finitely additive. The constructed
MC has no invariant countably additive measures.

It can be shown that the singular sets $D_{1}^{\varepsilon}$ and
$D_{2}^{\varepsilon}$ for any $\varepsilon$ form a cycle of states
$S^{\varepsilon}=\\{D_{1}^{\varepsilon},D_{2}^{\varepsilon}\\}$ and are also
supports of measures $\mu_{1}$ and $\mu_{2}$.

It can be proved that the family of all pairwise disjoint invariant finitely
additive measures of a given MC has cardinality at least a continuum, i. e.
$2^{\aleph_{0}}$. Consequently, the family of all generated pairwise disjoint
cycles of purely finitely additive measures of a given MC also has cardinality
at least a continuum.

This implies that the algebraic dimension of the set $\Delta_{ba}$ for a given
MC, that is, the cardinality of its Hamel basis, is not less than a continuum.

Note that the family of all purely finitely additive measures ‘‘ near ’’ zero
has the cardinality of the hypercontinuum, i. e. is equal to
$2^{2^{\aleph_{0}}}$.

Let us modify the considered MC - add the points $0$ and $1$ to
$X=(0,1)\cup(1,2)$ and get $X=[0,2)$. Let us determine the possible
transitions from these points using the same formulas as the original MC. We
get:

$p(0,\\{1\\})=1$, $p(1,\\{0\\})=1.$

This means that the family of state sets $S_{0}=\\{\\{0\\},\\{1\\}\\}$ for the
new MC is a new singular cycle of dimension $m=2$.

It corresponds to a new singular cycle of countably additive measures
$K_{0}=\\{\delta_{0},\delta_{1}\\}$, where $\delta_{0}$ and $\delta_{1}$ are
Dirac measures at the points $0$ and $1$, respectively. Their mean measure
$\mu=\frac{1}{2}\delta_{0}+\frac{1}{2}\delta_{1}$ is countably additive and is
the only invariant measure of the modified Markov chain in the class of
countably additive measures.

The phase portrait of the new MC is shown in Figure 2.

Figure 2: Phase portrait for MC with purely finitely additive cycles and with
one countably additive cycle

Note that the whole infinite family of disjoint purely finitely additive
cycles of measures $K$ considered above on $X=(0,1)\cup(1,2)$ remains the same
for the new MC.

###### Theorem 4.3

Let $K=\\{\mu_{1},\mu_{2},...,\mu_{m}\\}$be a finitely additive cycle of
measures for an arbitrary MC. If at least one cyclic measure $\mu_{i}$ is
purely finitely additive, then all other cyclic measures in $K$ and their mean
measure are also purely finitely additive. Such cycles will be called purely
finitely additive.

Proof. Let the cyclic measure $\mu_{1}$ be purely finitely additive (the
number is not important here) and $\mu_{2}=A\mu_{1}$.

Suppose that the measure $\mu_{2}$ is not purely finitely additive. We
decompose the measure $\mu_{2}$ into two components
$\mu_{2}=\lambda_{ca}+\lambda_{pfa}$ where $\lambda_{ca}$ is a countably
additive measure, and $\lambda_{pfa}$ is purely finitely additive. By
assumption $\mu_{2}\neq\lambda_{pfa}$ whence $\lambda_{ca}\neq 0$,
$\lambda_{ca}\geq 0,\lambda_{ca}(X)=\gamma>0$.

We apply the operator $A$ to the measure $\mu_{2}$

$A\mu_{2}=A\lambda_{ca}+A\lambda_{pfa}=\mu_{3}.$

The operator $A$ takes countably additive measures to the same ones and is
isometric in the cone of positive measures. It follows from this that the
measure $A\lambda_{ca}$ is countably additive, positive, and
$A\lambda_{ca}(X)=\gamma>0$. This means that the measure $\mu_{3}$ also has a
positive countably additive component $A\lambda_{ca}$.

Continuing this procedure further at the last step we get the decomposition

$\mu_{1}=A\mu_{m}=A^{m-2}\lambda_{ca}+A^{m-2}\lambda_{pfa},$

where the measure $A^{m-2}\lambda_{ca}$ is countably additive, positive, and
$A^{m-2}\lambda_{ca}(X)=\gamma>0$.

Thus, the initial measure $\mu_{1}$ has a nonzero countably additive component
and, thus, is not purely finitely additive, which contradicts the conditions
of the theorem. Therefore, the measure $\mu_{2}$ is also purely finitely
additive.

Repeating this procedure sequentially for all the other cyclic measures
$\mu_{3},\mu_{4},...,\mu_{m}$ we get that they are all purely finitely
additive.

It remains to prove that the mean cyclic measure

$\mu=\frac{1}{m}\sum_{i=1}^{m}\mu_{i}$

is also purely finitely additive. But this follows from the fact that the
space of purely finitely additive measures $pfa(X,\Sigma)$ is also linear,
which is proved nontrivially in [2] (Theorem 1.17). The theorem is proved.

Now let us present an extended cyclic analogue of the Alexandroff-Yosida-
Hewitt decomposition given in Section 2.

###### Theorem 4.4

Let $K=\\{\mu_{1},\mu_{2},...,\mu_{m}\\}$ be a finitely additive cycle of
measures of pairwise disjoint measures with period $m$ of an arbitrary MC and
$\mu_{i}=\mu^{ca}_{i}+\mu^{pfa}_{i}$ a decomposition of cyclic measures into a
countably additive component $\mu^{ca}_{i}$ and a purely finitely additive
component $\mu^{pfa}_{i},\;i=1,2,...,m$. Then these components are also
cyclic, form the cycles $K^{ca}$ and $K^{pfa}$, the cycle $K$ is the
coordinate sum of these cycles $K=K^{ca}+K^{pfa}$, and the mean measure of the
cycle $K$ is uniquely representable as the sum of its countably additive and
purely finitely additive components, which coincide with the mean measures of
the cycles $K^{ca}$ and $K^{pfa}$, respectively. Moreover, the cycles $K^{ca}$
and $K^{pfa}$ consist of pairwise disjoint measures and are disjoint with each
other, i. e. every measure from $K^{ca}$ is disjoint with every measure from
$K^{pfa}$.

Proof.

We denote tuples of countably additive and purely finitely additive components
of cyclic measures of a cycle $K$ by the symbols
$K^{ca}=\\{\mu_{1}^{ca},\mu_{2}^{ca},...,\mu_{m}^{ca}\\}$
$K^{pfa}=\\{\mu_{1}^{pfa},\mu_{2}^{pfa},...,\mu_{m}^{pfa}\\}$. The coordinate-
wise sum of these two tuples gives the original cycle $K=K^{ca}+K^{pfa}$. Now
we need to show that the measures $\mu_{i}^{ca}$ and $\mu_{i}^{pfa}$ are
cyclic, that is, the tuples $K^{ca}$ and $K^{pfa}$ are cycles.

Let us prove the theorem step by step.

Assume that some of the measures $\mu^{ca}_{i}$ is zero. Then
$\mu_{i}=\mu^{pfa}_{i}$, and according to Theorem 4.3 all other measures
$\mu_{j}=\mu^{pfa}_{j}$, i. e., the cycle $K=K^{pfa}$, and the theorem is
proved. Similarly, for $\mu^{pfa}_{i}=0$, the cycle $K$ is countably additive
by Theorem 4.2, $K=K^{ca}$, and the present theorem is proved. The main case
remains when all $\mu^{ca}_{i}\neq 0$ and all $\mu^{pfa}_{i}\neq 0$, which is
what we assume below.

Take two arbitrary measures $\mu^{ca}_{i}$ and $\mu^{ca}_{j}$ ($i\neq j$) from
$K^{ca}$.

Then

$0\leq\mu^{ca}_{i}\wedge\mu^{ca}_{j}\leq(\mu^{ca}_{i}+\mu^{pfa}_{i})\wedge(\mu^{ca}_{j}+\mu^{pfa}_{j})=\mu_{i}\wedge\mu_{j}.$

By the conditions of the theorem, all measures from $K$ are pairwise disjoint.
Therefore, $\mu_{i}\wedge\mu_{j}=0$ and $\mu^{ca}_{i}\wedge\mu^{ca}_{j}=0$, i.
e., all measures from $K^{ca}$ are pairwise disjoint. And since, as we now
assume, all measures from the tuple $K^{ca}$ are nonzero, then they are all
pairwise distinct.

Similarly, we obtain that all measures from the tuple $K^{pfa}$ are also
pairwise disjoint and distinct.

We emphasize that the tuples of measures $K^{ca}$ and $K^{pfa}$ have
dimensions $m$, which coincides with the period $m$ of the original cycle $K$.

By the conditions of the theorem, the cycle $K$ has an (arbitrary) period
$m\in N$. Consequently, each cyclic measure $\mu_{i}$ of the cycle $K$ is an
invariant measure of the operator $A^{m}$, that is, $\mu_{i}=A^{m}\mu_{i}$,
$i=1,2,...,m$. Take the first cyclic measure with its Alexandrov-Yosida-Hewitt
decomposition [2] $\mu_{1}=\mu_{1}^{ca}+\mu_{1}^{pfa}$. By Šhidak’s Theorem
([7, Theorem 2.5]) both components of the measure $\mu_{1}$ are also invariant
measures for the operator $A^{m}$, that is, $\mu_{1}^{ca}=A^{m}\mu_{1}^{ca}$,
$\mu_{1}^{pfa}=A^{m}\mu_{1}^{pfa}$.

Each of these components generates its own cycle

$\hat{K}^{ca}=\\{\mu_{1}^{ca},A\mu_{1}^{ca},,A^{m-1}\mu_{1}^{ca}\\},$
$\hat{K}^{pfa}=\\{\mu_{1}^{pfa},A\mu_{1}^{pfa},,A^{m-1}\mu_{1}^{pfa}\\}.$

Obviously, the coordinate-wise sum of these two cycles gives the whole cycle
$K=\hat{K}^{ca}+\hat{K}^{pfa}$.

Since the measure $\mu_{1}^{ca}$ is countably additive, then, according to
Theorem 4.2, all other cyclic measures of the cycle $\hat{K}^{ca}$ are
countably additive. Since the measure $\mu_{1}^{pfa}$ is purely finitely
additive, then, according to Theorem 4.3, all other cyclic measures of the
cycle $\hat{K}^{pfa}$ are purely finitely additive.

By the uniqueness of the decomposition of any measure into countably additive
and purely finitely additive components (see [2]), we obtain the following
equalities (here the symbol $A^{0}$ means the identical operator):

$\mu_{1}^{ca}=A^{0}\mu_{1}^{ca},$ $\mu_{2}^{ca}=A\mu_{1}^{ca},...$
$\mu_{m}^{ca}=A^{m-1}\mu_{1}^{ca},$

where on the left are the measures of the tuple $K^{ca}$, and on the right are
the cyclic measures of the cycle $\hat{K}^{ca}$.

Similar equalities are also true for purely finitely additive components.

From this we get that $K^{ca}=\hat{K}^{ca}$, $K^{pfa}=\hat{K}^{pfa}$, i.e.
tuples $K^{ca}$ $K^{pfa}$ are cycles, and $K={K}^{ca}+{K}^{pfa}$. Note that
this decomposition of the cycle $K$ is unique. The main statement of the
theorem is proved.

Now the corresponding equalities for the mean measures of cycles are obvious.

In [2] (Theorem 1.16), it was proved that any countably additive measure is
disjoint with any purely finitely additive measure. Therefore, the cycles of
the measures $K^{ca}$ and $K^{pfa}$ are disjoint. Above we showed that all
measures from $K^{ca}$ and $K^{pfa}$ are also pairwise disjoint.

The theorem is proved.

###### Corollary 4.1

A finitely additive cycle of measures $K$ is countably additive if and only if
its mean measure is countably additive.

###### Corollary 4.2

A finitely additive cycle of measures $K$ is purely finitely additive if and
only if its mean measure is purely finitely additive.

Comment.

Under the conditions of Theorem 4.4 just proved, the requirement of pairwise
disjointness of cyclic measures in the cycle $K$ is essential. If we remove
it, then the theorem becomes incorrect.

###### Theorem 4.5

Let an arbitrary MC have a singular cycle of the sets of states
$S=\\{D_{1},D_{2},...,D_{m}\\}$. Then the MC has a singular cycle of finitely
additive measures $K=\\{\mu_{1},\mu_{2},...,\mu_{m}\\}\subset S_{ba}$, such
that $\mu_{i}(D_{j})=1$, if $i=j$, and $\mu_{i}(D_{j})=0$, if $i\neq j$.

Proof.

We denote the set $D=\cup_{i=1}^{m}D_{i}$. As follows from Definition 3.12,
the set $D$ is stochastically closed for a MC, i. e. $p(x,D)=1$ for all $x\in
D$. Therefore, we can restrict the MC to the set $D$ by the rule:
$\tilde{p}(x,E)=p(x,E\cap D)$ for all $x\in D$ and $E\in\Sigma$. We obtain a
new MC on the space $(D,\Sigma_{D})$, where the sigma-algebra
$\Sigma_{D}=D\cap\Sigma$. The transition function $\tilde{p}(x,E)$ generates
the Markov operator $A_{{}_{D}}$, which coincides with the original operator
$A$ on the measure space $ba(D,\Sigma_{D})$.

By Šidak [7, theorem 2.2], a restricted MC has in its $S_{ba}$ invariant
finitely additive measure $\mu=A_{{}_{D}}\mu$. Let us expand the invariant
measure $\mu$ into the sum of measures $\mu_{i}$ constructed in a similar way
on cyclic sets $D_{i}$, $i=1,2,...,m$, according to the rule:
$\mu_{i}(E)=\mu(E\cap D_{i})$ for all $E\in\Sigma_{D}$, and $i=1,2,...,m$.
Obviously, $\mu=\frac{1}{m}\sum_{i=1}^{m}\mu_{i}$ on the $(D,\Sigma_{D})$.

Since, by the conditions of the theorem, the cyclic sets $D_{i}$ are pairwise
singular, the measures $\mu_{i}$ are also pairwise singular, the sets $D_{i}$
are carriers of the measures $\mu_{i}$ , $i=1,2,...,m$.

Now we need to show that the measures $\mu_{i}$, $i=1,2,...,m$ form a cycle
according to Definition 3.2.

Let $E\subset D_{2},E\in\Sigma_{D}$. The mean measure $\mu$ is invariant by
construction. Therefore,

$\mu(E)=A_{{}_{D}}\mu(E)=A_{{}_{D}}(\frac{1}{m}\sum_{i=1}^{m}\mu_{i})(E)=\frac{1}{m}\sum_{i=1}^{m}A_{{}_{D}}\mu_{i}(E)$

$=\frac{1}{m}\sum_{i=1}^{m}\int\limits_{D}p(x,E)\mu_{i}(dx)=\frac{1}{m}\sum_{i=1}^{m}\int\limits_{D_{i}}p(x,E)\mu_{i}(dx)$
$=\frac{1}{m}\int\limits_{D_{1}}p(x,E)\mu_{1}(dx)=\frac{1}{m}\int\limits_{D}p(x,E)\mu_{1}(dx)=\frac{1}{m}A\mu_{1}(E).$

On the other hand,

$\mu(E)=\frac{1}{m}\sum_{i=1}^{m}\mu_{i}(E)=\frac{1}{m}\mu_{2}(E).$

Since $\mu=A\mu$, we get
$\frac{1}{m}\mu_{2}(E)=\frac{1}{m}A_{{}_{D}}\mu_{1}(E)$, from which
$\mu_{2}(E)=A_{{}_{D}}\mu_{1}(E)$ for all $E\subset D_{2}$, i. e.
$\mu_{2}=A_{{}_{D}}\mu_{1}$ on the $(D,\Sigma_{D})$.

Similarly, we get $\mu_{i+1}=A_{{}_{D}}\mu_{i}$ for $i=2,...,m-1$ and
$\mu_{1}=A_{{}_{D}}\mu_{m}$ on the $(D,\Sigma_{D})$.

So, the set of measures $K=\\{\mu_{1},\mu_{2},...,\mu_{m}\\}$ forms a cycle of
a MC narrowed to the set of States $D=\cup_{i=1}^{m}D_{i}$.

Now we perform the reverse procedure. Restoring the values of the transition
function $p(x,E)$ to the entire measurable space $(X,\Sigma)$. Continue with
$(X,\Sigma)$ constructed measures $\mu$ and $\mu_{i}$, $i=1,2,...,m$,
according to the rule: for all sets $E\subset X\setminus D$, $E\in\Sigma$, we
assume $\mu(E)=0$, $\mu(E_{i})=0$, $i=1,2,...,m$.

Obviously, we get a finite-additive measure cycle defined already on the
entire phase space $(X,\Sigma)$. The theorem is proved.

###### Remark 4.1

In Theorem 4.5, we proved that the disjoint cycle $S$ of the sets of states of
a MC generates a disjoint cycle of finitely additive measures $K$. This
statement cannot be strengthened. In the previous Example 4.1, we showed that
a MC with a disjoint state cycle $S$ may not have any invariant (or cyclic)
countably additive measure at all, but have invariant (and cyclic) purely
finitely additive measures.

Now we prove one general Lemma not regardless of Markov chains.

###### Lemma 4.1

Let $(X,\Sigma)$ be an arbitrary measurable space on which given:

1) non-negative measurable bounded function $f:X\to R^{1}$ with a condition
$0\leq f(x)\leq 1$ for all $x\in X$;

2) a bounded positive countably additive measure $\mu:\Sigma\to R$ with the
condition $0\leq\mu(E)\leq 1$ for all $E\in\Sigma$ and $\mu(X)=1$ (i.e., a
probability measure).

Then, if

$\int\limits_{X}f(x)\mu(dx)=1,$

then $f(x)=1\;\;[\mu]$ almost everywhere, i. e. $\mu\\{x\in X:f(x)=1\\}=1$.

Proof.

We denote the sets $F=\\{x\in X:f(x)=1\\}$, $G=\\{x\in X:f(x)<1\\}$.
Obviously, $F,G\in\Sigma,F\cap G=\emptyset,X=F\cup G$. We need to prove that
$\mu(F)=1$ or $\mu(G)=0$. Assume the contrary. Let $\mu(G)>0$.

By construction, the set of possible values of the function $f(x)$ for $x\in
G$ is the half-interval $E=[0,1)$. We split the half-interval $E$ into a
countable sum of pairwise disjoint half-intervals
$E_{n}=[1-\frac{1}{n},1-\frac{1}{n+1}),n\in N,E=\cup_{n=1}^{\infty}E_{n}$. We
take the inverse images of these sets $G_{n}=f^{-1}(E_{n})=\\{x\in X:f(x)\in
E_{n}\\}=\\{x\in X:1-\frac{1}{n}\leq f(x)<1-\frac{1}{n+1}\\}$. The inverse
images of $G_{n},n\in N,$ are also pairwise do not intersect and
$G=\cup_{n=1}^{\infty}G_{n}$. Since the measure $\mu$ is countably additive,
then $\mu(G)=\mu(\cup_{n=1}^{\infty}G_{n})=\sum_{n=1}^{\infty}\mu(G_{n})$. By
assumption, $\mu(G)>0$. Therefore, there is a number $k\in N$, such that
$\mu(G_{k})=\alpha>0$.

Now let’s make integral transformations with ascending inequalities.

$1=\int\limits_{X}f(x)\mu(dx)=\int\limits_{X\setminus
G_{k}}f(x)\mu(dx)+\int\limits_{G_{k}}f(x)\mu(dx)$ $\leq\int\limits_{X\setminus
G_{k}}1\cdot\mu(dx)+\int\limits_{G_{k}}(1-\frac{1}{k+1})\mu(dx)$
$=\mu(X\setminus G_{k})+(1-\frac{1}{k+1})\mu(G_{k})=\mu(X\setminus
G_{k})+\mu(G_{k})-\frac{1}{k+1}\mu(G_{k})$
$=\mu(X)-\frac{1}{k+1}\alpha=1-\frac{1}{k+1}\alpha<1.$

Hence we get $1<1$, i.e. contradiction.

Therefore, $\mu(G)=0$ and $\mu(F)=1$. The lemma is proved.

If in Lemma 4.1 we abandon the countable additivity of the measure $\mu$, then
the lemma becomes invalid. Let us give a corresponding counterexample.

Example 4.2. Let a function $f(x)=x$ and a purely finitely additive measure
$\mu$ be given on the interval $X=(0,1),\Sigma=\mathfrak{B}$, satisfying the
condition $\mu((1-\varepsilon,1))=1$ for any $0<\varepsilon<1$.

Since $1>f(x)$ for all $x\in(0,1)$, then for any $0<\varepsilon<1$ we have

$1\geq\int\limits_{(0,1)}f(x)\mu(dx)=\int\limits_{(0,1)}x\mu(dx)=\int\limits_{(1-\varepsilon,1)}x\mu(dx)$
$\geq\int\limits_{(1-\varepsilon,1)}(1-\varepsilon)\mu(dx)=(1-\varepsilon)\mu((1-\varepsilon),1)=1-\varepsilon,$

i. e.

$1\geq\int\limits_{(0,1)}f(x)\mu(dx)\geq 1-\varepsilon$

Hence, $\int\limits_{(0,1)}f(x)\mu(dx)=1$. However, the set $F=\\{x\in
X:f(x)=1\\}$ is empty and $\mu(\\{x\in X:f(x)=1\\})=0$. We can say that the
function $f(x)=x$ is not equal to 1 everywhere, not just $[\mu]$ \- almost
everywhere on the interval $X=(0,1)$. Lemma 4.1 does not hold for such a pair
$f$ and $\mu$.

###### Theorem 4.6

Let an arbitrary MC have a disjoint countably additive cycle of measures
$K=\\{\mu_{1},\mu_{2},...,\mu_{m}\\}\subset S_{ca}$. Then the MC has a
singular cycle of state sets $S=\\{D_{1},D_{2},...,D_{m}\\}$, such that
$\mu_{i}(D_{j})=1$, if $i=j$; $\mu_{i}(D_{j})=0$, if $i\neq j$, and
$p(x,D_{i+1})=1$ $[\mu_{i}]$ almost everywhere for $x\in D_{i}$, for
$i=1,2,...,m$, and $p(x,D_{1})=1$ $[\mu_{m}]$ almost everywhere for $x\in
D_{m}$.

Proof. As noted in Theorem 3.1 (with reference to [2]), if a cycle of
countably additive measures is disjoint, then it is also singular. Therefore,
there exist pairwise singular (disjoint) supports of cyclic measures
$S=\\{D_{1},D_{2},...,D_{m}\\}$. Moreover, $\mu_{i}(D_{j})=1$, if $i=j$, and
$\mu_{i}(D_{j})=0$, if $i\neq j$. It is necessary to prove that the family of
sets $S$ also form a cycle by Definition 3.12, and possibly in view of Remark
3.1.

Take the first two adjacent cyclic measures $\mu_{1},\mu_{2}$ from the cycle
$K$. Since $\mu_{2}=A\mu_{1}$, then the following equalities are true:

$1=\mu_{2}(D_{2})=A\mu_{1}(D_{2})=\int\limits_{X}p(x,D_{2})\mu_{1}(dx)=\int\limits_{D_{1}}p(x,D_{2})\mu_{1}(dx).$

Note that the measure $\mu_{1}$ is countably additive, $\mu_{1}(D_{1})=1$ and
$\mu_{1}\in S_{ca}$. The transition function of the Markov chain satisfies the
inequalities $0\leq p(x,D_{2})\leq 1$ for all $x\in D_{1}$. The conditions of
Lemma 4.1 are fulfilled. Hence, $p(x,D_{2})=1$ $[\mu_{1}]$ almost everywhere
for $x\in D_{1}$.

Similarly, one can show that all other pairs of neighboring measures
$\mu_{i},\mu_{i+1}$ of the cycle $K$ and pairs of neighboring sets
$D_{i},D_{i+1}$ of the family $S$ satisfy the conditions
$p(x,D_{i+1})=1\;\;[\mu_{i}]$ almost everywhere for $x\in D_{i}$, for
$i=1,2,...,m-1$ and $p(x,D_{1})=1$ $\;\;[\mu_{m}]$ almost everywhere for $x\in
D_{m}$.

This means that the family of sets $S=\\{D_{1},D_{2},...,D_{m}\\}$ is a cycle
that satisfies the statement of the theorem. The theorem is proved.

###### Corollary 4.3

If the conditions of Theorem 4.6 are satisfied, then $p(x,D_{i})=0$
$[\mu_{i}]$ almost everywhere for $x\in D_{i}$, for $i=1,2,...,m$.

###### Remark 4.2

The proof of Theorem 4.6 is based on Lemma 4.1, in which the requirement of
countable additivity of the measure $\mu$ is essential (see Example 4.2).
Accordingly, this requirement for the measures $\mu_{1},...,\mu_{m}$ is also
necessary for Theorem 4.6.

###### Theorem 4.7

Let an arbitrary MC have one finitely additive cycle of measures $K$ of any
period and its mean measure $\mu$ is the only invariant finitely additive
measure for the operator $A$. Then the cycle $K$ and its mean measure $\mu$
are countably additive.

Proof. Consider a cycle of finitely additive measures
$K=\\{\mu_{1},\mu_{2},...,\mu_{m}\\}$ and its mean measure
$\mu=\frac{1}{m}\sum_{i=1}^{m}\mu_{i}$. In Section 3 shows that the mean
measure $\mu$ of the cycle $K$ is invariant for the operator $A$, i.e.
$\mu\in\Delta_{ba}$. By the condition of the theorem, this measure is unique
in $\Delta_{ba}$, i. e. $\Delta_{ba}=\\{\mu\\}$.

In [5, Theorem 8.3], it is proved that if a MC has in $S_{ba}$ a unique
invariant measure $\mu$, i. e. $\Delta_{ba}=\\{\mu\\}$, then this measure is
countably additive. Therefore, by Theorem 4.2 and Corollary 4.1, the cycle $K$
is countably additive.

The theorem is proved.

Therefore, it follows (under the above conditions) that there are no
‘‘single’’ purely finitely additive cycles.

## Acknowledgments

This work was supported by the Russian Foundation for Basic Research (project
No. 20-01-00575-a)

## References

  * [1] K. Yosida, S. Kakutani, ‘‘Operator-theoretical treatment of Markoff’s processes and mean ergodic theorem’’, Annals of Mathematics, Second Series, 42:1 (1941), 188–228.
  * [2] K. Yosida, E. Hewitt,‘‘Finitely Additive Measures’’, Trans. Amer. Math. Soc., 72:1 (1952), 46–66.
  * [3] N. Dunford, J. Schwartz, Linear operatiors, Part I: General Theory, Interscience Publischer, 1958.
  * [4] D. Revuz, Markov Chains, Oxford. North Holland, Math. Libr., 1984.
  * [5] A. I. Zhdanok, ‘‘Finitely additive measures in the ergodic theory of Markov chains I’’ , Siberian Advances in Mathematics. 13:1 (2003), 87–125; in Russian: A. I. Zhdanok, ‘‘Konechno-additivnyye mery v ergodicheskoy teorii tsepey Markova I’’ , Matematicheskiye trudy, 4:2 (2001), 53–95.
  * [6] A. I. Zhdanok, ‘‘Finitely additive measures in the ergodic theory of Markov chains II’’ , Siberian Advances in Mathematics. 13:2 (2003), 108–125; in Russian: A. I. Zhdanok, ‘‘Konechno-additivnyye mery v ergodicheskoy teorii tsepey Markova II’’ , Matematicheskiye trudy, 5:1 (2002), 45–65.
  * [7] Z. Šidak, ‘‘Integral representations for transition probabilities of Markov chains with a general state space’’ , Czechoslovak Math. J., 12(87):4 (1962), 492–522.
  * [8] A. I. Zhdanok, ‘‘Dimension of the space of invariant finitely additive measures of general Markov chains and their ergodic properties’’, arXiv preprint arXiv:1804.02787, 2018.
  * [9] A. I. Zhdanok, ‘‘Weak ergodic theorem for Markov chains in the absence of invariant countably additive measures’’, arXiv preprint arXiv:1807.11868, 2018.
  * [10] A. I. Zhdanok, ‘‘Ergodicity conditions for general Markov chains in terms of invariant finitely additive measures’’, arXiv preprint arXiv:2006.08664, 2020.


11institutetext:  Imperial College London 11email:
<EMAIL_ADDRESS>22institutetext: Google DeepMind 22email:
<EMAIL_ADDRESS>33institutetext: Imperial College London 33email:
<EMAIL_ADDRESS>

# Characterising Decision Theories with Mechanised Causal Graphs

Matt MacDermott 11 Tom Everitt 22 Francesco Belardinelli 11

###### Abstract

How should my own decisions affect my beliefs about the outcomes I expect to
achieve? If taking a certain action makes me view myself as a certain type of
person, it might affect how I think others view me, and how I view others who
are similar to me. This can influence my expected utility calculations and
change which action I perceive to be best. Whether and how it should is
subject to debate, with contenders for how to think about it including
evidential decision theory, causal decision theory, and functional decision
theory. In this paper, we show that mechanised causal models can be used to
characterise and differentiate the most important decision theories, and
generate a taxonomy of different decision theories.

###### Keywords:

Decision Theory Causality Game Theory.

##  1 Introduction

What’s the best course of action, given a particular objective, and some
beliefs about the present situation? To make this question more concrete,
decision theory typically represents beliefs with a probability distribution
or causal model, and objectives with a real-valued utility function, such that
the preferred course of action is to maximise the expected utility. Even under
these constraints, the "correct" decision procedure remains subject to debate.
Should expected utility be calculated by conditioning on the action [16, 1],
intervening on the action [23, 30, 12, 17], intervening on the policy [33,
25], or by some other method [6, 31]? And in what kind of model?

The choice of procedure matters especially in situations where my very action
can teach me something about myself. On the one hand, learning about myself
informs me about the behaviour of similar agents – so that if I find myself in
a prisoner’s dilemma with one, for example, my decision about whether to co-
operate tells me something about theirs. My decision also informs me about
what others might think of me – so that it helps me know what to expect from
anybody who is making sufficiently accurate predictions about me.

The part of the decision theory debate we are interested in is how and when it
is appropriate to let these sort of inferences influence one’s decision. This
question is particularly relevant for AI systems. Whilst we humans rarely
encounter exact copies of ourselves or oracular predictors of our behaviour,
AI systems have source code (or model weights) that can be duplicated or
inspected by other agents. We might therefore expect them to frequently find
themselves in the sort of situations described in decision-theoretic thought
experiments.

This has several important consequences. Firstly, if we are going to be
delegating our decision-making to artificial agents, we had better be clear on
what constitutes good decision-making. Understanding the pros and cons of
different decision theories can help us design agents that handle tricky
situations adequately.

Secondly, powerful AI systems may be dangerous [4, 5]. Understanding how a
system’s design and training influences its decision theory [19, 3] may help
us anticipate and avoid situations where things go wrong. To illustrate this
point, note that several proposals for aligning AI systems involve using
multiple agents to police each other’s behaviour, in the hopes that a Nash
equilibrium of mutual defection emerges to keep the various parts of the
system honest [15, 20]. But as we will see in the case of the prisoner’s
dilemma, some decision theories can be used to _avoid_ Nash equilibria to the
mutual benefit of the agents involved. An understanding of decision theory can
help us avoid potentially catastrophic situations where powerful agents meant
to keep each other in check collude against their overseers.

##### Contributions

In this paper we show that mechanised causal models [13, 18] offer a unified
framework for comparing and analysing different decision theories. In
particular, standard decision theory problems can be usefully modelled using
mechanised causal graphs (Section 2), and common decision theories can be
characterised and distinguished based on which nodes they condition and
intervene on (Section 3). This in turn allows us to identify dimensions along
which decision theories differ, and propose a taxonomy of available decision
principles (Section 4). Finally, we use mechanised graphs to clarify when a
certain class of decision problem is well-defined (Section 5).

##  2 Modeling Decision Problems

In this section, we describe some decision problems often used to distinguish
different principles for decision-making, and how to model them with causal
graphs.

###  2.1 Decision Problems

Several thought experiments have long been used in the decision theory
literature to probe at intuitions around whether a rational agent should
choose actions based on the evidence they provide about expected outcomes, or
based on their causal effects. We start by considering the following Newcomb’s
Problem, as it first appeared in [26].

######  Example 1 (Newcomb’s Problem)

You stand before two boxes. One is transparent and contains one thousand
dollars; the other is opaque and either contains either one million dollars or
nothing. Your choice is between taking both boxes ("two-boxing") and taking
just the opaque box ("one-boxing"). A reliable predictor, who has been right
in $99\%$ of previous cases, has put the million in the opaque box if and only
if it predicted you would one-box.

Newcomb’s problem gives its name to the class of ‘Newcomblike’ problems. Such
problems arise when your action provides evidence about the state of the world
beyond its causal effect. A variant of Newcomb’s problem makes both boxes
transparent [12], which will help to illustrate considerations about how you
should use your observations to update your beliefs:

######  Example 2 (Transparent Newcomb)

You face the same choice as in Newcomb’s problem, except that now both boxes
are transparent, and the predictor has put the million in the second box if
and only if they predicted you would one-box upon seeing it.

Finally, we introduce the a version of the Twin Prisoner’s Dilemma [22], to
illustrate subtleties in the definition of causality:

######  Example 3 (Twin Prisoner’s Dilemma)

You face a Prisoner’s Dilemma. You and your opponent will each co-operate or
defect. You rank the outcomes from best to worse as follows: defecting against
co-operation, mutual co-operation, mutual defection, being defected against
while co-operating. You can see that your opponent is an agent with identical
source code to your own. You know that the source code will compile into the
same policy for you as for your opponent, but the only way to determine what
the policy actually does is to decide your action.

###  2.2 Causal Models

The different decision problems can be modeled using Pearl’s causal models
[29], which consists of three kinds of probabilistic models: associational,
interventional, and counterfactual.

We will use capital letters ($V$) for variables, lowercase letters ($v$) for
instantiations of variables, and bold letters ($\bm{V}$ or $\bm{v}$) for sets
of the above. We write $dom(V)$ for the set of oucomes of a random variable
$V$.

######  Definition 1 (Bayesian Network)

A _Bayesian network_ over a set of random variables $\bm{V}$ with joint
distribution $Pr(\bm{V})$ is a directed acyclic graph (DAG)
$\mathcal{G}=(\bm{V},\mathcal{E})$ with vertices $\bm{V}$ and edges
$\mathcal{E}$ such that the joint distribution can be factorised as
$Pr(\bm{V})=\prod_{V\in\bm{v}}Pr(V\mid\bm{Pa_{V}})$, where $\bm{Pa_{V}}$ are
the parents of $V$ in $G$.

$D$$P$$U$ (a)

$D$$P$$U$$Pre$ (b)

$D$$P$$U$$\tilde{D}$$\tilde{P}$ (c)

Figure 1: Newcomb’s problem as (a) Bayesian network, (b) a causal Bayesian
network, and (c) a mechanised causal Bayesian network with $\tilde{U}$
omitted.

We borrow from the literature on influence diagrams [14, 8] the convention of
using square nodes for decision variables, diamond nodes for utility
variables, and round nodes for everything else. However, it is important to
remember that our models are not influence diagrams, since we assume
probability distributions over decision variables rather than leaving them
blank. This introduces the question of how such probability distributions
should feature in expected utility calculations, which is precisely the debate
about causal and evidential decision theory.

Newcomb’s problem can be modeled with a Bayesian network as in fig. 1(a),
where we have variables representing the agent’s decision $D$, the prediction
$P$, and the utility $U$. The association between the agent’s decision and the
prediction is represented with the (non-causal) edge $D\to P$. Note that while
this edge doesn’t represent a causal relationship, nor would a reverse edge
$P\to D$, as the prediction does not causally influence the decision (changing
the prediction would not change the decision). The utility $U$ depends on both
the decision $D$ and the prediction $P$, which is modelled with the (causal)
edges $D\to U\leftarrow P$.

Causal Bayesian networks [29] are a particular kind of Bayesian network that
can represent the effects of external interventions, effectively by requiring
that edges always represent direct causal influences. An intervention on a set
of variables can then be understood formally as replacing the conditional
probability distributions of those variables, which changes the marginal
distributions of causally downstream variables without affecting those
upstream.

######  Definition 2 (Causal Bayesian Network)

A _causal Baysian network_ over a set of random variables $\bm{V}$ with joint
interventional distributions $\\{Pr(\bm{V}\mid do(\bm{Y}=\bm{y})\\}$ is a
Bayesian network $\mathcal{G}=(\bm{V},\mathcal{E})$ such that for any
$\bm{Y}\subseteq\bm{V}$ and $\bm{y}\in dom(\bm{Y})$, the joint distribution
equals

$Pr(\bm{V}\mid
do(\bm{Y}=\bm{y}))=\prod_{V\in\bm{V}\setminus\bm{Y}}Pr(V\mid\bm{Pa}_{V})$

for values of $\bm{V}$ compatible with $\bm{y}$, and values of $\bm{V}$
incompatible with $\bm{y}$ have probability $0$.

Figure 1(b) shows Newcomb’s problem represented as a Causal Bayesian network.
To make all arrows represent causal relationships, it is necessary to
introduce a confounding variable representing the predisposition of the agent
to one-box or two-box. The other variables are as in fig. 1(a).

A more systematic way of representing agents’ predispositions is to include
nodes for their policies, as well as for the mechanisms governing other
variables in the graph [18, 13]. This can be done with a special kind of
causal Bayesian network called a mechanised causal Bayesian network.

######  Definition 3 (Mechanised Causal Bayesian Network)

A _mechanised causal Bayesian network_ is a causal Bayesian network over a set
of variables $\bm{\mathcal{V}}$ which is partioned into _object-level
variables_ $\bm{V}$ and _mechanism-level variables_ $\bm{\tilde{V}}$. Each
object-level variable $V\in\bm{V}$ has a single mechanism parent
$\tilde{V}\in\bm{\tilde{V}}$, such that the value of $\tilde{V}$ sets the
probability distribution $Pr(V\mid\bm{Pa_{V}})$, where $\bm{Pa_{V}}$ is the
set of object-level parents of $V$.

We call the mechanism of a decision variable a _decision rule_ variable. An
agent’s policy is a tuple consisting of the decision rules for each of its
decision nodes. In this paper we restrict our attention to settings with a
single decision variable, and so we will use the terms somewhat
interchangeably 111Following the convention of the decision theory literature,
we usually restrict agents to deterministic policies. Stochastic policies can
be modelled by allowing the agent to observe a source of randomness before
making a decision.

Newcomb’s problem is represented with a mechanised causal graph in fig. 1(c),
obtained from fig. 1(b) by adding mechanism parents $\tilde{D},\tilde{U}$, and
$\tilde{P}$ for each of the object-level variables $D,U,$ and $P$ (since the
utility mechanism $\tilde{U}$ is not relevant to our analysis, we suppress it
in our diagrams). We will no longer need the confounding "predisposition"
variable to explain the correlation of the agent’s decision with the
prediction. Instead, we can model the connection between the prediction and
the agent’s behaviour by letting the mechanism of the prediction variable
depend on the mechanism variable of the of the agent’s decision.

$D$$P$$U$$\tilde{D}$$\tilde{P}$ (a)

$D$$P$$U$ (b)

Figure 2: (a) Transparent Newcomb, and (b) Transparent Newcomb where the
predictor predicts the decision rather than the decision rule.

The Transparent Newcomb problem can be modeled in much the same way, but with
an edge added from $P$ to $D$, representing the fact that the agent observes
the prediction, which means that the prediction is now able to causally
influence the decision (see fig. 2). As in the causal influence diagram
literature, we will used dashed edges to represent agents’ observations.

###  2.3 Notions of Causality

Finally, the Twin Prisoner’s Dilemma brings up an important distinction about
causality. Abstractly, a causal model over a set of variables needs to specify
two operations for each variable: how to intervene, and how to measure. Once
these operations are specified, a well-defined probability distribution is
generated for each possible combination of interventions.

In the study of decision problems, the operations we have in mind are often
sufficiently obvious from an informal description of the variables that we do
not need to explicitly specify them. Indeed, this is the case for the
prediction, decision, and utility in figs. 1 and 2. But in the Twin Prisoner’s
Dilemma, one might interpret the policy node in two different ways, and the
interpretation will affect the causal structure. We could interpret
intervening on your policy $\tilde{D}$ as changing the physical result of the
compilation of your source code, such that an intervention will only affect
your decision $D$, and not that of your twin $T$. Under this physical notion
of causality, we get fig. 3(a), where there is a common cause $S$ explaining
the correlation between the agent’s policy and its twin’s.

But on the other hand, if we think of intervening on your policy as changing
the way your source code compiles in all cases, then intervening on it will
affect your opponent’s policy, which is compiled from the same code. In this
case, we get the structure shown in fig. 3(b), where an intervention on my
policy would affect my twin’s policy222We could alternatively imagine mutual
causation between the agent’s policy and the twin’s policy, but for the
purposes of this paper we will model the world from the subjective first-
person perspective of a particular agent.. We can view this as an intervention
on an abstract "logical" variable rather than an ordinary physical variable.
We therefore call the resulting model a _logical-causal_ model.

Pearl’s notion of causality is the physical one, but Pearl-style graphs have
also been used in the decision theory literature to represent logical
causality [31, 33, 21]. One purpose of this paper is to show that mechanism
variables are a useful addition to any graphical model being used in decision
theory.

$D$$T$$U$$\tilde{D}$$\tilde{T}$$S$ (a)

$D$$T$$U$$\tilde{D}$$\tilde{T}$ (b)

Figure 3: The Twin Prisoner’s Dilemma (a) from the perspective of a causal
decision theorist and (b) from the perspective of a functional decision
theorist.

##  3 Decision Theories Using Mechanised Causal Graphs

In this section we use mechanised causal graphs to describe three competing
approaches to calculating the expected utility of a course of action: causal
decision theory (CDT), evidential decision theory (EDT), and functional
decision theory (FDT). While causal graphs have often been used to
characterise the difference between causal and evidential expected utility
calculations, the introduction of mechanism variables allows us to go a step
further and define FDT’s feature of "updatelessness" as a property of grapical
queries.

###  3.1 Causal Decision Theory

Causal decision theory [17, 12, 30, 23] asks you to consider the causal effect
of each of the options you have at your disposal. CDT has various notable
formalisations, and many arguments have been made in its favour, but perhaps
its greatest appeal is that choosing an action for any reason other than its
causal effect seems intuitively bizarre.

> Slogan: Choose the action with the best causal effect.

In Newcomb’s problem, if you only care about the causal effects of your
actions, you should two-box. You will get the opaque box either way and its
contents have been decided already; you cannot causally influence whether you
get the million. You can affect whether you get the thousand – so your
expected wealth is one thousand dollars higher under two-boxing than one-
boxing. Things are similar in Transparent Newcomb and the Twin Prisoner’s
Dilemma – your decision does not causally affect the contents of the boxes or
whether your twin co-operates, so you should one-box and defect respectively.

##### Expected Utility Calculations

A causal decision theorist computes the expected utility of taking each action
$d\in dom(D)$ as

$\mathbb{E}\left[U\mid do(D=d),\bm{Obs}_{D}=\bm{obs}_{D}\right].$

Figure 4(b) shows the operation performed by CDT in a mechanised causal graph
for Newcomb’s problem. The do-intervention severs the edge from $\tilde{D}$ to
$D$, so the value of $D$ tells us nothing about $P$, and the agent two-boxes.
In Transparent Newcomb (fig. 2) and the Twin Prisoner’s Dilemma (fig. 3(a))
the story is much the same.

##### Model Requirements.

CDT agents compute their expected utility under an intervention, so they
require a model at the second rung of Pearl’s causal hierarchy. And since no
mechanism variables appear in the expression, the model does not need to be
mechanised. But as we just saw, CDT agents can happily use models with
mechanism variables. They can also use models at the third rung of the
hierarchy.

In order to obtain a model of a decision problem sufficient to apply CDT, we
need to estimate the probability distribution $P(U\mid do(D=d),\bm{Obs}_{D})$
for each $d\in dom(D)$. In principle we can do this by performing a randomised
controlled trial experiment: find sufficiently similar agents to ourselves
facing the same decision problem, assign them an action to take at random, and
record their observations and the utility they recieve. But we need to be able
to make these assignments as an outsider to the system, so that for example, a
Newcomblike predictor could not have foreseen our intervention and predicted
the agent’s action accordingly.

conditioningintervening

$D$$P$$U$$\tilde{D}$$\tilde{P}$$D$ (a) EDT

$D$$P$$U$$\tilde{D}$$\tilde{P}$$D$ (b) CDT

$D$$P$$U$$\tilde{D}$$\tilde{P}$ (c) FDT

Figure 4: The operation performed by (a) an evidential decision theorist, (b)
a causal decision theorist, and (c) a functional decision theorist on a
graphical model of Newcomb’s Problem.

conditioningintervening

$D$$P$$U$$\tilde{D}$$\tilde{P}$$P$$D$ (a) EDT

$D$$P$$U$$\tilde{D}$$\tilde{P}$$P$$D$ (b) CDT

$D$$P$$U$$\tilde{D}$$\tilde{P}$ (c) FDT

Figure 5: The operation performed by (a) an evidential decision theorist, (b)
a causal decision theorist, and (c) a functional decision theorist on a model
of the Transparent Newcomb problem.

###  3.2 Evidential Decision Theory

Evidential decision theory [1, 16] says you should condition on your decision,
and can be distilled into the following slogan:

> Slogan. Choose the action with the best news value.

In Newcomb’s problem, if you care about the evidence your actions provide, you
should one-box. Though the contents of the opaque box are fixed, your beliefs
about them aren’t. If you one-box, there’s a $99\%$ chance the opaque box
contains the million; if you two-box there’s a $99\%$ chance it doesn’t.

Though EDT is not as immediately intuitively compelling as CDT, in some
situations EDT agents appear to fare better: for example, EDT agents almost
always leave Newcomb’s problem as millionaires, while CDT agents almost never
do. This is sometimes called the "If you’re so rational, why ain’cha rich?"
argument [24].

In Transparent Newcomb, on the other hand, your decision no longer provides
any information about the contents of the second box, since you already know
it. EDT therefore agrees with CDT that you should two-box. In the Twin
Prisoner’s Dillema, co-operation is evidence your twin will co-operate, and
defection is evidence your twin will defect. Mutual co-operation is preferable
to mutual defection, so EDT recommends that you co-operate.

##### Expected Utility Calculations

An evidential decision theorist computes the expected utility of taking each
action $d\in dom(D)$ as

$\mathbb{E}\left[U\mid D=d,\bm{Obs}_{D}=\bm{obs}_{D}\right].$

Figure 4(a) shows the operation performed by EDT in a graphical model of
Newcomb’s problem. Since there are no observed variables, we just condition on
$D$. There is an active path from $D$ to $U$ via $P$ – the agent’s decision
gives information about their decision rule, which in turn gives information
about the prediction mechanism, the prediction, and finally the agent’s
utility. An EDT agent opts to one-box in order to maximise its expected
utility via this backdoor path.

Figure 5(a) shows the operation performed by EDT in the case of Transparent
Newcomb. Since $P$ is now observed, we condition on it, blocking the backdoor
path from $D$ to $U$. The EDT agent two-boxes in order to maximise its
expected utility via the direct link from $D$ to $U$.

The graphical models in fig. 3(a) and fig. 3(b) can both be used to apply EDT
to the Twin Prisoner’s Dilemma. In either case, conditioning on $D$ affects
the value of $T$ via a backdoor path, and so the agent chooses to co-operate
so that its twin does the same.

##### Model Requirements

Since EDT agents’ expected utility calculations only involve associational
queries, they just require a model at the first rung of Pearl’s causal
hierarchy. They do not require a mechanised model, but they can use one.

A model of a decision problem sufficient to apply EDT can be obtained more
easily than in the case of CDT, since we only need to collect observational
rather than interventional data. We can simply observe similar agents facing
the same decision problem, record their observations, their decision, and the
utility they recieve, and then estimate $P(U\mid D,\bm{Obs_{D}})$.

###  3.3 Functional Decision Theory

Functional decision theory, as presented in [33] and [21], can be summed up as
follows:

> Slogan. Choose the way you would like all instances of your decision
> function to behave.

We propose to think of FDT in a slightly different way, as a version of CDT
with two key differences: firstly, FDT chooses the best decision rule to
follow, rather then the best action to take, and secondly, FDT uses a logical
rather than physical notion of causality. Using this idea, we can suggest a
new definition of FDT in mechanised causal graphs.

##### Expected Utility Calculations

A functional decision theorist computes the expected utility of taking each
action $d\in dom(D)$ as

$\mathbb{E}\left[U\mid do(\tilde{D}=\tilde{d})\right].$

In Newcomb’s problem (fig. 4(c)), intervening on $\tilde{D}$ affects $U$ via
both $D$ and $P$. In Transparent Newcomb (fig. 5(c)), the fact that FDT does
not condition on observed variables means the path to $U$ via $P$ remains
unblocked, and so an FDT agent one-boxes in both.

The property of not conditioning on observed variables is known as
"updatelessness" (Section 5), and it is this property, rather than FDT’s
alternative notion of causality, which explains its behaviour here. An
updateless version of CDT would one-box as well, since the physical and
logical-casual models are the same.

But the logical view of causality is relevant in the Twin Prisoner’s Dilemma.
An FDT agent treats their twin’s policy as a logical consequence of their own,
so that the problem becomes analogous to Newcomb’s problem (see fig. 3(b)). In
particular, this means that the twin’s decision about whether to co-operate is
downstream of the variable on which FDT intervenes, and so an FDT agent
follows a policy of co-operation in order to influence the twin. Note that
policy-selection alone is not enough to achieve co-operation here, since in a
physical causal model the twin’s policy is not downstream of the agent’s own.

##### Model Requirements.

FDT agents require a model at the second rung of Pearl’s causal hierarchy, and
they need it to involve their decision rule variable $\tilde{D}$.

However, in contrast to CDT, FDT agents require a model of the interventional
distributions under interventions on logical rather than physical variables.
While we can often intuitively imagine how the world would look under a
logical intervention – if all existing instances of an agent’s source code
compiled in different way, for example – the notion is not sufficiently
formalised that we can say how one could actually go out into the world and
determine such interventional distributions from observation and experiment.
In other words, FDT has an epistemic problem – we cannot yet say how FDT
agents can find out what they need to know, even in principle. For this,
something like a formal theory of logical causality would be needed.

###  3.4 A Discussion of Updatelessness

To motivate FDT, consider that the "Why ain’cha rich?" argument can be turned
on both EDT and CDT in cases where agents would benefit from being able to
make binding precomitments, such as Transparent Newcomb.

EDT and CDT agents alike reason that since you can see that the second box is
full, you are choosing between a sure million and a sure one million one
thousand. However, the second box will only be full if the predictor happens
to have predicted that you would one-box. Since CDT and EDT agents in fact
two-box, and since the predictor is right $99\%$ of the time, they will almost
always be choosing between a sure nothing and a sure one thousand. We can
calculate the expected winnings of a CDT or EDT agent facing Newcomb’s problem
as $$11\ 000$333$99\%\times$$$1\ 000+1\%\times$$$1\ 000\ 000$.. Given the
opportunity to make a binding precommitment to one-boxing if the second box is
full, either type of agent would take it, since doing so would up their
expected winnings to $$990\ 010$ 444$99\%\times\text{\$}1\ 000\
000+1\%\times\text{\$}1000$ (the agent is free to take the thousand if the
million is not present)..

It is insightful to notice that an agent that acts as it would ideally have
precommitted to act can achieve exactly the same outcomes even in the absence
of the opportunity to precommit. Suppose an agent finds itself in the
Transparent Newcomb problem, not having precommitted to anything, realises it
would have liked to have precommited to one-boxing upon seeing the million,
and decides to act in accordance with that commitment anyway. With $99\%$
probability the predictor will have predicted this and the agent will come
away a millionaire.

Several proposals formalise this idea in terms of selecting the best policy to
follow, rather than the best action to take [11, 25], or in terms of not
performing a Bayesian update on your beliefs after making an observation [6].
The proposals amount to almost the same idea, and in the framework of
mechanised causal graphs it becomes clear that in order to act as you would
ideally have precommitted to act it is necessary to both switch from selecting
your decision $D$ to your decision rule $\tilde{D}$, and stop conditioning on
your observations $\bm{Obs}_{D}$.

We prefer to call this idea "updatelessness" [6] rather than "policy-
selection", primarily because selecting the policy while conditioning on
observations will not have the desired effect. Indeed, it is somewhat
difficult to construct a reasonable decision problem in which conditioning on
$\bm{Obs_{D}}$ while selecting $\tilde{D}$ is different from conditioning
$\bm{Obs_{D}}$ while selecting $D$. It might therefore be most natural to
think of all of the decision theories discussed here as ways of calculating of
the expected utility of following each decision rule, with some of them
conditioning these calculations on the current observation, and some not.
However, in order not to stray to far from ordinary convention, we will
continue to notate updateful decision theories as selecting $D$.

Mechanised causal graphs clarify that the original definition of functional
decision theory (as choosing the output of all instances of your decision
function) can be thought of as a combination of updatelessness with an
alternative notion of causality555FDT as presented in [33] selects the action
the decision rule outputs on the current observation, rather than the whole
decision rule. This should not be confused with updatefulness. For simplicity
we treat it as selecting the whole decision rule..

A final point to note is that issues of updatelessness can only arise in
models of decision-making where agents are asked to choose conditional
policies, such as in extensive-form games, or the graphical models we consider
here. When we represent a game in normal-form, we effectively stipulate that
there is a single decision to be made by each player, unconditional on any
observations. As in the Twin Prisoner’s Dilemma, updatelessness will not
affect an agent’s decision in a "twin" version of any normal-form game.

##  4 A Taxonomy of Decision Theories

In this section we categorise the decision theories considered so far along
two axes, and briefly discuss the decision theories occupying the other
positions.

##### The Evidential/Causal/Functional Axis

A decision theory is

  * •

_evidential_ if it computes expected utility by conditioning:

$\mathbb{E}\left[U\mid\dots\right].$

  * •

_causal_ if it computes expected utility by intervening in a causal model:

$\mathbb{E}\left[U\mid do(\dots)\dots\right].$

  * •

_functional_ if it computes expected utility by intervening in a logical-
causal model:

$\mathbb{E}\left[U\mid do(\dots)\dots\right].$

##### The Updateless/Updateful Axis

A decision theory is

  * •

_updateful_ if it selects $D$ and conditions on $\bm{Obs}_{D}$:

$\mathbb{E}\left[U\mid\dots D\dots\textbf{\emph{Obs}}_{D}\right].$

  * •

_updateless_ if it selects $\tilde{D}$ (without conditioning on
$\bm{Obs_{D}}$):

$\mathbb{E}\left[U\mid\dots\tilde{D}\dots\right].$

Altogether there are six positions on these axes, each of which corresponds to
a distinct decision theory. Table 1 summarises their respective expected
utility calculations, and table 2 shows how each behaves in the decision
problems we’ve considered.

| Evidential | Causal | Functional
---|---|---|---
Updateful | $\mathbb{E}\left[U\mid D,\bm{Obs}_{D}\right]$ |  | $\mathbb{E}\left[U\mid do(D),\bm{Obs}_{D}\right]$
---
in a causal model.
| $\mathbb{E}\left[U\mid do(D),\bm{Obs}_{D}\right]$
---
in a logical-causal model.
Updateless | $\mathbb{E}\left[U\mid\tilde{D},\right]$ |  | $\mathbb{E}\left[U\mid do(\tilde{D})\right]$
---
in a causal model.
| $\mathbb{E}\left[U\mid do(\tilde{D})\right]$
---
in a logical-causal model.
Table 1: The expected utility calculations performed by each decision theory. | Newcomb | Transparent Newcomb | Twin PD
---|---|---|---
EDT | one-box | two-box | co-operate
CDT | two-box | two-box | defect
Updateful FDT | one-box | two-box | co-operate
Updateless EDT | one-box | one-box | co-operate
Updateless CDT | one-box | one-box | defect
FDT | one-box | one-box | co-operate
Table 2: The behaviour of the each decision theory in the example decision
problems.

The axes give us a natural naming scheme: "(updateful|updateless)
(evidential|causal|functional) decision theory". Unfortunately our existing
terminology might confuse things: "EDT" and "CDT" can be thought of as
shortenings of "updateful EDT" and "updateful CDT" respectively, while "FDT"
should be thought of as a shortening of "updateless FDT". We will abbreviate
"updateless EDT" as "UEDT" and "updateless CDT" as "UCDT", but to avoid
confusion we will not abbreviate "updateful FDT" any further.

We will briefly mention a few key points about the other decision theories in
the table.

Updateless CDT. Updateless CDT has been frequently discussed in the literature
under names such as policy-CDT [28]. It requires a causal model over a set of
variables that includes the agent’s decision rule. Such a model can be
obtained by following the experimental procedure for obtaining an unmechanised
model, but randomly assigning decision rules, rather than actions, to observed
agents.

Updateless EDT. Since it only requires an associational model over a set of
variables that includes the decision rule, UEDT shares none of FDT’s epistemic
issues, but only seems to diverge from its decision-making on problems which
philosophers consider questionably well-defined, such as the smoking lesion
problem [27]. For that reason UEDT is probably an adequate substitute for FDT,
both for the purposes of decision-making and for analysing the incentives of
ML systems.

Updateful FDT. To our knowledge, an updateful variant of FDT has not
previously appeared in the literature, although it bears some similarity to
[32]. It shares the epistemic problems of its updateless cousin. Intuitively
we can transform a model suitable for FDT into a model suitable for updateful
FDT by reversing the arrow from $\tilde{D}$ to $D$ – choosing your decision
should logically affect your decision rule. In contrast to the updateless
case, the updateful variants of FDT and EDT intuitively disagree on
uncontroversial problems such as XOR Blackmail [31, 21].

###  4.1 Comparison To Garrabrant’s Axes

Our axes are essentially a simplified version of the axes informally discussed
in [9], which make three distinctions: a decision theory can be evidential or
causal, updateful or updateless, and can model the world using a physical or
algorithmic agent ontology. The final axis corresponds to the question of
whether you imagine you are controlling a logical variable (the output of an
algorithm) or a physical one. In other words, whether you are choosing for
you, right here right now, or whether you are choosing for agents like you in
situations like this.

There are eight possible positions on these axes, but it is not clear that
each position corresponds to a distinct decision theory. In particular, the
physical vs algorithmic agent ontology axis appears irrelevant to
evidentialists: evidence about what you decide, right here right now, is
evidence about what agents like you decide in situations like this and vice
versa.666Wei Dai’s updateless decision theory [6], is intended to be
evidential and updateless with an algorithmic ontology, and seemingly
disagrees with UEDT on problems like the Smoking Lesion. Since UDT and FDT are
not formally defined it is hard to compare the two, but their intended notions
of dependence appear to coincide, and we prefer to think of it as logical-
causal rather than evidential.

We therefore prefer to collapse the third axis into the first and think of the
ontological question as being about two competing notions of causality. We do
not claim that our axes are more fundamentally meaningful than Garrabrant’s,
but they allow for a simplified presentation which removes some redundancy,
and a naming system which lines up well with existing terminology.

##  5 Well-Defining Transparent Newcomblike Problems

Decision problems that involve an agent being shown the result of a prediction
about their action before choosing it are sometimes considered to be
questionably well-defined, since it’s possible for an agent to choose in such
a way that falsifies the prediction. For example, in some versions of
Transparent Newcomb, the predictor is said to put the million in the box if
and only if the it predicts the agent will one-box [2, 10]. But if the agent
follows the decision rule "one-box if and only if the million is not present",
the prediction will always be wrong, and the premise that the predictor is
highly accurate is falsified.

The author of [25] gets around this by stipulating that agents are banned from
following such policies. An alternative approach [7, 33], and the one used in
this paper, is to have the predictor predict what the agent will choose upon
receiving a certain observation, rather than what the agent will do full stop.
In this version of Transparent Newcomb, the predictor fills the box if and
only if it predicts the agent will one-box upon seeing the box is full.

Using mechanism variables, we can adopt a general principle which clarifies
why this works and ensures we never run into the issue when defining decision
problems. We say that accurate predictions should be thought of as depending
causally, logically or evidentially on an agent’s decision rule rather than on
their decision. Predicting how an agent will respond to one specific
observation is a special case of making a prediction about their decision
rule. Intuitively this avoids the circular situation where the decision causes
the prediction and the prediction causes the decision. But note that the issue
is not fundamentally about causality: even the associational proposition that
in $99\%$ of cases where the agent one-boxes, the predictor fills the box, and
in $99\%$ of cases where the agent two-boxes, the box is left empty, is
falsified by the agent following the aforementioned policy.

This becomes especially clear when we try to represent the situation
graphically. The two conditional distributions cannot represented with a DAG –
we inevitably get a cycle, as in fig. 2(b). On the other hand, we can posit
any conditional distribution of the prediction given the decision rule,
alongside any conditional distribution of the decision given the prediction,
without getting a cycle.

##  6 Conclusions

In this paper, we have shown how mechanised causal graphs can be used to
characterise a range of different decision theories, and the axes along which
they differ. We hope this analysis will be a step towards a clearer
understanding of machine learning systems, and their interactions with other
agents and humans.

In particular, this paper may enable incentive analysis of agents with
different decision theories. Previous work has analysed the incentive
structures of agents using causal decision theory in different machine
learning setups [8]. But agents following different decision theories will
face different incentives. Mechanised causal graphs should allow us to combine
the two ideas and analyse the incentives structures in each case.

####  6.0.1 Acknowledgements

The authors would like to thank Caspar Oesterheld, Ryan Carey, Scott
Garrabrant, and Francis Rhys Ward for feedback and discussion. This work was
supported by UK Research and Innovation [grant number EP/S023356/1], in the
UKRI Centre for Doctoral Training in Safe and Trusted Artificial Intelligence.

## References

  * [1] Ahmed, A.: Evidence, Decision and Causality. Cambridge University Press, 1 edn. (Aug 2014). https://doi.org/10.1017/CBO9781139107990, https://www.cambridge.org/core/product/identifier/9781139107990/type/book
  * [2] Arntzenius, F.: No Regrets, or: Edith Piaf Revamps Decision Theory. Erkenntnis 68(2), 277–297 (Mar 2008). https://doi.org/10.1007/s10670-007-9084-8, http://link.springer.com/10.1007/s10670-007-9084-8
  * [3] Bell, J., Linsefors, L., Oesterheld, C., Skalse, J.: Reinforcement Learning in Newcomblike Environments. In: Advances in Neural Information Processing Systems. vol. 34, pp. 22146–22157. Curran Associates, Inc. (2021), https://proceedings.neurips.cc/paper/2021/hash/b9ed18a301c9f3d183938c451fa183df-Abstract.html
  * [4] Bostrom, N.: Superintelligence: Paths, Dangers, Strategies. Oxford University Press (2014), chapter 1
  * [5] Carlsmith, J.: Is power-seeking ai an existential risk? arXiv preprint arXiv:2206.13353 (2022)
  * [6] Dai, W.: Towards a new decision theory (2009), https://www.lesswrong.com/posts/de3xjFaACCAk6imzv/towards-a-new-decision-theory
  * [7] Drescher, G.L.: Good and Real: Demystifying Paradoxes from Physics to Ethics. MIT Press (2006), google-Books-ID: GXrLvcODPtoC
  * [8] Everitt, T., Carey, R., Langlois, E.D., Ortega, P.A., Legg, S.: Agent incentives: A causal perspective. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 35, pp. 11487–11495 (2021), issue: 13
  * [9] Garrabrant, S.: MIRI/OP Exchange About Decision Theory (2021), https://www.lesswrong.com/posts/FBbHEjkZzdupcjkna/miri-op-exchange-about-decision-theory-1
  * [10] Gauthier, D.: XII—In the Neighbourhood of the Newcomb-Predictor (Reflections on Rationality). Proceedings of the Aristotelian Society 89(1), 179–194 (Jun 1989). https://doi.org/10.1093/aristotelian/89.1.179, https://academic.oup.com/aristotelian/article/89/1/179/1800805
  * [11] Gauthier, D.: Assure and Threaten. Ethics 104(4), 690–721 (1994), http://www.jstor.org/stable/2382214
  * [12] Gibbard, A., Harper, W.L.: Counterfactuals and two kinds of expected utility. Springer (1981)
  * [13] Hammond, L., Fox, J., Everitt, T., Carey, R., Abate, A., Wooldridge, M.: Reasoning about Causality in Games. Artificial Intelligence 320, 103919 (Jul 2023). https://doi.org/10.1016/j.artint.2023.103919, http://arxiv.org/abs/2301.02324, arXiv:2301.02324 [cs]
  * [14] Howard, R.A., Matheson, J.E.: Influence diagrams. Decision Analysis 2(3), 127–143 (2005)
  * [15] Irving, G., Christiano, P., Amodei, D.: AI safety via debate (Oct 2018), http://arxiv.org/abs/1805.00899, arXiv:1805.00899 [cs, stat]
  * [16] Jeffrey, R.C.: The logic of decision. University of Chicago Press (1990)
  * [17] Joyce, J.M.: The foundations of causal decision theory. Cambridge University Press (1999)
  * [18] Kenton, Z., Kumar, R., Farquhar, S., Richens, J., MacDermott, M., Everitt, T.: Discovering Agents (Aug 2022), http://arxiv.org/abs/2208.08345, arXiv:2208.08345 [cs]
  * [19] Krueger, D., Maharaj, T., Leike, J.: Hidden incentives for auto-induced distributional shift. arXiv preprint arXiv:2009.09153 (2020)
  * [20] Leike, J., Krueger, D., Everitt, T., Martic, M., Maini, V., Legg, S.: Scalable agent alignment via reward modeling: a research direction (Nov 2018), http://arxiv.org/abs/1811.07871, arXiv:1811.07871 [cs, stat]
  * [21] Levinstein, B.A., Soares, N.: Cheating Death in Damascus. The Journal of Philosophy 117(5), 237–266 (Jan 2020)
  * [22] Lewis, D.: Prisoners’ dilemma is a newcomb problem. Philosophy & Public Affairs pp. 235–240 (1979)
  * [23] Lewis, D.: Causal decision theory. Australasian journal of philosophy 59(1), 5–30 (1981), publisher: Taylor & Francis
  * [24] Lewis, D.: Why Ain’cha Rich?’. Noûs pp. 377–380 (1981), publisher: JSTOR
  * [25] Meacham, C.J.G.: Binding and its consequences. Philosophical Studies 149(1), 49–71 (May 2010). https://doi.org/10.1007/s11098-010-9539-7, http://link.springer.com/10.1007/s11098-010-9539-7
  * [26] Nozick, R.: Newcomb’s Problem and Two Principles of Choice (1969)
  * [27] Oesterheld, C.: Understanding the Tickle Defense in Decision Theory (2018)
  * [28] Oesterheld, C., Conitzer, V.: Extracting Money from Causal Decision Theorists. The Philosophical Quarterly 71(4), pqaa086 (Sep 2021). https://doi.org/10.1093/pq/pqaa086, https://academic.oup.com/pq/article/doi/10.1093/pq/pqaa086/6118001
  * [29] Pearl, J.: Causality: models, reasoning, and inference. Cambridge University Press, Cambridge, U.K. ; New York (2000)
  * [30] Skyrms, B.: Causal decision theory. The Journal of Philosophy 79(11), 695–711 (1982)
  * [31] Soares, N., Fallenstein, B.: Toward Idealized Decision Theory (Jul 2015). https://doi.org/10.48550/arXiv.1507.01986, http://arxiv.org/abs/1507.01986, arXiv:1507.01986 [cs]
  * [32] Spohn, W.: Reversing 30 years of discussion: why causal decision theorists should one-box. Synthese 187(1), 95–122 (Jul 2012). https://doi.org/10.1007/s11229-011-0023-5, http://link.springer.com/10.1007/s11229-011-0023-5
  * [33] Yudkowsky, E., Soares, N.: Functional Decision Theory: A New Theory of Instrumental Rationality (May 2018). https://doi.org/10.48550/arXiv.1710.05060, http://arxiv.org/abs/1710.05060, arXiv:1710.05060 [cs]


See pages 1-last of aniket.pdf