text:
\begin{document}

\def\ques{{\cor \underline{??????}\cob}}
\def\nto#1{{\coC \footnote{\em \coC #1}}}
\def\fractext#1#2{{#1}/{#2}}
\def\fracsm#1#2{{\textstyle{\frac{#1}{#2}}}}
\def\nnonumber{}

\def\cor{{}}
\def\cog{{}}
\def\cob{{}}
\def\coe{{}}
\def\coA{{}}
\def\coB{{}}
\def\coC{{}}
\def\coD{{}}
\def\coE{{}}
\def\coF{{}}

\ifnum\coloryes=1

  \definecolor{coloraaaa}{rgb}{0.1,0.2,0.8}
  \definecolor{colorbbbb}{rgb}{0.1,0.7,0.1}
  \definecolor{colorcccc}{rgb}{0.8,0.3,0.9}
  \definecolor{colordddd}{rgb}{0.0,.5,0.0}
  \definecolor{coloreeee}{rgb}{0.8,0.3,0.9}
  \definecolor{colorffff}{rgb}{0.8,0.3,0.9}
  \definecolor{colorgggg}{rgb}{0.5,0.0,0.4}

 \def\cog{\color{colordddd}}
 \def\cob{\color{black}}

 \def\cor{\color{red}}
 \def\coe{\color{colorgggg}}

 \def\coA{\color{coloraaaa}}
 \def\coB{\color{colorbbbb}}
 \def\coC{\color{colorcccc}}
 \def\coD{\color{colordddd}}
 \def\coE{\color{coloreeee}}
 \def\coF{\color{colorffff}}
 \def\coG{\color{colorgggg}}

\fi

\ifnum\isitdraft=1
   \chardef\coloryes=1
   \baselineskip=17pt
   \input macros.tex
   \def\blackdot{{\color{red}{\hskip-.0truecm\rule[-1mm]{4mm}{4mm}\hskip.2truecm}}\hskip-.3truecm}
   \def\bdot{{\coC {\hskip-.0truecm\rule[-1mm]{4mm}{4mm}\hskip.2truecm}}\hskip-.3truecm}
   \def\purpledot{{\coA{\rule[0mm]{4mm}{4mm}}\cob}}

   \def\pdot{\purpledot}
\else
   \baselineskip=15pt
   \def\blackdot{{\rule[-3mm]{8mm}{8mm}}}
   \def\purpledot{{\rule[-3mm]{8mm}{8mm}}}
   \def\pdot{}

\fi

\def\tdot{\fbox{\fbox{\bf\tiny I'm here; \today \ \currenttime}}}
\def\nts#1{{\hbox{\bf ~#1~}}}
\def\nts#1{{\cor\hbox{\bf ~#1~}}}
\def\ntsf#1{\footnote{\hbox{\bf ~#1~}}}
\def\ntsf#1{\footnote{\cor\hbox{\bf ~#1~}}}
\def\bigline#1{~\\\hskip2truecm~~~~{#1}{#1}{#1}{#1}{#1}{#1}{#1}{#1}{#1}{#1}{#1}{#1}{#1}{#1}{#1}{#1}{#1}{#1}{#1}{#1}{#1}\\}
\def\biglineb{\bigline{$\downarrow\,$ $\downarrow\,$}}
\def\biglinem{\bigline{---}}
\def\biglinee{\bigline{$\uparrow\,$ $\uparrow\,$}}

\newtheorem{Theorem}{Theorem}[section]
\newtheorem{Corollary}[Theorem]{Corollary}
\newtheorem{Proposition}[Theorem]{Proposition}
\newtheorem{Lemma}[Theorem]{Lemma}
\newtheorem{Remark}[Theorem]{Remark}
\newtheorem{Example}[Theorem]{Example}
\newtheorem{Claim}[Theorem]{Claim}
\newtheorem{Assumption}[Theorem]{Assumption}
\newtheorem{definition}{Definition}[section]
\def\theequation{\thesection.\arabic{equation}}
\def\endproof{\hfill$\Box$\\}
\def\square{\hfill$\Box$\\}
\def\comma{ {\rm ,\qquad{}} }
\def\commaone{ {\rm ,\qquad{}} }
\def\dist{\mathop{\rm dist}\nolimits}
\def\sgn{\mathop{\rm sgn\,}\nolimits}
\def\Tr{\mathop{\rm Tr}\nolimits}
\def\div{\mathop{\rm div}\nolimits}
\def\supp{\mathop{\rm supp}\nolimits}
\def\divtwo{\mathop{{\rm div}_2\,}\nolimits}
\def\re{\mathop{\rm {\mathbb R}e}\nolimits}
\def\div{\mathop{\rm{Lip}}\nolimits}
\def\indeq{\qquad{}}
\def\period{.}

\def\semicolon{\,;}

\title{Dynamic optimal contract under parameter uncertainty with risk averse agent and principal}
\author{Kerem U\u{G}URLU}
\maketitle

\date{}

\begin{center}
\end{center}

\medskip

\indent Department of Applied Mathematics, University of Washington, Seattle, WA 98195\\
\indent e-mails:keremu@uw.edu

\begin{abstract}
We consider a continuous time Principal-Agent model on a finite time horizon, where we look for the existence of an optimal contract both parties agreed on. Contrary to the main stream, where the principal is modelled as risk-neutral, we assume that both the principal and the agent have exponential utility, and are risk averse with same risk awareness level. Moreover, the agent's quality is unknown and modeled as a filtering term in the problem, which is revealed as time passes by. The principal can not observe the agent's real action, but can only recommend action levels to the agent. Hence, we have a \textit{moral hazard} problem. In this setting, we give an explicit solution to the optimal contract problem.
\end{abstract}

\noindent\thanks{\em Keywords: \/}dynamic  principal agent problem, moral hazard, optimal control.

\section{Introduction}

We consider optimal contracting between two parties, principal (``she") and agent (``he") in continuous time, when agent's actual effort can not be observed by the principal. In economics, this type of problems is called ``hidden action" or ``moral hazard" problem, where the agent's control of the drift of the output process can not be contracted upon. To give an example for the moral hazard problem, we can consider a scenario, where the investor (``principal) hires a portfolio manager (``agent") to manage her savings. The investor can not observe the actual effort (or action) of the portfolio manager but only the current wealth of the portfolio. Hence, in case the investor is not satisfied about the performance of the portfolio manager, the manager could blame the market and argue he gave the best performance for her savings, since the investor can not observe the actual efforts of her portfolio manager, anyway.

The seminal paper on the continuous time principal-agent problem is \cite{HM87}, where both parties have exponential utilities and agree on a linear optimal contract. Their results are generalized and extended by several authors, ( see e.g. \cite{SS93, SS97, HS02, CWZ09, CZ07, M98, M00} among others). A nice survey of the literature is provided by Sung in \cite{S01}. Recently, \cite{CDT16} has considered a general formulation of the principal-agent problem with a lump-sum payment on a finite horizon, where the agent influences both the agent and the volatility of the output, where the proofs use techniques based on Backward Stochastic Differential Equations approach to non-Markovian stochastic control.

In another seminal paper, \cite{S08} works in continuous time moral hazard model with infinite horizon and the payments are paid continuously, rather than as a lump sum payment at the terminal time. In \cite{S08}, the principal is risk neutral and the agent is risk averse and the agent only controls the drift of the output. \cite{PJ15} extends \cite{S08} to the case of unobserved drift and makes use of the Stochastic Maximum Principle. \cite{N14} solves a principal-agent moral hazard problem, where both the principal and the agent are risk averse, the payments are continuous, and the agent controls the unobserved drift term of the output. The main difference in the contract between a model with a risk averse and a risk neutral principal is whether there is an ongoing consumption and dividends, as would be the case with a risk aversion, or only ``lumpy" consumption and dividends which would be the case with risk-neutrality. While most of the literature focuses on a risk neutral principal, there are exceptions like the seminal work \cite{HM87} and the recent work \cite{N14}. The current manuscript is another work in this direction with a risk averse principal.

In this paper, we solve a moral hazard problem in continuous time Brownian model, where there is an additional endogenous learning term representing agent's unknown quality added to the model. To represent unknown quality of the agent, we follow the framework introduced in \cite{PJ15}. However, we do not assume that the principal is risk-neutral as in \cite{PJ15}, but instead both the principal and the agent have exponential utility with same risk-awareness level as in \cite{N14}. Our model is both quantitatively and qualitatively different from the one in \cite{PJ15} and from \cite{N14}. In the risk neutral case as in \cite{PJ15}, contracting is profitable, because the principal can extract profits by providing insurance to the agent. In our case, combined with the unknown quality of the agent, the interaction is more complicated. We can not conclude directly that the economic benefits will decrease as the difference in risk aversion between the principal and the agent shrinks, since we don't know the quality of the agent a priori, but his quality is revealed with time. The same obstacle has been observed in \cite{PJ15}, where their results hold conditioned enough time has passed to conclude qualitative results about the model. In our model, we see that as the unknown quality of the agent is revealed with time such that it does not affect the model significantly, our model converges to the analogous findings without the parameter uncertainty. On the other hand, even though the risk awareness if the principal is taken into consideration in \cite{N14}, there is no endogenous learning term, hence there are no aforementioned complications related to it. Furthermore, we also show that both parties agree on a contract, where the agent gives full effort from the beginning of the contract until the horizon $T$. Hence, neither the risk awareness of the principal nor the unknown quality of the agent do not affect the agent's actual effort level given throughout the model, even though the principal can not observe it, which was to be observed in \cite{PJ15}, whereas \cite{N14} focused on interior optimal efforts.

The rest of the paper is as follows. In Section 2, we outline the general model of the problem. In Section 3, we describe the agent's problem and find the dynamics of the continuation value function of the agent. In Section 4, we solve the principal's optimal control problem, describe the optimal contract, and in Section 5 we further discuss and elaborate our main results and conclude the paper.
\section{The Model}
In this section, we give the framework and dynamics of the model. Let $\{W_t\}_{t \geq 0}$ be a standard Brownian motion on a probability space $(\Omega,\mathcal{F},\mathbb{P})$, where $\mathcal{F}_t$ is generated by the Brownian motion $W_t$. As in \cite{PJ15}, we assume that the cumulative output $y_t$ up to time $T$ satisfies the stochastic integral equation
\begin{equation}
\label{main_eqn}
y_t = \int_0^t \big( \eta + a_s \big) ds + \int_0^t \sigma dW_s,
\end{equation}
for $0 \leq t \leq T$, where $\eta$ stands for the quality of the agent and is denoted by $\eta$, and $a_t \in [0,M]$ for $0 \leq t \leq T$ is the effort provided by the agent. $\eta$ is unknown and we model it as in \cite{PJ15} with the common prior being normal with mean $m_0$ and precision $h_0$. Posterior over $\eta$, denoted by $\hat{\eta}$, depends on $y_t$ and on cumulative effort $A_t \triangleq \int_0^t a_s ds$. Conditional on $(y_t,A_t,t)$, posterior belief about $\eta$ is also normal with
\begin{align}
\label{eqn22}
\hat{\eta}(y_t - A_t,t) &\triangleq \mathbb{E}_t[\eta| y_t,A_t] \\
\hat{\eta}(y_t - A_t,t) &\triangleq \frac{h_0m_0 + \sigma^{-2}(y_t -A_t)}{h_t}
\nonumber \\
h_t &\triangleq h_0 + \sigma^{-2}t
\nonumber \\
\hat{\eta}(0,0) &= m_0 \nonumber.
\end{align}
The principal does not observe the agent's effort, but can only recommend actions $\hat{\bar{a}}$. We denote the filtration generated by output and recommended actions $(\bar{y},\hat{\bar{a}})$ as
\begin{equation}
\mathcal{F}_t^y \triangleq \sigma(y_s, \hat{\bar{a}}_s; 0\leq s\leq t)
\end{equation}
and $\mathbb{F}^y \triangleq \{ \mathcal{F}_t^y \}_{t \geq 0}$, the $\mathbb{P}$-augmentation of this filtration. As in \cite{PJ15}, we take the utility function of the agent with $\lambda \in (0,1), \theta > 0$ as
\begin{equation}
\label{eqn25}
u(w,a) = -e^{-\theta w + \theta \lambda a}
\end{equation}
and actions of the agent are limited in a compact set $a_t \in [0,M]$ for $0 \leq t \leq T$.
On the other hand, the agent knows the actual level of effort $\bar{a}$, which only he knows. Hence, the agent's information is more than the principal. We denote the filtration generated by output, recommended  actions and actual actions up to time $t$ as $(\bar{y},\bar{a}^*)$ as
\begin{equation}
\mathcal{F}_t^a \triangleq \sigma(y_s, \bar{a}_s, \bar{a}^*; 0\leq s\leq t)
\end{equation}
and $\mathbb{F}^a \triangleq \{ \mathcal{F}_t^a \}_{0 \leq t \leq T}$, the $\mathbb{P}$-augmentation of this filtration. The agent is restricted to the class of control processes $\mathcal{A} \triangleq \{ a_t: [0,T] \times \Omega \rightarrow [0,M] \}$ that are $\mathbb{F}^a$-predictable.
We work with the induced distributions on the space of continuous functions. We take the sample space $\Omega$ to be the space of all continuous paths $C[0,T]$ equipped with the supremum norm $\lVert \cdot \rVert_{\infty}$. On $C[0,T]$, we let $W_t^0 = \omega(t)$ be the family of coordinate functions and $\mathcal{F}_t^0 = \sigma\{ W_s^0, s \leq t \}$ the filtration generated by $W_t^0$. We denote by $P^0$ the corresponding Wiener measure on $(\Omega, \mathcal{F}_t^0)$ and let $\mathcal{F}_t$ be the completion with the null sets of $\mathcal{F}_T^0$. On this space, we define the corresponding Brownian motion $W_t^0$ as in Equation \eqref{main_eqn}. The set of admissible contracts $\mathcal{C}$ is the set of $\mathbb{F}^Y \triangleq \{ \mathcal{F}_t^Y\}_{0 \leq t \leq T}$ predictable functions $(a_t,w_t): [0,T] \times Y \rightarrow A \times W$. Hence, the contract specifies a wage $\bar{w}_t$ and a recommended action $\bar{a}_t$ at date $t$ that depend on the whole past history of the output $\bar{y}_t$. Then, given a contract, the agent takes his own choice of action $a_t$ at each time $t$. Thus, the set of admissible actions $\mathcal{A}$ for the agent are those $\mathcal{F}_t^a$-predictable functions $(\bar{a},\bar{w}): [0,T] \times Y \rightarrow A \times W$.
\begin{definition}\label{def21} A contract is called implementable if the agent agrees to the contract at time zero and chooses the recommended actions: $(a^*,w^*) = (\bar{a},\bar{w})$.
\end{definition}
The dependence on the whole past implies that we can not use a direct approach to the agent's problem, since the entire past history $\bar{y}$ would be a state variable. To overcome this difficulty, we make the problem tractable as in \cite{B73,B78},\cite{CWZ09}, \cite{N14} by taking the key state variable to be the density of the output process rather than the output process itself. By considering different action choices corresponding to different output processes, we take the relative density process $\Gamma_t$, as defined in Equation \eqref{eqn211}. For $\sigma > 0$, we define
\begin{equation}
\label{eqn17}
dy_t = \sigma dW_t^0,
\end{equation}
where $y_0$ is given. This is the evolution of output under an effort policy $\bar{a}^0$, which makes the drift of output equal to zero at each time $t \in [0,T]$. Hence, different effort choices alter the evolution of output by changing the distribution over outcomes in $y$ with their corresponding $\Gamma_t$.
\section{The Agent's Problem} We impose a terminal date $T$ on the contracting horizon. Until time $T$, both the principal and the agent are committed to the contract. To have an incentive compatible contract, we need to specify what action the agent would choose when facing a given contract. First, we assume the following assumption.
The agent's continuation value is
\begin{equation}
\label{eqn38}
v(a,t) \triangleq \mathbb{E}\bigg[ \int_t^T e^{-\rho(s-t)}u(w_s,a_s)ds + e^{-\rho(T-t)}g(w_T) | \mathcal{F}_t^a \bigg],
\end{equation} where $\bar{y}_t \triangleq \{ y_s; 0 \leq s \leq t \}$ is the output history, $\rho \in (0,1)$ is the constant discount rate and the functions $u$ and $g$ are defined to be below. The history dependence on the past makes it necessary to change the relevant state variable.
We denote
\begin{equation}
f(t,\bar{y},a_t) = \hat{\eta} (y_t - A_t,t) + a_t,
\end{equation}
where
\begin{align}
A_t &= \int_0^t a_s ds,
\end{align}
here we recall that $\bar{y}_t$ means $y$ depends on the whole path. We denote the density depending on action $\bar{a}$ of $\mathcal{F}_t$-predictable processes:
\begin{equation}
\label{eqn211}
\Gamma_t(\bar{a}) = \exp \big( \int_0^t \sigma^{-1}f(s,\bar{y},a_s)dW_s^0 - \frac{1}{2}\int_0^t \lvert \sigma^{-1}f(s,\bar{y},a_s) \rvert^{2} ds \big),
\end{equation}
where $W_t^0$ is as defined in Equation \eqref{eqn17}. $\Gamma_t$ is an $\mathcal{F}_t$-martingale (as the assumptions on $f$ ensures that Novikov's condition is satisfied) with $\mathbb{E}[\Gamma_T(\bar{a}) ] = 1$ for all $\bar{a} \in \mathcal{A}$ where $\mathcal{A}$ stands for the set of admissible actions. Thus, by Girsanov theorem, we define a new measure $P^{\bar{a}}$ via:
\begin{equation}
\frac{dP^{\bar{a}}}{dP^0} = \Gamma_T(\bar{a}),
\end{equation}
and  by the filtering theorem of Fujisaki \cite{F72}, the process $W_t^{\bar{a}}$ is defined by
\begin{equation}
W_t^{\bar{a}} = W_t^0 - \int_0^t \bar{\sigma}^{-1}f(s,\bar{y},a_s)ds
\end{equation}
is a Brownian motion under $P_{\bar{a}}$. Thus we have
\begin{align}
dy_t &= \sigma dW_t^0 \\
&= \sigma [ dW_t^{\bar{a}} + \sigma^{-1}f(t,\bar{y},a_t)dt ] \\
&= f(t,\bar{y},a_t)dt + \sigma dW_t^{\bar{a}}
\end{align}
Hence each effort choice $\bar{a}$ results in a different Brownian motion $W_t^a$. $\Gamma_t$ defined above satisfies $\Gamma_t = \mathbb{E}[ \Gamma_T |\mathcal{F}_t^{\bar{a}}]$. Moreover, via derivation as in \cite{PJ15} by Ito lemma we have $\hat{\eta}$ is a $P^{\bar{a}}$-martingale with decreasing variance
\begin{equation}\label{filt_mart}
d\hat{\eta}(y_t -A_t,t) = \frac{\sigma^{-1}}{h_t}dW_t^{\bar{a}}
\end{equation}
Using the state variable as the density process $\Gamma_t$, we rewrite the optimization problem as
\begin{equation}
v(a,t) = \mathbb{E}_t^0\bigg[ \int_t^T \Gamma_{s,T}^a e^{-\rho(s-t)}u(w_s),a_s)ds + e^{-\rho(T-t)}g(w_T) | \mathcal{F}_t^0 \bigg],
\end{equation}
where the terminal value function being $g(w_T) = -e^{\frac{1-\rho}{r}-\lambda \theta r w_T}$ of the agent is to be derived below.
This approach makes our optimization problem as tractable with optimal control techniques. The agent's problem then is to solve
\begin{equation}
v^*(t) = \sup_{\bar{a} \in \mathcal{A}}v(\bar{a},\bar{w}).
\end{equation}
\begin{Theorem} \label{hamilton} For each fixed action process $a(\cdot)$, there exists a unique decomposition for the agent's continuation value Equation \eqref{eqn38} that satisfies
\begin{align}
\label{decomposition}
dv_t &= [\rho v_t - u(w_t,a_t)]dt + \sigma \gamma_t^a dW_t^{\bar{a}} \\
v_T &= g(w_T),
\end{align}
for some square integrable process $\gamma_t^a$, namely $\mathbb{E}^a[\int_0^T (\gamma_t^a)^2 dt] < \infty$. The process $\gamma_t^a$ is denoted as ``incentive compatibility parameter" in moral hazard literature (see e.g. \cite{CZ12}).
\end{Theorem}
\begin{proof} Recall for each action $a$ we have for that action $a$
\begin{align}
v(a,t) &= \mathbb{E}_t^a\bigg[ \int_t^T e^{-\rho(s-t)}u(w_s,a_s)ds + e^{-\rho(T-t)}g(w_T) | \mathcal{F}_t^a \bigg]
\\ \nonumber
&= e^{\rho t}\mathbb{E}_t^a\bigg[ \int_0^T e^{-\rho s}u(w_s,a_s)ds + e^{-\rho(T-t)}g(w_T)) | \mathcal{F}_t^a \bigg]
\\ \nonumber & \indeq
- e^{\rho t}\int_0^t e^{-\rho s} u(w_s,a_s)ds
\\ \nonumber
dv(a,t) &= \rho v_t dt + \gamma_t^a \sigma dW_t^a - u(w_t,a_t)dt,
\end{align}
where we appeal to the Martingale representation theorem by Fujisaki \cite{F72} for square integrable martingales. We note here that
\begin{equation}
\mathbb{E}_t^a\bigg[ \int_0^T e^{-\rho(s-t)}u(w_s,a_s)ds + e^{-\rho(T-t)}g(w_T) | \mathcal{F}_t^a \bigg],
\end{equation}
is a square integrable martingale since the functions $g(\cdot), u(\cdot,\cdot)$ are bounded for $a\in [0,M]$ and $t \in [0,T]$.
\end{proof}
Next, we characterize the necessary and sufficient conditions to maximize the value function of the agent in Equation \eqref{eqn38}. Our result is analogous to Proposition 4 in \cite{PJ15}.
\begin{Lemma} Maximizing the Hamiltonian defined as
\begin{equation}
H(t,y,a,A,\gamma) \triangleq u(w_t,a_t) + \gamma( \hat{\eta}(A_t,y) + a_t )
\end{equation}
is sufficient for the agent to maximize his value function as in Equation \eqref{eqn38}. Furthermore, it is necessary for the incentive compatibility parameter $\gamma_t^a$ to satisfy
\begin{equation}
\gamma_t^a(a,w) = -u_a(w_t,a_t^*) + \frac{\sigma^{-2}}{h_t}p_t,
\end{equation}
where the term $p_t$ is as defined in Equation \eqref{eqn332}.

\end{Lemma}
\begin{proof} By integrating Equation \eqref{decomposition} for the optimal action $\hat{a}$ and for any other action $\bar{a}$, we have
\begin{align}
e^{-\rho T}v(T) &= e^{-\rho T}g(w_T) = e^{-\rho t}v(t,\hat{a}) - \int_t^T e^{-\rho s}u(w_s,\hat{a}_s)ds + \int_t^T \hat{\zeta}_s\sigma dW_s^{\hat{a}}
\nonumber \\
e^{-\rho T}v(T) &= e^{-\rho T}g(w_T) = e^{-\rho t}v(t,\bar{a}) - \int_t^T e^{-\rho s}u(w_s,\bar{a}_s)ds + \int_t^T \bar{\zeta}_s\sigma dW_s^{\bar{a}},
\end{align}
where $\zeta_t \triangleq e^{-\rho t}\gamma_t$. Moreover, we have
\begin{align}
dy_t &= \sigma dW_t^0
\nonumber \\
dW_t^{\hat{a}} &= dW_t^0 - \frac{1}{\sigma}(\hat{\eta}(y_t - \hat{A}_t,t) + \hat{a}_t)dt
\nonumber \\
dW_t^{\bar{a}} &= dW_t^0 - \frac{1}{\sigma}(\hat{\eta}(y_t - \bar{A}_t,t) + \bar{a}_t)dt
\nonumber \\
dW_t^{\hat{a}} &= dW_t^{\bar{a}} + \frac{1}{\sigma} [ \tilde{\eta}(y_t - \bar{A},t) + \bar{a}_t - \tilde{\eta}(y_t - \hat{A},t) - \hat{a}_t ]dt
\end{align}
Hence, the following holds
\begin{align}
&v(t,\bar{a}) - v(t,\hat{a}) = e^{\rho t}\mathbb{E}_{\bar{a}}\bigg[ \int_t^T e^{-\rho(s-t)}[u(w_t,\bar{a}_t) - u(w_t,\hat{a}_t)]dt +
\nonumber \\ &\indeq
+ \int_t^T \hat{\gamma}_t \sigma dW_t^{\bar{a}}
\nonumber \\ &\indeq
+ \int_t^T \hat{\gamma}(\bar{a}_t - \hat{a}_t + \tilde{\eta}(y_t,\bar{A}_t) - \tilde{\eta}_t(y_t,\hat{A}_t))dt  \bigg]
\nonumber \\ &\indeq
= e^{\rho t}\mathbb{E}_{\bar{a}}\bigg[ \int_t^T [H(\bar{a},\hat{\gamma}) - H(\hat{a},\hat{\gamma}) ] dt + \int_t^T \hat{\gamma}_t \sigma dW_t^{\bar{a}}
\nonumber \\ &\indeq
\leq e^{\rho t}\mathbb{E}_{\bar{a}} \bigg[ \int_t^T \hat{\gamma}_t \sigma dW_t^{\bar{a}} \bigg] = 0.
\end{align}
The last term is a martingale due to square integrability of $\hat{\gamma}_t$ and $a \in [0,M]$ being bounded. Hence, we have proved the sufficient condition for the agent.
Next, we prove the necessary condition for the agent's value function in Equation $\eqref{eqn38}$.
\begin{align*}
&\tilde{a}_t^\epsilon  \triangleq a_t + \epsilon\Delta a_t
\\ \nonumber
&  \nabla v_t(a) \triangleq \lim_{\epsilon \rightarrow 0}\frac{v_t(\tilde{a}) - v_t(a)}{\epsilon}
\end{align*}
and by small perturbation, we have
\begin{align}
&e^{-\rho t}\nabla v_t(a) = e^{-\rho t}\lim_{\epsilon \rightarrow 0} \frac{1}{\epsilon} \mathbb{E}_{\tilde{a}}\bigg[ \int_t^T e^{-\rho s}[ u(w,\tilde{a}^\epsilon) - u(w,a)]ds
\nonumber \\ &\indeq
+ \int_t^T \hat{\zeta}_sdW_s^{\bar{a}^\epsilon} + \int_t^T \hat{\zeta}( \tilde{a}^\epsilon - a + \hat{\eta}(y_s,A_s^\epsilon) - \hat{\eta}(y_s,A_s) )ds
\bigg],
\end{align}
which gives the condition
\begin{equation}
\mathbb{E}_{\tilde{a}}\bigg[ \int_t^T e^{-\rho s}u_a\Delta a_s + \zeta_s \bigg(\Delta a_s -  \frac{\sigma^{-2}}{h_s}\int_t^s \Delta a_r dr \bigg)  \bigg] \leq 0,
\end{equation}
Integrating by parts, we get that
\begin{equation*}
\mathbb{E}_{\tilde{a}}\bigg[ \int_t^T \bigg( e^{-\rho s}u_a + \zeta_s -  \int_s^T \zeta_r \frac{\sigma^{-2}}{h_r} dr \bigg) \Delta a_s  ds \bigg] \leq 0,
\end{equation*}
By noting that $\Delta a_s$ is arbitrary, we get
\begin{equation}
\bigg( \mathbb{E}_t^a \bigg[ \int_t^T -\zeta_s \frac{\sigma^{-2}}{h_s} ds  \bigg] + \zeta_t + e^{-\rho s}u_a(w_s,a_s ) \bigg)( a_t - a^*_t) \leq 0
\end{equation}
By focusing only at time $t$ and using $\Delta a_t$ is arbitrary, we conclude that  for\\ $a_t \in [0,M]$, we have
\begin{equation}
\label{eqn332}
\zeta_t + e^{-\rho t}u_a(w_t,a^*_t) - \frac{\sigma^{-2}}{h_t}p_t \geq 0,
\end{equation}
where
\begin{equation}
\label{eqn333}
p_t = h_t \mathbb{E}\bigg[ - \int_t^T \zeta_s \frac{1}{h_s}ds \bigg| \mathcal{F}_t^a \bigg].
\end{equation}
Since increasing $\gamma_t^a$ causes the volatility of the output to increase in Equation $\eqref{decomposition}$, the principal wants to minimize the incentive compatibility parameter $\gamma_t^a$. Hence, by multiplying the equation by $e^{\rho t}$ in Equation \eqref{eqn332}, we assume that the principal confines with
\begin{equation}
\label{eqn334}
\gamma_t^a(a,w)= - u_a(w_t,a^*_t) + \frac{\sigma^{-2}}{h_t}p_t,
\end{equation}
and conclude the result.
\end{proof}

We rewrite the term $p_t$ in Equation \eqref{eqn332} in a more tractable way as in \cite{PJ15} as follows. First, we denote
\begin{equation*}
\tilde{p}_t \triangleq \frac{\sigma^{-2}}{h_t}p_t
\end{equation*}
Then, we have
\begin{equation*}
\tilde{p}_t = \mathbb{E}\bigg[ -\int_t^T e^{-\rho(s-t)}\zeta_s \frac{\sigma^{-2}}{h_s}ds\bigg],
\end{equation*}
By differentiating with respect to time $t$, we get
\begin{align*}
\frac{d\tilde{p}_t}{dt} &= \rho \tilde{p}_t + \frac{\sigma^{-2}}{h_t}\gamma_t
\\
&= \rho \tilde{p}_t - \frac{\sigma^{-2}}{h_t}(u_a(w_t,a_t) + \tilde{p}_t ),
\end{align*}
Integrating this expression, we obtain
\begin{equation}
\label{eqn335}
\tilde{p}_t = \frac{\sigma^{-2}}{h_t}\mathbb{E}_a\bigg[ \int_t^T e^{-\rho(s-t)}u_a(w_s,a_s) ds \bigg]
\end{equation}
\begin{Remark}
By the above derivation we see that $\gamma_t(w,a)$ is bounded by wage process $w_t$ being non-negative and $a \in [0,M]$. Furthermore, we also note that when there is no term $p_t$ in Equation \eqref{eqn334}, we have $\gamma_t = -u_a$, which corresponds to the first order condition with respect to $a$ of the term
\begin{equation}
\tilde{H}(t,y,a,\gamma) = u(w,a) + \gamma_t a_t,
\end{equation}
the Hamiltonian term without the filtering term in the model Equation \eqref{main_eqn}.
\end{Remark}
For the terminal date, we assume that from date $T$ on the unknown filtering term $\hat{\eta}$ is revealed, no more production takes place and both the principal and agent live off their assets for the infinite future, earning the same constant rate of return $r$. We assume both the principal and the agent solve the problem of the following form
\begin{align}
\label{eqn336}
V_T(a_0) &= \max_{b_t} - \int_0^\infty \exp(-\rho t - \lambda \theta b_t)dt
\nonumber \\
&= \max_{b_t} - \int_T^\infty \exp(-\rho (t-T) - \lambda \theta b_t)dt,
\end{align}
with $c_0$ given and $dc_t = (rc_t - b_t)dt$. For the agent $b_t = w_t$ and $a_0 = w_T$. The Hamilton-Jacobi-Bellman (HJB) equation for \eqref{eqn336} reads as
\begin{equation}
\rho V_T(a) = \max_b\{ -\exp(-\lambda \theta b) + V^\prime_T(c)[rc - b] \},
\end{equation}
whose solution is
\begin{equation*}
    V_T(c) = -\exp \big( \frac{1-\rho}{r} - \lambda \theta r c \big),
\end{equation*}
with optimal
\begin{equation*}
b(c) = \frac{\rho - 1}{\lambda \theta r} + rc.
\end{equation*}
Hence, we have for the terminal time $T$, the agent's and principal's terminal value function $v_T$ and $V_T^p$ as
\begin{align}
\label{eqn100}
g(w_T) &= -\exp\big( \frac{1-\rho}{r} - \lambda \theta r w_T \big)
\\
v_T &= g(w_T)
\\
V_T^p &= g(y_T - w_T).
\end{align}

\section{Principal's Problem}
From the principals point of view, the dynamics of the output follows
\begin{equation}
dy_t = (ry_t + \hat{\eta} + a_t  -d_t)dt + \sigma dW_t^a.
\end{equation}
We assume there is a common risk aversion $\lambda$ between the principal and the agent. The principal discounts at the same rate $\rho$ with the agent and has a flow utility
\begin{equation}
U(d_t)= -\exp(-\lambda \theta d_t)
\end{equation}
over his consumption $d_t$ with the value function
\begin{equation}
\label{eqn442}
J(t,y,v,\hat{\eta}) = \max_{d,w,a} \mathbb{E}_t^a\bigg[ \int_t^T e^{-\rho(s-t)}U(d_s)ds + e^{-\rho(T-t)}V^p_T(y_T - w_T) | \mathcal{F}_t^a \bigg],
\end{equation}
where $V^p_T(y_T - w_T)$ is defined as follows.
\begin{align*}
V^p_T(y_T - w_T) &= -\exp\big( \frac{1-\rho}{r} - \lambda \theta r (y_T - w_T) \big)
\\
&= -\exp\big( \frac{1-\rho}{r} - \lambda \theta ry_T  \big) \exp( \lambda \theta r w_T ),
\end{align*}
Using the terminal value of the agent at time $T$, the principal value function at time $T$ reads as using Equation \eqref{eqn100}
\begin{align*}
    v_T &= -\exp \big( \frac{1-\rho}{r} - \lambda \theta r w_T \big)
    \\
    J(T,y_T,v_T) &= -\frac{\exp^2( \frac{1-\rho}{r} )}{v_T}\exp(-\lambda \theta r y_T)
\end{align*}
For convenience, we summarize the value function dynamics of the principal as follows:
\begin{align}
\label{eqn442}
d\hat{\eta} &= \frac{\sigma^{-1}}{h_t}dW_t^a \\
\hat{\eta}(y_t - A_t, t) &= \frac{h_0m_0 + \sigma^{-2}(y_t-A_t)}{h_t} \\
\eta(0,0) &= m_0 \\
dv_t &= [\rho v_t - u(w_t,a_t) ]dt + \sigma\gamma_t^a(a,w)dW_t^a \\
v_T &= -\exp\big( \frac{1-\rho}{r} \big)\exp(-\lambda \theta r w_T) \\
dy_t &= \big( r y_t + \hat{\eta} + a_t - d_t \big)dt + \sigma dW_t^a \\
\label{eqn448}
y_0 &= 0
\end{align}
We define the controlled value function for fixed admissible action process $a_t$ as
\begin{equation}
J^u(t,v,y,\hat{\eta}) = \mathbb{E}_{t,T}^a[\int_t^T e^{-\rho(s-t)}e^{-\lambda \theta d_s}ds + V_T^p(y_T - w_T)| \mathcal{F}_t^a]
\end{equation}
and the value function of the control problem given $(t,\hat{\eta},v,y) \in [0,T] \times \mathbb{R}^3$ as,
\begin{equation}
\label{eqn450}
J(t,\hat{\eta},v,y) := \sup_{a(\cdot) \in \mathcal{A}}J^a(t,\hat{\eta},v,y)
\end{equation}
We next state our main theorem in this section and prove it in the subsection below, subsequently.
\begin{Theorem}
\label{thm41}
Suppose that the principal and the agent with an unknown quality term have the value functions Equation \eqref{eqn442} and Equation \eqref{eqn38}, respectively, then a contract is implementable in the sense of Definition \ref{def21}, where both parties agree to recommend and give full effort for all times $0\leq t \leq T$.
\end{Theorem}
\subsection{Proof of Theorem \ref{thm41}}
To prove Theorem \ref{thm41}, we guess an explicit solution for the value function in Equation \eqref{eqn450} and verify our guess subsequently.
Next, we guess that for $0 \leq t \leq T$ the value function of the principal is a $\mathcal{C}^{1,2}$ function of the form
\begin{equation}
J(t,y,v,\hat{\eta}) = \frac{e^{g(t,\hat{\eta})}}{v}\exp(-\lambda \theta r y)
\end{equation} and verify its validity below.
We further guess that for the optimal action process $a^*_t$
\begin{equation}
e^{-\theta w + \theta \lambda a^*_t} = k(t,\hat{\eta})v
\end{equation}

Then by Theorem \ref{hamilton}, we have that
\begin{align}
dp_t &= \theta\lambda dv_t
\\
p_t &= \theta \lambda \mathbb{E}^a\bigg[ \int_t^T e^{-\rho(s-t)}u ds \bigg]
\\
p_t &= \theta \lambda [1 - e^{\int_t^T (\rho - k(s,\eta))ds}]v_t
\\
\varphi_t(k) &= 1 - e^{\int_t^T (\rho - k(s,\eta))ds}
\end{align}
Furthermore, using our guess for the value function, we obviously have
\begin{align*}
J_y &= -\lambda \theta r J \\
J_{yy} &= \lambda^2 \theta^2 r^2 J \\
J_v &= -\frac{1}{v}J \\
J_{yv} &= \lambda \theta r \frac{1}{v} J \\
J_{vv} &= \frac{2}{v^2}J
\end{align*}
Following our guess for the value function being in $\mathcal{C}^{1,2}$, the Hamilton-Jacobi-Bellman (HJB) equation is of the form
\begin{align}
\label{eqn102}
\rho J - J_t &= \max_{w,d,a} \bigg\{  -\exp(-\lambda \theta d) + J_y [ry + \eta + a - w - d]
\nonumber \\&\indeq
+ J_v [ \rho v + e^{-\theta w + \lambda \theta a} ]
\nonumber \\&\indeq
+ \frac{1}{2}J_{yy}\sigma^2 + \frac{1}{2}J_{vv}\sigma^2\gamma_t^2
\nonumber \\&\indeq
+ \frac{1}{2}J_{\eta\eta}\frac{\sigma^{-2}}{h_t} + J_{y\eta}\frac{1}{h_t}
\nonumber \\&\indeq
+ J_{yv}\sigma^2\gamma_t + J_{v\eta}\frac{\gamma_t}{h_t}
\bigg \}
\end{align}
Next, we show that our guess value function necessitates that the principal advises full action, namely $a^*_t \equiv M$ for $0 \leq t \leq T$.
\begin{Lemma}\label{guessLem} The recommended action is $a^* = M$, namely the right corner is optimal for the principal.
\end{Lemma}
\begin{proof} By writing the first order condition for wage $w$ and action $a$ from the HJB, we have the following pair of equations:
\begin{align}
\label{eqn476}
-J_y + J_v[-\theta e^{-\theta w + \lambda\theta a }] + \frac{1}{2}J_{vv}\sigma^2 2 \gamma \gamma_w + J_{yv}\sigma^2 \gamma_w + J_{v\eta} \frac{\gamma_w}{h_t} &= 0
\\
\label{eqn477}
J_y + J_v[ \lambda \theta e^{-\theta w + \lambda\theta a } ] + \frac{1}{2}J_{aa}\sigma^2 2 \gamma \gamma_a + J_{yv}\sigma^2 \gamma_a + J_{v\eta} \frac{\gamma_a}{h_t} &= 0
\end{align}
Then, our guess for the value function
\begin{align}
J &= e^{g(t,\eta)}\frac{e^{-\lambda \theta r y}}{v}
\\
J_y &= -\lambda \theta r e^{g(t,\eta)}\frac{e^{-\lambda \theta r y}}{v},
\end{align}
we see that $J_y$ is positive, since $v$ is negative.By the relation above,\\ $\frac{\partial \gamma}{\partial w} = -\lambda\frac{\partial \gamma}{\partial a} > -\frac{\partial \gamma}{\partial a}$. Hence, by noting $0<\lambda <1$ and by derivatives of the exponential function with respect to $a$ and $w$, the first order condition for $w$ binds, whereas the first order condition for $a$ does not bind. So we have either $a=0$ or $a=M$ as optimal actions. But for $a=0$ to be optimal, the right derivative should be less than or equal to 0 at $a= 0$, but this can not be the case due to first order condition for $a$ and $w$ above. Similarly, the right corner's left derivative is positive, whenever the first order condition for $w$ binds, hence  optimal action $a^*_t = M$ for all $t \in [0,T]$.
\end{proof}

Using our guesses for the utility function and the value function and suppressing the arguments of the functions for simplicity below, we rewrite the HJB equation as follows
\begin{align*}
\rho J - J_t &= \max_{w,d}\bigg\{ -e^{-\lambda \theta d} -\lambda \theta r J [ ry + \eta + \frac{\log(kv)}{\lambda \theta} + \frac{\log(\lambda \theta r e^{g(t,\eta)})}{\lambda \theta} -\frac{\log(-v)}{\lambda \theta} - ry ]
\nonumber \\&\indeq
-\frac{1}{v}J[\rho v + k v] + \frac{1}{2}\lambda^2 \theta^2 r^2 J \sigma^2 + \frac{1}{2}\frac{2}{v^2}\sigma^2 \theta^2 \lambda^2 \big( k + \frac{\sigma^{-2}}{h_t}\varphi \big)^2v^2
\nonumber \\&\indeq
\frac{1}{2}J_{\eta\eta}\frac{\sigma^{-2}}{h_t} - \lambda \theta r J_{\eta}\frac{1}{h_t}
\nonumber \\&\indeq
+\lambda \theta r \frac{1}{v}J\sigma^2\lambda \theta [k + \frac{\sigma^{-2}}{h_t}\varphi]v - \frac{1}{v}J_{\eta}\frac{1}{h_t}\lambda \theta v [k + \frac{\sigma^{-2}}{h_t}\varphi]
\bigg\}
\end{align*}
By cancelling the terms and by first order condition on $d$, i.e. $e^{-\lambda \theta d} = -rJ$, we get
\begin{align}
\label{eqn477}
\rho J - J_t &= \bigg\{ rJ - \lambda \theta J [\eta + \frac{\log (-k)}{\lambda \theta} + \frac{\log(\lambda \theta r e^{g(t,\eta)})}{\lambda \theta}]
\nonumber \\&\indeq
-J[\rho + k] + \sigma^2\theta^2\lambda^2[k + \frac{\sigma^{-2}}{h_t}\varphi]^2J
\nonumber \\&\indeq
+\frac{1}{2}J_{\eta\eta}\frac{\sigma^{-2}}{h_t} - \lambda \theta r J_\eta\frac{1}{h_t}
\nonumber \\&\indeq
+ \lambda^2 \theta^2 \sigma^2 r J [k + \frac{\sigma^{-2}}{h_t}\varphi] - \lambda \theta  \frac{1}{h_t}[k + \frac{\sigma^{-2}}{h_t}\varphi]J_\eta
\bigg\}
\end{align}
By our guess for the value function, we have
\begin{align*}
J &= \frac{e^{g(t,\eta)}}{v}e^{-\lambda \theta r y}
\\
J_t &= g_t J
\\
J_{\eta} &= g_\eta J
\end{align*}
Hence, the HJB Equation \eqref{eqn477} reads as
\begin{align}
\label{guess_HJB}
\rho - g_t &=  r - \lambda \theta \bigg[\eta + \frac{\log (-k)}{\lambda \theta} + \frac{\log(\lambda \theta r)}{\lambda \theta} + \frac{g(t,\eta)}{\lambda \theta} \bigg]
\nonumber \\&\indeq
-[\rho + k] + \sigma^2\theta^2\lambda^2[k + \frac{\sigma^{-2}}{h_t}\varphi(k)]^2
\nonumber \\&\indeq
+\frac{1}{2}g_{\eta\eta}\frac{\sigma^{-2}}{h_t} - \lambda \theta r g_\eta\frac{1}{h_t}
\nonumber \\&\indeq
+ \lambda^2 \theta^2 \sigma^2 r  [k + \frac{\sigma^{-2}}{h_t}\varphi(k)] - \lambda \theta  \frac{1}{h_t}[k + \frac{\sigma^{-2}}{h_t}\varphi(k)]g_\eta
\end{align}
with the terminal condition $g(T,\hat{\eta}) = e^{2(\frac{1-\rho}{r})}$ for all $\hat{\eta} \in \mathbb{R}$.
\newline\newline
For ease of notation, we introduce the following expressions.
\begin{align}
K_1(t,\hat{\eta}) &= -\rho + r - \lambda \theta \hat{\eta} - \log(-k(t,\hat{\eta})) - \log(\lambda \theta r) - \rho -k(t,\eta) \\
&+ \sigma^2\theta^2\lambda^2[k(t,\hat{\eta}) + \frac{\sigma^{-2}}{h_t}\varphi(k(t,\hat{\eta}))]^2 + \lambda^2\theta^2\sigma^2r [k(t,\hat{\eta})] \\
K_2(t,\hat{\eta}) &= -\lambda \theta r \frac{1}{h_t} - \lambda \theta\frac{1}{h_t}[k(t,\hat{\eta}) + \frac{\sigma^{-2}}{h_t}\varphi(k(t,\hat{\eta}))]\\
K_3(t) &= \frac{\sigma^{-1}}{h_t}
\end{align}
By Feynman-Kac, the existence and uniqueness of the PDE above is guaranteed as
\begin{equation}
g(t,\hat{\eta}) = \mathbb{E}_t^a\bigg[ \int_t^T e^{-(T-s)}K_1(s,\hat{\eta}_s)ds + e^{-(T-t)}e^{2\frac{1-\rho}{T}} | \mathcal{F}_t^a\bigg],
\end{equation}
under the action $a$ such that $\hat{\eta}$ is an Ito process driven by the equation \begin{equation}
d\hat{\eta} = K_2(t,\hat{\eta})dt + K_3(t,\hat{\eta}_t)dW_t^a
\end{equation}
Moreover, using our guesses for the value function and utility function, we rewrite the first order condition for $w$ as
\begin{align}
\label{eqn101}
&\lambda \theta r J - \frac{1}{v}[-\theta kv]J + \frac{1}{2}\frac{2}{v^2}J\sigma^2 2 \theta \lambda v [ k + \frac{\sigma^{-2}}{h_t}\varphi](-\theta)^2\lambda^2kv
\\ & \indeq
+\lambda \theta r \frac{1}{v}J\sigma^2\theta\lambda v [k + \frac{\sigma^{-2}}{h_t}\varphi] + g_{\eta}\frac{1}{v}J\theta^2\lambda^2\frac{kv}{h_t} = 0
\end{align}
Hence by cancelling $v$ from the equation and dividing by $J$, the Equation \eqref{eqn101} reads as
\begin{align}
\label{k_eqn}
&\lambda \theta r + \theta k - \sigma^2 2 \theta \lambda[k + \frac{\sigma^{-2}}{h_t}\varphi]\theta^2\lambda^2k
\\& \indeq
+ \lambda \theta r \sigma^2\theta \lambda [k + \frac{\sigma^{-2}}{h_t}\varphi] + g_\eta\theta^2 \lambda^2\frac{k}{h_t} = 0.
\end{align}
Equation \eqref{guess_HJB} and Equation \eqref{k_eqn}, $k(t,\hat{\eta})$ and $g(t,\hat{\eta})$ are implicitly defined and can be found numerically.
\subsection{Verification Theorem}
By the discussion above, we have the following converse relation. Our guess
\begin{equation}
\label{eqn476}
J(t,y,v,\hat{\eta}) = \frac{e^{g(t,\hat{\eta})}}{v}\exp(-\lambda \theta r y)
\end{equation}
is a $\mathcal{C}^{1,2}$ function. It also satisfies the HJB equation \eqref{eqn102}
\begin{align*}
\rho J - J_t &= \max_{w,d,a} \big\{  -\exp(-\lambda \theta d) + J_y [ry + \eta + a - w - d]
\nonumber \\&\indeq
+ J_v [ \rho v + e^{-\theta w + \lambda \theta a} ]
\nonumber \\&\indeq
+ \frac{1}{2}J_{yy}\sigma^2 + \frac{1}{2}J_{vv}\sigma^2\gamma_t^2
\nonumber \\&\indeq
+ \frac{1}{2}J_{\eta\eta}\frac{\sigma^{-2}}{h_t} + J_{y\eta}\frac{1}{h_t}
\nonumber \\&\indeq
+ J_{yv}\sigma^2\gamma_t + J_{v\eta}\frac{\gamma_t}{h_t}
\big \}
\end{align*} with boundary condition
\begin{equation}
 J(T,y_T,v_T) = -\frac{\exp^2( \frac{1-\rho}{r} )}{v_T}\exp(-\lambda \theta r y_T).
\end{equation}
Using our guesses for the utility function we also have by the discussion above for optimal action $a^*$
\begin{align*}
e^{-\theta w + \theta \lambda a^*} &= k(t,\eta) v
\\
-\lambda \theta w + \lambda \theta a^* &= \log (kv)
\\
-\lambda \theta w &= \log (kv) - \lambda \theta a^*
\\
-w &= \frac{\log kv}{\lambda \theta} - M
\\
a^* - w = M - w &= \frac{\log(kv)}{\lambda \theta}
\\
-e^{-\lambda \theta d} &= \lambda \theta r J
\\
e^{-\lambda \theta d} &= -r \frac{e^{g(t,\hat{\eta})}}{v}e^{-\lambda \theta r y}
\\
-\lambda \theta d &= \log (rg(t,\hat{\eta})) - \log(-v) - \lambda \theta r y
\\
-d &= \frac{\log(rj^1)}{\lambda\theta} - \frac{\log(-v)}{\lambda \theta} - ry
\end{align*}
Hence, for each fixed $(t,y,v,\hat{\eta})$
the expression
\begin{align}
&\max_{w,d,a} \big\{  -\exp(-\lambda \theta d) + J_y [ry + \eta + a - w - d]
\nonumber \\&\indeq
+ J_v [ \rho v + e^{-\theta w + \lambda \theta a} ]
\nonumber \\&\indeq
+ \frac{1}{2}J_{yy}\sigma^2 + \frac{1}{2}J_{vv}\sigma^2\gamma_t^2
\nonumber \\&\indeq
+ \frac{1}{2}J_{\eta\eta}\frac{\sigma^{-2}}{h_t} + J_{y\eta}\frac{1}{h_t}
\nonumber \\&\indeq
\label{eqn478}
+ J_{yv}\sigma^2\gamma_t + J_{v\eta}\frac{\gamma_t}{h_t}
\big \}
\end{align} attains its maximum $(a^*,w^*,d^*)$ at
\begin{align}
\label{eqn480}
a^* &= M \\
\label{eqn481}
w^* &= M - \frac{\log k(t,\hat{\eta}^{a^*})v}{\lambda \theta} \\
\label{eqn482}
d^* &= yr - \frac{\log(-v)}{\lambda \theta} - \frac{\log(r)}{\lambda \theta} - \frac{g(t,\hat{\eta}^{a^*})}{\lambda \theta},
\end{align} where the functions $g(t,\hat{\eta})$ and $k(t,\hat{\eta})$ are determined by Equation $\eqref{k_eqn}$ and Equation $\eqref{guess_HJB}$. Hence, Equation \eqref{eqn476} is indeed the solution of the HJB Equation \eqref{eqn478} and we conclude the verification theorem.

\section{Discussion and Conclusion}
In this paper, we have studied a principal-agent problem with moral hazard. Contrary to the mainstream, where the principal is assumed to be risk-neutral, we have assumed that both the principal and the agent have exponential utility as in Equation \eqref{eqn25}, and they are risk-averse with the same risk awareness level $\lambda$ as in \cite{N14}. We take also an unknown endogenous learning term representing the unknown quality of the agent into account, which is revealed as time passes by. We see that both parties agree on a contract, where the agent gives full effort from beginning until the finite horizon $T$. Full effort of the agent in the optimal contract is also observed in \cite{PJ15}, where the authors assumed the principal to be risk-neutral. Hence, we see that the risk-awareness level of the principal does not affect a role in the agent's actual effort in the contract, but only the agent's utility is determinant in that respect. The optimality of the right corner of the admissible action interval of the agent as to be seen in Lemma \ref{guessLem} is due to the specific nature of the utility function chosen in Equation \eqref{eqn25}. Changing the utility function of the agent would cause the arguments in Lemma \ref{guessLem} would not hold anymore. In that case, one usually \textit{assumes} that the optimal effort is in the interior of the effort interval. On the other hand, we see that the payments to the agents in terms of wages and dividends are affected by the posterior belief on the unknown quality of the agent $\hat{\eta}$, as well as on the risk-awareness $\lambda$ of the principal as to be seen in the Equations \eqref{eqn480}, \eqref{eqn481} and \eqref{eqn482}. However, we can not conclude that there is a direct negative effect on the payment to the agent due to the nonlinear nature of the parameters. We further note that since the uncertainty on quality of the agent decreases as to be seen in Equation \eqref{eqn22}, its effect on the dynamics of the problem decreases as time $t$ passes.

config: arxiv


TITLE: Abelian subgroup in an infinite non-abelian $3$-group
QUESTION [6 upvotes]: Does an infinite non-abelian $3$-group has an infinite abelian subgroup?

This result holds for $2$-groups, but I wonder whether this holds or not for $3$-groups.
Thanks in advance.

REPLY [4 votes]: The answer is affirmative if $G$ has exponent $3$.
Recall that a group $G$ is locally finite if every finite subset of $G$ generates a finite subgroup, that is if every finitely generated subgroup of $G$ is finite.  It follows from a well known result on Burnside Problem, that every 3-group is locally finite.
Now from a result of P. Hall, Kulatilaka and Kargapolov (which can be found in Robinson's book
"A course in the theory of groups", Section 14.3), one knows that every locally finite group which is infinite, contains an infinite abelian subgroup.
As, I think you have not imposed a condition on the exponent of $G$, I think there is $2$-generators groups of exponent $3^n$ with $n$ sufficiently large, in which every proper subgroup is cyclic, so do not contain infinite proper subgroup


TITLE: Calculating g-force of spinning a toddler
QUESTION [1 upvotes]: I sometimes spin my nephew on the ground (we have a very slippery floor). So as my nephew is $90 \; cm$ tall and I rotate him roughly $60$ times a minute, I'm applying a g-force of $1.8$ according to the formula
$$RCF \; \text{or} \; g-force = 0.00001118 \cdot \text{rotor radius} \cdot (rpm)^2 = 0.00001118\cdot45\cdot60\cdot60.$$ Does $1.8 g$ sound right?

REPLY [2 votes]: If you want to find the force that you're applying, it's best experimentally like this.
Ask someone to stand at the side and estimate the angle $\theta$ to the vertical, that your nephew's body makes as you spin him.  Estimate this angle at the point where you're applying the force, near your hands.
If you are applying a force $F$ at the angle $\theta$
the vertical component of this force matches his weight
$$F\cos\theta=mg$$
$$F= \frac{mg}{\cos\theta}$$
If you wanted to find the centripetal acceleration that your nephew is subject to, it's $$gtan\theta $$ the acceleration and angle will vary along his body, being greater further from the centre of rotation.  Depending where you measure the angle, you should expect about 60 degrees if your calculation is correct, careful of the slippy floor!


text:
\newcommand{\Kst}{K_{\star}}
\newcommand{\piKst}{\pi^{\Kst}}

\section{Past Work and Classical Settings \label{ssec:app_classical}}

In this section, we describe in detail how our non-stochastic control setting compares with other control settings considered in the literature. At the end of the section, we conclude with a more thorough discussion of the separations (and lack thereof) between stochastic and non-stochastic control. Recall that our linear system is described by the dynamic equations
\begin{align}
\matx_{t+1} = \Ast \matx_t + \Bst \matu_t + \matw_t, \quad
 \maty_t = \Cst \matx_t + \mate_t, \label{eq:LDS_system_app}
\end{align}
Of special interest are the \emph{fully observed} settings, where $\maty_t = \matx_t$. We may also imagine an intermediate,  \emph{full-rank observation} setting, where $\dimy = \dimx$, and $\sigma_{\min}(\Cst) > 0$. Note that this latter setting allows for observation noise $\mate_t$, while the former does not. Finally, in full generality $\Cst \in \R^{\dimy \dimx}$ may have rank $\rank(\Cst) < \dimx$, and thus states cannot in general be recovered from observations.

\subsection{Online LQR \label{ssec:app_lqr}}
The linear quadratic regularity, or LQR, corresponds to the setting where the state is fully observed $\matx_t = \maty_t$, and the noise $\matw_t $ is selected from a mean-zero, light-tailed stochastic process - typically i.i.d. Gaussian. Crucially, the noise $\matw_t$ is assumed to have some non-degenerate covariance: e.g., $\matw_t \iidsim \calN(0,\Sigma)$ for some $\Sigma \succ 0 $. One then considers quadratic cost functions which do not vary with time:
\begin{align*}
\ell_t(x,u) = \ell(x,u) = x^\top R x + u^\top Q u,
\end{align*}
where $R$ and $Q$ are positive definite matrices. In particular, $\ell(x,u)$ is a strong-convex function, and thus the LQR setting is subsumed by our present work.

For the above setting, the optimal control policy (in the limit as $T \to \infty$) is described by a static feedback law $\matu_t = K_{\star} \matx_t$, where $K_{\star}$ solves the Discrete Algebraic Riccati Euqation, or DARE; we denote the corresponding control policy $\pi^{\Kst}$. Note that this is in fact the optimal \emph{unrestricted} control policy (say, over any policy which executes inputs as functions of present and past observations), despite having the simple static feedback form.

Results for online LQR consider a regret benchmark typically considered performance with respect to this benchmark (see e.g. \cite{abbasi2011regret,dean2018regret,mania2019certainty,cohen2019learning})
\begin{align*}
\overline{R}_T(\Alg) := J_T(\Alg) - T \lim_{n \to \infty}\frac{1}{n}\Exp_{\matw}[J_n(\piKst)]
\end{align*}
where the righthand term is the \emph{infinite horizon} average cost induced by placing the optimal control law $\Kst$. One can show (e.g. \cite{simchowitz2020naive})  $\Exp_{\matw}[J_n(\piKst)]$ is increasing in $n$. Thus, by Jensen's inequality, it holds that for any $\Pi \subset \Pildc$ containing $\pi^{\Kst}$,
\begin{align*}
\Exp_{\matw}[\overline{R}_T(\Alg)] &= \Exp_\matw [J_T(\Alg)] - T \lim_{n \to \infty}\frac{1}{n}\Exp_{\matw}[J_n(\piKst)] \\
&\le J_T(\Alg) - \Exp_{\matw}[J_T(\piKst)] \\
&= \Exp_\matw [J_T(\Alg)]- \inf_{\pi \in \Pi} \Exp_{\matw}[J_T(\pi)] \\
&\le \Exp_\matw [J_T(\Alg)] -  \Exp_{\matw}\inf_{\pi \in \Pi}J_T(\pi) \\
&\le \Exp_{\matw}[J_T(\Alg) -  \inf_{\pi \in \Pi}J_T(\pi) ] := \Exp_{\matw}[\Regret_T(\Alg;\Pi)],
\end{align*}
where $\Regret_T$ is our non-stochastic benchmark.
Hence, we find that, in expectation, the standard benchmark for online LQR is weaker than ours. Nevertheless, the two benchmark typically concide up to lower order terms due to martingale concentration. Observe however a key conceptual difference: the LQR regret $\overline{R}_T$ can be defined with an \emph{a prior} benchmark, because the dynamics are stochastic. On the other hand, the non-stochastic benchmark is defined \emph{a posteriori}, after because the noises are selected by an adversary.

\subsection{Online LQG \label{ssec:app_lqg}}
In the LQG, or linear quadratic gaussian control, one typically assumes a partially observed dynamical system, inheriting the full generality of \Cref{eq:LDS_system_app}. Again, the cost function is typically taken to be quadratic function of input and output:
\begin{align*}
\ell_t(y,u) = \ell(y,u) = y^\top R y + y^\top Q y,
\end{align*}
Again, $R,Q$ are assumed to be positive defined, and thus our assumption that $\ell_t$ are strongly convex subsumes the LQG setting.  Typically, online LQG assumes that both the process noise $\matw_t$  \emph{and the observation noise $\mate_t$} are not only mean zero and stochastic, but also well conditioned. For example, $\matw_t \iidsim \calN(0,\Sigma_w)$ and $\mate_t \iidsim \calN(0,\Sigma_e)$, where $\Sigma_w,\Sigma_e \succ 0$.

Whereas the unconstrained optimal policy in LQR is an \emph{static} feedback law, the optimal LQG policy is \emph{dynamic} linear controller of the form considered in this work. This is true even if $\Cst = I$ but there is non-zero process noise $\mate_t$; that is, $\maty_t = \matx_t + \mate_t$.


text:
\section{Introduction}

Semidefinite Programs (SDPs) are a class of mathematical programming problems that have a wide range of applications in areas such as control theory, statistics, signal processing, and combinatorial optimization~\cite{vandenberghe1996semidefinite, fares2002robust}. Moreover, a variety of approximation algorithms for combinatorial optimization problems involve solving a SDP relaxation and then rounding the solution to produce a feasible point with provable suboptimality guarantees. There are efficient algorithms such as interior-point methods~\cite{vandenberghe2005interior}, which can be used to solve SDPs. However, as the problem size increases, the memory required by these algorithms becomes a key computational bottleneck. In one regime of interest for very large-scale problems, it is not even possible to store a dense $n\times n$ decision variable in core memory.

One prominent approach to dealing with this bottleneck, pioneered by~\citet*{burer}, is to parameterize the positive semidefinite (PSD) decision variable as $X = UU^T$, and reformulate SDPs as nonlinear programs in the variable $U\in \mathbb{R}^{n\times r}$, where the value of $r$ is depends on the predetermined bound on the rank of the solution and must satisfy Barvinok-Pataki bound \cite{barvinok1995problems,pataki1998rank} for optimality guarantees. This approach has received a lot of attention (see, for example,~\cite{bhojanapalli2016dropping, chen2015fast, journee2010low, boumal2018global}) because it is able to resolve scalability issues with SDPs to some extent by using low-rank parameterization. However, this approach requires an \emph{a priori} bound on the rank of an optimal solution~\cite{waldspurger2018rank}. Recently, another approach for SDPs in low memory has emerged. This involves maintaining a lower dimensional sketch of the decision variable, while preserving the convexity of the problem formulation. This approach has primarily been developed in cases where either we know an \textit{a priori} bound on the rank of the solution \cite{ding2019optimal} or the aim is to generate a low-rank approximation of the solution~\cite{sketchy}.

In this paper, we develop methods to `solve' SDPs in low memory without prior knowledge of the rank of an optimal solution. We do not explicitly aim to represent the matrix decision variable $X$, but rather to sample a zero-mean random vector with covariance $X$. This sampled representation of the solution only requires $\mathcal{O}(n)$ memory and is sufficient to implement rounding schemes for a number of SDP relaxations of binary optimization problems. Moreover, other succinct representations of the solution, such as low-rank approximations, can be computed in low memory by repeatedly generating sampled solutions (see Section~\ref{sec:PostProc}).

Our aim, then, is to develop an algorithm that generates random variables with covariance that is a (near-)optimal point to a SDP. Initially, we focus on trace constrained SDPs
\begin{equation}\label{prob:PrimalSDP}
\tag{BoundedSDP}
\max_X\ \ g(\mathcal{B}(X))\ \ \ \textup{subject to}\ \ \ \begin{cases} &\textup{Tr}(X) \leq \alpha\\
&X \succeq 0,\end{cases}
\end{equation}
where the objective function $g$ is concave and smooth and $\mathcal{B}(\cdot): \mathbb{S}^{n} \rightarrow \mathbb{R}^d$ is a linear mapping. This problem class was studied by \citet{sketchy} and our approach is very much inspired by their work. The map $\mathcal{B}$ projects the $\binom{n+1}{2}$-dimensional variable to a much smaller $d$-dimensional space. One way to incorporate any additional constraints to this problem is to add a corresponding penalty term in the objective, at the expense of maintaining exactly feasible iterates (see Section~\ref{sec:LintoBounded}). In Section~\ref{Sec:Applications}, we discuss how to extend further our main idea to certain other constraint sets without compromising on feasibility.

\subsection{Motivating Example: Maximum Cut Problem}\label{Sec:MaxCutIntro}
The maximum cut problem (\textsc{MaxCut}) involves maximizing the quadratic function defined by the Laplacian of a graph over binary decision variables, i.e.,
\begin{equation}\label{prob:MaxCut}
\tag{MaxCut}
\max_{x\in \{-1,1\}^n}\ \ x^T C x
\end{equation}
where $C = (1/4)L_G$ and $L_G$ is the Laplacian of a graph. Note that the cost matrix $C$ is a symmetric diagonally dominant matrix with positive entries on the diagonal. In a celebrated result, \citet*{GW} developed a $\alpha_{GW}$-approximation algorithm (with $\alpha_{GW}\approx 0.878$) that involves solving the SDP relaxation
\begin{equation}\label{prob:relaxedMC}
\tag{MaxCut-SDP}
\max_{\textup{diag}(X) = \mathbbm{1}, X\succeq 0}\ \ \left\langle C, X\right\rangle
\end{equation}
followed by a randomized rounding scheme. If $X^{\star}$ is an optimal solution of~\eqref{prob:relaxedMC}, the rounding scheme involves sampling a zero-mean Gaussian vector $z$ with covariance $X^{\star}$, so that the binary vector $\textup{sign}(z)$ is a random feasible point to \textsc{MaxCut} that achieves the stated approximation guarantee in expectation. To implement this rounding scheme, there is no need to explicitly compute $X^{\star}$; instead it is enough to construct a zero-mean random (Gaussian) vector with covariance $X^{\star}$. This observation is a key motivation for our notion of sampled solutions for SDPs.

Following \cite{yurtsever2019scalable}, we define the working memory of an algorithm as follows.

\begin{definition}
The \emph{working memory} of an algorithm is defined as the total memory utilized by the algorithm apart from the memory required to represent the problem instance.
\end{definition}

If we have an algorithm to solve~\eqref{prob:relaxedMC} that can track such samples rather than the full decision variable, we can potentially implement the Goemans-Williamson method using $\mathcal{O}(n)$ working memory. One of the main contributions of this paper is to show that this in fact possible (see Algorithm~\ref{algo:GenSample}).

\begin{comment}
\subsection{Algorithmic Approach: Frank-Wolfe with Gaussian Sampling}
A positive semidefinite matrix $X$ can be considered to be the covariance matrix of a Gaussian random vector $z$. Moreover, a nonnegative weighted sum of two covariance matrices implies a nonnegative weighted addition of their samples. The main idea of the paper is to generate a random sample from a covariance matrix and maintain and update the sample to track the update in its covariance matrix. For~\eqref{prob:PrimalSDP}, the extreme points of the feasible set are rank-1 matrices and a random Gaussian sample generated from such an extreme point is a multiple of its rank-1 factorization. This sample can then be represented in low memory and a first-order algorithm (see, for example,~\citet*{frank1956algorithm}), whose update rule at each iteration involves a positive fractional step in the direction of an extreme point, can be modified to include Gaussian sampling.
By keeping track of the random Gaussian sample through the iterative algorithm, we can effectively track its covariance $X$. In this paper we use Gaussian sampling in conjunction with the Frank-Wolfe algorithm to solve~\eqref{prob:PrimalSDP}.
\end{comment}

\subsection{Our Contributions}
We now summarize the key contributions of the paper.

\paragraph{Sample-based solutions to convex programs} A key conceptual contribution of this paper is to propose the idea of sample-based solutions to convex programs. We consider two approaches:
\begin{itemize}
\item Gaussian samples: In this case, the aim is to represent the positive semidefinite solution $X$ of a SDP via a zero mean Gaussian vector $z\sim \mathcal{N}(0,X)$ such that its covariance is $X$.
\item Extreme-point samples: In this case, the aim is to represent the solution $x$ of a convex program via a random extreme point of the feasible region such that its expected value is $x$.
\end{itemize}

\paragraph{Generating Gaussian sample-based solution to SDPs} Using an algorithmic framework based on the Frank-Wolfe algorithm, we show that it is possible to compute an $\epsilon$-optimal Gaussian sample-based solution of~\eqref{prob:PrimalSDP} and a near-feasible, near-optimal Gaussian sample-based solution to SDP with $d$ linear equality constraints and bounded feasible region. The working memory of our algorithm is $\mathcal{O}(n+d)$ and it generates a solution with provable optimality guarantees after $ \mathcal{O}\left(n^2/\epsilon^2\right)$ iterations (see Lemma~\ref{lemma:SubOptFeas}).

\paragraph{Approximation algorithm for \textsc{MaxCut}} For \textsc{MaxCut}, we provide an implementation of Goemans-Williamson rounding method that results in a $(1-\epsilon)\alpha_{GW}$-approximate solution (with $\alpha_{GW} \approx 0.878$) to \textsc{MaxCut} that requires additional storage of at most $3n$ numbers. This result Theorem~\ref{thm:MaxCutResult} in Section~\ref{Sec:MaxCut} is stated in a less detailed form below.

\begin{theorem}
Given $\epsilon \in (0,1)$ and a diagonally dominant cost matrix $C$, there exists a polynomial time $\mathcal{O}\left(\frac{n^3}{\epsilon^3}\log(2n)\log\left(\frac{2n}{\epsilon}\right)\times \textup{mvc}\right)$ randomized algorithm, where $\textup{mvc}$ is the complexity of matrix-vector multiplication with $C$, that generates a random binary vector $w\in \{-1,1\}^n$ which satisfies
\begin{equation}
\alpha_{GW}(1-\epsilon) \textup{opt} \leq \mathbb{E}[w^TCw] \leq \textup{opt},
\end{equation}
where $\textup{opt}$ is the maximum of $w^TCw$ over the set $w\in \{-1,1\}^n$. The working memory of the algorithm is at most $3n$ numbers.
\end{theorem}

A key conceptual difference between our approach and existing factorization or sketching methods is that no \emph{a priori} bound on the rank of the optimal solution is required. Indeed, in the case of~\eqref{prob:relaxedMC}, it is well-known that the optimal solution can have rank $\Theta\left(\sqrt{n}\right)$~\cite{barvinok1995problems,pataki1998rank}.

\paragraph{Generating extreme-point sample-based solution to convex programs} For a convex optimization problem with compact feasible region, if the extreme points of the feasible region can be represented in low memory, then we can track its solution in low memory provided that we can solve the linear optimization subproblem over the feasible region in low memory. This allows us to move to a more general setting where the decision variable need not be a positive semidefinite matrix. We provide a modified Frank-Wolfe algorithm (see Algorithm~\ref{algo:FWRandom}) whose output is a random extreme point such that it satisfies the optimality bounds for constrained convex program in expectation.

\subsection{Related Work on Low Memory Algorithms for SDP}

In this subsection, we briefly summarize key ideas in the literature related to low memory algorithms for SDP with $d$ linear equality constraints and bounded feasible region. One approach is to replace the PSD matrix by a low-rank factorization and use nonlinear programming techniques to compute the solution of the resulting nonconvex problem. This technique was pioneered by~\citet*{burer}. The factorization sacrifices convexity and its associated optimality guarantees and typical numerical algorithms are only able to generate first- or second-order critical points. Nevertheless,~\citet*{boumal} showed that if the constraint set is a smooth manifold and the rank $r$ of the factorization is set to at most $r$ with $r(r+1)\geq 2d$, then any second-order critical point for SDP is a global optimum. This bound is a consequence of Barvinok-Pataki bound~\cite{barvinok1995problems, pataki1998rank} which states that SDP with $d$ linear equality constraints and a bounded feasible region admits a global optimum with rank $r$ that satisfies $r(r+1) \leq 2d$. Using a second-order method \cite{journee2010low} or a Riemannian gradient descent algorithm \cite{boumal2018global}, it is possible to compute an $\epsilon$-optimal solution to the factorized problem that satisfies the Barvinok-Pataki bound, and requires $\mathcal{O}(n\sqrt{d})$ working memory. On the other hand,~\citet*{waldspurger2018rank} showed that unless $r$ is at least as large as $\sqrt{2d}$, a typical numerical algorithm can converge to nonoptimal critical points for the resulting nonconvex problem. This method not only requires an \textit{a priori}  knowledge of the rank of the solution but it is also requires $\Omega(n\sqrt{d})$ working memory to generate a solution with provable optimality guarantees.

\paragraph{} A recent approach to solving linearly constrained SDPs in low memory involves sketching the decision variable to a low dimensional subspace and using first-order algorithms to compute a solution of the optimization problem in the space of the sketched decision variable. Unlike factorization approaches that break the convexity of the linearly constrained SDP, sketching the variable preserves the convexity of the problem formulation. These methods are based on techniques for sketching low rank matrices. For instance,~\citet{tropp2017practical} provide an algorithmically simple sketching technique to compute a low-rank approximation of a matrix $A\in \mathbb{R}^{n\times n}$ by exploiting the spectral decay of the matrix. Their algorithm preserves the positive semidefiniteness of the decision variable.

Such sketching and reconstruction techniques  were extended by~\citet{sketchy} to generate an approximate \mbox{rank-$r$} factorization of a solution to a smooth convex optimization problem with bounded nuclear norm constraint. They do so by sketching the decision variable to a lower dimension and using the Frank-Wolfe algorithm to track the sketched variable. With the sketched variable, the working memory required for their method is $\Theta (d+nr)$. Although the sketch used in~\cite{sketchy} is different from the sample-based solutions in this paper, the algorithmic architecture of our approach is inspired by~\cite{sketchy}.

In their recent work,~\citet{yurtsever2019scalable} extend the approach from~\cite{sketchy} to deal with SDPs with $d$ linear equality constraints. They provide a polynomial-time randomized sketching algorithm that, with high probability, computes a rank-$r$ approximation of a near-feasible solution to SDP with $d$ linear equality constraints. The working memory required to compute this solution via sketching is $\mathcal{O}(d+rn/\zeta)$, i.e., it is linear in number of equality constraints and the rank of the computed solution. The nonnegative quantity $\zeta \in (0,1)$ controls how close the rank-$r$ approximation $X_r$ produced by the algorithm is to the best rank-$r$ approximation $\widehat{X}$ of the solution $X$. More precisely, with high probability these quantities satisfy
$\|X-X_r\|_{\star} \leq (1+\zeta)\|X-\widehat{X}\|_{\star}$, where

$\|\cdot\|_{\star}$ is the nuclear norm.
We will discuss the similarities and differences between our work and~\cite{yurtsever2019scalable} in Section~\ref{Sec:Conclusion}.

Alternatively,~\citet{ding2019optimal} compute a low-rank solution to an SDP with linear equality constraints by first approximately finding the subspace in which the solution lies. This subspace is computed by finding the null space of the dual slack variable. By restricting the search space of the primal solution to a smaller subspace, they restrict the memory required. The dual problem is solved only approximately, with the assumption that the rank of the primal optimal solution satisfies the Barvinok–Pataki bound~\cite{barvinok1995problems, pataki1998rank}, which results in some error in the computation of the subspace in which the primal solution lies. The working memory for their method is then $\Theta (d+nr)$, where $r$ is the rank of an optimal solution to SDP and satisfies the Barvinok-Pataki bound. Table~\ref{table:ComparisonMemory} shows the comparison of memory required by the above methods with the memory requirement of Algorithm~\ref{Algo1}. Note that the methods given in the literature compute a rank-$r$ solution to SDP with $d$ linear equality constraints while Algorithm~\ref{Algo1} generates random samples that have covariance equal to a near-feasible, near-optimal solution to the SDP.

\begin{table}[ht]\centering
\begin{tabular}{|l |c|}
\hline
\parbox[c]{2cm}{\raggedright Reference} & \parbox[c]{5.5cm}{ Working Memory Required}\\
\hline
\citet{tropp2017practical}&$\Theta(d+nr)$\\
\citet{yurtsever2019scalable}&$\mathcal{O}(d+rn/\zeta)$\\
\citet{ding2019optimal}&$\Theta(d+nr)$\\
\hline
Algorithm~\ref{Algo1}&$\mathcal{O}(d+n)$\\
\hline
\end{tabular}
\caption{Working memory requirement to compute the solution to SDP with $d$ linear equality constraints. The first three methods in the table compute a rank-$r$ approximate solution and Algorithm~\ref{Algo1} from this paper generates a sample-based solution}\label{table:ComparisonMemory}
\end{table}

\paragraph{}A widely studied special case of SDP is~\eqref{prob:relaxedMC}. Since~\eqref{prob:relaxedMC} has $n$ linear equality constraints, the Barvinok-Pataki bound~\cite{barvinok1995problems, pataki1998rank} states that the rank of the optimal solution could be as high as~$\Omega(\sqrt{n})$. As such, the algorithms for solving~\eqref{prob:relaxedMC} could require~$\Omega(n^{1.5})$ working memory. One such algorithm is given by~\citet*{klein1996efficient} which generates a \mbox{rank-1} update to the intermediate solution of~\eqref{prob:relaxedMC} at each iteration. The number of iterations required for convergence, and thus the rank of the intermediate solution could be as large as $n$. By restricting the rank of the solution to $\mathcal{O}(\sqrt{n})$,~\citet*{klein1998space} restrict the working memory to be $\mathcal{O}\left(n^{1.5}\right)$. An improvement on this memory requirement is provided by \citet{yurtsever2019scalable}. Their sketching method generates, with high probability, a rank-1 approximation $zz^T$ of a near-feasible, $\epsilon$-optimal solution $X$ to~\eqref{prob:relaxedMC} using $\mathcal{O}(n/\zeta)$ working memory such that for some $\zeta \in (0,1)$, $\|X-zz^T\|_{\star} \leq (1+\zeta)\|X-\widehat{X}\|_{\star}$, where $\widehat{X}$ is the best rank-1 approximation of $X$ and $\|\cdot\|_{\star}$ is the nuclear norm. Note that, the memory required is linear in $n$, however, it has dependence on the approximation parameter~$\zeta$.

Our sampling technique requires $\mathcal{O}(n)$ memory as we only aim to represent the samples of a near-optimal solution. This eliminates the dependency on the rank $r$ of the low rank approximation of a near-optimal solution or the accuracy to which the approximation is computed.

\begin{comment}
\citet*{yurtsever2019scalable} a randomized algorithm that uses $\mathcal{O}(n/\zeta)$ memory and with high probability, computes $(1+\zeta)$-optimal low rank-1 approximation of $\epsilon$-optimal solution to~\eqref{prob:relaxedMC}.

Since~\eqref{prob:relaxedMC} has $n$ linear equality constraints, Barvinok-Pataki bound~\cite{barvinok1995problems, pataki1998rank} states that the rank of the optimal solution could be as high as~$\sqrt{n}$. As such, the algorithms for solving~\eqref{prob:relaxedMC} could require~$\Omega(n^{1.5})$ memory. One such algorithm is given by~\citet*{klein1996efficient} which generates a rank-1 update to the intermediate solution of~\eqref{prob:relaxedMC} at each iteration. By restricting the rank of the solution to $\mathcal{O}(\sqrt{n})$,~\citet*{klein1998space} restrict the memory required to be $\mathcal{O}\left(n^{1.5}\right)$. For large $n$, this requirement can be high.

\paragraph{}A widely studied special case of SDP is~\eqref{prob:relaxedMC}. \citet*{klein1996efficient} explore efficient algorithms to generate solutions to \textsc{MaxCut} by solving~\eqref{prob:relaxedMC}. Their algorithm generates a rank-1 update to the intermediate solution of~\eqref{prob:relaxedMC} at each iteration. The number of iterations required for convergence, and thus the rank of the intermediate solution could be high. By restricting the rank of the solution to $\mathcal{O}(\sqrt{n})$,~\citet*{klein1998space} restrict the memory required for solving the problem to $\mathcal{O}\left(n^{1.5}\right)$. However, for large $n$, this requirement can still be high.
\end{comment}

\begin{comment}
In this subsection, we briefly summarize key ideas in the literature related to low memory algorithms for SDP. One approach is to replace the PSD matrix by its low-rank factorization and use nonlinear programming techniques to compute a solution. This technique was pioneered by~\citet*{burer}. These methods require \emph{a priori} knowledge of the rank of the solution which could be as high as  $\Theta(\sqrt{2d})$ for an equality constrained problem with $d$ constraints~\cite{waldspurger2018rank}. We briefly review some of the related methods and their results.

Factored gradient descent method by~\citet*{bhojanapalli2016dropping} is used to minimize a convex function $f(X)$ over the set of $n\times n$ PSD matrices by recasting it as $\min_U f(UU^T)$ over the set $U \in \mathbb{R}^{n\times r}$ with $r\leq n$. The nonlinear problem is solved under the assumption that the objective function is $M$-smooth. They provide a sublinear convergence guarantee to its optimal solution $X^*$ with an error of $\mathcal{O}(1/k)$ after $k$ iterations if the rank of the solution $r^*$ is known. If the rank of the solution is not known or is set to a value less than $r^*$, then the algorithm converges sublinearly to the best rank-$r$ approximation of $X^*$.

\citet*{chen2015fast} run a projected gradient descent on $\min_{U\in\mathcal{U}} f(UU^T)$, where $\mathcal{U}$ is a convex feasible set. Under a smoothness assumption on the objective function, the algorithm converges linearly to a statistically useful solution. However, the projection onto the feasible set is the most computationally expensive step in each iteration of their algorithm.

\citet{journee2010low} again solve factorized nonlinear problem of the form $\min_{U\in \mathcal{U}} f(UU^T)$, where $\mathcal{U}= \{U\in \mathbb{R}^{n\times r}: \textup{Tr}(A_iUU^T) = b_i\ i=1,\dotsc, m\}$, using quadratic second-order method under the assumption that the problem admits a low-rank solution and that the constraint matrices are mutually independent. In their recent work,~\citet*{boumal2018global} apply Riemannian gradient descent algorithm to the factorized SDP. If the gradient of the objective function is Lipschitz continuous, after random initialization, their algorithm computes an $\epsilon$-optimal solution to the factorized SDP in $\mathcal{O}\left(1/\epsilon^2\right)$ iterations.

\paragraph{} A recent approach to solving SDPs in low memory involves sketching the variable to compute a low dimensional mapping and using first-order algorithms on the mapped subspace. Solving the linear programs has an obvious advantage over the nonlinear techniques discussed here. The survey~\cite{Woodruff} explores the idea of sketching via matrix multiplication between a random matrix with iid entries and the input matrix. A low-rank approximation is reconstructed with \emph{a priori} error bounds where the error is defined by the nuclear norm of the difference between the original matrix and the approximate matrix. However, certain critical properties of the matrix such as sparsity and positive semidefiniteness are lost in the sketched lower dimension.

\citet{tropp2017practical} provide a simple sketching technique to compute a low-rank approximation of the input matrix $A\in \mathbb{R}^{m\times n}$ by exploiting the spectral decay of the matrix. They also provide an algorithm which preserves positive semidefiniteness of the approximation. This is an extension of the algorithm given by~\citet{sketchy} with similar error bounds. They focus on developing a sketching technique for the convex problems with trace constraint. The aim of this method is to obtain a rank-$r$ approximation of the solution by sketching the matrix to a lower dimension and using conditional gradient algorithm to track the sketched variable.

In their recent work,~\citet{ding2019optimal} compute a low-rank solution to the problem by first approximately finding the subspace in which the solution lies. This subspace is computed by finding the null space of the dual slack variable. By restricting the search space of the primal solution to a smaller subspace, they restrict the memory required. The dual problem is solved only approximately which results in error in the computation of the subspace in which the primal solution lies. Moreover, some knowledge of the bound on the rank of the solution is required.

\paragraph{}~\citet*{klein1996efficient} explore efficient algorithms to solve \textsc{MaxCut} problem. Their algorithm generates a rank-1 update to the intermediate solution at each iteration. The number of iterations required for convergence, and thus the rank of the intermediate solution could be high. By restricting the rank of the solution to be $\mathcal{O}(\sqrt{n})$,~\citet*{klein1998space} restrict the memory required for solving the problem to $\mathcal{O}\left(n^{1.5}\right)$. For large $n$, this requirement can still be high.
\end{comment}

\subsection{Notations}
The inner product $\left\langle A, B \right\rangle = \textup{Tr}\left(A^TB\right)$ denotes the matrix inner product and $\| A \|_F^2 = \langle A, A\rangle$ is the Frobenius norm. Unless otherwise specified, $\| \cdot \|$ represents Euclidean norm for vectors. For a matrix $X$, $\textup{diag}(X)$ represents a vector of the diagonal entries of matrix $X$. For a vector $x$, $\textup{diag}^*(x)$ represents a diagonal matrix with the entries of $x$ on the diagonal. The vector $\mathbbm{1}$ has each element value equal to one. The notation $\nabla g(\cdot)$ is used to denote the gradient and $\nabla^2g(\cdot)$ is used to denote the Hessian of a twice differentiable function $g$. We use $\mathcal{A}(\cdot):\mathbb{S}^n\rightarrow \mathbb{R}^d$ to denote a linear mapping of a symmetric $n\times n$ matrix to a $d$-dimensional space and $\mathcal{A}^*(\cdot):\mathbb{R}^d\rightarrow \mathbb{S}^n$ to denote its adjoint. The notation $\succeq$ denotes the semidefinite order. The notation $\lambda_{\textup{max}}(\cdot)$ is used to denote the largest eigenvalue of a matrix. The notations $\mathcal{O}, \Omega, \Theta$ have the usual computer science complexity interpretation.

\subsection{Outline}
The paper is organized as follows. In Section~\ref{Sec:Prelimnaries}, we discuss standard results related to the Frank-Wolfe algorithm. These form the basis of algorithms and analysis discussed later. In Section~\ref{Sec:Methodology}, we present the idea of sampled solutions to SDPs, and provide a modified version of Frank-Wolfe that generates such sampled solutions. In Section~\ref{Sec:MaxCut}, we apply our algorithm to generate sampled solutions to~\eqref{prob:relaxedMC}. We also show how to round this sampled solution to give an implementation of the Goemans-Williamson method that requires $\mathcal{O}(n)$ working memory. In Section~\ref{Sec:Applications} we discuss an extension of the idea of sampled solutions to SDPs to a more general setting in which the feasible solution is no longer required to be a trace constrained PSD matrix. We propose a modification of the Frank-Wolfe algorithm that generates a random extreme point of the feasible region, such that the expectation of the generated random solution is near-optimal. In Section~\ref{sec:PostProc}, we discuss how to obtain other approximations of the solution of structured convex programs by combining our sampled representations with streaming algorithms. Section~\ref{Sec:Conclusion} discusses further possible extensions of our work and briefly presents preliminary numerical experiments.


TITLE: A word problem on probability
QUESTION [3 upvotes]: I'm doing some probability exercise and I got stuck.
This is the problem:
I have the average length of a pipe in a set of pipes: 14.5cm. Then I know that the pipes follow a normal law.
I must calculate the standard deviation knowing that the probability to find pipes of length between 11.3cm and 14.5cm is 25%.
Also I need to calculate the probability that a casual pipe taken from 70 pipes taken from the original set of pipes, has the average length less then 13.2cm.
I did the following things to find the standard deviation:
$$P(11.3<x<14.5)=0.25=P(x<14.5)-P(x<11.3)$$
$$P(x<14.5)=0.5$$
$$P(x<11.3)=0.25=P(z<\frac{11.3-14.5}{\sigma})=P(z<\frac{-3.2}{\sigma})$$
$$P(z<\frac{-3.2}{\sigma})=1-P(z>\frac{3.2}{\sigma})$$
$$P(z>\frac{3.2}{\sigma})=0.75$$
So $z\simeq0.68$ looking on the table; then $\sigma=4.7$.
Is what I did logically correct? Looking at the draw that I did it should be right.
What I need to do to proceed? I tried to calculate $P(x<13.2)$ but this don't give me what the exercise ask.

REPLY [1 votes]: Your calculation in $a)$ looks right to me. My standard deviation with more decimal places is  $σ=4.7478$.
As I understand it. In $b)$ you take a sample with a size of $70$. The sizes of the  pipes are independent. Thus you have 70 independent and identically distributed random variables.
The average of the sample is distributed as $\overline X\sim\mathcal N\left(\mu, \frac{\sigma^2}{n}\right)=\mathcal N\left(14.5, \frac{4.7478^2}{70}\right)   $
Thus $P(\overline X <13.2)=\Phi\left( \frac{13.2-14.5}{\sqrt{\frac{4.7478^2}{70}}} \right) $


text:
{\bf Problem.} Find the greatest value of $a$ such that $a^2-10a+21 \le 0$.
{\bf Level.} Level 2
{\bf Type.} Algebra
{\bf Solution.} We factor the quadratic, getting $(a-7)(a-3) \le 0$. The expression is equal to $0$ when $a=7 \text{ or } 3$. When $a \le 3$ or $a \ge 7$, the quadratic is positive, since the two factors have the same sign. When $3 \le a \le 7$, the quadratic is non-positive. Therefore, $a=\boxed{7}$ is the greatest value of $a$ for which $a^2 - 10a + 21\le 0$.

set_name: MATH


TITLE: Graph with two strongly connected components
QUESTION [0 upvotes]: Let there be two strongly connected components in directed graph $G$. It is known that the basis of graph $G$ is connected and it does not have bridges. Prove that there exists such edge that if we change its direction, then graph $G$ will become strongly connected.
I did my best to translate the problem from Swedish to English so let me know if the problem is not clear enough. We just started learning directed graphs so any help is greatly appreciated.

REPLY [2 votes]: I take it that the basis of $G$ is the underlying undirected graph.  That is, $G$ with the orientation of the edges removed. Say the two strongly connected components are $S$ and $T$.  Since the basis is connected there must be an edge joining a vertex in $S$ and a vertex in $T$.  WLOG we may say $e=st,$ where $s\in S,t\in T$.  If $e$ were the only edge between $S$ and $T$ it would be a bridge in the basis, so there is another such edge $f$.  If $f=\tau\sigma,\tau\in T,\sigma\in S$, then $G$ is strongly connected, so $f$ also goes from $S$ to $T$.  Changing the direction of either $e$ or $f$ would make $G$ strongly connected.


TITLE: What is the formula for conversion ratio?
QUESTION [1 upvotes]: I got a simple math problem.I am trying the find the conversion ratio between two symbol.Let assume that

A : B
1 : 100 (1 A = 100 B)
A : C
1 : 300 (1 A = 300 C)
B : C
1 : ? (1 B = ? C)

What is the C equivalent of 1 B? and what is the formula used to calculate such problem? I wanted to find the r value.

B value X r = C value

REPLY [1 votes]: For each A you get $100$ B and $300$ C


TITLE: Need help with finding all angles of 11 sided 3D object
QUESTION [3 upvotes]: Question: I'm an artist trying to build a hendecahedron for a project (Image below to see the shape). This object consists of 5 pentagons at the base, 1 pentagon on the bottom, then 5 quadrilaterals on top as the spire that all conjoin at at a point. Can anyone show me a re-usable formula to calculate the angles and lengths of one of the quadrilaterals in the spire given only the length of one side of the pentagons at the base and the size of the pentagon on the bottom and the height I want the spire to be ? lets say each side of one of the bottom pentagrams is one foot.
Here is an image of the Object I am trying to recreate:

Details:
I want to re-create a shape similar to the image above no matter how big I chose to make the pentagons on the base or how tall I choose to make the spire. I plan on cutting each face out in cardboard first then fashioning them all together. which is why I need a formula(s) to plug in the length of one hexagon and the height of the spire to give me the angles and lengths of the quadrilaterals I will need to cut out in 2D.
if anyone can point me in the right direction or give me specific dimensions and angles for each face of an object that comes close to that object it would be very very very much appreciated.
Thank you so much for reading and helping me with my project if you choose to do so. I am not a math person, I am leaning on a high school education, I hope my terminology is accurate to the photo.

REPLY [9 votes]: There is a problem in the design,
if I understand the phrases "the height I want the spire to be"
and "how tall I choose to make the spire":
these suggest there is freedom to choose the spire height.

Those quadrilaterals incident to the apex $a$ are not flat for all
apex heights $z$:

In general there is a crease along the edge $ac$;
the segment $bd$ is slightly inside the polyhedron.
The crease sharpens as $z$ increases.
So, for a given pentagon edge-length, there is just one $z$ for which the quadrilaterals are flat:
the $z$ achieved by extending the five faces surrounding the top
pentagon of a dodecahedron, as per @user347489's comment.
If the regular pentagon edges are of length $1$,
I calculate $z=3.6034$ above the base,
the distance from $a$ to $b$ is $|ab|=2.61803$,
and the four quadrilateral angles are $108^\circ, 108^\circ, 108^\circ, 36^\circ$.


TITLE: How many three-character initials are possible using upper-case letters, a space, and four punctuation marks?
QUESTION [0 upvotes]: When a new high score is achieved in in a classic video game, the player is given the option to enter three initials on the leaderboard. The three initials can be any letter ( capital only), a space, and any of these punctuation marks : period, comma, colon, hyphen. the player may repeat any initial space or punctuation mark. how many initials are possible?

I believe since the order doesn't matter, I would set this up as combination? I'm not confident on how to find the solution for this homework problem

REPLY [1 votes]: Short Answer:
Your answer is correct. In general, permutations are used when order does matter, and combinations are used when order doesn't matter. However, people still often confuse permutation and combinations while knowing this.
In your problem, the order does matter. For example, ABC is certainly different than CBA. Additionally, repetition is allowed in your problem. You can have the initials, AAB or AAA. Therefore, you can use the formula for permutations with repetition where $n$ is the number of things to choose from and $r$ is how many we choose. This is given by
$$n^r = 31^3 = 29791$$
Long Answer: Regardless, I think it is not necessarily helpful to just look up equations. It is more useful to attempt to derive the equation that you need for your problem. For example, you know you have $31$ things, so you know there are $31$ different ways to choose the first character.
What about the second character? Well, for each option for the first character, there are $31$ ways for you to choose the second character. This is equivalent to $31 \times 31$, or you may think of it as $31 + 31 + 31 \cdots$ up to $31$ additions.
Now, what about the third character? Well, this is similar as before, we have $31 \times 31$ options for the first two characters as we just worked out. For each of these options, we have $31$ options for the third character. Therefore, we have $31 \times 31 \times 31$, or can think of it as $(31 \times 31) + (31 \times 31) \cdots$ up to $31$ additions.


TITLE: $\mathbb{Z}/2\otimes_{\mathbb{ Z}} \mathbb{ Z}$
QUESTION [0 upvotes]: What is the tensor product of $\mathbb{Z}/2$ and $\mathbb{ Z}$ considered as $\mathbb{ Z}$-modules? That is I want to calculate $\mathbb{Z}/2\otimes_\mathbb{ Z} \mathbb{ Z}$. Is it 0?

REPLY [3 votes]: As Stefano says in the comments, for a ring $A$ and an $A$-module $M$, you alwys have $A \otimes_A M \approx M$ via the map $a \otimes m \mapsto am$.
So, in particular, you always have $\mathbb Z/n \otimes_{\mathbb Z} \mathbb Z \approx \mathbb Z/n$.


TITLE: Parametrize a curve with respect to arc length
QUESTION [1 upvotes]: “It is often useful to parametrize a curve with respect to arc length because arc length arises naturally from the shape of the curve and does not depend on a particular coordinate system.” Quoted from Jim Stewart Calculus, Early Transcendentals, fourth edition, page 850
I understand why arc length does not depend on a particular coordinate system, but what does it mean to say that it “arises naturally” from the shape of a curve?

REPLY [2 votes]: In short, this is a comment that is best understood in contexts, yet less so by itself and in general. See below.

Let's start in general.
Arclength of an arbitrary (continuous) curve $f\in\mathcal{C}([a,b],X)$ is typically defined as
$$
\text{arc length}=\sup_{\text{all partitions }\mathcal{P}}\sum_{i=1}^N||f(x_i)-f(x_{i-1})||=:L([a,b]) \quad...(1)
$$
where $\mathcal{P}=\{ a=x_0\leq\cdots\leq x_N=b\}$ and $X$ is a metric space, for example $\mathbb{R}^n$.
If you are more in the physical sciences instead of mathematics, you may interpret (1) as going along the curve in discrete and finite number of steps while summing the straight line distances traversed these steps, and the arc length is the "least upper bound", or maximum distance you obtain.
See picture below from Wikipedia.

Based on (1), you can prove that $L([a,t_1])\leq L([a, t_2])\quad\forall a\leq t_1\leq t_2\leq b$. In other words, as you travel from one end of the curve to another, the length of the curve segment you travel so far can only increase.
As a result, the map $\mathcal{l}(t)=L([a,t])$ is a valid function. If the curve is nice, $l$ may be bijective, in which case you can recover a point on the curve by its distance on the curve from origin $a$ via $f(l^{-1}(\text{distance}))$. That is to say your curve can be parametrized by its arc length.
Let me stress again: the curve has to be nice. And Stewart did say "often".
For example, a circle in $\mathbb{R}^2$ can be considered as the image of $f\in\mathcal{C}([0,2\pi],\mathbb{R}^2)$ where $f(t)=(\cos t,\sin t)$. Points on the circle can be parameterized by distance from $(1,0)$ on the circle. The conversion from distance to Cartesian coordinates is given by $f(\text{distance})$. Here $l(t)=t$. And the form of $l$ arises from the fact that $f$ traces out a unit circle.
In this context, Stewart's words "arises naturally from the shape of the curve" has good meaning.
Now, the distance function $x,y\rightarrow||x-y||$ on $X$ does not depend on the coordinate system. So $L$ is coordinate in-dependent. (To have a (local) coordinate system means to have a (local) homeomorphism to $\mathbb{R}^n$.)

At the end, let me share my idea of why definition (1) has a good physical meaning.
Note that when we say curve, we really mean the image set under function $f$, namely the set $C=\{f(x)|x\in[a,b]\}$. Consider any finite sample $P=\{y_i\}_{i=0}^N$ of the set $C$. ie. $P\subseteq C, |P|<\infty$.
Join the sample points by "straight" lines. Then the sum lengths of these straight line segments must be smaller than or equal to the length of the curve, should the notion of length make sense. That is
$$
\sum_{i=1}^N||y_i-y_{i-1}||\leq L<\infty
$$
Therefore, this "arc length" $L$ provides an upper bound to all possible sum lengths produced by finite sampling of the curve followed by linear interpolation. Any bounded set of the reals has a least upper bound (aka supremum). Hence the definition of arc length (1).
Now the we have the definition, we recognize that supremum can be infinity and consequently $L$ can be $\infty$. So we are allowed to have curves that does not have a finite length (or depending on your taste, a well-defined length). But the use of supremum allows us to define "arc length" on any curve.


TITLE: Bousfield-Kan: Cosimplicial Replacement of a fibration of diagrams is a fibration?
QUESTION [4 upvotes]: I've been working through Bousfield and Kan's book on Homotopy Limits for background work on my dissertation, and there is a statement that I've just not been able to solve (and my adviser doesn't really know how to fix the issue that I'm running into).  I'll try and be brief about my question, since it is a bit involved.  The statement I'm attempting to prove is this:
Chapter XI, Sect. 5, Proposition 5.3: Let $f: X \longrightarrow X'$ in $\mathcal{C}^{\mathcal{I}}$ be a morphism of diagrams such that $f_i : X_{i} \longrightarrow X'_{i}$ if a fibration for every $i \in \mathcal{I}$.  Then if we apply cosimplicial replacement $\Pi^{\*}$, we have that $\Pi^{\*}(f): \Pi^{\*}X \longrightarrow \Pi^{\*}X'$ is a fibration of cosimplicial objects over $\mathcal{C}$.
So my question is simply this: How do we prove this statement?
Here are some of my thoughts:
Recall that the fibrations in the category of cosimplicial objects over $\mathcal{C}$ are morphisms $f: X \longrightarrow Y$ such that $(f^{n+1},s_{n}^{X}) : X^{n+1} \longrightarrow Y^{n+1} \times _{M^{n}Y} M^{n}X$ are all fibrations in $\mathcal{M}$ for all $n \ge -1$.  Here $M^{n}X$ is the set of all tuples $(x^{0}, x^{1}, ..., x^{n}) \in X^{n} \times \cdots \times X^{n}$ such that $s^{i}x^{j}=s^{j-1}x^{i}$ for $0 \leq i < j \leq n$.  (I've included this since this definition of matching space seems non-standard; it is not quite the same as the one given in Hirschhorn).
My idea has been to try and realize each morphism as a retract of a known fibration. Using the shorthand $X^{n+1}=(\Pi^{\*}(X))^{n+1}$, $Y^{n+1}=(\Pi^{\*}(Y))^{n+1}$, $M^{n}X=M^{n}(\Pi^{\*}(X))$ to denote the matching space (and similarly for $M^{n}Y$), and $Z  =  X^{n+1} \times_{Y^{n+1}} (Y^{n+1} \times_{M^{n}Y} M^{n}X)$, I can get the diagram with top row $X^{n+1} \longrightarrow Z \longrightarrow X^{n+1}$ where the first of these maps is a universal map for pullbacks and the second of these is just projection onto the first coordinate; and bottom row $Y^{n+1} \times_{M^{n}Y} M^{n}X \longrightarrow Y^{n+1} \times_{M^{n}Y} M^{n}X \longrightarrow Y^{n+1} \times_{M^{n}Y} M^{n}X$ where both maps are the identity.  The vertical maps on the left and right are $f: X^{n+1} \longrightarrow Y^{n+1} \times_{M^{n}Y} M^{n}X$ where $f = (\alpha^{n+1},s_{n}^{X})$ (here $\alpha^{n+1} : X^{n+1} \longrightarrow Y^{n+1}$ and $s_{n}^{X}: X^{n+1} \longrightarrow M^{n}X$ is the natural map for matching spaces).  This map $f$ is the map I want to show is a fibraion.  The middle vertical map is just projection onto the second coordinate.
This gives me a possible retract diagram (I'm sorry it's so poorly described; I don't know how to get diagrams to work on this site).  The left square commutes by construction (although I have brushed over a lot of the construction), but the right square does not, or at least not necessarily.  It's here that I'm a bit lost...
In any event, does anyone know the full proof of the statement I gave above?  Am I on the right track?  And if not, what approach should I be taking?
Thank you so much!

REPLY [5 votes]: First I would like to refer you Goerss and Jardine's book "Simplicial homotopy theory" as an alternative resource, with modern typesetting. In particular, Example VII.4.2 gives a construction of the cosimplicial replacement from Bousfield-Kan and there is a very helpful discussion in VIII.2.
The cosimplicial replacement of a diagram $F:J\rightarrow \mathcal C$ produces a codegeneracy free cosimplicial object $X^\bullet$. In particular, $X^{n}=Z^nX\times M^{n-1}X$ where
\begin{equation}
Z^nX(j)=\prod_{f\in J_n} F(\mathrm{target}f)
\end{equation} where $J_n$  is the set of all $n+1$ composable arrows in $J$, with the first arrow originating at $j$ and none of which are the identity. The matching object can be identified with those arrows that have at least one identity morphism.
Now switching to your notation we are trying to see if the map:
\begin{equation}
X^{n+1}\cong Z^{n+1}X \times M^n X\rightarrow Y^{n+1}\times_{M^n Y} M^n X\cong Z^{n+1}Y\times M^n X
\end{equation}
is a fibration. The map is the identity on $M^n X$ and the map $Z^{n+1} X\rightarrow Z^{n+1} Y$ is just the product, indexed as above, of levelwise fibrations, hence a fibration. Note it is also easy to see that this construction takes levelwise weak equivalences to weak equivalences.


TITLE: Gauss Jordan elimination problem.
QUESTION [0 upvotes]: I am reading about Gauss Jordan elimination and this makes sense:

We want 0s about every leading 1 which seems to make determining the variables a lot easier.
But how does this one work? I can't seem to figure out the intermediate steps:

It looks like to start the 4th row is swapped with the first.

REPLY [1 votes]: In my post here I describe an algorithm which will guarantee that you reach RREF.  (Side note: this isn't the algorithm that computers use, but it is similar)
As mentioned in comments above, there are many different sequences of steps you can take to row reduce a matrix completely, but the final result of any row reduction will be exactly the same.  That is to say that you may if you wish begin the row reduction process for your specific example with swapping the fourth and first rows and that will still be a fine beginning (though you might not have known ahead of time that this was a particularly useful thing to do).
Following the algorithm I link strictly to a t for your specific matrix begins:
$\begin{bmatrix}\color{red}1&1&0&0&0&20\\0&0&1&-1&0&-20\\0&1&1&0&0&20\\1&0&0&0&-1&-10\\0&0&0&-1&1&-10\end{bmatrix}$
We first check that the first-row first-column entry (marked in $\color{red}{red}$) is nonzero.  It is!  On to the next step... we check that it is equal to $1$  It is!  Now, we zero out everything else in its column by subtracting appropriate multiples of the first row from other rows as necessary.
$R_4-R_1\mapsto R_4$
$\begin{bmatrix} \color{red}{1}&1&0&0&0&20\\\color{blue}0&0&1&-1&0&-20\\\color{blue}0&1&1&0&0&20\\\color{blue}0&-1&0&0&-1&-30\\\color{blue}0&0&0&-1&1&-10\end{bmatrix}$
Now that that column is taken care of, we can move our attention to the next pivot location, marked below in $\color{red}{red}$.
$\begin{bmatrix} 1&1&0&0&0&20\\0&\color{red}0&1&-1&0&-20\\0&1&1&0&0&20\\0&-1&0&0&-1&-30\\0&0&0&-1&1&-10\end{bmatrix}$
We ask the question of it it is zero.  It is unfortunately.  We then ask the question of if there are any nonzero entries from the same column below it.  There is, for example in the third row.  We swap the rows then.
$R_2\leftrightarrow R_3$
$\begin{bmatrix}1&1&0&0&0&20\\0&\color{red}1&1&0&0&20\\0&0&1&-1&0&-20\\0&-1&0&0&-1&-30\\0&0&0&-1&1&-10\end{bmatrix}$
We then ask the question of if the pivot we are focusing on currently is equal to $1$.  It is!  Now, we subtract appropriate multiples of that row from other rows in an attempt to zero out the rest of the pivot's column.
$R_1-R_2\mapsto R_1$
$R_4+R_2\mapsto R_4$
$\begin{bmatrix}1&\color{blue}0&-1&0&0&0\\0&\color{red}1&1&0&0&20\\0&\color{blue}0&1&-1&0&-20\\0&\color{blue}0&1&0&-1&-10\\0&\color{blue}0&0&-1&1&-10\end{bmatrix}$
Continue in this fashion, positioning pivot points from left-to-right and clearing out all other entries in the columns to be zero, swapping rows if necessary to get a nonzero entry in the pivot location, dividing or multiplying rows to get pivot positions equal to $1$ rather than some other nonzero number, or even skipping columns entirely if no nonzero entry can act as a pivot for that column.


TITLE: Can an abelian group be turned into two nonisomorphic vector spaces by different actions of the same field?
QUESTION [3 upvotes]: I was wondering if you could find an abelian group and define two different actions of a field on it such that the resulting vector spaces are of different dimensions over the field.
I tried various extensions of $\mathbb Q$. Now, since the set $V$ is already an abelian group, the action of $\mathbb Z$, and therefore $\mathbb Q$, are already determined. So I tried $\mathbb Q(\alpha)$, but I got stuck here too: if $\alpha$ is algebraic, then its action is restricted to satisfy its polynomial, so the vector spaces would still be isomorphic. If $\alpha$ is transcendental, I tried having it act trivially, but that doesn't work since it's impossible to extend this to rational functions in $\alpha$, as is required.
Is what I'm trying to do even possible? If so, could I have some hints on an example?

REPLY [3 votes]: Consider $\mathbb{R}$ and $\mathbb{R}^2$. As $\mathbb{Q}$-vector spaces they have the same dimension, so they are isomorphic as abelian groups a fortiori. Of course, they are not isomorphic as $\mathbb{R}$-vector spaces.


TITLE: proving that $89 \mid 2^{44}-1$
QUESTION [1 upvotes]: i tried to prove that $2^{44} \equiv 1\pmod{89}$.
I noticed that by Fermat's little theorem $2^{88} \equiv 2^{44}\cdot 2^{44} \equiv 1\pmod{89}$
which means that $2^{44}$ is the inverse of itself $\rightarrow 2^{44} \equiv 1 \pmod{89}$ or $2^{44}\equiv 88 \pmod{89}$.
how can I rule out the second option?

REPLY [1 votes]: $2^{44} - 1 = (2^{22})^2 - 1 = (2^{22}+1)(2^{22} - 1) = (2^{22}+1)(2^{11} + 1)(2^{11} - 1) = (2^{22}+1)(2^{11} + 1)\times 2047 = (2^{22}+1)(2^{11} + 1)\times 23 \times 89$