\section{Introduction}

In this paper, we are interested in composition operators on the classical \textit{Hardy space} \mbox{$H^{2}$}. This Hilbert space is given by the set of analytic functions $\displaystyle f = \sum_{n=0}^{\infty}a_n z^n$ on the open unit disk \mbox{$\mathbb{D}$}\ such that $$\|f\|^{2}=\sum_{n=0}^{\infty}|a_n|^{2}<\infty.$$ A \textit{composition operator} $C_{\mbox{$\varphi$}}$ on \mbox{$H^{2}$}\ is given by $C_{\mbox{$\varphi$}}f = f \circ \mbox{$\varphi$}$. When \mbox{$\varphi$}\ is an analytic self-map of \mbox{$\mathbb{D}$}, \mbox{$C_{\varphi}$}\ is necessarily bounded. A \textit{Toeplitz operator} $T_\psi$ on $H^2$ is given by $T_\psi f = \psi f$ when $\psi \in \mbox{$H^{\infty}$}$, the space of bounded analytic functions on \mbox{$\mathbb{D}$}. We occasionally write $\mbox{$W_{\psi,\varphi}$} = T_\psi \mbox{$C_{\varphi}$}$ and call such an operator a \textit{weighted composition operator}. When \mbox{$\varphi$}\ is linear-fractional, \mbox{$C_{\varphi}\st$}\ has a simple form which involves composition operators and (adjoints of) Toeplitz operators, which we will put to use later in this paper.

The weak normality properties of composition operators and weighted composition operators on \mbox{$H^{2}$}\ have been of great interest. For example, work has been done on when \mbox{$C_{\varphi}$}\ and \mbox{$W_{\psi,\varphi}$}\ are normal \cite{Bourdon}, subnormal \cite{ck}, and cohyponormal \cite{coko}. In \cite{Hammond}, Garcia and Hammond posed the following problem: ``Characterize all complex symmetric composition operators \mbox{$C_{\varphi}$}\ on the classical Hardy space \mbox{$H^{2}$}.'' An operator $T$ on a Hilbert space $\mathcal{H}$ is complex symmetric if there exists a conjugate-linear, isometric involution $J$ on $\mathcal{H}$ so that $T = J T^* J$. We call such an operator $J$ a \textit{conjugation}. For applications and further information about complex symmetric operators, see \cite{Garcia1}, \cite{Garcia2} and \cite{GW}.

Due to a result of Garcia and Wogen \cite{GW}, any automorphism of order $2$ is complex symmetric. In \cite{Bourdon1}, Bourdon and Noor found that other automorphisms cannot be complex symmetric except possibly for the unsolved case when \mbox{$\varphi$}\ is an elliptic automorphism of order 3. In \cite{Noor1}, Noor found the exact conjugation needed for the involutive disk automorphisms to induce complex symmetric composition operators. Jung, Kim, Ko, and Lee were thought to have found a non-automorphic example in \cite{jkkl}, but were disproved by Noor in \cite{Noor2}. Noor stated that even a narrower question remains open: does there exist a non-constant and non-automorphic symbol \mbox{$\varphi$}\ for which \mbox{$C_{\varphi}$}\ is complex symmetric but not normal on \mbox{$H^{2}$}?

In this paper, we give examples of linear-fractional, non-automorphic maps \mbox{$\varphi$}\ that induce complex symmetric composition operators on $H^2$. In doing so, we answer positively the question of Noor, and we answer in part the question originally posed by Garcia and Hammond. We summarize our results with the following statement.

\begin{theorem}[Summary] Let $a, b \in \mbox{$\mathbb{D}$}$ with $|a|+|b(1-a)| \leq 1$.  Then for $\sigma(z) = az + b(1-a)$ and $\mbox{$\varphi$}(z) = az/(1-b(1-a)z)$, $C_{\sigma}$ and \mbox{$C_{\varphi}$}\ are complex symmetric on \mbox{$H^{2}$}. \end{theorem}

Our strategy will be to first prove the result for linear maps $\sigma$ with real fixed point $b$, and from there, we will extend to complex fixed points and then to functions of the form found in \mbox{$\varphi$}\ above. To that end, here we mention the Cowen adjoint formula for composition operators with linear-fractional symbol \cite[Theorem 9.2]{cm1}. The theorem is well-known but we restate it here due to its frequent use throughout the paper.

\begin{theorem}[Cowen adjoint formula]\label{adjoint} If $\sigma = \frac{az+b}{cz+d}$ is an analytic self-map of $\mbox{$\mathbb{D}$}$, then on $H^2$, $C_{\sigma}^{*} = T_g C_{\mbox{$\varphi$}} T_{h}^{*}$, where $g = 1/(-\overline{b}z+\overline{d}), h = cz + d$, and $\mbox{$\varphi$} = (\overline{a}z-\overline{c})/(-\overline{b}z+\overline{d})$, and $g, h$ necessarily belong to \mbox{$H^{\infty}$}. The function \mbox{$\varphi$}\ is called the \textit{Krein adjoint} of $\sigma$, while $g, h$ are called the \textit{Cowen auxillary functions} of $\sigma$.\end{theorem}

\section{Results}

Let $J$ be the operator defined by $(Jf)(z) = \overline{f(\overline{z})}$. Then $J$ is a conjugation. We will consider when $J$ commutes with other involutions, so that the involution in our construction is conjugate-linear.

\begin{theorem}\label{conjlinear} Suppose $J_1$ and $J_2$ are isometric involutions which commute, and exactly one of them is conjugate-linear. Then $J_1 J_2$ is a conjugation. \end{theorem}

\begin{proof} A product of isometries is an isometry. Since $J_1 J_2 J_1 J_2 = J_1 J_2 J_2 J_1 = J_1 J_1 = I$, $J_1 J_2$ is an involution. Without loss of generality, say $J_1$ is conjugate-linear. Then $J_1 J_2 (af + bg) = J_1 (a J_2f + bJ_2g) = \overline{a} J_1 J_2f + \overline{b}J_1 J_2g$. Therefore, $J_1 J_2$ is a conjugation. \end{proof}

\begin{theorem}\label{commute} Suppose that $\psi \in H^{\infty}$ and $\mbox{$\varphi$}: \mbox{$\mathbb{D}$} \rightarrow \mbox{$\mathbb{D}$}$ both map $(-1,1)$ into itself. Then $J$ commutes with $T_\psi$ and $C_{\mbox{$\varphi$}}$ and therefore also with \mbox{$W_{\psi,\varphi}$}. \end{theorem}
\begin{proof} $JC_{\mbox{$\varphi$}} f = J f(\mbox{$\varphi$}(z)) = \overline{f(\mbox{$\varphi$}(\overline{z}))}$ and $C_{\mbox{$\varphi$}} J f = C_{\mbox{$\varphi$}} \overline{f(\overline{z})} = \overline{f(\overline{\mbox{$\varphi$}(z)})}$. Now, for multiplication operators, $T_\psi J f = \psi(z) \overline{f(\overline{z})}$ and $J T_\psi f = \overline{\psi(\overline{z})}\overline{f(\overline{z})}$. In both situations, the expressions agree on $(-1,1)$. Since they are the same functions on a set with an accumulation point, they equal each other on the entire open disk. \end{proof}

\begin{theorem}\label{unitary} Suppose $b \in (-1,1), \tau = \frac{b- z}{1 - b z}$ and $\zeta = \sqrt{1-b^2} \frac{1}{1-b z}$. Then $T_\zeta C_\tau$ is unitary and self-adjoint; therefore, it is an isometric involution (but not conjugate-linear). Furthermore, $JT_{\zeta}C_{\tau}$ is a conjugation. \end{theorem}
\begin{proof} The fact that $T_{\zeta} C_{\tau}$ is unitary and self-adjoint can be found in both \cite{Bourdon} and \cite{wcomp} (the weight $\zeta$ is $K_{\tau(0)}$ divided by $\|K_{\tau(0)}\|$). By Theorem \ref{commute}, since $b$ is real, $J$ and $T_{\zeta}C_{\tau}$ commute. By Theorem \ref{conjlinear}, then, $JT_{\zeta} C_{\tau}$ is a conjugation. \end{proof}

\begin{theorem}\label{adjoint2} Let $a \in \mbox{$\mathbb{D}$}, b \in (-1,1)$ with $|a|+|b(1-a)| \leq 1$, and let $\sigma(z) = az + b(1-a)$. Furthermore, let $\mbox{$\varphi$}(z) = \overline{a}z/(1-b(1-\overline{a})z), \psi(z) = 1/(1-b(1-\overline{a})z)$. Then $C_{\sigma}^{*} = T_{\psi} C_{\mbox{$\varphi$}}$. \end{theorem}
\begin{proof} By the Cowen adjoint formula found in Theorem \ref{adjoint}, $C_{\sigma}^{*} = T_{\psi} C_{\phi}$.  \end{proof}

We are now ready to perform some calculations that show $C_\sigma$ is complex symmetric. We are purposefully letting $b$ belong to $(-1,1)$ so that our choice of involution works; however, we will later remove this requirement.

\begin{theorem}\label{mix} Let $a \in \mbox{$\mathbb{D}$}, b \in (-1,1)$ with $|a|+|b(1-a)| \leq 1$ and let $\sigma(z) = az + b(1-a)$. Furthermore, let $\mbox{$\varphi$}(z) = \overline{a}z/(1-b(1-\overline{a})z), \psi(z) = 1/(1-b(1-\overline{a})z)$. Then $C_\sigma = JT_\zeta C_\tau T_\psi C_{\mbox{$\varphi$}} JT_\zeta C_\tau$, where $\tau, \zeta$ are as in Theorem \ref{unitary}. \end{theorem}

\begin{proof} We show this by direct calculation:

\begin{align*}
JT_\zeta C_\tau T_\psi C_\varphi JT_\zeta C_\tau f(z) &=
JT_\zeta C_\tau  T_\psi C_\varphi \overline{\zeta(\overline{z})} \;\overline{f(\tau(\overline{z}))} \\
&= JT_\zeta C_\tau \psi(z) \overline{\zeta(\overline{\varphi(z)})} \;\overline{f(\tau(\overline{\varphi(z)}))} \\
&= J \zeta(z)  \psi(\tau(z)) \overline{\zeta(\overline{\varphi(\tau(z))})} \;\overline{f(\tau(\overline{\varphi(\tau(z))}))} \\
&=  \overline{\zeta(\overline{z})} \;  \overline{\psi(\tau(\overline{z}))}
\zeta(\overline{\varphi(\tau(\overline{z}))}) \;f(\tau(\overline{\varphi(\tau(\overline{z}))})).
\end{align*}

First, we check the compositional symbol. For clarity, we will work this out one composition at a time. Recall that we are assuming $b$ is real.

\begin{align*}
\tau(\overline{z}) &= \frac{b-\overline{z}}{1-b\overline{z}}
\end{align*}
\begin{align*}
\overline{\mbox{$\varphi$}(\tau(\overline{z}))} &= \overline{\mbox{$\varphi$}\left(\frac{b-\overline{z}}{1-b\overline{z}}\right)}  \\
&= \overline{\left( \frac{\overline{a}\frac{b-\overline{z}}{1-b\overline{z}}}{1-b(1-\overline{a})\frac{b-\overline{z}}{1-b\overline{z}}} \right) } \\
&= \frac{a\frac{b-z}{1-bz}}{1-b(1-a)\frac{b-z}{1-bz}} \\
&= \frac{a(b-z)}{1-bz-b(1-a)(b-z)} \\
&= \frac{ab-az}{1-b^2+ab^2-abz}
\end{align*}
\begin{align*}
\tau(\overline{\mbox{$\varphi$}(\tau(\overline{z}))}) &=  \frac{b-\frac{ab-az}{1-b^2+ab^2-abz}}{1-b\frac{ab-az}{1-b^2+ab^2-abz}}\\
 &= \frac{b-b^3+ab^3-ab^2z-ab+az}{1-b^2+ab^2-abz-ab^2+abz}\\
&= \frac{b-b^3+ab^3-ab^2z-ab+az}{1-b^2} \\
&= \frac{(1-b^2)(az+b(1-a))}{1-b^2} \\
&= az + b(1-a) = \sigma
\end{align*}

Now, we will evaluate each of the three multiplicative factors separately, and see that they simplify to $1$:
\begin{align*}
\overline{\zeta(\overline{z})} &= \frac{\sqrt{1-b^2}}{1-bz}
\end{align*}
\begin{align*}
\overline{\psi(\tau(\overline{z}))} &= \overline{\psi\left(\frac{b-\overline{z}}{1-b\overline{z}}\right)} \\
&= \overline{\left(\frac{1}{1-b(1-\overline{a})\frac{b-\overline{z}}{1-b\overline{z}}}\right)} \\
&= \overline{\left(\frac{1-b\overline{z}}{1-b\overline{z}-b(1-\overline{a})(b-\overline{z})}\right)} \\
&= \frac{1-bz}{1-bz-b(1-a)(b-z)} \\
&= \frac{1-bz}{1-bz-b(b-ab-z+az)} \\
&= \frac{1-bz}{1-bz-b^2+ab^2+bz-abz} \\
&= \frac{1-bz}{1-b^2+ab^2-abz}
\end{align*}

For the third multiplication factor, recall that we have already simplified $\overline{\mbox{$\varphi$}(\tau(\overline{z}))}$ above:
\begin{align*}
\zeta(\overline{\mbox{$\varphi$}(\tau(\overline{z}))}) &= \zeta\left(\frac{ab-az}{1-b^2+ab^2-abz}\right) \\
&= \sqrt{1-b^2} \frac{1}{1-b\frac{ab-az}{1-b^2+ab^2-abz}} \\
&= \sqrt{1-b^2}\frac{1-b^2+ab^2-abz}{1-b^2+ab^2-abz-ab^2+abz} \\
&= \sqrt{1-b^2}\frac{1-b^2+ab^2-abz}{1-b^2} \\
&= \frac{1-b^2+ab^2-abz}{\sqrt{1-b^2}}
\end{align*}

Putting these together, we have
\begin{align*}
\overline{\zeta(\overline{z})} \;  \overline{\psi(\tau(\overline{z}))}
\zeta(\overline{\varphi(\tau(\overline{z}))}) &= \\
\left(\frac{\sqrt{1-b^2}}{1-bz}\right) \left(\frac{1-bz}{1-b^2+ab^2-abz}\right)\left(\frac{1-b^2+ab^2-abz}{\sqrt{1-b^2}}\right) &= 1
\end{align*}
and we are finished.
\end{proof}

\begin{cor}\label{breal} Let $a \in \mbox{$\mathbb{D}$}, b \in (-1,1)$ with $|a|+|b(1-a)| \leq 1$ and let $\sigma(z) = az + b(1-a)$. Then $C_{\sigma}$ is complex symmetric. \end{cor}
\begin{proof} By Theorem \ref{unitary}, $J T_\zeta C_\tau $ is a conjugation. By Theorem \ref{adjoint2}, $C_{\sigma}^{*} = T_\psi \mbox{$C_{\varphi}$}$. By Theorem \ref{mix}, $C_\sigma = J T_\zeta C_\tau T_\psi C_{\mbox{$\varphi$}} J T_\zeta C_\tau  = J T_\zeta C_\tau C_{\sigma}^{*} J T_\zeta C_\tau$. \end{proof}

We now use unitarily equivalence to allow $b$ to be complex.

\begin{cor}\label{bdisk} Let $a, b \in \mbox{$\mathbb{D}$}$ with $|a|+|b(1-a)| \leq 1$ and let $\sigma(z) = az + b(1-a)$.Then $C_{\sigma}$ is complex symmetric.\end{cor}
\begin{proof} By Corollary \ref{breal} , $C_{\sigma_{1}}$ is complex symmetric, where $\sigma_{1}(z) = az + b_1(1-a)$ with $a \in \mbox{$\mathbb{D}$}, b_1 \in (-1,1)$ and $|a|+|b_{1}(1-a)| \leq 1$. Let $U_{\theta}$ be defined by $U_{\theta} f = C_{e^{i\theta}z} f = f(e^{i\theta}z)$ for some angle $\theta$ and note that $U_{\theta}$ is a unitary operator with inverse $U_{-\theta}$. Then $U_{-\theta} C_{\sigma_{1}} U_{\theta}$ is unitarily equivalent to $ C_{\sigma}$ where $\sigma = az + e^{i\theta}b_{1}(1-a)$, so it is also complex symmetric. Letting $b = b_{1}e^{i\theta}$, since this is true for any angle $\theta$, the conclusion follows. \end{proof}

The work above shows that if $\sigma$ is a linear symbol with interior fixed point, $C_{\sigma}$ is complex symmetric on $H^2$. However, as we will see below, that work also shows that $C_{\mbox{$\varphi$}}$ is complex symmetric, where \mbox{$\varphi$}\ is the Krein adjoint of $\sigma$.

\begin{cor}\label{phi} Let $a, b \in \mbox{$\mathbb{D}$}$ with $|a|+|b(1-a)| \leq 1$. Let $\mbox{$\varphi$}(z) = az/(1-b(1-a)z), \psi(z) = 1/(1-b(1-a)z)$. Then \mbox{$W_{\psi,\varphi}$}\ is complex symmetric.\end{cor}
\begin{proof} $\mbox{$W_{\psi,\varphi}^{\textstyle\ast}$} = C_{\sigma}$, where $\sigma(z) = \overline{a}z + \overline{b}(1-\overline{a})$, is complex symmetric by Corollary \ref{bdisk}. Since the adjoint of \mbox{$W_{\psi,\varphi}$}\ is complex symmetric, \mbox{$W_{\psi,\varphi}$}\ is also complex symmetric. \end{proof}

\begin{cor} Let $a, b \in \mbox{$\mathbb{D}$}$ with $|a|+|b(1-a)| \leq 1$ and let $\mbox{$\varphi$}(z) = az/(1-b(1-a)z)$. Then $C_{\mbox{$\varphi$}}$ is complex symmetric. \end{cor}
\begin{proof} First, recall that $zH^2$ is a reducing subspace for $C_{\mbox{$\varphi$}}$. Let $\psi(z) = 1/(1-b(1-a)z)$. By Corollary \ref{phi}, \mbox{$W_{\psi,\varphi}$}\ is complex symmetric and therefore so is $a\mbox{$W_{\psi,\varphi}$}$. By the unitary operator $T_{z}: \mbox{$H^{2}$} \rightarrow z\mbox{$H^{2}$}$, $a\mbox{$W_{\psi,\varphi}$}$ is unitarily equivalent to $\mbox{$C_{\varphi}$}|_{z\mbox{$H^{2}$}}$. Therefore, $\mbox{$C_{\varphi}$}|_{z\mbox{$H^{2}$}}$ is complex symmetric by some conjugation $J_2: zH^2 \rightarrow zH^2$. On $H^2$, $\mbox{$C_{\varphi}$} = I \oplus \mbox{$C_{\varphi}$}|_{z\mbox{$H^{2}$}}$ and $I$ is trivially complex symmetric by any conjugation, say $J_1$, on the constants. Then $\mbox{$C_{\varphi}$}$ is complex symmetric on $H^2$ by the conjugation $J_1 \oplus J_2$.   \end{proof}

\section{Further Questions}

\begin{enumerate}
\item We have shown several operators $C_{\mbox{$\varphi$}}$ to be complex symmetric when $\mbox{$\varphi$}$ is linear-fractional with interior fixed point and no fixed point on the boundary. However, there are other examples, e.g. $\mbox{$\varphi$} = 1/(3-z)$. Are these operators also complex symmetric?
\item Are there composition operators on $H^2$ that are complex symmetric, yet whose symbols are not linear fractional?
\end{enumerate}

\section*{References}


\section{Introduction}
Since the invention of electric lighting in the 19th century, artificial light at night (ALAN) has had a major impact on both human society and the environment. ALAN propagates into nocturnal landscapes and has hence been recognized as one type of environmental pollution, light pollution (LP). The fact that ALAN can be seen from space should be well known since its observation during the first crewed US American orbital flight more than 50 years ago \cite{Biggs:2012}. However, the public is much less aware of LP than of other types of environmental pollution. Although ALAN has globally increased by 3-6$\%$ per year \cite{Hoelker:2010_b, book:Narisada} over the last decades, the effects on the environment and on human well-being are still poorly understood \cite{Hoelker:2010_b}.

Early work on LP concentrated mostly on the decrease of contrast of the night sky and the resulting lack of the ability to observe stars during the night (see \cite{book:Narisada} for an overview). Later it was found that LP has strong effects on flora, fauna \cite{book:rich_longcore} and human well-being \cite{Stevens:2015}. Recently, concerns were raised that LP might have an impact on whole ecosystems and biodiversity, and several investigations in that context have been performed \cite{Hoelker:2010_a, Gaston:2015_ptb}. While most work has focused on terrestrial animals, some recent work investigated the influence of ALAN on aquatic life \cite{Perkin:2011}. This includes studies on the diel vertical migration of zooplankton in lakes \cite{Moore:2000}, the alteration of microbial communities \cite{Hoelker:2015} and photophysiology of freshwater cyanobacteria \cite{Poulin:2014}. Since ALAN is increasingly recognized as an environmental stressor, several studies to quantify the amount of ALAN leaving the Earth's surface have been performed. A combination of satellite images and theoretical modeling resulted in the World Atlas of night sky brightness \cite{Cinzano:2001_wa}.

Artificial skyglow is one type of LP that is mainly observed in densely populated areas where ALAN is scattered by atmospheric molecules or aerosols and returned to Earth \cite{Aube:2015}. Skyglow can be drastically amplified by several orders of magnitude due to the presence of clouds as shown by empirical \cite{Kyba:2011_sqm, Puschnig:2014_Vienna} and theoretical \cite{Kocifaj:2014_cloud_theory} work. This amplification depends not only on the amount of upwelling radiation caused by ALAN but also on its spectral distribution, the topography of the landscape, the vegetation cover and especially the weather condition \cite{Kyba:2012_mssqm}.

Despite its possible impact on ecosystems \cite{Kyba:2013_LE}, it is not straightforward to estimate the amount of skyglow at a specific location from satellite images alone, as these are only usable in clear conditions. Furthermore, the seminal World Atlas of night sky brightness \cite{Cinzano:2001_wa} is based on almost 20 year old satellite data; and unfortunately no such updated global data base is available, yet. ALAN however, is rapidly changing especially very recently due to the availability of cheap and efficient solid state lighting. As a result, prediction of the current exposure to LP at a field site, particularly for overcast conditions, is difficult.

This lack of reliable data, together with the development of cheap handheld sky brightness meters \cite{Cinzano_sqm:2005} and novel measurement schemes based on imaging technology \cite{Duriscoe:2007, Kollath:2010} have triggered several local \cite{Biggs:2012, Pun:2014} and global \cite{Kyba:2015_isqm} ground-based studies of the night sky brightness (NSB). In this work, we measured the NSB at Lake Stechlin over a period of four months in summer and early autumn to evaluate the amount of artificial skyglow at an experimental field site. We employed continuous four-month measurements with a sky quality meter (SQM) as well as imaging with a digital single lens reflex (DSLR) camera. The motivation of our work is to characterize skyglow at a field site where an experiment is planned to assess the impact of LP on a lake ecosystem. For this experiment it has to be verified that the field site is located in one of the darkest regions of Germany \cite{Cinzano:2001_wa}, which makes it possible to use unmanipulated experimental units as controls.

\section{The field site}
Measurements were made at the LakeLab (Fig. \ref{lakelab}; www.lake-lab.de), which is an experimental mesocosm facility installed in Lake Stechlin, a clearwater lake with a surface area of 4.25 km² and a maximum depth of 69.5 m. The lake is situated about 70 km north of the city of Berlin in a forested area. The nearest village is Neuglobsow (53$^{\circ}$8$^{\prime}$48$^{\prime\prime}$N, 13$^{\circ}$2$^{\prime}$49$^{\prime\prime}$E) with less than 300 inhabitants. The lake is part of a nature reserve belonging to one of the darkest areas of Germany (according to \cite{Cinzano:2001_wa}).

The experimental facility is situated in the south-western bay of the lake (53$^{\circ}$8$^{\prime}$36.5$^{\prime\prime}$N, 13$^{\circ}$1$^{\prime}$42.7$^{\prime\prime}$E). The floating construction consists of one large enclosure  with 30 m diameter and 24 smaller enclosures that are 9 m in diameter (Fig. \ref{lakelab}). Each enclosure (mesocosm) is isolated from the lake by plastic curtains that reach down into the lake sediment at a depth of about 20 m. The entire structure is anchored to the lake bottom to prevent drift.

The purpose of the LakeLab is to assess impacts of global environmental change on ecological processes and biodiversity in lake ecosystems. The relatively large size of the experimental units (1270 m$^3$ each) and their large number (24) provide a rare opportunity to test for effects under controlled and yet realistic conditions by capturing most of the natural complexity of lake ecosystems, and at the same time ensuring adequate replication when only one or two factors are experimentally varied while all others are kept constant. Multiple environmental stressors can be tested including LP.  Thus, experiments in the LakeLab combine the advantages of field and laboratory experimental research.

\begin{figure}
\centering
(a) \includegraphics[width=13cm]{LakeLab.JPG}
(b) \includegraphics[width=13cm]{meso.JPG}
\caption{(a) Distant and (b) close-up view of the experimental facility (LakeLab) in Lake Stechlin, Germany, where night sky brightness measurements were conducted. (Pictures by A. Jechow).}
\label{lakelab}
\end{figure}

\section{Methods}
 \subsection{The Sky Quality Meter (SQM)}
Continuous night sky luminance measurements were performed between June and September 2015 with an SQM manufactured by Unihedron (Grimsby, Ontario, Canada). The SQM version with an integrated lens (SQM-Lxx) measures luminance for a patch of the sky with an opening angle of 20$^{\circ}$ \cite{Cinzano_sqm-l:2007}. The combination of a silicon photo diode (TSL237S) and a band-pass filter (HOYA CM-500) results in a spectral response roughly similar to that of the scotopic human vision \cite{Cinzano_sqm:2005}. The SQM provides the luminance in units of magnitude per square arc second (mag$_{SQM}$/arcsec$^2$), which is a logarithmic scale that decreases with increasing brightness. Because the spectral sensitivity does not match the Johnson V band, we followed the convention of Biggs and others \cite{Biggs:2012} to use mag$_{SQM}$/arcsec$^2$ (see also \cite{Cinzano_sqm:2005}). A value of 21.6 mag$_{SQM}$/arcsec$^2$, corresponds to the brightness (or darkness) of a typical historic moonless clear night with only natural contributions to the NSB \cite{Kollath:2010, Kyba:2015_isqm}. A decrease of 5 mag$_{SQM}$/arcsec$^2$ equals an increase in luminance by a factor of 100. This scale used in astronomy can be converted to so-called natural sky units (NSU) to provide a more intuitive comparison between different NSBs \cite{Kyba:2015_isqm}. One NSU indicates how much brighter or darker a sky is compared to a typical historic clear night sky (21.6 mag$_{SQM}$/arcsec$^2$; NSU=1). It is defined as

\begin{equation}
NSU = 10^{0.4(21.6-x)},
\end{equation}
where x is the observed value in mag$_{SQM}$/arcsec$^2$.

SQMs are widely used, due to their low cost even in large-scale projects involving citizen scientists \cite{Kyba:2013_GaN}. A recent study collected and compared global data from SQMs to evaluate the variations in artificial skyglow at multiple locations experiencing different light pollution situations \cite{Kyba:2015_isqm}. During such long term measurements, the SQM proved to be robust and reliable. Due to an internal sensor and correction algorithm, it is almost insensitive to temperature variations in the range of -25$^{\circ}$C to 70$^{\circ}$C \cite{Schnitt:2013}.

\begin{figure}
\centering
\includegraphics[width=6cm]{SQM.png}
\caption{Sky quality meter (SQM) mounted in a weather-proof housing on the floating platform at the experimental facility (LakeLab) in Lake Stechlin, Germany. (Picture by A. Jechow).}
\label{SQM}
\end{figure}
We used a battery-powered version of the SQM with an integrated data logger (SQM-LU-DL). The SQM was set to measure the sky luminance every 10 minutes. The device was integrated in a weather-proof housing (Unihedron) and was permanently mounted (Fig. \ref{SQM}) on the experimental facility in Lake Stechlin. Care was taken that the SQM pointed straight up to the sky.

\subsection{Fish-eye lens sky imaging with a digital single-lens reflex camera}
Modern DSLR cameras with the ability to save images in an unaltered raw format have recently been used to evaluate NSB \cite{Kollath:2010, Kocifaj:2015}. Calibration is necessary to translate the brightness values of the camera to physical luminance values. It is then possible to process false color images that show spatially resolved NSB in units of mag/arcsec$^2$ or NSU, respectively. If carefully calibrated, it is possible to reach 10 percent precision with such an imaging measurement system \cite{Kollath:2010}.

We used a Canon EOS D6 camera and a Sigma EX DG circular fish-eye lens. The lens has a focal length of f=8 mm and an aperture of F3.5. The camera features a 20.2 Megapixel full frame (36 mm x 24 mm) CMOS sensor and an integrated GPS tracker. The camera was cross-calibrated with a thoroughly calibrated camera during an earlier measurement campaign \cite{Kyba:2015_lonne}. Pictures were obtained in full format (5472 pixel x 3648 pixel) with ISO1600 setting and an exposure time of 30 seconds and saved in raw format. As is standard in astrophotography, dark frames were taken with the same settings and subtracted from the data images. This reduces noise and provides the appropriate baseline. The images were processed using a homebuilt software and then saved in JPEG format with a quadratic frame of 900 pixel x 900 pixel.

Usually DSLR cameras are pointed to the zenith to obtain so called ``all-sky images'' \cite{Kollath:2010, Kocifaj:2015}. However, aberrations and distortion effects are most prominent at the edges of the images. As we are mostly interested in the brightness at the horizon we pointed the camera not only to the zenith but also approximately towards the horizon to avoid such negative effects.

\subsection{Weather conditions}
To estimate the cloud coverage at the field site, weather conditions were obtained from the OGIMET free data base (www.ogimet.com). For the LakeLab at Lake Stechlin, data from the closest weather station (Neuruppin ID 10270) at about 20 km distance was used.

\section{Results}
 \subsection{Continuous zenith sky brightness measurements}
Figure \ref{full} shows the variation in sky luminance in NSU on a logarithmic scale as a function of time from the beginning of June until the end of September. NSU values were recorded automatically during twilight and the night, while the SQM saturates in bright conditions and therefore no data was recorded during daytime.

The diel change in sky brightness from nighttime to daytime is clearly visible in the plot. No filtering or averaging was used in the plot and the full data is shown. Each spike represents the lowest value obtained each night, while the gaps between the spikes are daylight periods.

It is also clear from Fig. \ref{full} that the moon phases change the NSB from bright periods at full moon (e.g. around 1 July 2015) to dark periods at new moon (e.g. around 15 July 2015). Lowest NSB values ranged from 0.32 NSU (22.84 mag$_{SQM}/$arcsec$^2$ on 26 July 2015 in cloudy conditions) to 10.4 NSU (1 July 2015 at full moon). The reading of about 10 NSU around full moon does not mean that moonlight is only 10 times brighter than starlight. Rather, the moon is a bright point source outside of the measured patch of the sky. The increased brightness readings are due to leaking of a small fraction of moonlight into the SQM optics or the secondary zenith sky brightening due to lunar twilight. For this reason, SQM measurements are usually analyzed only in the absence of moonlight.

The minimum NSB depends not only on the moon phase, but also on the length of the day, which changes due to the axial tilt of the earth. For example astronomical twilight (defined as the period when the sun is between 12 $^{\circ}$ and 18 $^{\circ}$ below the horizon) does not end at the site between mid-May and end of July. This can be resolved in the data set when paying attention to the lowest NSB from the start of the observation until the end of July. The moonlight oscillation overlapped with a seasonal solar oscillation and the nights become brighter around solstice. In Fig. \ref{nightlength} two clear nights are shown around solstice (red) and later in September (black). The NSB at summer solstice does not reach below 3 NSU, and only a short period of about 3 hours below 10 NSU each night. In contrast, the clear night in September maintains values near 1 NSU from 21:00 to 05:00 H.
\begin{figure}[!t]
\centering
\includegraphics[width=10cm]{full.png}
\caption{Night sky brightness measurements performed with the Unihedron sky quality meter (SQM) from June 2015 to September 2015 with a temporal resolution of 10 minutes. The luminance is given in natural sky units (NSU) on a logarithmic scale. The red horizontal line represents the brightness of a historical clear night at 1 NSU (21.6 mag$_{SQM}/$arcsec$^2$). The influence of moon phases and weather conditions can be observed.}
\label{full}
\end{figure}

\begin{figure}[!t]
\centering
\includegraphics[width=10cm]{length.png}
\caption{Zenith night sky luminance at LakeLab measured with an SQM on a clear night around summer solstice (red line) and a clear night in September (black line). In fall, the night lasts about 7 hours at values around 1 NSU, while at summer solstice the night is not fully present as zenith brightness does not reach below 3 NSU.}
\label{nightlength}
\end{figure}

 \subsection{Influence of clouds on zenith sky brightness}
Night sky luminance can vary dramatically with the presence of clouds. In an environment without LP, clouds will darken the sky. However, in areas with LP clouds can make the sky considerably brighter: maximum values up to 2200 NSU have been reported \cite{Kyba:2015_isqm}. This effect is due to the broad and relatively high reflectance of clouds and is discussed in more detail in \cite{Lamphar:2015}.

In our measurements the influence of clouds was clearly visible. Figure \ref{clear_clouds} shows two consecutive nights without (blue line: 18 July 2015 - moonset at 22:06 H) and with (red line: 19 July 2015 - moonset at 22:31 H) the presence of broken clouds as well as a third night which was completely overcast (black line: 25 July 2015 - moonset at 00:28). The consecutive nights have similar durations of about 4 hours with values below 10 NSU and a period of more than 2 hours with NSU values around 1. The influence of the lunar twilight for these two nights is hardly perceptible.

\begin{figure}[!t]
\centering
\includegraphics[width=10cm]{clearbrokenovercast.png}
\caption{Zenith night sky luminance at LakeLab measured with an SQM on a clear night (blue line), a night with broken clouds (red line) and an overcast night (black line). The presence of clouds make the sky darker.}
\label{clear_clouds}
\end{figure}

While the luminance values of the clear night smoothly approached the minimum of about 1.3 NSU, oscillations and jumps from darker to brighter sky luminance are apparent during the following night when broken clouds were present. This variation can be observed between 22:00 H and midnight but the most dramatic change occurred at around 02:00 H. Here the sky luminance dropped two times below values of 1 NSU before returning to the previous value of about 1.1-1.2 NSU. For the night with broken clouds (blue lin in plot) a value as low as 0.43 NSU (22.5 mag$_{SQM}$/arcsec$^2$) was observed, and for the completely overcast night (red line in plot) a value as low as 0.32 NSU (22.84 mag$_{SQM}$/arcsec$^2$) was observed. The slow decrease in brightness at the beginning of that night can presumably be attributed to moonlight and the following lunar twilight.

The data collected at the LakeLab indicates that clouds darken the night sky at this location, whereas the opposite would be observed with a significant amount of artificial skyglow caused by ALAN. This is illustrated by comparing the SQM data acquired at the LakeLab with that from other sites.
\begin{figure}[!b]
\centering
\includegraphics[width=6.75cm]{comp_clear.png}
\includegraphics[width=6.75cm]{comp_clouds.png}
\caption{Zenith night sky luminance on a clear night (a) and an overcast night (b) measured with SQMs at four different locations. In the presence of clouds a decrease in brightness is observed at the two rural locations Lochow (black line) and LakeLab (green line), while a drastic increase in brightness is observed at the two suburban locations IGB headquarter at Lake M{\"u}ggelsee (blue line) and Schulzendorf (red line). As a result, the NSB at the suburban sites is up to 50 times higher than at the rural sites, although the measurements were made in summer close to the solstice.}
\label{comp}
\end{figure}
Figure \ref{comp} shows the SQM data collected at four different locations for (a) a clear night (16 June2015) and (b) an overcast night (17 June 2015). One SQM was located at another experimental IGB field site \cite{Holzhauer2015}, which is situated in the International Dark-Sky Reserve Westhavelland about 70 km West of Berlin (52$^{\circ}$42$^{\prime}$N 12$^{\circ}$27$^{\prime}$E). The data from this SQM is labeled Lochow and shown by a black line in the plot. Two other SQMs are situated in a suburban setting at the outskirts of Berlin, one at the IGB headquarter at M{\"u}ggelsee (52$^{\circ}$26$^{\prime}$55$^{\prime\prime}$N 13$^{\circ}$38$^{\prime}$52$^{\prime\prime}$E) in the suburbs of Berlin and another one in Schulzendorf (52$^{\circ}$21$^{\prime}$36$^{\prime\prime}$N 13$^{\circ}$35$^{\prime}$24$^{\prime\prime}$E), a municipality close to the southeastern outskirts of Berlin (about 8,000 inhabitants).

The plots show NSB in a linear scale for two consecutive nights without moonlight. During the clear night (Fig. \ref{comp} a) the difference between the four locations is small but perceptible with values ranging from 1.1 NSU at Lochow (black) to 5 NSU at IGB headquarter at M{\"u}ggelsee (blue). However, these differences increase dramatically in the presence of clouds (Fig. \ref{comp} b). The two rural sites got darker (LakeLab and Lochow), whereas the two suburban sites (Schulzendorf and M{\"u}ggelsee) got much brighter than during the clear night. At Lochow, the night got as dark as 0.7 NSU while at Lake M{\"u}ggelsee at the outskirts of Berlin the LP was amplified by the clouds reaching values of more than 30 NSU before midnight and above 20 NSU after midnight. This decrease in brightness is characteristic as lamps are typically switched off as the night progresses \cite{Kyba:2011_sqm, Puschnig:2014_Vienna}. Both nights were very close to the summer solstice and the night in the Berlin area was very short (no astronomical twilight and nautical twilight from 23:45 H to about 2:30 H). Nevertheless, the zenith NSB was up to 50 times higher at the suburban than at the rural sites. For comparison, the NSB in the center of Berlin (Hackescher Markt) typically reaches values between 20 and 40 NSU on clear nights and between 250 and 750 NSU under overcast conditions \cite{Kyba:2015_isqm}.

\subsection{Fish-eye lens sky images}
Fish-eye lens sky images were taken during the night from 23 September 2015 to 24 September 2015 under clear weather conditions. On these dates, the moon rose at about 16:20 H local time and set at about 02:00 H at night. Astronomical twilight began at about 05:00 H in the morning on 24 September 2015. Therefore, a suitable time window for the NSB measurements was between 03:00 H and 05:00 H. NSB values obtained from the continuous four-month measurement with the SQM were in the range of 1.0-1.1 NSU between 02:00 H and 05:00 H, which was confirmed with a handheld SQM while taking the fish-eye lens images.

The pictures were taken at Lake Stechlin close to the position of the permanent SQM but on a large pontoon (53$^{\circ}$8$^{\prime}$35.2$^{\prime\prime}$N, 13$^{\circ}$1$^{\prime}$41.0$^{\prime\prime}$E) to avoid blurring of the pictures by rocking of the the floating LakeLab construction. The camera was pointed to the zenith to obtain an all-sky image (Fig. \ref{allsky1} a). In addition, the camera was pointed approximately towards the horizon in different azimuth directions to obtain undistorted images from distant light sources near the horizon (Fig. \ref{allsky1} b, Fig. \ref{allsky2}). Several dark frames were taken under the same measurement conditions by leaving the lens carefully covered so that no light could penetrate the optics and reach the detector. Weather conditions allowed data taking at a clear sky and very low amount of wind. No swaying of the floating construction was noted. The Milky Way was overhead and brightly visible by the naked eye.

\begin{figure}
(a) \includegraphics[width=5.4cm]{0309.png}
(b) \includegraphics[width=5.4cm]{0303.png}

(c) \includegraphics[width=5.4cm]{log_0309.png}
(d) \includegraphics[width=5.4cm]{log_0303.png}
\includegraphics[width=1.2cm]{colors_log.png}

(e) \includegraphics[width=5.4cm]{lin_0309.png}
(f) \includegraphics[width=5.4cm]{lin_0303.png}
\includegraphics[width=1.2cm]{colors_lin.png}
\caption{All-sky photo of the night sky at Lake Stechlin taken by pointing the camera to the zenith (a), horizontal fish-eye lens photo taken by pointing the camera to the southern horizon (b), and false-color images of these photographs (c-f) showing night sky brightness in natural sky units (NSU).}
\label{allsky1}
\end{figure}

\begin{figure}
(a) \includegraphics[width=5.4cm]{0296.png}
(b) \includegraphics[width=5.4cm]{0298.png}

(c) \includegraphics[width=5.4cm]{log_0296.png}
(d) \includegraphics[width=5.4cm]{log_0298.png}
\includegraphics[width=1.2cm]{colors_log.png}

(e) \includegraphics[width=5.4cm]{lin_0296.png}
(f) \includegraphics[width=5.4cm]{lin_0298.png}
\includegraphics[width=1.2cm]{colors_lin.png}
\caption{Horizontal fish-eye lens photos of the night sky (a, b) and false color images of these photos (c-f) of the night sky brightness in natural sky units (NSU) showing the view from the LakeLab towards the north (a, c, e) and to the west (b, d, f).}
\label{allsky2}
\end{figure}
The original photographs and the calculated false-color images showing the NSB luminance are depicted in Fig. \ref{allsky1} and \ref{allsky2}. In each figure, the upper rows (a and b) show the actual photographs in true color but with enhanced contrast. The middle rows (c and d) show false-color images over the full dynamic range from 0.1 to 20 NSU on a logarithmic scale. The lower rows (e and f) show false-color images on a fine linear scale between 0.1 NSU and 3 NSU

The left column of Fig. \ref{allsky1} (a, c and e) shows the zenith night sky at 04:57 H. The upper left corner of the pictures points approximately to the north and the lower left corner points eastwards. The structure of the Milky Way is clearly visible in Fig. \ref{allsky1} (a), and Figs. \ref{allsky1} (c) and (e) clearly show that the NSB at the zenith is dominated by the Milky Way. A distinct increase in NSB is apparent on the horizon.

In the right column of Fig. \ref{allsky1} (b, d and f) the horizontal view from the LakeLab towards the south at 4:44 H is shown. In the upper picture (Fig. \ref{allsky1} b), the lit buildings of the IGB on the shore of Lake Stechlin can be seen as well as a glow in the distance. The false color images reveal a bright area in the center of the picture with an NSB of about 4 NSU. This is likely due to the town of Gransee (about 6,000 inhabitants, 53$^{\circ}$0$^{\prime}$N 13$^{\circ}$9$^{\prime}$E, distance ca. 18 km). Furthermore, a larger distant circular region with NSB values of 2 NSU is presumably due to Berlin at a distance of about 70 km. The bright region on the left side is the town of F{\"u}rstenberg (about 6,000 inhabitants, 53$^{\circ}$11$^{\prime}$N 13$^{\circ}$9$^{\prime}$E, distance ca. 9 km).

The left column of Fig. \ref{allsky2} (a, c and e) shows the horizontal view from the LakeLab towards the east at 04:31 H. Two bright orange areas are apparent on the horizon (Fig. \ref{allsky2} a). The area on the left is the town of Neustrelitz (about 20,000 inhabitants, 53$^{\circ}$22$^{\prime}$N 13$^{\circ}$4$^{\prime}$E, distance ca. 25 km) and the area on the right is the town of F{\"u}rstenberg. The area around Neustrelitz had a NSB of up to 7 NSU while the NSB reached about 3 NSU in the direction of F{\"u}rstenberg. The false-color images (Fig. \ref{allsky2} c,e) reveal a less pronounced bright area on the horizon left of Neustrelitz, which is presumably due to the town of Wesenberg (about 3,000 inhabitants, 53$^{\circ}$16$^{\prime}$N 12$^{\circ}$58$^{\prime}$E, distance ca. 15 km) as well as a small bright strip east of Neustrelitz, which we assume to be the town of Neubrandenburg (about 66,000 inhabitants, 53$^{\circ}$33$^{\prime}$N 13$^{\circ}$16$^{\prime}$E, distance ca. 45 km). The sharp bright spot on the right hand side is Sirius.

In the right column of Fig. \ref{allsky2} (b, d and f) the horizontal view from the LakeLab towards the west at 4:35 H is shown. The red spot in the center of the upper picture (Fig. \ref{allsky2} b) is the tower of the former nuclear power plant of Rheinsberg. The distant orange glow behind it is presumably the town of Wittstock (about 15,000 inhabitants, 53$^{\circ}$10$^{\prime}$N 12$^{\circ}$30$^{\prime}$E, distance ca. 35 km) with a NSB of 4 NSU. The bright spot on the left side is the town of Rheinsberg (about 8,000 inhabitants, 53$^{\circ}$6$^{\prime}$N 12$^{\circ}$53$^{\prime}$E, distance ca. 10 km).

Surprisingly, the closest village, Neuglobsow, is not clearly resolvable in these pictures, which may be attributed to the dense forest vegetation surrounding the village and the absence of industrial areas, shopping centers or similar infrastructure. Furthermore, part-night street lighting is applied in Neuglobsow: only half of the luminaires are lit during the night.

From our data, we evaluate the influence of skyglow originating from Berlin to be low compared to nearby settlements. This is in agreement with a long term NSB study performed in Potsdam (160,000 inhabitants) \cite{Puschnig:2014_Potsdam}, located at 28 km distance from Berlin and where the LP was already reduced compared to the metropolitan center.

\section{Summary and conclusion}
We investigated the NSB at a research field site situated on a lake 70 north of the city of Berlin. Continuous monitoring between the beginning of June and the end of September 2015 was performed using a small photometer (an SQM) collecting data every 10 minutes. In addition, fish-eye lens imaging was performed on a moonless clear night to spatially resolve and quantify distant skyglow caused by LP.

With the SQM, zenith NSBs as low as 0.32 NSU (22.84 mag$_{SQM}/$arcsec$^2$)  were found under overcast conditions. On clear moonless nights, values of about 1 NSU (21.5-21.7 mag$_{SQM}/$arcsec$^2$) were obtained. The darkening in the presence of clouds indicates that the zenith NSB was not strongly influenced by LP. In areas with LP, a brightening would be observed as shown by simultaneous suburban SQM measurements. Furthermore, the circa-lunar NSB variation was clearly perceptible, which is usually blurred or even wiped out when monitoring zenith NSB in the presence of strong LP.

All-sky and horizontal fish-eye lens imaging revealed several nearby and distant towns as sources of LP measurable on Lake Stechlin. However, the NSB values were below 5 NSU and the brightness was confined to areas close to the horizon.

Overall, the data indicates that the influence of skyglow caused by LP is minor at Lake Stechlin during summer and fall, suggesting that this field site is suitable to study the influence of skyglow on lake ecosystems.

\section{Acknowledgements}
This work was supported by the ILES project funded by the Leibniz Association, Germany (SAW-2015-IGB-1), the ``Verlust der Nacht'' project funded by the Federal Ministry of Education and Research, Germany (BMBF-033L038A) and the EU COST Action ES1204 (Loss of the Night Network). The DSLR camera was provided by the GFZ German Research Centre for Geoscience. The authors would like to thank the ILES team for fruitful discussions and Stefan Heller, Armin Penske and Michael Sachtleben for help with the SQMs.

\section{References}


\section{Background and Overview}\label{sec:bo}

The arc of this paper begins and ends with a discussion of the Prisoner's Dilemma, but it passes through a new result in provability logic.  Thus, it will hopefully be of interest to game theorists and logicians alike.

\subsection{Open-source Prisoner's Dilemma}

Consider the Prisoner's Dilemma, a game with two possible actions C (Cooperate) and D (Defect), with the following payoff matrix:

  \begin{table}[ht]
  \centering
    \setlength{\extrarowheight}{2pt}
    \begin{tabular}{cc|c|c|}
      & \multicolumn{1}{c}{} & \multicolumn{2}{c}{Player $2$}\\
      & \multicolumn{1}{c}{} & \multicolumn{1}{c}{$C$}  & \multicolumn{1}{c}{$D$} \\\cline{3-4}
      \multirow{2}*{Player $1$}  & $C$ & $(2,2)$ & $(0,3)$ \\\cline{3-4}
      & $D$ & $(3,0)$ & $(1,1)$ \\\cline{3-4}
    \end{tabular}
  \end{table}

\noindent In other words, by choosing $D$ over $C$, each player can destroy 2 units of its opponent's utility to gain 1 unit of its own.  As long as the payoffs are truly represented in the matrix---for example, there are no reputational costs of choosing $D$ that are not already imputed in the payoffs---then $(D,D)$ is the only Nash equilibrium, and the only correlated equilibrium.  In fact, irrespective of the opponent's move, it is better to defect.  It is therefore broadly believed that $(D,D)$ is an inevitable outcome between ``rational'' agents in a truly represented (non-iterated) Prisoner's Dilemma.

But consider a version of the game---as first studied by \citet{Tennenholtz:2004:Program}---wherein each player is an algorithm which can read its opponent's source code, as well as its own, before the game.  Is $D$ still the obvious correct strategy?  As a warm-up, one can imagine designing various algorithmic ``agents'' to compete in such games.  For example, an agent who always cooperates:

\begin{Verbatim}[frame=single]
def CooperateBot(Opponent) :
	return C
\end{Verbatim}

\citet{Tennenholtz:2004:Program} considers a simple agent which cooperates if and only if the opponent is identitically equal to itself:

\begin{Verbatim}[frame=single]
def IsMeBot(Opponent) :
	if Opponent=IsMeBot
		return C
	else
		return D
\end{Verbatim}

When playing against IsMeBot, the opponent is incentivized to ``be IsMeBot'', and in particular, cooperate.  To capture this intuition, Tenenholtz defines a {\em \bf program equilibrium} to be a pair of agents (programs) competing in a game, with access to one another's source code, such that replacing either agent by a different agent would decrease its expected payoff.  Thus, a program equilibrium is a Nash equilibrium of the `meta-game' of choosing which program to play.

Agents in a program equilibrium can return outputs that do not constitute a Nash equilibrium (of the object-level game), even in a one-shot game, as can be seen here: (IsMeBot,IsMeBot) is a program equilibrium, returning outputs (C,C) and payoffs (2,2).  This program equilibrium of IsMeBot is highly fragile, however: if we let IsMeBot' be the same program but with a tiny irrelevant change to its code---a comment perhaps---then IsMeBot will defect against it.  Agents studied by \citet{Fortnow:2009:Program} are similarly fragile.

To the end of someday designing real-world cooperative agents, it is therefore interesting to design a more ``robust'' cooperative agent, whose behavior does not depend too heavily on the details of the implementation of its opponent, but which nonetheless incentivizes its opponent to cooperate.  For this, consider:

\begin{Verbatim}[frame=single]
def FairBot_k(Opponent) :
	search for a proof of length k that
		Opponent(FairBot_k) = C
	if found,
		return C
	else
		return D
\end{Verbatim}

\noindent Here a `proof of length k' means a mathematical proof---say, in some implementation of Peano Arithmetic---using fewer than $k$ characters (symbols) to write out as a text file.  To begin thinking about these agents, observe that

\begin{itemize}
\item $\mathrm{CooperateBot}(\mathrm{FairBot}_k) = C$, because $\mathrm{CooperateBot}$ always returns $C$;
\item $\mathrm{FairBot}_k(\mathrm{CooperateBot}) = C$ when $k$ is large enough to complete the shortest proof that $\mathrm{CooperateBot}(\mathrm{FairBot}_k)=C$ (which, given the simplicity of $\mathrm{CooperateBot}$, will be very short), and $D$ when $k$ is too small to complete the proof.

\end{itemize}

\subsection{The Example of FairBot vs FairBot}

\noindent The first interesting question that arises is then:

\begin{center}
What is $\mathrm{FairBot}_k(\mathrm{FairBot}_k)$?
\end{center}

\noindent It is not so hard to see that if $k$ is too small to complete any proofs, each FairBot returns $D$.  But suppose $k$ is extremely large, for example, $10^{100}$.  Does $\mathrm{FairBot}_k(\mathrm{FairBot}_k)$ find a proof that $\mathrm{FairBot}_k(\mathrm{FairBot}_k)=C$ and therefore return $C$, validating the proof?  Or does it continue searching for a proof that $\mathrm{FairBot}_k(\mathrm{FairBot}_k)=C$ until the proof bound is reached, and having found no such proof, return $D$, consistent with the failed proof search?

It is worth pausing a moment to reflect on this question, since, when given no hints, 100\% of the dozens of mathematicians and computer scientists I've seen asked it have answered incorrectly at first (myself included).

Consider that each instance of $\mathrm{FairBot}_k$ is waiting for a proof that the other $\mathrm{FairBot}_k$ will return $C$ before it will return $C$ itself, and since neither algorithm has a clause in its code to take a ``leap of faith'' in such a situation, it seems that neither algorithm will ``make the first move'', so their proof searches must simply keep searching until they reach their limit $k$ and return $D$.

However, this reasoning turns out to be incorrect, because of a version of L\"{o}b's Theorem that is the main result of this paper, proven in Section \ref{sec:blob}.  It implies that $\mathrm{FairBot}_k(\mathrm{FairBot}_k) = C$ for large $k$.  Aside from being surprising, this result opens up a whole class of behaviors that can outperform the classical $(D,D)$ equilibrium in a truly formulated, non-iterated Prisoner's Dilemma.  Moreover, this performance can be made more robust, into a statement about any two agents willing to cooperate based on a proof of their opponents' cooperation.

Such interesting ``L\"{o}bian" behavior first seemed plausible from the work of \citet{Barasz:2014:RobustCooperation} and \citet{LaVictoire:2014:PrisDilemmaLob}, who illustrated something like program equilibria among certain non-computable logical entities they called ``modal agents'', including an analog of FairBot in that context.

\subsection{Robust Cooperative Program Equilibria}

The main application of this paper is to establish robust cooperative program equilibria for computationally bounded agents.  In particular, it is possible to write algorithms which are unexploitable in a Prisoner's Dilemma---that is, they never receive the undesirable outcome $(C,D)$ as Player 1---and which achieve the outcome $(C,C)$ against a variety of opponents, such that there is no incentive for their opponents to deviate from cooperation, even though there is no iteration or reputation to be earned in the game.  This is what we mean by ``robust cooperation''.

To summarize the result, we write $\bx{k}p$ for the statement ``$p$ can be proven using $k$ or fewer written symbols''.
Given a nonnegative increasing function $G$, we say that an agent $A_k$ taking a parameter $k \in \mathbb{N}$ is {\bf G-fair} if
$$\proves{} \bx{k+G(\textrm{LengthOf}(Opp))}[Opp(A_k) = Cooperate] \implies A_k(Opp) = Cooperate$$
In other words, if $A_k$ finding a proof that its opponent cooperates is sufficient for $A_k$ to cooperate, we say it is $G$-fair, provided the proof lengths in the search did not exceed $k+G(\textrm{LengthOf}(Opp))$.  Then we have, in terms to be made precise later,

\begin{theorem*}[{\bf Robust cooperation of bounded agents}] If certain bounds are satisfied by the G\"{o}del encoding of our proof system, and the function $G$ exceeds a certain asymptotic lower bound, then for any $G$-fair agents $A_k$ and $B_k$, we have for all sufficiently large $m,n$,
$$A_m(B_n) = B_n(A_m) = Cooperate$$
\end{theorem*}

This result depends crucially on a new version of L\"{ob}'s Theorem.

\subsection{L\"{o}b's Theorem}

L\"{o}b's Theorem states that, if $\bx{}p$ denotes the provability of statement $p$ in Peano Arithmetic (or any extension of it), then
$$\bx{}(\bx{}p \implies p) \implies \bx{}p$$
If the reader has never encountered this result, consider the case where $p$ is the Riemann Hypothesis, $RH$.  Suppose that the Riemann Hypothesis is, unbeknownst to us, false.  Without yet knowing whether $RH$ is true, it is tempting for us to claim at least that {\em if RH is provable, then RH is true}, i.e. $\bx{}RH \implies RH$.  However, if that claim were itself provable, i.e. if $\bx{}(\bx{}RH \implies RH)$, then L\"{o}b's Theorem tells us that $\bx{}RH$---the Riemann Hypothesis is provable---which is very bad news for the soundness of our proof system if the Riemann Hypothesis is actually false!

Thus, L\"{o}b's Theorem defies the intuition that we might soundly prove the ``self-trust'' statement that {\em if we prove $p$, then $p$ is true}.  This counterintuitiveness is in fact the same phenomenon as the surprising outcome that $\mathrm{FairBot}_k(\mathrm{FairBot}_k)=C$ from earlier, except that the FairBots---being algorithms which halt---only concern proofs up to a certain bounded length, $k$. Hence the motivation of this paper: to establish a version of L\"{o}b's theorem for proofs bounded in length by a parameter,~$k$.  In rough terms, we prove:
\begin{theorem*}[Parametric Bounded L\"{o}b]
Suppose $p(-)$ is a logical formula with a single unquantified variable, and that $f:\mathbb{N} \to \mathbb{N}$ is computable and  exceeds a certain asymptotic lower bound.  Then $\exists\hat k$ :
\begin{align*}
             &\proves{} \forall k,\; \bx{f(k)}p(k) \implies p(k)\\
\;\;\Rightarrow\;\; &\proves{} \forall k>\hat k, \; p(k)
\end{align*}
\end{theorem*}

\subsection{Comparison to previous work}

As mentioned, \citet{Tennenholtz:2004:Program} first defined program equilibria and studied various `non-robust' examples similar to IsMeBot above, which depend on program equality.  In particular, if one agent is written in C++ while the other is written in Python, they will defect against each other.  Examples studied by \citet{Fortnow:2009:Program} are similarly fragile.

Later, \citet{Peters:2012:Definable} consider agents encoded as a first-order formulas over the integers which can reference the G\"{o}del-numbering of the formula for the other player as well as its own, but these agents are non-computable in a way similar to those of \citet{Barasz:2014:RobustCooperation} and \citet{LaVictoire:2014:PrisDilemmaLob}.

By comparison, the program equilibria exhibited here are both computable and {\em robust}, in that they do not depend on tests for program equality, and generally exist between many pairs of agents provided they both follow a certain principle of fairness, in which a new bounded L\"{o}b's Theorem plays a crucial role.

\subsection{Long-Term Relevance}

As automated reasoning and decision-making systems improve, it is plausible that some such systems might exhibit a capacity to reason in generality about their own design principles, and those of other systems.  As an illustrative example, such a system can be designed expressly today: a theorem-prover can be handed a copy of its own source code and queried to write proofs about it.  Less contrivedly, there might be economic value in creating systems that can reason about themselves and others, such as for collaboration or negotiation.  For example, a human can reason that he is mentally outclassed in the middle of a competitive game of Go against a new player, and therefore resign to hedge his losses.  Such reasoning invokes a theory of the reasoning capacity of one's opponent, and of oneself: algorithms reasoning about algorithms.

It therefore seems prudent to explore what game-theoretic dynamics emerge from algorithms reasoning about each other, beginning with the simplest cases we can currently state and examine, similar in spirit to the way RAND Corporation's Thomas Schelling began his understanding of nuclear deterrence~\citep{Schelling:1958:ConflictProspectus,Schelling:1966:Arms}, by analyzing simple examples of non-zero-sum games \citep{Schelling:1958:Reinterpretation}.

In this paper, we find that classical game theory---and more generally, causal decision theory \citep{Gibbard:1978}---is not an adequate framework for describing the competitive interactions of algorithms that reason about the source codes of their opponent algorithms and themselves. When given read access to one another's source code---an extreme scenario for two humans, but trivial for computer systems---competing algorithms can exhibit counterintuitive ``L\"{o}bian'' behaviors which, among other things, can robustly achieve cooperative outcomes that outperform classical Nash equilibria and correlated equilibria.  Moreover, the time at which each algorithm outputs its cooperative decision occurs later in time than the causal pathway by which it benefits from the decision (namely, the pathway wherein its opponent predicts its behavior using its source code; see Section \ref{sec:cdt}).

Thus, without further investigation, our more classical intuitions about what group-level behaviors will emerge from such algorithms may miss the mark entirely.

\section{Fundamentals}
Here we begin building up the main technical result of the paper.  The algorithms examined here will make use of provability logic as a way of ``reasoning about reasoning'', and the main resource bounds on the algorithms, for simplicity, will be the lengths of the proofs they may discover.

\subsection{Proof Length and Notation}
If the first line of a three-line proof is so long that it would not fit on any physical computer system, saying the proof is ``only three lines long'' is not very descriptive.  Therefore, we will measure proof length in {\em characters} instead of lines, the way one might measure the size of a text file on a computer.  An extensive analysis of proof lengths measured in characters is covered by \citet{Pudlak:1998}.

We will fix a proof system $S$ (e.g. an extension of Peano Arithmetic) throughout, and write
$$S \proves{n} \phi, \quad \text{or simply} \quad \proves{n} \phi$$
to mean that there exists an $S$-proof of $\phi$ using $n$ or fewer characters.  After a choice of G\"{o}del encoding for $S$, it is customary to write $\bx{}\phi$ for $\exists n : Bew(n,\qquote{\phi})$, i.e., there exists a number $n$ encoding a proof of $\phi$.  This allows $S$ to indirectly talk about the existence of proofs in $S$.  We will extend this definition to talk about proof lengths:
$$\bx{n}\phi \quad \text{means} \quad \exists m : Bew(m,\qquote{\phi}) {\textrm{ and }} \mathrm{ProofLength}(m)<n$$
where $\mathrm{ProofLength}(m)$ denotes the length, in characters, of the proof encoded by $m$.  In other words, $\bx{n}\phi$ is the $S$-encoded statement that $\phi$ can be proven in $S$ with $n$ or fewer characters.

\subsection{Proof System}\label{sec:system}
We let $S$ be any first-order proof system that
\begin{itemize}
\item[1)] can represent computable functions in the sense of Section \ref{sec:rep},
\item[2)] can write any number $k\in\mathbb{N}$ using $\mathcal{O}\lg k$ symbols, and
\item[3)] allows the definition and expansion of abbreviations during proofs.
\end{itemize}
For example, we could take Peano Arithmetic, where each proof line is either
\begin{itemize}
\item an axiom, or
\item an application of Modus Ponens from lines above it,
\end{itemize}
and additionally allow ourselves to write numbers in a binary format, and allow proof lines which are
\begin{itemize}
\item the definition of an abbreviation that may be used in subsequent lines, or
\item an expansion of an abbreviation used in a previous line.
\end{itemize}

\noindent We have chosen to allow abbreviations in our proof system for two reasons.  The first is that real-world automated proof systems will tend to use abbreviations because of memory constraints.  The second is that abbreviations make the lengths of the shortest proofs in this system slightly easier to analyze: for example, if a number $N$ with a very large number of digits occurs in the shortest proof of a proposition, it will not occur multiple times; instead, it will occur only once, in the definition of an abbreviation for it.  Then, we don't have to carefully count the number of times the numeral occurs in the proof to determine its contribution to the proof length; its contribution will simply be linear in its length, or $\lg N$.

We write
\begin{itemize}
\item[] $\mathrm{Lang}(S)$ for the language of $S$,
\item[] $\mathrm{Lang}_r(S)$ for the formulas in $\mathrm{Lang}(S)$ with $r$ free variables, and
\item[] $\mathrm{Const}(S)$ for the set of constants in $S$ (e.g. $0$, $\mathcal{S} 0$, etc.).
\end{itemize}

\subsection{G\"{o}del Encoding}
We fix throughout a G\"{o}del numbering
 $$\#(-) : \mathrm{Lang}(S) \to \mathbb{N}$$
and a ``numeral'' mapping
$${}^\circ(-) : \mathbb{N} \to \mathrm{Const}(S)\subseteq \mathrm{Lang}(S)$$
for expressing naturals as constants in $S$.  Note that in traditional $\mathcal{P}\!\mathcal{A}$, for example, ${}^\circ 5 = \mathcal{S}\Ss\mathcal{S}\Ss\Ss0$.  However, to be more realistic we have assumed that $S$ uses a binary encoding to be more efficient, so e.g.,
$${}^\circ 5 = 101.$$
The maps $\#(-)$ and ${}^\circ(-)$ combine to form a G\"{o}del encoding
$$\qquote{(-)} : \mathrm{Lang}(S)\to\mathrm{Const}(S)$$
$$\qquote{\phi}:={}^\circ \# \phi$$
which allows $S$ to write proofs about itself.

\subsection{Convention for Representing Computable Functions}\label{sec:rep}
The astute reader will notice that throughout, although $\mathcal{P}\!\mathcal{A}$ and related first-order theories typically have no symbols for functions, we will often write objectionable expressions like
$$\proves{} \ldots \text{something about $f(x)$} \ldots$$
where $f:\mathbb{N}\to\mathbb{N}$ is some computable function.

However, there is a convention for interpreting such statements.  It is known \citep[see, e.g. Theorem 6.8 of][Part II]{Cori:2001} that for any computable function $f:\mathbb{N}\to\mathbb{N}$, there exists a ``graph'' predicate $\Gamma_f(-,-)\in\mathrm{Lang}_2(\mathcal{P}\!\mathcal{A})$ such that
$$\forall x\in\mathbb{N}, \; \mathcal{P}\!\mathcal{A} \proves{} \forall y, \; \Gamma_f({}^\circ x,y) \iff y = {}^\circ f(x)$$

\noindent We have assumed that $S$ is capable of representing computable functions in this way (e.g., by being an extension of $\mathcal{P}\!\mathcal{A}$).

The two-place predicates $\Gamma_f$ are cumbersome in writing because each usage introduces a quantifier.  For example, if we we have functions $f$, $g$ and $h$ and we want to say that $S$ proves that for any $x$ value, $f(x) < g(x) + h(x)$, technically we should write
$$\proves{} \forall x \forall y_1 \forall y_1 \forall y_3,\; \Gamma_f(x,y_1) {\textrm{ and }} \Gamma_g(x,y_2){\textrm{ and }} \Gamma_h(x,y_3) \implies y_1 < y_2 + y_3$$
However, for easier reading, in such cases we will abuse notation and write
$$\proves{} \forall x, \; f(x) < g(x) + h(x),$$
leaving the expansion in terms of $\Gamma$'s and $\forall y$'s as an exercise to any willing reader.

\subsection{Asymptotic Notation}
We use the convention that $f \prec g$ means that for any $M\in \mathbb{N}$, there exists an $N\in\mathbb{N}$ such that $\forall n>N, Mf(n) < g(n)$.  We write $\mathcal{O} g$ for the set of functions $f\preceq g$, and for a specific function $\mathcal{E}$ we will sometimes write write $\mathcal{E} \mathcal{O} g$ for the set of functions of the form $\mathcal{E} \circ f$ where $f\in \mathcal{O} g$.

\section{A Parametric Diagonal Lemma}
L\"{o}b's Theorem can be proven via the classical Diagonal Lemma \citep{Carnap:1934}, which states that for any formula $F(-)\in\mathrm{Lang}_1(S)$ (having one free variable), there exists a sentence $\psi\in\mathrm{Lang}_0(S)$ (with no free variables) such that
$$\proves{} \psi \iff F(\qquote\psi).$$
However, to reason about computer systems with certain as-yet unset parameters, we will need a generalization of the Diagonal Lemma for formulas with free variables to represent those parameters in a way that avoids writing a separate proof for every instance of the parameters:

\begin{proposition}[Parametric Diagonal Lemma]Suppose $S$ is a first-order theory capable of representing all computable functions, as in Section \ref{sec:rep}.  Then for any predicate $G\in\mathrm{Lang}_{r+1}(S)$, there exists a predicate $\psi\in\mathrm{Lang}_r(S)$ such that
$$\proves{} \forall \bar k = (k_1,\ldots,k_r), \; \psi(\bar k) \iff G(\qquote\psi,\bar k)$$
\end{proposition}
\begin{proof}
We define a ``partial self-evaluation function'' $e:\mathbb{N}\to\mathbb{N}$ as follows:
$$e(n) = \begin{cases}
\#\left[\theta(\qquote\theta,-,\ldots,-)\right] &\mbox{if } n = \#\theta \text{ for some }\theta\in\mathrm{Lang}_{r+1}(S) \\
0 & \mbox{otherwise }
\end{cases}
$$
Now, $e$ is computable, and therefore representable in $\mathrm{Lang}(S)$, so we can define $\beta\in\mathrm{Lang}_{r+1}(S)$ by
$$\beta(n,\bar k) := G(e(n),\bar k)$$
(using the notational convention of Section \ref{sec:rep} to avoid writing extra quantifiers and $\Gamma_e$'s).  Then, $\forall \theta\in\mathrm{Lang}_{r+1}(S)$,
$$\proves{} \forall \bar k\; \beta(\qquote{\theta},\bar k) \iff G(\qquote{\theta(\qquote{\theta},-,\ldots,-)},\bar k)$$
Now let $\theta = \beta$, so we have
$$\proves{} \forall \bar k\; \beta(\qquote(\beta),\bar k) \iff G(\qquote{\beta(\qquote{\beta},-,\ldots,-)},\bar k)$$
Finally, taking $\psi(\bar k) = \beta(\qquote{\beta},\bar k)$ yields the desired result
$$\proves{} \forall \bar k\; \psi(\bar k) \iff G(\qquote{\psi},\bar k)$$

\end{proof}

\section{A Bounded Provability Predicate, \texorpdfstring{$\bx{k}$}{box k}}
\subsection{Defining \texorpdfstring{$\bx{k}$}{box k}}
Given a choice of G\"{o}del encoding for Peano Arithmetic, it is classical that a predicate $Bew(-,-) \in \mathrm{Lang}_2(S)$ exists such that $Bew(m,n)$ means, in natural language, that the number $m$ encodes a proof in $\mathcal{P}\!\mathcal{A}$, and that the number $n$ encodes the statement it proves.  So, the standard provability operator $\bx{}:\mathrm{Lang}(\mathcal{P}\!\mathcal{A})\to\mathrm{Lang}(\mathcal{P}\!\mathcal{A})$ can be defined as
$$\bx{}\phi := \exists m : Bew(m,\qquote\phi).$$
We take for granted that $Bew$ exists for $S$ and can be extended to a three-place predicate $Bew(-,-,-) \in \mathrm{Lang}_2(S)$ such that $Bew(m,n,k)$ means that

\begin{itemize}
\item $m$ encodes a proof in $S$,
\item $n$ encodes the statement it proves, and
\item the proof encoded by $m$ uses at most $k$ characters when written in the language of $S$ ({\em not} when written using the encoding.)
\end{itemize}
Then we can define a ``bounded'' box operator:
$$\bx{k}\phi = \exists m : Bew(m,\qquote{\phi},k).$$
We also take for granted a computable ``single variable evaluation'' function, $Eval_1:\mathbb{N}\to\mathbb{N}$, such that for any $\phi(-)\in\mathrm{Lang}_1(S)$,
$$Eval_1(\qquote\phi,k) = \qquote{\phi({}^\circ k)}$$
Since $Eval_1$ is computable, it can be represented in $\mathrm{Lang}(S)$ as in Section \ref{sec:rep}.
This allows us to extend the $\bx{k}$ operator to act on sentences $\phi(-)$ with an unbound variable:
$$(\bx{k}\phi)(\ell) := \exists m : Bew(m,Eval_1(\qquote\phi,\ell),k)$$
In words, ``There is a proof using $k$ or fewer characters of the formula $\phi(\ell)$''.

\subsection{Basic Properties of \texorpdfstring{$\bx{k}$}{box k}}
Each of the following properties will be needed multiple times during the proof of Parametric Bounded L\"{o}b.  Since the proof is already highly symbolic, we give these properties English names to recall them.

\begin{property}[Implication Distribution]
There is a constant $c\in \mathrm{Const}(S)$ such that for any $p,q\in\mathrm{Lang}(S)$,
$$\proves{} \forall a\forall b,\; \bx{a}(p\implies q) \implies (\bx{b}p \implies \bx{a+b+c} q).$$
\end{property}

\begin{proof}[Proof sketch]
The fact that one can combine a proof of an implication with the proof of its antecedent to obtain a proof of its consequent can be proven in general, with quantified variables in place of the G\"{o}del numbers of the particular statements involved.  Let us suppose this general proof has length $c_0$.  Then, we need only instantiate the statements in it to $p$ and $q$.  However, if $p$ and $q$ are long expressions, they can have been abbreviated in the earlier proofs without lengthening them, so they can be written in abbreviated form again during this step.  Hence, the total cost of combining the two proofs is around $c=2c_0$, which is constant with respect to $p$ and $q$.
\end{proof}

\begin{property}[Quantifier Distribution]
There is a constant $C\in \mathrm{Const}(S)$ such that for any $\phi(-) \in \mathrm{Lang}_1(S)$,
\begin{align*}
             &\proves{}\bx{N}\left(\forall k \phi(k)\right)\\
\;\;\Rightarrow\;\; &\proves{} \forall k \; \bx{C+2N+\lg k} \phi(k)\text{, which in turn}\\
\;\;\Rightarrow\;\; &\proves{} \forall k \; \bx{\mathcal{O}\lg k} \phi(k)
\end{align*}
\end{property}

\begin{proof}
An encoded proof of $\phi({}^\circ K)$ for a specific $K$ can be obtained by specializing the conclusion of an $N$-character encoded proof of $\forall k \phi(k)$ and appending the specialization with ${}^\circ K$ in place of $k$ at the end.  To avoid repeating ${}^\circ K$ numerous times in the final line (in case it is large), we will use an abbreviation for $\phi$.  Thus the appended lines can say:
\begin{itemize}
\item[(1)] let $\Phi$ stand for $\qquote{\phi}$
\item[(2)] $\Phi({}^\circ K)$
\end{itemize}
Let us analyze how many characters are needed to write such lines.  First, we need a string $\Phi$ to use as an abbreviation for $\phi$.  Since no string of length $\frac{N}{2}$ has yet been used as an abbreviation in the earlier proof (otherwise we can shorten the proof by not defining and using the abbreviation), we can surely have $\mathrm{Length}(\Phi)<\frac{N}{2}$.  We also need some constant $c$ number of characters to write out the system's equivalent of ``let'', ``stand for'', ``('', and ``)''.  Finally, we need $\lg K$ characters to write ${}^\circ K$.  Altogether, the proof was extended by $C+N+\lg(k)$ characters, for a total length of $2N+c+\lg k$.
\end{proof}

\section{Parametric Bounded L\"{o}b}\label{sec:blob}

\begin{definition}[Proof expansion function]\label{def:E}We choose a computable function $\mathcal{E}:\mathbb{N}\to\mathbb{N}$ to bound the expansion of proof lengths when we G\"{o}del-encode them.  Its definition is that it must be large enough to satisfy the following two properties:
\end{definition}

\begin{property}[Bounded Necessitation]
$\forall \phi \in \mathrm{Lang}(S)$,
\begin{align}
             &\proves{k} \phi \\
\;\;\Rightarrow\;\; &\proves{\mathcal{E} k} \bx{k} \phi
\end{align}
\end{property}

\begin{property}[Bounded Inner Necessitation]
For any $\phi \in \mathrm{Lang}(S)$,
$$\proves{} \bx{k}\phi \implies \bx{\mathcal{E} k}\bx{k}\phi.$$
\end{property}

\noindent {\bf Estimating $\mathcal{E}$.}  How large must $\mathcal{E}$ be in practice?  G\"{o}del numberings for sequences of integers can be achieved in $\mathcal{O} n$ space \citep{Tsai:2002}, as can G\"{o}del numberings of term algebras \citep{Tarau:2013}.  To check that one line is an application of Modus Ponens from previous lines, if the proof encoding indexes the implication to which MP is applied, is a test for string equality that is linear in the length of the lines.  Finally, to check that an abbreviation has been applied or expanded, if the proof encoding indexes where the abbreviation occurs, is also a linear time test for string equality.
Thus, it seems reasonable to expect $\mathcal{E} \in \mathcal{O} k$ for real-world theorem-provers.  But however large it may be, in any case we have:

\begin{theorem}[Parametric Bounded L\"{o}b]\label{thm:pblob}
Suppose $p(-)\in\mathrm{Lang}_1(S)$ is a formula with a single unquantified variable, and that $f:\mathbb{N} \to \mathbb{N}$ is computable and satisfies $f(k) \succ \mathcal{E}\mathcal{O}\lg k$.  Then $\exists\hat k$ :
\begin{align*}
             &\proves{} \forall k,\; \bx{f(k)}p(k) \implies p(k)\\
\;\;\Rightarrow\;\; &\proves{} \forall k>\hat k, \; p(k)
\end{align*}
\end{theorem}

\noindent{\em Note:} In fact a weaker statement
$$\proves{} \forall k>k_1,\; \bx{f(k)}p(k) \implies p(k)$$
is sufficient to derive the consequent, since we could just redefine $f(k)$ to be $0$ for $k\leq k_1$ and then $\bx{f(k)}p(k) \implies p(k)$ is vacuously true and provable for $k \leq k_1$ as well.

\begin{proof}
{\em (In this proof, each centered equation will follow directly from the one above it unless otherwise noted.)}

We begin by choosing some function $g(k)$ such that $\lg k \prec g(k)$ and $\mathcal{E} g(k) \prec f(k)$.  For example, we could take $g(k) = \floor{\sqrt{(\lg k)(\mathcal{E}\- f(k))}}$.  Define a predicate $G(-,-)\in\mathrm{Lang}_2(S)$ by
$$G(n,k) := \left(\exists m : Bew(m,Eval_1(n,k),g(k))\right) \implies p(k)$$
so that for any $\phi(-)\in\mathrm{Lang}_1(S)$,
$$G(\qquote\phi,k) = \bx{g(k)}\phi(k) \implies p(k).$$
Now, by the Parametric Diagonal Lemma, $\exists \psi(-)\in\mathrm{Lang}_1(S)$ such that in some number of characters $n$,
\eqn{\label{eqn1}
\proves{n} \forall k \; \psi(k) \iff G(\qquote\psi,k)
}
By Bounded Necessitation,
$$\proves{} \bx{n} \left(\forall k \; \psi(k) \iff G(\qquote\psi,k)\right)$$
By Quantifier Distribution, since $n$ is constant with respect to $k$,
$$\proves{} \forall k \; \bx{\mathcal{O}\lg k} \left(\psi(k) \iff G(\qquote\psi,k)\right),$$
in which we can specialize to the forward implication,
$$\proves{} \forall k \; \bx{\mathcal{O}\lg k} \left(\psi(k) \implies G(\qquote\psi,k)\right)$$
By Implication Distribution of $\bx{\mathcal{O}\lg k}$,
$$\proves{} \forall k \forall a \; \bx{a}\psi(k) \implies \bx{a+\mathcal{O}\lg k}G(\qquote\psi,k)$$
By Implication Distribution again, this time of $\bx{a+\mathcal{O}\lg k}$ over the implication $G(\qquote\psi,k) = \bx{g(k)}\phi(k) \implies p(k)$, we obtain
$$\proves{} \forall k \forall a \forall b \; \bx{a}\psi(k) \implies
\left(\bx{b}\bx{g(k)}\psi(k) \implies \bx{a+b+\mathcal{O}\lg k}p(k)\right)$$
Now we specialize this equation to $a=g(k)$ and $b=h(k)$, where $h:\mathbb{N}\to\mathbb{N}$ is a computable function satisfying $\mathcal{E} g(k)\prec h(k)\prec f(k)$, for example $h(k) = \floor{\sqrt{f(k)\mathcal{E} g(k)}}$:
$$\proves{} \forall k \; \bx{g(k)} \psi(k) \implies
\left(\bx{h(k)}\bx{g(k)}\psi(k) \implies \bx{g(k)+h(k)+\mathcal{O}\lg k} p(k)\right)$$
Then since $g(k)+h(k)+\mathcal{O}\lg k < f(k)$ after some bound $k > k_1$, we have
$$\proves{} \forall k>k_1, \; \bx{g(k)}\psi(k) \implies \left(\bx{h(k)}\bx{g(k)}\psi(k) \implies \bx{f(k)} p(k)\right)$$
Now, by hypothesis, $\proves{} \forall k\; \bx{f(k)}p(k)\implies p(k)$, thus
\eqn{\label{eqn9}
\proves{} \forall k>k_1, \; \bx{g(k)}\psi(k) \implies \left(\bx{h(k)}\bx{g(k)}\psi(k) \implies p(k)\right)
}
Also, without any of the above, from Bounded Inner Necessitation we can write
$$\proves{} \forall k \forall a \; \bx{a}\psi(k)\implies \bx{\mathcal{E} a}\bx{a}\psi(k)$$
From this, with $a=g(k)$, we have
$$\proves{} \forall k \; \bx{g(k)}\psi(k)\implies \bx{\mathcal{E} g(k)}\bx{g(k)}\psi(k)$$
Now, since $\mathcal{E} g(k) < h(k)$ after some bound $k>k_2$, we have
\eqn{\label{eqn12}
\proves{} \forall k > k_2 \; \bx{g(k)}\psi(k)\implies \bx{h(k)}\bx{g(k)}\psi(k)
}
Next, from Equations \ref{eqn9} and \ref{eqn12}, assuming we chose $k_2\geq k_1$ for convenience, we have
\eqn{\label{eqn13}
\proves{} \forall k>k_2,\; \bx{g(k)}\psi(k)\implies p(k)
}
But from Equation \ref{eqn1}, the implication here is equivalent to $\psi(k)$, so we have
$$ \proves{N} \forall k>k_2,\; \psi(k),$$
where $N$ is the number of characters needed for the proof above.  From this, by Bounded Necessitation, we have
$$\proves{} \bx{N} [\forall k>k_2,\; \psi(k)].$$
By Quantifier Distribution of $\bx{N}$,
$$\proves{} \forall k>k_2,\; \bx{\mathcal{O}\lg k} \psi(k)$$
and since $\mathcal{O}\lg k < g(k)$ after some bound $k>\hat k$, taking $\hat k \geq k_2$ for convenience, we have
\eqn{\label{eqn17}
\proves{}\forall k>\hat k,\; \bx{g(k)}\psi(k).
}
Finally, from Equations \ref{eqn13} and \ref{eqn17} we have
$$\proves{} \forall k>\hat k,\; p(k),$$
as required.
\end{proof}

\section{Robust Cooperation of Bounded Agents in the Prisoner's Dilemma}

\citet{Barasz:2014:RobustCooperation}, \citet{LaVictoire:2014:PrisDilemmaLob}, and others have exhibited various proof-based agents who robustly cooperate in the Prisoner's Dilemma by basing their decisions on proofs about each other's cooperation.  However, their agents are purely logical entities which can discover proofs of unbounded length, and so are impossible to run on a physical computer.  This leaves open the question of whether such behavior is achievable by agents with bounded computational resources.

So, consider the following bounded agent, where $G$ is some increasing, non-negative function to be determined later, and $G=0$ recovers the definition of FairBot from Section 1:

\begin{Verbatim}[frame=single]
def FairBot_k(Opponent) :
	let B = k + G(LengthOf(Opponent))
	search for proof of length at most B that
		Opponent(FairBot_k) = Cooperate
	if found,
		return Cooperate
	else
		return Defect
\end{Verbatim}

Question: What is $\mathrm{FairBot}_k(\mathrm{FairBot}_k)$?  It seems intuitive that each FairBot is waiting for the other to provably cooperate, in a bottomless regression that will exhaust the proof bound B.  Thus, they will find no proof of cooperation, and hence defect.

However, this turns out not to be the case, as a consequence of Parametric Bounded L\"{o}b.  We let $$p(k) := [\mathrm{FairBot}_k(\mathrm{FairBot}_k) = Cooperate].$$
Since $G\geq 0$, $k \leq B$ in the definition of FairBot, so we have
$$\proves{} \bx{k}p(k) \implies \bx{B}p(k).$$
Now since $\bx{B}p(k)$ is FairBot's criterion for cooperation, we also have
$$\proves{} \bx{B}p(k) \implies p(k), \textrm{ \ so}$$
$$\proves{} \forall k, \; \bx{k} p(k) \implies p(k),$$
whence for sufficiently large $\hat k$, by Parametric Bounded L\"{o}b,
$$\proves{} \forall k>\hat k,\; p(k).$$
In other words, $FairBot_k$ cooperates with $FairBot_k$ for large $k$.

This result is interesting for three reasons:

\begin{itemize}
\item[1.]  It is {\em surprising}.  100\% of the dozens of mathematicians and computer scientists that I've asked to guess the output of $\mathrm{FairBot}_k(\mathrm{FairBot}_k)$ have guessed incorrectly (expecting the proof searches to enter an infinite regress and thus reach their bounds), or have given an invalid argument for cooperation (such as ``it would be better to cooperate, so they will").
\item[2.] It is {\em advantageous}. FairBot outperforms the classical Nash/correlated equilibrium solution (Defect, Defect) to the Prisoner's Dilemma, in a one-shot game with no iteration or future reputation.  Moreover, it does so {\em while being unexploitable}: if an opponent will defect against FairBot, FairBot will find no proof of the opponent's cooperation, so it will also defect.
\item[3.] It is {\em robust}.  Previous examples of cooperative program equilibria studied by \citet{Tennenholtz:2004:Program} and \citet{Fortnow:2009:Program} all involved cooperation based on {\em equality of programs}, a very fragile condition.  For example, the agent IsMeBot from the introduction will mutually defect against an identical opponent written in a different programming language, or even in a slightly different style.  Such fragility is not desirable if we wish to build real-world cooperative systems.
\end{itemize}

Taking this robustness further, we next demonstrate mutual cooperative program equilibria among a wide variety of (unequal) agents, provided only that they employ a certain ``principle of fairness".  Given a non-negative increasing function $G$, we say that an agent $A_k$ taking a parameter $k \in \mathbb{N}$ is {\bf G-fair} if

$$\proves{} \bx{k+G(\textrm{LengthOf}(Opp))}[Opp(A_k) = C] \implies A_k(Opp) = C$$
In other words, if $A_k$ finding a proof that its opponent cooperates is sufficient for $A_k$ to cooperate, we say it is $G$-fair, provided the proofs in the search did not exceed length $k+G(\textrm{LengthOf}(Opp))$.  The agents $\mathrm{FairBot}_k$ defined above are $G$-fair, and the reader is encouraged to keep these examples in mind for the following result:

\begin{theorem}[{\bf Robust cooperation of bounded agents}]Suppose that
\begin{itemize}
\item the proof expansion function $\mathcal{E}$ (defined in Section \ref{sec:blob}) of our proof system satisfies $\mathcal{E} \mathcal{O} \lg k \prec k$,
\item $f$ is any function satisfying $\mathcal{E}\mathcal{O}\lg k \prec f(k) \prec k$, and
\item $G$ is any increasing function satisfying $G(\ell) > 6f(2^\ell)$.
\end{itemize}
Then, for any $G$-fair agents $A_k$ and $B_k$, we can choose a threshold $r$ such that for all $m,n>r$,
$$A_m(B_n) = B_n(A_m) = Cooperate$$
\end{theorem}

\noindent {\bf Feasibility of bounds.} Before proceeding, recall from Section \ref{sec:blob} that we can achieve $\mathcal{E} \in \mathcal{O} k$ for automatic proof systems that are designed for easy verifiability, in which case $\mathcal{E} \mathcal{O} \lg k = \mathcal{O} \lg k$, well below the $\prec k$ requirement.

\begin{proof}
For brevity, we let
\begin{align}
a(k) &:= G(\mathrm{LengthOf}(A_k)), \\
b(k) &:= G(\mathrm{LengthOf}(B_k)), \\
\alpha(m,n) &:= [A_m(B_n) = Cooperate], \text{ and }\\
\beta(n,m) &:= [B_n(A_m) = Cooperate]
\end{align}
so we can write the $G$-fairness conditions more compactly as
\begin{align}
\label{eqnC1}     \proves{} &\bx{m+b(n)} \beta(n,m) \implies \alpha(m,n) \text{ and}\\
\nonumber    \proves{} &\bx{n+a(m)} \alpha(m,n) \implies \beta(n,m).
\end{align}

Now, $\mathrm{LengthOf}(A_k) > \lg k$ and $\mathrm{LengthOf}(B_k) > \lg k$ since they must reference the parameter $k$ in their code.  Applying $G$ to both sides yields
\eqn{\label{eqnC2} a(k),b(k) > G(\lg k) > 6f(k).}
Define an ``eventual cooperation" predicate:
$$p(k) := \forall m> k,\; \forall n> k, \; \alpha(m,n) {\textrm{ and }} \beta(n,m).$$
Using Quantifier Distribution once on the definition of $p(k)$,
$$\proves{} \forall k [\bx{f(k)}p(k) \implies \forall m>k, \; \bx{C+2f(k)+\lg m } [\forall n > k, \; \alpha(m,n) {\textrm{ and }} \beta(n,m)]]$$
Applying Quantifier Distribution again,
\eqn{\label{eqnC2a}\proves{} \forall k [\bx{f(k)}p(k) \implies \forall m>k, \forall n > k, \;  \bx{3C+4f(k)+2\lg m +\lg n }[\alpha(m,n) {\textrm{ and }} \beta(n,m)]]}
Now, for $m,n$ large and $>k$, we have
\begin{align*}
3C + \lg n  &< n &&\textrm{ \quad and by (\ref{eqnC2}),}\\
4f(k) + 2\lg m  < 6f(m) &< a(m). &&
\end{align*}
Adding these inequalities yields
$$3C+4f(k)+2\lg m +\lg n < n+a(m),$$
so for some $k_1$, from (\ref{eqnC2a}) we derive
$$\proves{} \forall k>k_1,\; [\bx{f(k)}p(k) \implies \forall m>k, \forall n > k, \;  \bx{n+a(m)}\alpha(m,n)].$$
Similarly, we also have
\begin{align*}
3C + 2\lg m  &< m &&\textrm{ \quad and }\\
4f(k) + \lg n  < 5f(n) &< b(n), &&\text{ \quad so for some $k_2\geq k_1$,}
\end{align*}
$$\proves{} \forall k>k_2 \; [\bx{f(k)}p(k) \implies \forall m>k, \forall n > k, \;  \bx{n+a(m)}\alpha(m,n) {\textrm{ and }} \bx{m+b(n)}\beta(n,m)]$$
Thus by (\ref{eqnC1}),
$$\proves{} \forall k > k_2 [\bx{f(k)}p(k) \implies \forall m>k, \forall n > k, \;  c(n,m) {\textrm{ and }} c(m,n)]\text{, i.e.}$$
$$\proves{} \forall k > k_2, \; \bx{f(k)}p(k) \implies p(k)$$
Therefore, by Parametric Bounded L\"{o}b (and the note following it), for some $\hat k$ we have
$$\proves{} \forall k > \hat k, \; p(k).$$
In other words, for all $m,n>\hat k + 1$,
$$A_m(B_n)=B_n(A_m)=Cooperate.$$
\end{proof}

\subsection{Ramifications for Causal Decision Theory}\label{sec:cdt}
Causal Decision Theory \citep{Gibbard:1978} is a framework for evaluating the desirability of an action by assessing the causal consequences of the action itself.  The interaction of $\mathrm{FairBot}_m$ and $\mathrm{FairBot}_n$ present a challenge to Causal Decision Theory, in a way similar to Newcomb's Problem \citep{Nozick:1969}, a classic scenario wherein one agent is able to predict the actions of another.

Concretely, imagine $\mathrm{FairBot}_m$ and $\mathrm{FairBot}_n$ are played against each other while being run on separate computers in separate rooms, and that they will print their final responses, $C$ or $D$, at the same time.  When $\mathrm{FairBot}_m$ decides to cooperate with $\mathrm{FairBot}_n$, it does so {\em after} computing a proof that $\mathrm{FairBot}_n(\mathrm{FairBot}_m)=C$, but {\em before} its opponent $\mathrm{FairBot}_n$ actually prints its response.  There is therefore no causal effect transmitted from the value that $\mathrm{FairBot}_n$ prints to its screen to the value that $\mathrm{FairBot}_m$ prints to its screen.  So from a purely causal perspective, there is an ``incentive'' for $\mathrm{FairBot}_n$ to print $D$ instead of $C$, since that would have ``no effect'' on its opponent, and would counterfactually yield the better outcome $(D,C)$ in place of $(C,C)$.  Thus one might argue that $\mathrm{FairBot}_n$ is acting sub-optimally in this scenario: its response could be changed to obtain a better outcome, $(D,C)$.

However, such reasoning is misplaced from a strategic standpoint.  $\mathrm{FairBot}_n$ cannot output $D$ while its opponent $\mathrm{FairBot}_m$ outputs $C$, for that outcome would be logically incoherent.  Although the instance of $\mathrm{FairBot}_n$ running as Player 2 has no causal effect on the $\mathrm{FairBot}_m$ running as Player 1, it cannot treat its decision as independent: the outcome $(C,D)$ is simply not attainable by any agent under any circumstances when Player 1 is $\mathrm{FairBot}_m$.

This prompts a re-thinking of what it means to make an optimal decision as an algorithm whose source code is transparent.  Such questions, and some of their long-term relevance, have already been considered at length in \citet{Soares:2015:TowardIDT}.

\section{Summary}
We have discovered a version of L\"{o}b's Theorem which can be applied to algorithms with bounded computational resources.  This result, in turn, can be used by algorithmic agents that have access to one another's source codes to achieve cooperative outcomes (among other things) that out-perform classical Nash equilibria and correlated equilibria, via conditions that are much more robust than previously known examples depending on program equality.  Moreover, the causal pathway by which each agent benefits from its own decision to cooperate happens {\em before} the agent actually computes its decision, which prompts a re-thinking of the causal analysis of optimal decision-making known as Causal Decision Theory in a setting where decision-making agents are algorithms with transparent source-codes.

In light of these findings, classical game theoretic results and the intuitions we derive from them may be quite far from describing what we should actually expect from systems of agents capable of reasoning about each other's design.  In order to ensure robust and beneficial long-term deployment of advanced AI technologies in the future, as described in \citet{Russell:2015:ResearchPriorities} and supported by over 100 researchers in the Future of Life Institute's Open Letter \citep{Tegmark:2015:FLIOpenLetter}, it seems prudent to investigate these dynamics ahead of time, so as to be prepared for the sorts of game-theoretic scenarios that might arise between algorithmic agents in the future.

As a direction for potential future investigation, it seems inevitable that other agents described in the purely logical (non-computable) setting of  \citet{Barasz:2014:RobustCooperation} and \citet{LaVictoire:2014:PrisDilemmaLob} will likely have bounded, algorithmic analogs, and that many more general consequences of L\"{o}b's Theorem---perhaps all the theorems of G\"{o}del--L\"{o}b provability logic---will have resource-bounded analogs as well.

\section*{Acknowledgements}
My decision to search for a result in this area was strongly influenced by Paul Christiano's belief that some such result should exist.  As well, conversations with Patrick LaVictoire, Jessica Taylor, Sam Eisenstat, and Jacob Tsimerman were helpful in sanity-checking my ideas and maintaining my interest in the problem.

This research was supported as part of the Future of Life Institute (futureoflife.org) FLI-RFP-AI1 program, grant~\#2015-144576.

\printbibliography

\end{document}