# More on homotopy continuation method and discounted zero-sum stochastic game
with ARAT structure

A. Duttaa,1 and A. K. Dasb,2
_a Department of Mathematics, Jadavpur University, Kolkata, 700 032, India_
_b SQC & OR Unit, Indian Statistical Institute, Kolkata, 700 108, India_
_1 Email<EMAIL_ADDRESS>
_2 Email<EMAIL_ADDRESS>

###### Abstract

In this paper, we introduce a homotopy function to trace the trajectory by
applying modified homotopy continuation method for finding the solution of
two-person zero-sum discounted stochastic ARAT game. We show that the
algorithm has the higher order of convergence. For the proposed algorithm, the
homotopy path approaching the solution is smooth and bounded. Two numerical
examples are illustrated to show the effectiveness of the proposed algorithm.
Keywords: Two-person zero-sum stochastic game, discounted ARAT stochastic
game, homotopy method, optimal value, optimal stationary strategy.

AMS subject classifications: 91A05, 91A15, 90C33, 90C30, 14F35.

11footnotetext: Corresponding author

##  Introduction

In this paper, we consider two-person zero-sum discounted stochastic ARAT
game. Shapley [37] introduced stochastic game and showed that there exist an
optimal value and optimal stationary strategies for a stochastic game with
discounted payoff, which depends only on the current state and not on the
history. There are many applications of stochastic games like search problems,
military applications, advertising problems, the traveling inspector model,
and various economic applications. For details see [10]. There are significant
research on theoretical as well as computational aspects of stochastic games.
For details see [38], [36], [35],[39],[40]. Raghaban et al. [36] studied
ARAT(Additive Rewards Additive Transition) games and showed that for a
$\beta$-discounted zero-sum ARAT game, the value exists and both players have
stationary optimal strategies, which may also be taken as pure strategies. A
stochastic game is said to be an Additive Reward Additive Transition game
(ARAT game) if the reward and and the transition probabilities satisfy

(i) $r(s,i,j)=r^{1}_{i}(s)+r^{2}_{j}(s)$ for $i\in A_{s},j\in B_{s},s\in S.$
(ii) $p_{ij}(s,s^{\prime})=p^{1}_{i}(s,s^{\prime})+p^{2}_{j}(s,s^{\prime})$
for $i\in A_{s},j\in B_{s},(s,s^{\prime})\in S\times S.$

We denote the matrix $((p^{1}_{i}(s,s^{\prime}),s,s^{\prime}\in S,i\in
A_{s})))$ as $P_{1}(s)$ where $S$ is the set of states. This is a
$m_{1}(s)\times d$ matrix where $m_{1}(s)$ is the cardinality of $A_{s}$ and
$d$ is the cardinality of $s$. Similarly the matrix $P_{2}(s)$ of order
$m_{2}(s)\times d$ is defined where $m_{2}(s)$ denotes the cardinality of the
set $B_{s}$. The Shapley equations for state $s,s^{\prime}\in S$ can be stated
as

$\,\,\,\,\,\,\,\text{Val}[r(s,i,j)+\beta\sum_{s^{\prime}}p_{ij}(s,s^{\prime})v_{\beta}(s^{\prime})]=v_{\beta}(s).$

This implies for player I: For any fixed $j$

$r(s,i,j)+\beta\sum_{s^{\prime}}p_{ij}(s,s^{\prime})v_{\beta}(s^{\prime})\leq
v_{\beta}(s)\ \ \forall\ i.$ (1.1)

For playeer II: For any fixed $i$

$r(s,i,j)+\beta\sum_{s^{\prime}}p_{ij}(s,s^{\prime})v_{\beta}(s^{\prime})\geq
v_{\beta}(s)\ \ \forall\ j$ (1.2)

Various approaches have been proposed for solving different classes of
stochastic games. One such approach is to formulate the ARAT game as
complementarity problem. The well-known Lemke’s algorithm solves LCPs when the
underlying matrix class belongs to a particular class. Cottle and Dantzig[4]
extended Lemke’s algorithm to VLCPs. The processability of Lemke’s algorithm
and Cottle-Dantzig’s algorithm is restricted on some classes of matrices. For
details see [7],[12]. One sufficient condition for Lemke-processibility and
Cottle-Dantzig processibility is that the underlying matrix should be both
$E_{0}$ and $R_{0}$ matrix [17],[24],[34].

The concept of a class of globally convergent methods[42], known as the
homotopy continuation method is used to prove the existence of solutions to
many economic and engineering problems such as systems of nonlinear
equations[8], nonlinear optimization problems, fixed point problems, nonlinear
programming, game problem and complementarity problems [43]. In this paper, we
introduce a homotopy function to solve discounted zero sum stochastic ARAT
game based on the modified homotopy continuation method and establish the
higher order global convergence of the homotopy method.

The paper is organized as follows. Section 2 presents some basic notations and
results which will be used in the next section. In section 3, we propose a new
homotopy function to find the solution of discounted zero sum stochastic ARAT
game. We show that the proposed homotopy function possesses a smooth and
bounded homotopy path to find the solution as the homotopy parameter $t$ tends
to $0$. To find the solution of homotopy function we modify predictor
corrector steps to increase the order of convergency of the algorithm. We also
find the sign of the positive tangent direction of the homotopy path. Finally,
in section 4, we illustrate numerical examples of ARAT stochastic games to
present the effectiveness of the introduced homotopy function.

##  Preliminaries

We begin by introducing some basic notations used in this paper. We consider
matrices and vectors with real entries. $R^{n}$ denotes the $n$ dimensional
real space, $R^{n}_{+}$ and $R^{n}_{++}$ denote the nonnegative and positive
orthant of $R^{n}.$ We consider vectors and matrices with real entries. Any
vector $x\in R^{n}$ is a column vector and $x^{T}$ denotes the row transpose
of $x.$ $e$ denotes the vector of all $1.$ If $A$ is a matrix of order $n,$
$\alpha\subseteq\\{1,2,\cdots,n\\}$ and
$\bar{\alpha}\subseteq\\{1,2,\cdots,n\\}\setminus\alpha$ then
$A_{\alpha\bar{\alpha}}$ denotes the submatrix of $A$ consisting of only the
rows and columns of $A$ whose indices are in $\alpha$ and $\bar{\alpha}$
respectively. $A_{\alpha\alpha}$ is called a principal submatrix of A and
det$(A_{\alpha\alpha})$ is called a principal minor of $A.$ In this paper we
consider the followings:

$\mathcal{R}=\\{x\in R^{n}:x>0,Ax+q>0\\}$

$\mathcal{\bar{R}}=\\{x\in R^{n}:x\geq 0,Ax+q\geq 0\\}$

$\mathcal{R}_{1}=\mathcal{R}\times R_{++}^{n}\times R_{++}^{n}$

$\mathcal{\bar{R}}_{1}=\mathcal{\bar{R}}\times R_{+}^{n}\times R_{+}^{n}.$

$\partial{\mathcal{R}_{1}}$ denotes the boundary of $\bar{\mathcal{R}_{1}}.$

###  Linear Complementarity Problem and its Generalization

The linear complementarity problem [28] is defined as follows: Given square
matrix $A\in R^{n\times n}$ and a vector $\,q\,\in\,R^{n},\,$ the linear
complementarity problem is to find $w\in R^{n}$ and $x\in R^{n}$ such that

$w-Ax=q,w\geq 0,\,x\geq 0,$ (2.1) $x^{t}w=0.$ (2.2)

This problem is denoted as LCP$(q,A).$ Several applications of linear
complementarity problems are reported in operations research [34], multiple
objective programming problems [16], mathematical economics and engineering.
For details see [9], [18], [14] and [15]. The linear complementarity problem
is well studied in the literature of mathematical programming and arises in a
number of applications in operations research, control theory, mathematical
economics, geometry and engineering. For recent works on this problem and
applications see [6], [25], [31] and [30] and references therein. In
complementarity theory several matrix classes are considered due to the study
of theoretical properties, applications and its solution methods. For details
see [14], [15], [19], [18], [29] and [27] and references cited therein. The
problem of computing the value vector and optimal stationary strategies for
structured stochastic games is formulated as a linear complementary problem
for discounted and undiscounded zero-sum games. For details see [23], [33] and
[26].

####  Vertical Linear Complementarity Problems

Cottle and Dantzig [5] extended the linear complementarity problem to a
problem in which the matrix $A$ is not a square matrix. The generalization of
the linear complementarity problem introduced by them is given below: Consider
a vertical block matrix $A\in R^{m\times k}(m\geq k),$
$A=\left[\begin{array}[]{c}A_{1}\\\ A_{2}\\\ A_{3}\\\ \vdots\\\
A_{k}\end{array}\right]$ such that $A_{j}\in R^{m_{j}\times k},1\leq j\leq
k,\sum_{j=1}^{k}m_{j}=m.$ This matrix is called vertical block matrix of type
$(m_{1},m_{2},\cdots m_{k})$ and consider $q\in R^{m}$ where
$m=\sum_{j=1}^{k}m_{j},$ the generalized linear complementarity problem is to
find $w\in R^{m}$ and $x\in R^{k}$ such that

$w-Ax=q,w\geq 0,x\geq 0,$ (2.3)
$x_{j}\prod_{i}^{m_{j}}{w^{i}}_{j},j=1,2,\cdots k.$ (2.4)

This generalization is known as vertical linear complementarity problem and
denoted by VLCP$(q,A)$. For further details see [5]. The vertical block matrix
arises naturally in the literature of stochastic games where the states are
represented by the columns and actions in each state are represented by rows
in a particular block. For details see [20], [22].

An equivalent square matrix $M$ can be constructed from a vertical block
matrix $A$ of type $(m_{1},...,m_{k})$ by copying $A._{j},m_{j}$ times for
$j=1,2,\cdots,k.$ Therefore $M._{p}=A._{j}$ $\forall p\in J_{j}$ . LCP$(q,M)$
is called as equivalent LCP of VLCP$(q,A)$. For more details see [22], [32].
Mohan et al. [22] proposed techniques to convert a VLCP to an LCP and also
showed that processibility conditions as well. Mohan et al.[21] formulated
zero-sum discounted Additive Reward Additive Transition (ARAT) games as a
VLCP.

######  definition 2.1:

[21] $A$ is said to be a vertical block $E(d)$-matrix for some $d>0$ if
VLCP$(d,A)$ has a unique solution $w=d,z=0.$

######  definition 2.2:

[21] A is said to be a vertical block $R_{0}$-matrix if VLCP$(0,A)$ has a
unique solution $w=0,z=0.$

We denote the class of vertical block $E(d)$ matrices as VBE$(d)$ the class of
vertical block $R_{0}$ matrices by VB$R_{0}$.

###  Discounted Stochastic Game with the Structure of Additive Reward and
Additive Transition

Consider a state space $S=\\{1,2,\cdots,N\\}$. For each $s\in S,$ consider the
finite action sets $A_{s}=\\{1,2,...,m_{s}\\}$ for Player I and
$B_{s}=\\{1,2,...,n_{s}\\}$ for Player II. For state $s\in S$ a reward law
$R(s)=[r(s,i,j)]$ is an $m_{s}\times n_{s}$ matrix whose $(i,j)$th entry is
the payoff from Player II to Player I when Player I chooses an action $i\in
A_{s}$ and player II chooses an action $j\in B_{s},$ while the game is being
played in state $s$ and the payoff from player I to player II is $-r(s,i,j).$
Let $p_{ij}(s,s^{\prime})$ denotes the probability of a transition from state
$s$ to state $s^{\prime},$ given that Player I and Player II choose actions
$i\in A_{s},j\in B_{s}$ respectively. Then transition law is defined by

$p=(p_{ij}(s,s^{\prime}):(s,s^{\prime})\in S\times S,i\in A_{s},j\in B_{s}).$

Let the game be played in stages $t=0,1,2,\cdots.$ At some stage $t$, the
players find themselves in a state $s\in S$ and independently choose actions
$i\in A_{s},j\in B_{s}.$ Player II pays Player I an amount $r(s,i,j)$ and at
stage $(t+1)$, the new state is $s^{\prime}$ with probability
$p_{ij}(s,s^{\prime})$. Play continues at this new state. The players guide
the game via strategies and in general, strategies can depend on complete
histories of the game until the current stage. We are however concerned with
the simpler class of stationary strategies which depend only on the current
state $s$ and not on stages. So for Player I, a stationary strategy $k\in
K_{s}=\\{k_{i}(s)|s\in S,i\in A_{s},k_{i}(s)\geq 0,\sum_{i\in
A_{s}}k_{i}(s)=1\\}$ indicates that the action $i\in A_{s}$ should be chosen
by Player I with probability $k_{i}(s)$ when the game is in state $s$.
Similarly for Player II, a stationary strategy $l\in L_{s}=\\{l_{j}(s)|s\in
S,j\in B_{s},$ $l_{j}(s)\geq 0,\sum_{j\in B_{s}}l_{j}(s)=1\\}$ indicates that
the action $j\in B_{s}$ should be chosen with probability $l_{j}(s)$ when the
game is in state $s$. Here $K_{s}$ and $L_{s}$ will denote the set of all
stationary strategies for Player I and Player II respectively. Let $k(s)$ and
$l(s)$ be the corresponding $m_{s}$ and $n_{s}$ dimensional vectors
respectively. Fixed stationary strategies $k$ and $l$ induce a Markov chain on
$S$ with transition matrix $P(k,l)$ whose $(s,s^{\prime})$th entry is given by

$P_{ss^{\prime}}(k,l)=\sum_{i\in A_{s}}\sum_{j\in
B_{s}}p_{ij}(s,s^{\prime})k_{i}(s)l_{j}(s)$

and the expected current reward vector $r(k,l)$ has entries defined by

$r_{s}(k,l)=\sum_{i\in A_{s}}\sum_{j\in
B_{s}}r(s,i,j)k_{i}(s)l_{j}(s)=k^{t}(s)R(s)l(s)$ .

With fixed general strategies $k,l$ and an initial state $s$, the stream of
expected payoff to Player I at stage $t$, denoted by
$v^{t}_{s}(k,l),t=0,1,2,\cdots$ is well defined and the resulting discounted
payoff is $\phi^{\beta}_{s}(k,l)=\sum_{0}^{\infty}\beta^{t}v^{t}_{s}(k,l)$ for
a $\beta\in(0,1),$ where $\beta$ is the discount factor. Due to this additive
property assumed on the transition and reward functions, the game is called
$\beta$-discounted zero-sum ARAT(Additive Reward Additive Transition) game.
For futther details see [13], [36], [11].

######  theorem 2.1:

[10]For ARAT stochastic games
(i) Both players possess $\beta$ discounted optimal stationary strategies that
are pure.
(ii) These strategies are optimal for the average reward criterion as well.
(iii) The ordered field property holds for the discounted as well as the
average reward criterion.

Now we observe the following property of the additive components $P_{1}$ and
$P_{2}$ of the transition probability matrix $P.$ For details see [21].

######  lemma 2.1:

If $p^{2}_{j}(s,s^{\prime})=0$ for all $s^{\prime}\in S$ and for some $j\in
B(s)$, then $P_{2}(s)=0.$

######  theorem 2.2:

[21]Consider the vertical block matrix $A$ arising from the zero-sum ARAT
game. Then $A\in$ VB$E(e)$ where $e$ is the vector each of whose entries is
$1.$

######  theorem 2.3:

[21] Consider the vertical block matrix $A$ arising from zero-sum ARAT game.
Then $A\in$VB$R_{0}$ if either the condition $(a)$ or the set of conditions
$(b)$ stated below is satisfied.
$(a)$ For each $s$ and each $j\in B_{s},\ p^{2}_{j}(s,s)>0.$
$(b)\ \ (i)$ For each $s$, the matrix $P_{1}(s)$ does not contain any zero
column and

$\leavevmode\nobreak\ (ii)$the matrix $P_{2}(s)$ is not a null matrix.

###  Homotopy Continuation Method

The key idea to solve a system of equations by the homotopy method is to solve
$H(x,t)=0,$ where $H:R^{n}\times[0,1]\to R^{n},x\in R^{n},t\in[0,1]$ is called
homotopy parameter. The homotopy method aims to trace the entire path of
equilibria in $H^{-1}=\\{(x,t):H(x,t)=0\\}$ by varying both $x$ and $t.$ A
parametric path is obtained from a set of functions $(x(s),t(s))\in H^{-1}.$
When we move along the homotopy path, the auxiliary variable $s$ either
decreases or increases monotonically. Differentiating $H(x(s),t(s))=0$ with
respect to $s$ we obtain $\frac{\partial H}{\partial
x}x^{\prime}(s)+\frac{\partial H}{\partial t}t^{\prime}(s)=0,$ where
$\frac{\partial H}{\partial x}$ and $\frac{\partial H}{\partial t}$ are
$n\times n$ Jacobian matrix of $H$ and $n\times 1$ column vector respectively.
So this is a system of $n$ differential equations in $n+1$ unknowns
${x_{i}}^{\prime}(s)\ \forall\ i$ and $t^{\prime}(s).$ This system of
differential equations has many solutions for which the solutions of the
differential equations differ by monotone transformation of the auxiliary
variable $s.$ Now we state some results on homotopy which will be required in
the next section.

######  lemma 2.2:

[2] Let $V\subset R^{m}$ be an open set and $g:R^{m}\to R^{q}$ be smooth. We
say $y\in R^{q}$ is a regular value for $g$ if $\text{Range}\,Dg(x)=R^{q}$
$\forall x\in g^{-1}(y),$ where $Dg(x)$ denotes the $m\times q$ matrix of
partial derivatives of $g(x).$

######  lemma 2.3:

[41] Let $V\subset R^{n},U\subset R^{m}$ be open sets, and let $\xi:V\times
U\to R^{l}$ be a $C^{\alpha}$ mapping, where $\alpha>\text{max}\\{0,m-l\\}.$
If $0\in R^{l}$ is a regular value of $\xi,$ then for almost all $a\in V,0$ is
a regular value of $\xi_{a}=\xi(a,.).$

######  lemma 2.4:

[41] Let $\xi:V\subset R^{m}\to R^{q}$ be $C^{\alpha}$ mapping, where
$\alpha>\text{max}\\{0,m-q\\}.$ Then $\xi^{-1}(0)$ consists of some $(m-q)$
dimensional $C^{\alpha}$ manifolds.

######  lemma 2.5:

[44] One-dimensional smooth manifold is diffeomorphic to a unit circle or a
unit interval.

######  lemma 2.6:

[3] Let $f:R^{n}\to R^{n}$ be a sufficiently differentiable function in a
neighborhood $D$ of $\alpha,$ that is a solution of the system $f(x)=0,$ whose
Jacobian matrix is continuous and nonsingular in D. Consider the iterative
method $z^{k}=\phi(x^{k},y^{k}),\ w^{k}=z^{k}-f^{\prime}(y^{k})^{-1}f(z^{k}),$
where $y^{k}=x^{k}-f^{\prime}(x^{k})^{-1}f(x^{k})$ and
$z^{k}=\phi(x^{k},y^{k})$ is the iteration function of a method of order $p.$
Then for an initial approximation sufficiently close to $\alpha,$ this method
has order of convergence $p+2$.

######  lemma 2.7:

[3] Consider the function $f:R^{n}\to R^{n}$ and the iterative method
$y^{k}=x^{k}-f^{\prime}(x^{k})^{-1}f(x^{k}),$
$z^{k}=x^{k}-2(f^{\prime}(y^{k})+f^{\prime}(x^{k}))^{-1}f(x^{k}),\
w^{k}=z^{k}-f^{\prime}(y^{k})^{-1}f(z^{k})$ has $5$th order convergence.

##  Main results

In this section, we consider the two-person zero-sum discounted stochstic ARAT
game and introduce a homotopy continuation method to find the solution of the
discounted zero-sum ARAT game. We state that a pair of strategies
$(k^{\star},l^{\star})$ is optimal for Player I and Player II in the
discounted game if for all $s\in S$
$\phi_{s}(k,l^{\star})\leq\phi_{s}(k^{\star},l^{\star})=v^{\star}_{s}\leq\phi_{s}(k^{\star},l)$
for any strategies $k$ and $l$ of Player I and Player II. The number
$v^{\star}_{s}$ is called the value of the game starting in state $s$ and
$v^{\star}=(v^{\star}_{1},v^{\star}_{2},\cdots,v^{\star}_{N})$ is called the
value vector. To find the optimal strategy of player I and player II of the
two-person zero-sum discounted ARAT stochastic game we propose a new function
based on the concept of homotopy.

Let $X_{1},X_{2}$ be two topological spaces and $f_{1},f_{2}:X_{1}\to X_{2}$
be continuous maps. A homotopy from $f_{1}$ to $f_{2}$ is a continuous
function $H:X_{1}\times[0,1]\to X_{2},$ defined by
$H(x,t)=(1-t)f_{1}(x)+tf_{2}(x)$ satisfying $H(x,0)=f_{1}(x),$
$H(x,1)=f_{2}(x)\ \forall x\in X_{1}.$ The value of $t$ will start from $1$
and goes to $0$ and in this way one can find the solution of the given
equation $f_{1}(x)=0$ from the solution of $f_{2}(x)=0.$

$H(u,t)=\left[\begin{array}[]{c}(1-t)[(A+A^{T})x+q-y_{1}-A^{T}y_{2}]+t(x-x^{(0)})\\\
Y_{1}x-tY_{1}^{(0)}x^{(0)}+(1-t)X(Ax+q)\\\
Y_{2}(Ax+q)-tY_{2}^{(0)}(Ax^{(0)}+q)\\\ \end{array}\right]=0$ (3.1)

where $Y_{1}=\text{diag}(y_{1}),$ $X=\text{diag}(x),$
$Y_{2}=\text{diag}(y_{2}),$ $Y_{1}^{(0)}=\text{diag}(y_{1}^{(0)}),$
$Y_{2}^{(0)}=\text{diag}(y_{2}^{(0)}),$ $u=(x,y_{1},y_{2})\in R_{+}^{n}\times
R_{+}^{n}\times R_{+}^{n},$
$u^{(0)}=(x^{(0)},{y_{1}}^{(0)},{y_{2}}^{(0)})\in\mathcal{R}_{1},$ and
$t\in(0,1].$

###  Computing Solution of ARAT Stochastic Game based on Homotopy Continuation
Method

Now we show that the solution of the proposed homotopy function will give the
solution of discounted ARAT stochastic game.

######  theorem 3.1:

Suppose $\Gamma_{u}^{(0)}=\\{(u,t)\in
R^{3n}\times(0,1]:H(u,u^{(0)},t)=0\\}\subset\mathcal{R}_{1}\times(0,1]\\},$
and $\cal{A}=\left[\begin{array}[]{cc}-\beta P_{1}&E-\beta P_{1}\\\ -E+\beta
P_{2}&\beta P_{2}\\\ \end{array}\right]$ and
$q=\left[\begin{array}[]{c}-r^{1}_{i}(s)\\\ r^{2}_{j}(s)\\\
\end{array}\right],$ where the matrix $P_{1}=P_{1}(s),P_{2}=P_{2}(s)$ and
$E=\left[\begin{array}[]{ccccc}e_{1}&0&0&\cdots&0\\\ 0&e_{2}&0&\cdots&0\\\
\vdots&\vdots&\vdots&\cdots&\vdots\\\ 0&0&0&\cdots&e_{d}\\\
\end{array}\right]$ is a vertical block identity matrix where $e_{j},1\leq
j\leq d,$ is a column vector of all $1^{\prime}$s. Then the homotopy function
3.1 solves discounted zero-sum stochastic ARAT game.

###### Proof.

Suppose for a zero-sum discounted ARAT game the optimal pure strategy in state
$s$ is $i_{0}$ for Player I and $j_{0}$ for Player II.
Then the inequality 1.1 and the inequality 1.2 reduces to

$r^{1}_{i}(s)+r^{2}_{j_{0}}(s)+\beta\sum_{s^{\prime}}p^{1}_{i}(s,s^{\prime})v_{\beta}(s^{\prime})+\beta\sum_{s^{\prime}}p^{2}_{j_{0}}(s,s^{\prime})v_{\beta}(s^{\prime})\leq
v_{\beta}(s)\ \forall\ i.$ (3.2)
$r^{1}_{i_{0}}(s)+r^{2}_{j}(s)+\beta\sum_{s^{\prime}}p^{1}_{i_{0}}(s,s^{\prime})v_{\beta}(s^{\prime})+\beta\sum_{s^{\prime}}p^{2}_{j}(s,s^{\prime})v_{\beta}(s^{\prime})\geq
v_{\beta}(s)\ \forall\ j.$ (3.3)

The inequalities 3.2 and 3.3 yield
$r^{1}_{i}(s)+\beta\sum_{s^{\prime}}p^{1}_{i}(s,s^{\prime})v_{\beta}(s^{\prime})≤v_{\beta}(s)−\eta_{\beta}(s)=\xi_{\beta}(s)\
\forall\ i,$
where
$\eta_{\beta}(s)=r^{2}_{j_{0}}(s)+\beta\sum_{s^{\prime}}p^{2}_{j_{0}}(s,s^{\prime})v_{\beta}(s^{\prime})$
and
$\xi_{\beta}(s)=r^{1}_{i_{0}}(s)+\beta\sum_{s^{\prime}}p^{1}_{i_{0}}(s,s^{\prime})$
and $\xi_{\beta}(s)+\eta_{\beta}(s)=v_{\beta}(s).$
Thus the inequalities are

$r^{1}_{i}(s)+\beta\sum_{s^{\prime}}p^{1}_{i}(s,s^{\prime})\xi_{\beta}(s^{\prime})−\xi_{\beta}(s)+\beta\sum_{s^{\prime}}p^{1}_{i}(s,s^{\prime})\eta_{\beta}(s^{\prime})\leq
0\ \forall i\in A_{s},s\in S$ (3.4)

and similarly the inequalities for Player II are

$r^{2}_{j}(s)+\beta\sum_{s^{\prime}}p^{2}_{j}(s,s^{\prime})\eta_{\beta}(s^{\prime})−\eta_{\beta}(s)+\beta\sum_{s^{\prime}}p^{2}_{j}(s,s^{\prime})\xi_{\beta}(s^{\prime})\geq
0\ \forall j\in B_{s},s\in S.$ (3.5)

Also for each $s$, in 3.4 there is an $i(s)$ such that equality holds.
Similarly, for each $s$ in 3.5 there is a $j(s)$ such that equality holds. Let
for $i\in A_{s},$

$w^{1}_{i}(s)=−r^{1}_{i}(s)−\beta\sum_{s^{\prime}}p^{1}_{i}(s,s^{\prime})\eta\beta(s^{\prime})+\xi\beta(s)−\beta\sum_{s^{\prime}}p^{1}_{i}(s,s^{\prime})\xi\beta(s^{\prime})\geq
0,$ (3.6)

and for $j\in B_{s}$,

$w^{2}_{j}(s)=r^{2}_{j}(s)−\eta\beta(s)+\beta\sum_{s^{\prime}}p^{2}_{j}(s,s^{\prime})\eta\beta(s^{\prime})+\beta\sum_{s^{\prime}}p^{2}_{j}(s,s^{\prime})\xi\beta(s^{\prime})\geq
0.$ (3.7)

We may assume without loss of generality that $\eta\beta(s),\xi\beta(s)$ are
strictly positive. Since there is at least one inequality in 3.6 for each
$s\in S$ that holds as an equality and one inequality in 3.7 for each $s\in S$
that holds as an equality, the following complementarity conditions will hold.

$\eta_{\beta}(s)\prod_{i\in A_{s}}w^{1}_{i}(s)=0\ for\ 1\leq s\leq d$ (3.8)

and

$\xi_{\beta}(s)\prod_{j\in B_{s}}w^{2}_{j}(s)=0\ for\ 1\leq s\leq d.$ (3.9)

The inequality 3.6 and inequality 3.7 along with the complementarity
conditions 3.8 and 3.9 lead to the VLCP$(q,\cal A)$ where the matrix $\cal{A}$
is of the form
$\cal{A}=\left[\begin{array}[]{cc}-\beta P_{1}&E-\beta P_{1}\\\ -E+\beta
P_{2}&\beta P_{2}\\\ \end{array}\right]$ and
$q=\left[\begin{array}[]{c}-r^{1}_{i}(s)\\\ r^{2}_{j}(s)\\\
\end{array}\right],$
where the matrix $P_{1}=P_{1}(s),P_{2}=P_{2}(s)$ and
$E=\left[\begin{array}[]{ccccc}e_{1}&0&0&\cdots&0\\\ 0&e_{2}&0&\cdots&0\\\
\vdots&\vdots&\vdots&\cdots&\vdots\\\ 0&0&0&\cdots&e_{d}\\\
\end{array}\right]$ is a vertical block identity matrix where $e_{j},1\leq
j\leq d,$ is a column vector of all $1^{\prime}$s. Now an equivalent square
matrix $A$ can be constructed from the vertical block matrix $\cal{A}$ of type
$(m_{1},...,m_{c})$ by copying $\cal{A}$$._{j},$ $m_{j}$ times for
$j=1,2,\cdots,c.$ Therefore $A._{p}=\cal{A}$$._{j}$ $\forall p\in J_{j}$ and
the LCP$(q,A)$ is the equivalent LCP of VLCP$(q,\cal A)$. We consider the
proposed homotopy function 3.1

$H(u,t)=\left[\begin{array}[]{c}(1-t)[(A+A^{T})x+q-y_{1}-A^{T}y_{2}]+t(x-x^{(0)})\\\
Y_{1}x-tY_{1}^{(0)}x^{(0)}+(1-t)X(Ax+q)\\\
Y_{2}(Ax+q)-tY_{2}^{(0)}(Ax^{(0)}+q)\\\ \end{array}\right]=0$ (3.10)

where $Y_{1}=\text{diag}(y_{1}),$ $X=\text{diag}(x),$
$Y_{2}=\text{diag}(y_{2}),$ $Y_{1}^{(0)}=\text{diag}(y_{1}^{(0)}),$
$Y_{2}^{(0)}=\text{diag}(y_{2}^{(0)}),$ $u=(x,y_{1},y_{2})\in R_{+}^{n}\times
R_{+}^{n}\times R_{+}^{n},$
$u^{(0)}=(x^{(0)},{y_{1}}^{(0)},{y_{2}}^{(0)})\in\mathcal{R}_{1},$ and
$t\in(0,1].$ We denote $\Gamma_{u}^{(0)}=\\{(u,t)\in
R^{3n}\times(0,1]:H(u,u^{(0)},t)=0\\}\subset\mathcal{R}_{1}\times(0,1]\\}.$
For the proposed homotopy function $t$ varies from $1$ to $0.$ Starting from
$t=1$ to $t\to 0$ if we have a smooth bounded curve, then we obtain a finite
solution of the equation 3.1 at $t\to 0.$ As $t\to 1,$ the equation 3.1 gives
the solution $(u^{(0)},1),$ and as $t\to 0,$ the equation 3.1 gives the
solution of the system of following equations:

$(A+A^{t})x+q-y_{1}-A^{t}y_{2}=0$

$Y_{1}x+X(Ax+q)=0$

$Y_{2}(Ax+q)=0$

where $Y_{1}=\text{diag}(y_{1})$ and $Y_{2}=\text{diag}(y_{2}).$ Hence the
solution of the homotopy function 3.1 gives the solution of discounted zero-
sum ARAT game. ∎

Therefore if the homotopy function 3.1 converges to its solution as the
parameter $t\to 0$, we obtain the solution of discounted ARAT stochastic game.

Now we establish the conditions under which the solution exists for the
proposed homotopy function 3.1. We prove the following result to show that the
smooth curve $\Gamma_{u}^{(0)}$ exists for the proposed homotopy function 3.1.

######  theorem 3.2:

Let initial point $u^{(0)}\in\mathcal{R}_{1}.$ Then $0$ is a regular value of
the homotopy function $H:R^{3n}\times(0,1]\to R^{3n}$ and the zero point set
$H^{-1}(0)=\\{(u,t)\in\mathcal{R}_{1}:H(u,t)=0\\}$ contains a smooth curve
$\Gamma_{u}^{(0)}$ starting from $(u^{(0)},1).$

###### Proof.

The Jacobian matrix of the above homotopy function $H(u,u^{(0)},t)$ is
$DH(u,u^{(0)},t)=$
$\left[\begin{array}[]{ccc}\frac{\partial{H(u,t)}}{\partial{u}}&\frac{\partial{H(u,t)}}{\partial{u^{(0)}}}&\frac{\partial{H(u,t)}}{\partial{t}}\\\
\end{array}\right].$ For all $u^{(0)}\in\mathcal{R}_{1}$ and $t\in(0,1],$
$\frac{\partial{H(u,t)}}{\partial{u^{(0)}}}=$
$\left[\begin{array}[]{ccc}-tI&0&0\\\ -tY_{1}^{(0)}&-tX^{(0)}&0\\\
-tY_{2}^{(0)}A&0&-tY^{(0)}\\\ \end{array}\right],$
where $Y^{(0)}=\text{diag}(Ax^{(0)}+q),X^{(0)}=\text{diag}(x^{(0)}),$
$y^{(0)}=Ax^{(0)}+q$.
Now
$\det(\frac{\partial{H}}{\partial{u^{(0)}}})=(-1)^{3n}t^{3n}\prod_{i=1}^{n}x_{i}^{(0)}y_{i}^{(0)}$
$\neq 0$ for $t\in(0,1].$ Therefore, $0$ is a regular value of
$H(u,u^{(0)},t)$ by the lemma 2.2. By lemma 2.3 and lemma 2.4, for almost all
$u^{(0)}\in\mathcal{R}_{1},$ $0$ is a regular value of $H(u,t)$ and
$H^{-1}(0)$ consists of some smooth curves and $H(u^{(0)},1)=0.$ Hence there
must be a smooth curve $\Gamma_{u}^{(0)}$ starting from $(u^{(0)},1).$ ∎

Hence by Implicit Function Theorem for every $t$ sufficiently close to $1$,
the homotopy function has a unique solution $(u,1)$ of 3.1, which is smooth in
the parameter $t$ in a neighbourhood of $(u^{(0)},1)$.

We prove the following result to show that the smooth curve $\Gamma_{u}^{(0)}$
for the proposed homotopy function 3.1 is bounded and convergent.

######  theorem 3.3:

Let $\mathcal{R}$ be a non-empty set and $A\in R^{n\times n}$ a matrix and
assume that there exists a sequence of points
$\\{u^{k}\\}\subset\Gamma_{u}^{(0)}\subset\mathcal{R}_{1}\times(0,1],$ where
$u^{k}=(x^{k},y_{1}^{k},y_{2}^{k},t^{k})$ such that $\|x^{k}\|<\infty\
\text{as}\ k\to\infty$ and $\|y_{2}^{k}\|<\infty\ \text{as}\ k\to\infty$ and
for a given $u^{(0)}\in\mathcal{R}_{1},$ $0$ is a regular value of
$H(u,u^{(0)},t),$ then $\Gamma_{u}^{(0)}$ is a bounded curve in
$\mathcal{R}_{1}\times(0,1].$

###### Proof.

Note that $0$ is a regular value of $H(u,u^{(0)},t)$ by theorem 3.2. By
contradiction we assume that
$\Gamma_{u}^{(0)}\subset\mathcal{R}_{1}\times(0,1]$ is an unbounded curve.
Then there exists a sequence of points $\\{v^{k}\\},$ where
$v^{k}=(u^{k},t^{k})\subset\Gamma_{u}^{(0)}$ such that
$\|(u^{k},t^{k})\|\to\infty.$ As $(0,1]$ is a bounded set and $x$ component
and $y_{2}$ component of $\Gamma_{u}^{(0)}$ is bounded, there exists a
subsequence of points
$\\{v^{k}\\}=\\{(u^{k},t^{k})\\}=\\{x^{k},y_{1}^{k},y_{2}^{k},t^{k}\\}$ such
that $x^{k}\to\bar{x},\ y_{2}^{k}\to\bar{y_{2}},\ t^{k}\to\bar{t}\in[0,1]\
\text{and}\ \|y^{k}\|\to\infty\ \text{as}\ k\to\infty,\ \text{where}\
y^{k}=\left[\begin{array}[]{c}y_{1}^{k}\\\ y_{2}^{k}\\\ \end{array}\right].$
Since $\Gamma_{u}^{(0)}\subset H^{-1}(0),$ we have

$(1-t^{k})[(A+A^{T})x^{k}+q-y_{1}^{k}-A^{T}y_{2}^{k}]+t^{k}(x^{k}-x^{(0)})=0$
(3.11) $Y_{1}^{k}x^{k}-t^{k}Y_{1}^{(0)}x^{(0)}+(1-t^{k})X^{k}(Ax^{k}+q)=0$
(3.12) $Y_{2}^{k}(Ax^{k}+q)-t^{k}Y_{2}^{(0)}(Ax^{(0)}+q)=0$ (3.13)

where $Y_{1}^{k}=\text{diag}(y_{1}^{k}),X^{k}=\text{diag}(x^{k})$ and
$Y_{2}^{k}=\text{diag}(y_{2}^{k}).$
Let $\bar{t}\in[0,1],\|y_{1}^{k}\|=\infty$ and $\|y_{2}^{k}\|<\infty$ as
$k\to\infty.$ Then $\exists\ i\in\\{1,2,\cdots,n\\}$ such that
$y_{1i}^{k}\to\infty$ as $k\to\infty.$ Let $I_{1y}=\\{i\in\\{1,2,\cdots
n\\}:\lim\limits_{k\to\infty}y_{1i}^{k}=\infty\\}.$ When $\bar{t}\in[0,1),$
for $i\in I_{1y}$ we write from equation 3.11,
$(1-t^{k})[((A+A^{T})x^{k})_{i}+q_{i}-y_{1i}^{k}-(A^{T}y_{2}^{k})_{i}]+t^{k}(x_{i}^{k}-x_{i}^{(0)})=0$
$\implies(1-t^{k})y_{1i}^{k}=(1-t^{k})[((A+A^{T})x^{k})_{i}+q_{i}-(A^{T}y_{2}^{k})_{i}]+t^{k}(x_{i}^{k}-x_{i}^{(0)})\\\
\implies
y_{1i}^{k}=[((A+A^{T})x^{k})_{i}+q_{i}-(A^{T}y_{2}^{k})_{i}]+\frac{t^{k}}{(1-t^{k})}(x_{i}^{k}-x_{i}^{(0)}).$
As $k\to\infty$ right hand side is bounded, but left hand side is unbounded.
It contradicts that $\|y_{1}^{k}\|=\infty.$
When $\bar{t}=1,$ from equation 3.12, we obtain,
$x_{i}^{k}=\frac{t^{k}y_{1i}^{(0)}x_{i}^{(0)}}{y_{1i}^{k}}$ for $i\in I_{1y}.$
As $k\to\infty,x_{i}^{k}\to 0.$
Again from equation 3.11, we obtain
$x_{i}^{(0)}=\frac{(1-t^{k})}{t^{k}}[((A+A^{T})x^{k})_{i}+q_{i}-y_{1i}^{k}-(A^{T}y_{2}^{k})_{i}]+x_{i}^{k}$
for $i\in I_{1y}.$ As $k\to\infty,$ we have
$x_{i}^{(0)}=-\lim\limits_{k\to\infty}\frac{(1-t^{k})}{t^{k}}y_{1i}^{k}\leq
0.$ It contradicts that $\|y_{1}^{k}\|=\infty.$
So $\Gamma_{u}^{(0)}$ is a bounded curve in $\mathcal{R}_{1}\times(0,1].$ ∎

Therefore the boundedness of the sequences $\\{x_{k}\\}$ and $\\{y_{2}^{k}\\}$
gurantee the boundedness of the sequence $\\{y_{1}^{k}\\},$ i.e. the
boundedness of the sequence $\\{v^{k}\\}.$

######  theorem 3.4:

Suppose the solution set $\Gamma_{u}^{(0)}$ of the homotopy function
$H(u,u^{(0)},t)=0$ is unbounded for $t\in[0,1)$. Then there exists
$(\xi,\eta,\zeta)\in R_{+}^{3n}$ such that $e^{t}\xi=1,$ $\xi^{t}A\xi\leq 0.$

###### Proof.

Let assume that the solution set $\Gamma_{u}^{(0)}$ is unbounded for
$t\in[0,1)$. Then there exists a sequence of points
$\\{v^{k}\\}\subset\Gamma_{u}^{(0)}\subset\mathcal{R}_{1}\times[0,1),$ where
$v^{k}=(u^{k},t^{k})=(x^{k},y_{1}^{k},y_{2}^{k},t^{k})$ such that
$\lim_{k\to\infty}t^{k}=\bar{t}\in[0,1)$. Now we consider following two cases.
Case 1: $\|y_{2}^{k}\|<\infty$ as $k\to\infty$. Since the solution set
$\Gamma_{u}^{(0)}$ is unbounded we consider the following two subcases.
Subcase (i) $\lim_{k\to\infty}e^{t}x^{k}=\infty:$
Let $\lim_{k\to\infty}\frac{x^{k}}{e^{t}x^{k}}=\xi\geq 0$ and
$\lim_{k\to\infty}\frac{y_{1}^{k}}{e^{t}x^{k}}=\eta\geq 0.$ So it is clear
that $e^{t}\xi=1.$ Then dividing by $e^{t}x^{k}$ and taking limit $k\to\infty$
from equations 3.11, 3.12, 3.13 we write

$\displaystyle(1-\bar{t})[(A+A^{T})\xi-\eta]+\bar{t}\xi=0$ (3.14)
$\displaystyle\xi_{i}\eta_{i}+\xi_{i}(A\xi)_{i}=0\ \forall\ i$ (3.15)

From equations 3.14 and 3.15 we write
$\eta=(A+A^{T})\xi+\frac{\bar{t}}{(1-\bar{t})}\xi$ and
$-\xi^{T}A\xi=\xi^{T}\eta.$ These two imply that
$\xi^{T}[(A+A^{T})\xi+\frac{\bar{t}}{(1-\bar{t})}\xi]=\xi^{T}\eta=-\xi^{T}A\xi$
for $\bar{t}\in[0,1).$ This implies that
$2\xi^{T}A\xi+\xi^{T}A^{T}\xi=-\frac{\bar{t}}{(1-\bar{t})}\xi\leq 0$ i.e.
$\xi^{T}A\xi\leq 0$ for $\bar{t}\in[0,1).$
Specifically for $\bar{t}=0,$ $\xi^{T}A\xi=0$ and for $\bar{t}\in(0,1),$
$\xi^{T}A\xi<0.$
Subcase (ii) $\lim_{k\to\infty}(1-t^{k})e^{t}x^{k}=\infty:$
Let
$\lim_{k\to\infty}\frac{(1-t^{k})x^{k}}{(1-t^{k})e^{t}x^{k}}=\xi^{\prime}\geq
0.$ Then $e^{t}\xi^{\prime}=1.$ Let
$\lim_{k\to\infty}\frac{y_{1}^{k}}{(1-t^{k})e^{t}x^{k}}=\eta^{\prime}\geq 0.$
Then multiplying the equation 3.11 with $(1-t^{k})$ and dividing by
$(1-t^{k})e^{t}x^{k}$, multiplying the equation 3.12 with $(1-t^{k})$ and
dividing by $((1-t^{k})e^{t}x^{k})^{2}$ and multiplying the equation 3.13 with
$(1-t^{k})$ and dividing by $((1-t^{k})e^{t}x^{k})^{2}$ and taking limit
$k\to\infty$, we write

$\displaystyle(1-\bar{t})[(A+A^{T})\xi^{\prime}-(1-\bar{t})\eta^{\prime}]+\bar{t}\xi^{\prime}=0$
(3.16)
$\displaystyle\xi^{\prime}_{i}\eta^{\prime}_{i}+\xi^{\prime}_{i}(A\xi^{\prime})_{i}=0\
\forall\ i$ (3.17)

Multiplying $(\xi^{\prime})^{T}$ in both sides of equation 3.16, we have
$(\xi^{\prime})^{t}(A+A^{T})\xi^{\prime}-(1-\bar{t})(\xi^{\prime})^{T}\eta^{\prime}=-\frac{\bar{t}}{(1-\bar{t})}(\xi^{\prime})^{T}\xi^{\prime}.$
Now using equation 3.17, we write
$(\xi^{\prime})^{T}(A+A^{T})\xi^{\prime}+(1-\bar{t})(\xi^{\prime})^{T}A\xi^{\prime}=-\frac{\bar{t}}{(1-\bar{t})}(\xi^{\prime})^{T}\xi^{\prime}\implies(\xi^{\prime})^{T}A^{t}\xi^{\prime}+(2-\bar{t})(\xi^{\prime})^{T}A\xi^{\prime}=-\frac{\bar{t}}{(1-\bar{t})}(\xi^{\prime})^{T}\xi^{\prime}$
for $\bar{t}\in[0,1).$ Hence
$(3-\bar{t})(\xi^{\prime})^{T}A\xi^{\prime}=-\frac{\bar{t}}{(1-\bar{t})}(\xi^{\prime})^{T}\xi^{\prime}\implies(\xi^{\prime})^{T}A\xi^{\prime}=-\frac{\bar{t}}{(1-\bar{t})(3-\bar{t})}(\xi^{\prime})^{T}\xi^{\prime}\leq
0.$ So we have $(\xi^{\prime})^{T}A\xi^{\prime}\leq 0$ for $\bar{t}\in[0,1).$
Specifically for $\bar{t}=0,$ $(\xi^{\prime})^{T}A\xi^{\prime}=0$ and for
$\bar{t}\in(0,1),$ $(\xi^{\prime})^{T}A\xi^{\prime}<0.$

Case 2: $\lim_{k\to\infty}e^{t}y_{2}^{k}=\infty$. Since the solution set of
$\Gamma_{u}^{(0)}$ is unbounded we consider following two subcases.
Subcase (i) $\lim_{k\to\infty}e^{t}x^{k}=\infty$:
Let $\lim_{k\to\infty}\frac{x^{k}}{e^{T}x^{k}}=\xi\geq 0,$
$\lim_{k\to\infty}\frac{y_{1}^{k}}{e^{T}x^{k}}=\eta\geq 0$ and
$\lim_{k\to\infty}\frac{y_{2}^{k}}{e^{T}x^{k}}=\zeta\geq 0.$ It is clear that
$e^{T}\xi=1.$ Then dividing by $e^{T}x^{k}$ and taking limit $k\to\infty$ from
equation 3.11, dividing by $(e^{T}x^{k})^{2}$ and taking limit $k\to\infty$
from equation 3.12, 3.13, we write

$\displaystyle(1-\bar{t})[(A+A^{T})\xi-\eta-A^{T}\zeta]+\bar{t}\xi=0$ (3.18)
$\displaystyle\xi_{i}\eta_{i}+\xi_{i}(A\xi)_{i}=0\ \forall\ i$ (3.19)
$\displaystyle\zeta_{i}(A\xi)_{i}=0\ \forall\ i$ (3.20)

From equation 3.18, we have
$\eta+A^{T}\zeta=(A+A^{T})\xi+\frac{\bar{t}}{1-\bar{t}}\xi$ for
$\bar{t}\in[0,1).$ Now multiplying $\xi^{T}$ in both sides we get
$\xi^{T}(A+A^{T})\xi+\frac{\bar{t}}{1-\bar{t}}\xi^{T}\xi=\xi^{T}\eta+\xi^{T}A^{T}\zeta.$
From equations 3.19 and 3.20, we write
$\xi^{T}(A+A^{T})\xi+\frac{\bar{t}}{1-\bar{t}}\xi^{T}\xi=-\xi^{T}A\xi.$ Hence
$\xi^{T}A\xi+\xi^{T}(A+A^{T})\xi=-\frac{\bar{t}}{1-\bar{t}}\xi^{T}\xi\leq 0$
for $\bar{t}\in[0,1).$ Therefore $\xi^{T}A\xi\leq 0$ for $\bar{t}\in[0,1).$
Specifically for $\bar{t}=0,$ $\xi^{T}A\xi=0$ and for $\bar{t}\in(0,1),$
$\xi^{T}A\xi<0.$

Subcase(ii) $\lim_{k\to\infty}(1-t^{k})e^{t}x^{k}=\infty:$
Let
$\lim_{k\to\infty}\frac{(1-t^{k})x^{k}}{(1-t^{k})e^{T}x^{k}}=\xi^{\prime}\geq
0.$ Then $e^{T}\xi^{\prime}=1.$ Let
$\lim_{k\to\infty}\frac{y_{1}^{k}}{(1-t^{k})e^{T}x^{k}}=\eta^{\prime}\geq 0$
and $\lim_{k\to\infty}\frac{y_{2}^{k}}{(1-t^{k})e^{T}x^{k}}=\zeta^{\prime}\geq
0$ Then multiplying the equation 3.11 with $(1-t^{k})$ and dividing by
$(1-t^{k})e^{T}x^{k}$, multiplying the equation 3.12 with $(1-t^{k})$ and
dividing by $((1-t^{k})e^{T}x^{k})^{2}$ and multiplying the equation 3.13 with
$(1-t^{k})$ and dividing by $((1-t^{k})e^{T}x^{k})^{2}$ and taking limit
$k\to\infty,$ we obtain

$\displaystyle(1-\bar{t})(A+A^{T})\xi^{\prime}-(1-\bar{t})^{2}\eta^{\prime}-(1-\bar{t})^{2}A^{T}\zeta^{\prime}+\bar{t}\xi^{\prime}=0$
(3.21)
$\displaystyle\xi^{\prime}_{i}\eta^{\prime}_{i}+\xi^{\prime}_{i}(A\xi^{\prime})_{i}=0\
\forall\ i$ (3.22) $\displaystyle\zeta^{\prime}_{i}(A\xi^{\prime})_{i}=0\
\forall\ i$ (3.23)

Multiplying $(\xi^{\prime})^{T}$ in both side of equation 3.21, we have
$(\xi^{\prime})^{T}(A+A^{T})\xi^{\prime}-(1-\bar{t})(\xi^{\prime})^{T}\eta^{\prime}-(1-\bar{t})(\xi^{\prime})^{T}A^{T}\zeta^{\prime}=-\frac{\bar{t}}{(1-\bar{t})}(\xi^{\prime})^{T}\xi^{\prime}$.
Now from equations 3.22 and 3.23, we write
$(\xi^{\prime})^{T}(A+A^{T})\xi^{\prime}+(1-\bar{t})(\xi^{\prime})^{T}A\xi^{\prime}=(\xi^{\prime})^{T}A^{T}\xi^{\prime}+(2-\bar{t})(\xi^{\prime})^{T}\xi^{\prime}=(3-\bar{t})(\xi^{\prime})^{T}A\xi^{\prime}=-\frac{\bar{t}}{(1-\bar{t})}(\xi^{\prime})^{T}\xi^{\prime}\implies(\xi^{\prime})^{T}A\xi^{\prime}=-\frac{\bar{t}}{(1-\bar{t})(3-\bar{t})}(\xi^{\prime})^{T}\xi^{\prime}\leq
0$ for $\bar{t}\in[0,1).$
Specifically for $\bar{t}=0,$ $(\xi^{\prime})^{T}A\xi^{\prime}=0$ and for
$\bar{t}\in(0,1),$ $(\xi^{\prime})^{T}A\xi^{\prime}<0.$

Hence considering all the cases it is proved that the unboundedness of the
solution set $\Gamma_{u}^{(0)}$ of the homotopy function $H(u,u^{(0)},t)=0$
leads to the existence of $(\xi,\eta,\zeta)\in R_{+}^{3n}$ such that
$e^{t}\xi=1,$ $\xi^{t}A\xi\leq 0$ for $t\in[0,1).$

∎

######  Corollary 3.1:

For $\bar{t}=1$, the homotopy curve is bounded.

###### Proof.

Consider that the homotopy curve is unbounded in the neighbourhood of
$\bar{t}=1$. Then there exists a sequence of points
$\\{v^{k}\\}\subset\Gamma_{u}^{(0)}\subset\mathcal{R}_{1}\times[0,1),$ where
$v^{k}=(u^{k},t^{k})=(x^{k},y_{1}^{k},y_{2}^{k},t^{k})$ such that
$\lim_{k\to\infty}t^{k}=\bar{t}=1$. Now we consider following two cases.
Case 1: $\lim_{k\to\infty}e^{t}x^{k}=\infty.$
Case 2: $\lim_{k\to\infty}(1-t^{k})e^{t}x^{k}=\infty$.

Case 1. Let $\lim_{k\to\infty}e^{t}x^{k}=\infty$ and
$\lim_{k\to\infty}\frac{x^{k}}{e^{T}x^{k}}=\xi\geq 0.$ Hence $e^{t}\xi=1.$ If
$\|y_{2}^{k}\|<\infty$ as $k\to\infty,$ then from equation 3.14, we get
$\xi=0$ for $\bar{t}=1.$ If $\lim_{k\to\infty}e^{t}y_{2}^{k}=\infty,$ then
from equation 3.18, we get $\xi=0$ for $\bar{t}=1.$ This contradicts that
$e^{t}\xi=1.$

Case 2. Let $\lim_{k\to\infty}(1-t^{k})e^{t}x^{k}=\infty$ and
$\lim_{k\to\infty}\frac{(1-t^{k})x^{k}}{(1-t^{k})e^{T}x^{k}}=\xi^{\prime}\geq
0.$ Hence $e^{t}\xi^{\prime}=1.$ If $\|y_{2}^{k}\|<\infty$ as $k\to\infty,$
then from equation 3.16, we get $\xi^{\prime}=0$ for $\bar{t}=1.$ If
$\lim_{k\to\infty}e^{t}y_{2}^{k}=\infty,$ then from equation 3.21, we get
$\xi^{\prime}=0$ for $\bar{t}=1.$ This contradicts that $e^{t}\xi^{\prime}=1.$

Therefore the homotopy curve is bounded for $\bar{t}=1.$ ∎

######  theorem 3.5:

Let $A\in R^{n\times n}$ be a matrix. If the set $\mathcal{R}_{1}$ be nonempty
and $0$ is a regular value of $H(u,u^{(0)},t),$ then the homotopy path
$\Gamma_{u}^{(0)}\subset\mathcal{R}_{1}\times(0,1]$ is bounded.

###### Proof.

Suppose $A\in R^{n\times n}$ is a matrix and there exists a sequence of points
$\\{v^{k}\\}\subset\Gamma_{u}^{(0)}\subset\mathcal{R}_{1}\times(0,1],$ where
$v^{k}=(x^{k},y_{1}^{k},y_{2}^{k},t^{k}).$ Hence by the definition of
$\mathcal{R}_{1}$ $x^{k},y_{1}^{k},y_{2}^{k},\\\ Ax^{k}+q>0.$ From corollary
3.1 the homotopy curve is bounded for $t=1.$ Assume that the homotopy curve
$\Gamma_{u}^{(0)}\subset\mathcal{R}_{1}\times(0,1)$ is unbounded. Then from
theorem 3.4 $(\xi)^{T}A\xi<0$ for $t\in(0,1).$ But $Ax^{k}+q>0$ implies that
$A\xi\geq 0,$ where $\xi=$ $\lim_{k\to\infty}\frac{x^{k}}{e^{T}x^{k}}\geq 0$
for $\lim_{k\to\infty}{e^{T}x^{k}}=\infty,$ or $\xi=$
$\lim_{k\to\infty}\frac{(1-t^{k})x^{k}}{(1-t^{k})e^{T}x^{k}}\geq 0$ for
$\lim_{k\to\infty}{(1-t^{k})e^{T}x^{k}}=\infty.$ Hence $\xi,A\xi\geq 0$ imply
that $\xi^{T}A\xi\geq 0$ for $t\in(0,1)$, which contradicts that the homotopy
path is unbounded for $t\in(0,1).$ Hence the homotopy curve
$\Gamma_{u}^{(0)}\subset\mathcal{R}_{1}\times(0,1]$ is bounded. ∎

Therefore the homotopy curve $\Gamma_{u}^{(0)}$ is bounded for the parameter t
starting from $1$ to $0$ if the set $\mathcal{R}_{1}$ be nonempty and $0$ is a
regular value of the homotopy function 3.1 .

For an initial point $u^{(0)}\in\mathcal{R}_{1}$ we obtain a smooth bounded
homotopy path which leads to the solution of homotopy function 3.1 as the
parameter $t\to 0.$

######  theorem 3.6:

For $u^{(0)}=(x^{(0)},y_{1}^{(0)},y_{2}^{(0)})\in\mathcal{R}_{1},$ the
homotopy equation finds a bounded smooth curve
$\Gamma_{u}^{(0)}\subset\mathcal{R}_{1}\times(0,1]$ which starts from
$(u^{(0)},1)$ and approaches the hyperplane at $t=0.$ As $t\to 0,$ the limit
set $L\times\\{0\\}\subset\bar{\mathcal{R}}_{1}\times\\{0\\}$ of
$\Gamma_{u}^{(0)}$ is nonempty and every point in $L$ is a solution of the
following system:

$\begin{split}(A+A^{T})x+q-y_{1}-A^{T}y_{2}=0\\\ Y_{1}x+X(Ax+q)=0\\\
Y_{2}(Ax+q)=0.\\\ \end{split}$ (3.24)

###### Proof.

Note that $\Gamma_{u}^{(0)}$ is diffeomorphic to a unit circle or a unit
interval $(0,1]$ in view of lemma 2.5. As
$\frac{\partial{H(u,u^{(0)},1)}}{\partial{u^{(0)}}}$ is nonsingular,
$\Gamma_{u}^{(0)}$ is diffeomorphic to a unit interval $(0,1].$ Again
$\Gamma_{u}^{(0)}$ is a bounded smooth curve by the theorem 3.3. Let
$(\bar{u},\bar{t})$ be a limit point of $\Gamma_{u}^{(0)}.$ Now consider four
cases: $(i)(\bar{u},\bar{t})\in\mathcal{R}_{1}\times\\{1\\}:$ As the equation
$H(u,1)=0$ has only one solution $u^{(0)}\in\mathcal{R}_{1},$ this case is
impossible.
$(ii)(\bar{u},\bar{t})\in\partial{\mathcal{R}_{1}}\times\\{1\\}:$ there exists
a subsequence of $(u^{k},t^{k})\in\Gamma_{u}^{(0)}$ such that $x_{i}^{k}\to 0$
or $(Ax^{k}+q)_{i}\to 0$ for $i\subseteq\\{1,2,\cdots n\\}.$ From the last two
equalities of the homotopy function 3.1, we have $y_{1}^{k}\to\infty$ or
$y_{2}^{k}\to\infty.$ Hence it contradicts the boundedness of the homotopy
path by the theorem 3.3.
$(iii)(\bar{u},\bar{t})\in\partial{\mathcal{R}_{1}}\times(0,1):$ Also
impossible followed by the case $(ii).$
$(iv)(\bar{u},\bar{t})\in\bar{\mathcal{R}}_{1}\times\\{0\\}:$ The only
possible case.

Hence $\bar{u}=(\bar{x},\bar{y_{1}},\bar{y_{2}})$ is a solution of the system
3.24

$(A+A^{T})x+q-y_{1}-A^{T}y_{2}=0$

$Y_{1}x+X(Ax+q)=0$

$Y_{2}(Ax+q)=0.$

∎

Note that theorem 3.6 establishes the solution of the proposed homotopy
function which validates the theorem 3.1. This in turn leads to the solution
of discounted ARAT stochastic game.
In this approach the initial point
$u^{(0)}=(x^{(0)},y_{1}^{(0)},y_{2}^{(0)})\in\mathcal{R}_{1}$ has to be a
feasible point. Hence choose the initial point such that $x^{(0)}>0,\
Ax^{(0)}+q>0.$ Here $(\bar{u},0)$ is the solution of the homotopy function
3.1. Therefore $\bar{u}\in\bar{R}_{1}$ is the solution of the system of
equations 3.24. Hence $\bar{Y}_{1}\bar{x}=0$ and $\bar{X}(A\bar{x}+q)=0,$
where $\bar{Y}_{1}=$diag$(\bar{y}_{1})$ and $\bar{X}=$diag$(\bar{x})$. It is
clear that the component $\bar{x}$ of
$\bar{u}=(\bar{x},\bar{y_{1}},\bar{y_{2}})$ provides the solution of
discounted ARAT stochastic game.

###  Tracing Homotopy Path

We trace the homotopy path $\Gamma_{u}^{(0)}\subset\mathcal{R}_{1}\times(0,1]$
from the initial point $(u^{(0)},1)$ as $t\to 0.$ To find the solution of the
discounted ARAT stochastic game we consider homotopy path along with other
assumptions. Let $s$ denote the arc length of $\Gamma_{u}^{(0)}.$ We
parameterize the homotopy path $\Gamma_{u}^{(0)}$ with respect to $s$ in the
following form

$H(u(s),t(s))=0,\ u(0)=u^{(0)},\ t(0)=1.$ (3.25)

The solution of the equation 3.25 satisfies the initial value problem

$\dot{u}=-\frac{\partial}{\partial u}H(u,t)^{-1}\frac{\partial}{\partial
t}H(u,t),\ u(0)=u^{(0)}$ (3.26)

From equation 3.1 the choice of $H$ is $H(u,t)=(1-t)f(u)+tg(u)=0,$ where

$f(u)=\left[\begin{array}[]{c}(A+A^{T})x+q-y_{1}-A^{T}y_{2}\\\
Y_{1}x+X(Ax+q)\\\ Y_{2}(Ax+q)\\\ \end{array}\right]$ and
$g(u)=\left[\begin{array}[]{c}x-x^{(0)}\\\ Y_{1}x-Y_{1}^{(0)}x^{(0)}\\\
Y_{2}(Ax+q)-Y_{2}^{(0)}(Ax^{(0)}+q)\\\ \end{array}\right].$
Hence the system 3.26 becomes

$\dot{u}=-((1-t)J_{f}+tJ_{g})^{-1}(g(u)-f(u)),\ u(0)=u^{(0)}$

where $J_{f}$ and $J_{g}$ are Jacobian matrices of the functions $f$ and
$g$.Hence $\dot{u}=-\tilde{J}^{-1}\tilde{f},$ where
$\tilde{J}=(1-t)J_{f}+tJ_{g}$ and $\tilde{f}=g(u)-f(u)$.
The initial value problem 3.26 reduces to

$\dot{u}=p(u,t),\ u(0)=u^{(0)}$ where $p(u,t)=-\tilde{J}^{-1}\tilde{f}$

This problem will be solved by iterative process

$u_{(i+1)}=P(u_{i},t_{i},h_{i}),$ where $h_{i}=t_{i+1}-t_{i}.$

Here $u_{i}$ is an approximation of $u(s).$ $P(u_{i},t_{i},h_{i})$ is given by

$P(u,t,h)=I_{m}(u,t,h),$ where $I_{0}(u,t,h)=u$

and $K_{j}=\frac{\partial}{\partial u}H(I_{j},t+h)^{+}H(I_{j},t+h)$

$L_{j}=I_{j}-K_{j}$

$KK_{j}=(\frac{\partial}{\partial u}H(L_{j},t+h)+\frac{\partial}{\partial
u}H(I_{j},t+h))^{+}H(I_{j},t+h)$

$LL_{j}=I_{j}-2*KK_{j}$

The next iteration

$I_{j+1}=LL_{j}-\frac{\partial}{\partial u}H(L_{j},t+h)^{+}H(L_{j},t+h),$ for
$j=0,1,2,\cdots,m-1.$

Therefore in each step finding the value of $I_{j+1}$ for $m$ times we obtain
the next iteration and iterative process will continue until the termination
criteria is satisfied.

Algorithm 1 : Modified Homotopy Continuation Method

Step 0: Initialize $(u^{(0)},t_{0})$ and a natural number $m\in(0,50).$ Set
$l_{0}\in(0,1).$ Choose $\epsilon_{2}>>\epsilon_{3}>>\epsilon_{1}>0$ which are
very small positive quantity. Step 1:
$\tau^{(0)}=\xi^{(0)}=(\frac{1}{n_{0}})\left[\begin{array}[]{c}s^{(0)}\\\
-1\\\ \end{array}\right]$ for $i=0,$ where
$n_{0}=\|\left[\begin{array}[]{c}s^{(0)}\\\ -1\\\ \end{array}\right]\|$ and
$s^{(0)}=(\frac{\partial H}{\partial u}(u^{(0)},t_{0}))^{-1}(\frac{\partial
H}{\partial t}(u^{(0)},t_{0})).$
For $i>0,$ $s^{(i)}=(\frac{\partial H}{\partial
u}(u^{(i)},t_{i}))^{-1}(\frac{\partial H}{\partial t}(u^{(i)},t_{i})),$
$n_{i}=\|\left[\begin{array}[]{c}s^{(i)}\\\ -1\\\ \end{array}\right]\|,$
$\xi^{(i)}=(\frac{1}{n_{i}})\left[\begin{array}[]{c}s^{(i)}\\\ -1\\\
\end{array}\right]$.
If $\det(\frac{\partial H}{\partial u}(u^{(i)},t_{i}))>0,$
$\tau^{(i)}=\xi^{(i)}$ else $\tau^{(i)}=-\xi^{(i)},$ $i\geq 1.$
Set $l=0.$ Step 2: (Predictor and corrector point calculation)
$(\tilde{u}^{(i)},\tilde{t}_{i})=(u^{(i)},t_{i})+a\tau^{(i)},$ where
$a={l_{0}}^{l}.$ Compute
$(\hat{u}^{(i)},\hat{t}_{i})=H^{\prime}_{u^{(0)}}(\tilde{u}^{(i)},\tilde{t}_{i})^{+}H(\tilde{u}^{(i)},\tilde{t}_{i})$
and
$(\bar{u}^{(i)},\bar{t}_{i})=(\tilde{u}^{(i)},\tilde{t}_{i})-(\hat{u}^{(i)},\hat{t}_{i}).$
Now compute
$(\hat{uu}^{(i)},\hat{tt}_{i})=(H^{\prime}_{u^{(0)}}(\tilde{u}^{(i)},\tilde{t}_{i})+H^{\prime}_{u^{(0)}}(\bar{u}^{(i)},\bar{t}_{i}))^{+}H(\tilde{u}^{(i)},\tilde{t}_{i})$
and
$(\bar{uu}^{(i)},\bar{tt}_{i})=(\tilde{u}^{(i)},\tilde{t}_{i})-2(\hat{uu}^{(i)},\hat{tt}_{i}).$
Compute
$(u^{(i+1)},t_{i+1})=(\bar{uu}^{(i)},\bar{tt}_{i})-H^{\prime}_{u^{(0)}}(\bar{u}^{(i)},\bar{t}_{i})^{+}H(\bar{uu}^{(i)},\bar{tt}_{i}).$
Repeat the method from the computation of $(\tilde{u}^{(i)},\tilde{t}_{i})$ to
the computation of $(u^{(i+1)},t_{i+1})$ for $m$ times. In each step after
repeating the computation for $m$ times, can obtain the value of next
iteration. $(u^{(i+1)},t_{i+1})$
If $0<\|{t_{i+1}-t_{i}}\|<1,$ go to step 3. Otherwise if
$m^{\prime}=\min(a,\|({u}^{(i+1)},{t}_{i+1})-({u}^{(i)},{t}_{i})\|)>a_{0},$
update $l$ by $l+1,$ and recompute $(\tilde{t}_{i},\hat{t}_{i})$ else go to
step 3. Step 3: Determine the norm $r=\|H(u^{(i+1)},t_{i+1})\|.$ If $r\leq 1$
and $u^{(i+1)}>0$ go to step 5, otherwise if $a>\epsilon_{3},$ update $l$ by
$l+1$ and go to step 2 else go to step 4. Step 4: If
$|t_{i+1}-t_{i}|<\epsilon_{2},$ then if $|t_{i+1}|<\epsilon_{2},$ then stop
with the solution $(u^{(i+1)},t_{i+1}),$ else terminate (unable to find
solution) else $i=i+1$ and go to step 1. Step 5: If
$|t_{i+1}|\leq\epsilon_{1},$ then stop with solution $(u^{(i+1)},t_{i+1}),$
else $i=i+1$ and go to step 1.

Note that in step 2,
$H^{\prime}_{u^{(0)}}(u,t)^{+}=H^{\prime}_{u^{(0)}}(u,{t})^{T}(H^{\prime}_{u^{(0)}}(u,{t})H^{\prime}_{u^{(0)}}(u,t)^{T})^{-1}$
is the Moore-Penrose inverse of $H^{\prime}_{u^{(0)}}(u,t).$

We prove the following theorem to obtain the positive direction of the
proposed algorithm.

######  theorem 3.7:

If the homotopy curve $\Gamma_{u}^{(0)}$ is smooth, then the positive
predictor direction $\tau^{(0)}$ at the initial point $u^{(0)}$ satisfies
$\det\left[\begin{array}[]{c}\frac{\partial H}{\partial u\partial
t}(u^{(0)},1)\\\ \tau^{(0)^{T}}\\\ \end{array}\right]<0.$

###### Proof.

From the equation 3.1, we consider the following homotopy function
$H(u,t)=$
$\left[\begin{array}[]{c}(1-t)[(A+A^{T})x+q-y_{1}-A^{T}z_{2}]+t(x-x^{(0)})\\\
Y_{1}x-tY_{1}^{(0)}x^{(0)}+(1-t)X(Ax+q)\\\
Y_{2}(Ax+q)-tY_{2}^{(0)}(Ax^{(0)}+q)\\\ \end{array}\right]=0.$
Now $\frac{\partial H}{\partial u\partial t}(u,t)=$

$\left[\begin{array}[]{cccc}(1-t)(A+A^{T})+tI&-(1-t)I&-(1-t)A^{T}&Q\\\
Y_{1}+(1-t)(Y+XA)&X&0&-Y_{1}^{(0)}x^{(0)}-X(Ax+q)\\\
Y_{2}A&0&Y&-Y_{2}^{(0)}(Ax^{(0)}+q)\\\ \end{array}\right],$
where $Q=(x-x^{(0)})-[(A+A^{T})x+q-y_{1}-A^{t}y_{2}]$ and
$Y=\text{diag}(Ax+q).$
At the initial point $(u^{(0)},1)$
$\frac{\partial H}{\partial u\partial
t}(u^{(0)},1)=\left[\begin{array}[]{cccc}I&0&0&-[(A+A^{T})x^{(0)}+q-y^{(0)}_{1}-A^{T}y^{(0)}_{2}]\\\
Y^{(0)}_{1}&X^{(0)}&0&-Y^{(0)}_{1}x^{(0)}-X^{(0)}(Ax^{(0)}+q)\\\
Y^{(0)}_{2}A&0&Y^{(0)}&-Y^{(0)}_{2}(Ax^{(0)}+q)\\\ \end{array}\right].$
Let positive predictor direction be
$\tau^{(0)}=\left[\begin{array}[]{c}\kappa\\\
-1\end{array}\right]=\left[\begin{array}[]{c}(Q^{(0)}_{1})^{(-1)}Q_{2}^{(0)}\\\
-1\end{array}\right],$
where $Q^{(0)}_{1}=\left[\begin{array}[]{ccc}I&0&0\\\ Y^{(0)}_{1}&X^{(0)}&0\\\
Y^{(0)}_{2}A&0&Y^{(0)}\\\ \end{array}\right],$
$Q^{(0)}_{2}=\left[\begin{array}[]{c}-[(A+A^{T})x^{(0)}+q-y^{(0)}_{1}-A^{T}y^{(0)}_{2}]\\\
-Y^{(0)}_{1}x^{(0)}-X^{(0)}(Ax^{(0)}+q)\\\ -Y^{(0)}_{2}(Ax^{(0)}+q)\\\
\end{array}\right]$ and $\kappa$ is an $n\times 1$ column vector.
Hence, $\det\left[\begin{array}[]{c}\frac{\partial H}{\partial u\partial
t}(u^{(0)},1)\\\ \tau^{(0)^{t}}\\\ \end{array}\right]$
$=\det\left[\begin{array}[]{cc}Q^{(0)}_{1}&Q^{(0)}_{2}\\\
(Q^{(0)}_{2})^{t}(Q^{(0)}_{1})^{(-T)}&-1\\\ \end{array}\right]$
$=\det\left[\begin{array}[]{cc}Q^{(0)}_{1}&Q^{(0)}_{2}\\\
0&-1-(Q^{(0)}_{2})^{T}(Q^{(0)}_{1})^{(-T)}(Q^{(0)}_{1})^{(-1)}Q_{2}^{(0)}\\\
\end{array}\right]\\\ $
$=\det(Q^{(0)}_{1})\det(-1-(Q^{(0)}_{2})^{T}(Q^{(0)}_{1})^{(-T)}(Q^{(0)}_{1})^{(-1)}Q_{2}^{(0)})$
$=-\det(Q^{(0)}_{1})\det(1+(Q^{(0)}_{2})^{T}(Q^{(0)}_{1})^{(-T)}(Q^{(0)}_{1})^{(-1)}Q_{2}^{(0)})$
$=-\prod_{i=1}^{n}x^{(0)}_{i}y^{(0)}_{i}\det(1+(Q^{(0)}_{2})^{t}(Q^{(0)}_{1})^{(-T)}(Q^{(0)}_{1})^{(-1)}Q_{2}^{(0)})<0.$
So the positive predictor direction $\tau^{(0)}$ at the initial point
$u^{(0)}$ satisfies
$\det\left[\begin{array}[]{c}\frac{\partial H}{\partial u\partial
t}(u^{(0)},1)\\\ \tau^{(0)^{T}}\\\ \end{array}\right]<0.$ ∎

######  Remark 3.1:

We conclude from the theorem 3.7 that the positive tangent direction $\tau$ of
the homotopy path $\Gamma_{u}^{(0)}$ at any point $(u,t)$ be negative and it
depends on det$(Q_{1}),$ where
$Q_{1}=\left[\begin{array}[]{ccc}(1-t)(A+A^{T})+tI&-(1-t)I&-(1-t)A^{T}\\\
Y_{1}+(1-t)(Y+XA)&X&0\\\ Y_{2}A&0&Y\\\ \end{array}\right].$

Based on the earlier work the homotopy continuation method to solve the
initial value problem 3.26 was formulated with the iterative process as

$I_{j+1}=I_{j}-\frac{\partial}{\partial u}H(I_{j},t+h)^{+}H(I_{j},t+h),$ for
$j=0,1,2,\cdots,m-1.$

For details see [1]. However the proposed modified homotopy continuation
method solves homotopy function by solving the initial value problem 3.26 with
the following iterative process

$K_{j}=\frac{\partial}{\partial u}H(I_{j},t+h)^{+}H(I_{j},t+h)$

$L_{j}=I_{j}-K_{j}$

$KK_{j}=(\frac{\partial}{\partial u}H(L_{j},t+h)+\frac{\partial}{\partial
u}H(I_{j},t+h))^{+}H(I_{j},t+h)$

$LL_{j}=I_{j}-2*KK_{j}$

$I_{j+1}=LL_{j}-\frac{\partial}{\partial u}H(L_{j},t+h)^{+}H(L_{j},t+h),$ for
$j=0,1,2,\cdots,m-1.$

By this iterative process the proposed homotopy function achieves the order of
convergence as $5^{m}-1.$

######  theorem 3.8:

Suppose that the homotopy function has derivative, which is lipschitz
continuous in a convex neighbourhood $\cal N$ of $c,$ where $c$ is the
solution of the homotopy function $H(u,t)=0,$ whose Jacobian matrix is
continuous and nonsingular and bounded on $\cal N.$ Then the modified homotopy
continuation method has order $5^{m}-1.$

###### Proof.

By the Implicit Function Theorem ensures the existence of a unique continuous
solution $z(h)\in\cal N$ of $\dot{z}(h)=-\tilde{J}^{-1}\tilde{f},$ $z(0)=u$
and $h\in(-\delta,\delta),$ for some $\delta>0.$ Define
$\beta_{j}=\|z(h)-I_{j}(u,h)\|.$ From lemma 2.7 $\beta_{j}=O(h^{5^{j}}).$ Then
$\beta_{j+1}=\|z(h)-I_{j+1}\|\leq K{\beta_{j}}^{5}.$ Hence
$\beta_{j+1}=O(h^{5^{j+1}}).$ By induction method the modified homotopy
continuation method has convergency of order $5^{m}-1$ ∎

###  Solving Discounted Zero-Sum Stochastic Game with ARAT Structure

######  Example 3.1:

Consider a two player zero-sum discounted ARAT game with $s=2$ states. In each
state each player has $2$ actions. The transition probabilities are given by
$p^{1}_{1}(1,1)=\frac{1}{2},\ p^{1}_{1}(1,2)=0,\\\ $
$p^{1}_{2}(1,1)=\frac{1}{2},\ p^{1}_{2}(1,2)=0,\\\ $ $p^{1}_{1}(2,1)=0,\
p^{1}_{1}(2,2)=\frac{1}{2},\\\ $ $p^{1}_{2}(2,1)=0,\
p^{1}_{2}(2,2)=\frac{1}{2},\\\ $ $p^{2}_{1}(1,1)=\frac{1}{2},\
p^{2}_{1}(1,2)=0,\\\ $ $p^{2}_{2}(1,1)=0,\ p^{2}_{2}(1,2)=\frac{1}{2},\\\ $
$p^{2}_{1}(2,1)=0,\ p^{2}_{1}(2,2)=\frac{1}{2},\\\ $
$p^{2}_{2}(2,1)=\frac{1}{2},$ $p^{2}_{2}(2,2)=0.\\\ $ Note that
$p_{ij}(s,s^{\prime})=p^{1}_{i}(s,s^{\prime})+p^{2}_{j}(s,s^{\prime}).$
$P_{1}=P_{1}(s)=((p^{1}_{i}(s,s^{\prime}),s,s^{\prime}\in S,i\in A_{s}))$ and
$P_{2}=P_{2}(s)=((p^{2}_{j}(s,s^{\prime}),s,s^{\prime}\in S,j\in B_{s})).$
Let the discount factor $\beta=\frac{1}{2}.$
The reward structure:
$r^{1}_{1}(1)=4,\ \ r^{1}_{1}(2)=5,$
$r^{1}_{2}(1)=3$, $r^{1}_{2}(2)=4,$
$r^{2}_{1}(1)=3,\ \ r^{2}_{1}(2)=6,$
$r^{2}_{2}(1)=6$, $r^{2}_{2}(2)=2.$
Note that $r(s,i,j)=r^{1}_{i}(s)+r^{2}_{j}(s).$
Now we solve discounted ARAT game using the proposed homotopy function. The
initial point is
$u^{(0)}=(4,5,3,4,8,8,6,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0)^{T}$. As $t\to
0,$
$u=(0,7,0,6,9,0,0,7.33333,1,0,1,0,0,2.33333,3.33333,0,0,7,0,6,9,0,0,7.33333,0)$.
Hence the solution of discounted ARAT is $x=\left[\begin{array}[]{c}1\\\ 0\\\
1\\\ 0\\\ 0\\\ 2.33333\\\ 3.33333\\\ 0\\\ \end{array}\right].$

######  Example 3.2:

Consider another two player zero-sum discounted ARAT game with $s=2$ states.
In each state each player has $2$ actions. The transition probabilities are
given by
$p^{1}_{1}(1,1)=\frac{1}{4},\ p^{1}_{1}(1,2)=0,\\\ $
$p^{1}_{2}(1,1)=\frac{1}{4},\ p^{1}_{2}(1,2)=0,\\\ $ $p^{1}_{1}(2,1)=0,\
p^{1}_{1}(2,2)=\frac{1}{2},\\\ $ $p^{1}_{2}(2,1)=0,\
p^{1}_{2}(2,2)=\frac{1}{2},\\\ $ $p^{2}_{1}(1,1)=\frac{3}{4},\
p^{2}_{1}(1,2)=0,\\\ $ $p^{2}_{2}(1,1)=0,\ p^{2}_{2}(1,2)=\frac{3}{4},\\\ $
$p^{2}_{1}(2,1)=0,\ p^{2}_{1}(2,2)=\frac{1}{2},\\\ $
$p^{2}_{2}(2,1)=\frac{1}{2}$, $p^{2}_{2}(2,2)=0.\\\ $ Note that
$p_{ij}(s,s^{\prime})=p^{1}_{i}(s,s^{\prime})+p^{2}_{j}(s,s^{\prime}).$
$P_{1}=P_{1}(s)=((p^{1}_{i}(s,s^{\prime}),s,s^{\prime}\in S,i\in A_{s}))$ and
$P_{2}=P_{2}(s)=((p^{2}_{j}(s,s^{\prime}),s,s^{\prime}\in S,j\in B_{s})).$
Let the discount factor $\beta=\frac{1}{2}.$
The reward structure:
$r^{1}_{1}(1)=4,\ \ r^{1}_{1}(2)=5,$
$r^{1}_{2}(1)=3$, $r^{1}_{2}(2)=4,$
$r^{2}_{1}(1)=3,\ \ r^{2}_{1}(2)=6,$
$r^{2}_{2}(1)=6$, $r^{2}_{2}(2)=2.$
Note that $r(s,i,j)=r^{1}_{i}(s)+r^{2}_{j}(s).$
Now we solve discounted ARAT game using the proposed homotopy function. The
initial point is
$u^{(0)}=(1,1,1,1,20,20,10,10,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0)^{T}$. As
$t\to 0,$
$u=(0,9,0,6,7,0,0,7.33333,1,0,1,0,0,2,3.33333,0,0,9,0,6,7,0,0,7.33333,0)$.
Hence the solution of discounted ARAT is $x=\left[\begin{array}[]{c}1\\\ 0\\\
1\\\ 0\\\ 2\\\ 3.33333\\\ 0\\\ 0\\\ \end{array}\right].$

##  Conclusion

In this paper, we introduce a homotopy continuation method to find the
solution of discounted ARAT stochastic game. Mathematically, we obtain the
positive tangent direction of the homotopy path. We prove that the smooth
curve of the proposed homotopy function is bounded and convergent. We
establish that the proposed homotopy functions has $5^{m}-1$ order of
convergence. Two numerical examples are illustrated to demonstrate the
effictiveness of the proposed homotopy function.

##  Acknowledgment

The author A. Dutta is thankful to the Department of Science and Technology,
Govt. of India, INSPIRE Fellowship Scheme for financial support.

## References

  * [1] James P Abbott and Richard P Brent.  A note on continuation methods for the solution of nonlinear equations.  The ANZIAM Journal, 20(2):157–164, 1977.
  * [2] Shui Nee Chow, John Mallet-Paret, and James A Yorke.  Finding zeroes of maps: homotopy methods that are constructive with probability one.  Mathematics of Computation, 32(143):887–899, 1978.
  * [3] Alicia Cordero, José L Hueso, Eulalia Martínez, and Juan R Torregrosa.  Increasing the convergence order of an iterative method for nonlinear systems.  Applied Mathematics Letters, 25(12):2369–2374, 2012.
  * [4] Richard W Cottle and George B Dantzig.  Complementary pivot theory of mathematical programming.  Technical report, STANFORD UNIV CA OPERATIONS RESEARCH HOUSE, 1967.
  * [5] Richard W Cottle and George B Dantzig.  A generalization of the linear complementarity problem.  Journal of Combinatorial Theory, 8(1):79–90, 1970.
  * [6] AK Das, R Jana, and Deepmala.  Finiteness of criss-cross method in complementarity problem.  In International Conference on Mathematics and Computing, pages 170–180. Springer, 2017.
  * [7] B Curtis Eaves.  The linear complementarity problem.  Management science, 17(9):612–634, 1971.
  * [8] B Curtis Eaves and Romesh Saigal.  Homotopies for computation of fixed points on unbounded regions.  Mathematical Programming, 3(1):225–237, 1972.
  * [9] Michael C Ferris and Jong-Shi Pang.  Engineering and economic applications of complementarity problems.  Siam Review, 39(4):669–713, 1997.
  * [10] Jerzy Filar and Koos Vrieze.  Competitive Markov decision processes.  Springer Science & Business Media, 2012.
  * [11] János Flesch, Frank Thuijsman, and Okko Jan Vrieze.  Stochastic games with additive transitions.  European Journal of Operational Research, 179(2):483–497, 2007\.
  * [12] CB Garcia.  Some classes of matrices in linear complementarity theory.  Mathematical Programming, 5(1):299–310, 1973.
  * [13] Jacob K Goeree and Charles A Holt.  Stochastic game theory: For playing games, not just for doing theory.  Proceedings of the National Academy of sciences, 96(19):10564–10567, 1999.
  * [14] R Jana, AK Das, and A Dutta.  On hidden z-matrix and interior point algorithm.  Opsearch, 56(4):1108–1116, 2019.
  * [15] R Jana, A Dutta, and AK Das.  More on hidden z-matrices and linear complementarity problem.  Linear and Multilinear Algebra, 69(6):1151–1160, 2021.
  * [16] Michael M Kostreva and Malgorzata M Wiecek.  Linear complementarity problems and multiple objective programming.  Mathematical Programming, 60(1-3):349–359, 1993.
  * [17] MM KOSTREVA.  Direct algorithms for complementarity problems[ph. d. thesis].  1976\.
  * [18] SR Mohan, SK Neogy, and AK Das.  More on positive subdefinite matrices and the linear complementarity problem.  Linear Algebra and Its Applications, 338(1-3):275–285, 2001.
  * [19] SR Mohan, SK Neogy, and AK Das.  On the classes of fully copositive and fully semimonotone matrices.  Linear Algebra and its Applications, 323:87–97, 01 2001.
  * [20] SR Mohan, SK Neogy, and T Parthasarathy.  Pivoting algorithms for some classes of stochastic games: A survey.  International Game Theory Review, 3(02n03):253–281, 2001.
  * [21] SR Mohan, SK Neogy, T Parthasarathy, and S Sinha.  Vertical linear complementarity and discounted zero-sum stochastic games with arat structure.  Mathematical programming, 86(3):637–648, 1999.
  * [22] SR Mohan, SK Neogy, and R Sridhar.  The generalized linear complementarity problem revisited.  Mathematical Programming, 74(2):197–218, 1996.
  * [23] Prasenjit Mondal, S Sinha, SK Neogy, and AK Das.  On discounted ar–at semi-markov games and its complementarity formulations.  International Journal of Game Theory, 45(3):567–583, 2016.
  * [24] Katta G Murty and Feng-Tien Yu.  Linear complementarity, linear and nonlinear programming, volume 3.  Citeseer, 1988.
  * [25] SK Neogy, R. Bapat, AK Das, and T. Parthasarathy.  Mathematical programming and game theory for decision making.  11 2021.
  * [26] SK Neogy and AK Das.  Linear complementarity and two classes of structured stochastic games.  Operations Research with Economic and Industrial Applications: Emerging Trends, eds: SR Mohan and SK Neogy, Anamaya Publishers, New Delhi, India, pages 156–180, 2005.
  * [27] SK Neogy and AK Das.  On almost type classes of matrices with ${Q}$-property.  Linear and Multilinear Algebra, 53(4):243–257, 2005.
  * [28] SK Neogy and AK Das.  Principal pivot transforms of some classes of matrices.  Linear algebra and its applications, 400:243–252, 2005.
  * [29] SK Neogy and AK Das.  On weak generalized positive subdefinite matrices and the linear complementarity problem.  Linear and Multilinear Algebra, 61(7):945–953, 2013.
  * [30] SK Neogy, AK Das, and R Bapat.  Optimization models with economic and game theoretic applications.  Annals of Operations Research, 243, 07 2016.
  * [31] SK Neogy, AK Das, and R. Bapat.  Modeling, computation and optimization.  11 2021.
  * [32] SK Neogy, AK Das, and Abhijit Gupta.  Generalized principal pivot transforms, complementarity theory and their applications in stochastic games.  Optimization Letters, 6(2):339–356, 2012.
  * [33] SK Neogy, AK Das, S Sinha, and A Gupta.  On a mixture class of stochastic game with ordered field property.  In Mathematical programming and game theory for decision making, pages 451–477. World Scientific, 2008.
  * [34] Jong-Shi Pang.  Complementarity problems.  In Handbook of global optimization, pages 271–338. Springer, 1995\.
  * [35] TES Raghavan.  Stochastic games—an overview.  Stochastic Games and Related Topics, pages 1–9, 1991.
  * [36] Tirukkannamangai ES Raghavan, SH Tijs, and OJ Vrieze.  On stochastic games with additive reward and transition structure.  Journal of Optimization Theory and Applications, 47(4):451–464, 1985.
  * [37] Lloyd S Shapley.  Stochastic games.  Proceedings of the national academy of sciences, 39(10):1095–1100, 1953.
  * [38] Sagnik Sinha.  Contribution to the theory of stochastic games.  PhD thesis, Indian Statistical Institute, Delhi, 1989.
  * [39] Matthew J Sobel.  Noncooperative stochastic games.  The Annals of Mathematical Statistics, 42(6):1930–1935, 1971.
  * [40] Eilon Solan and Nicolas Vieille.  Stochastic games.  Proceedings of the National Academy of Sciences, 112(45):13743–13746, 2015.
  * [41] Xiuyu Wang and Xingwu Jiang.  A homotopy method for solving the horizontal linear complementarity problem.  Computational and Applied Mathematics, 33, 04 2013.
  * [42] Layne T Watson.  Globally convergent homotopy methods: a tutorial.  Applied Mathematics and Computation, 31:369–396, 1989.
  * [43] Layne T Watson and Raphael T Haftka.  Modern homotopy methods in optimization.  Computer Methods in Applied Mechanics and Engineering, 74(3):289–305, 1989.
  * [44] X Zhao, S Zhang, and Q Liu.  A combined homotopy interior point method for the linear complementarity problem.  Journal of Information and Computational Science, 7:1589–1594, 07 2010.


# A prescriptive method for fibre polarisation compensation in two bases

Teodor Strömberg  Peter Schiansky  Philip Walther  University of Vienna,
Faculty of Physics & Vienna Doctoral School in Physics, Boltzmanngasse 5,
A-1090 Vienna, Austria

###### Abstract

Single-mode optical fibres exhibit a small but non-negligible birefringence
that induces random polarisation rotations during light propagation. In
classical interferometry these rotations give rise to polarisation-induced
fading of the interferometric visibility, and in fibre-based polarimetric
sensors as well as quantum optics experiments they scramble the information
encoded in the polarisation state. Correcting these undesired rotations is
consequently an important part of many experiments and applications employing
optical fibres. In this Lab Note we review an efficient method for fully
compensating fibre polarisation rotations for general input states. This
method was not originally devised by us, but does to the best of our knowledge
not appear in the literature, and our interactions with the community have
indicated that it is not well known.

##  I Introduction

While single-mode (SM) optical fibres have a core that is nominally circularly
symmetric, stress in the fibre can break this symmetry and give rise to a
small amount of birefringence. The effect of this can be modelled as a series
of birefrigent elements with random axes and retardances [1], which even for
fibre patch cables of moderate length can result in completely random
transformations of an input polarisation state. Under the assumption that the
total polarisation mode dispersion is negligible, these polarisation
transformations can be considered unitary, and throughout the remainder of
this text we will assume this to be the case.

Random polarisation rotations can have a detrimental effect on many
applications of fibre optics, such as coherent receivers used in high-
bandwidth telecommunication systems [2], and interferometric fibre sensors [3,
4]. This has led to the development of a variety of application-specific
techniques for the control of the polarisation of light in fibres [5, 6, 7,
8], using both mechanical [9, 10] and electro-optical [11, 12, 13] fibre
polarisation controllers. In the aforementioned contexts the problem of
polarisation compensation consists of transforming a given, potentially time-
varying, state of polarisation to a fixed state. This can be framed as a
minimisation problem that can be satisfied using two quarter-wave plates to
rotate the polarisation [14]. In practice, however, devices additionally
containing one half-wave plate, capable of realising any unitary polarisation
rotation [15], are more frequently employed. In some applications, such as
fibre-optic gyroscopes [16], polarisation maintaining (PM) fibres [17] are
instead used to ensure a fixed output state.

In many quantum-information applications of fibre optics [18], such as quantum
key distribution [19], as well as in certain classical and quantum sensors
[20, 21, 22] the problem of polarisation compensation is more complicated.
This is because quantum information encoded in a polarisation state is
sensitive not only to the magnitude of the polarisation basis states, but also
their relative phase. Polarisation compensation therefore consists of ensuring
a well-behaved input-output relation for every possible input polarisation,
not just a single one. This is equivalent to satisfying two simultaneous
minimisation problems for two non-orthogonal polarisations, as opposed to a
minimisation problem for a single polarisation state. While PM fibres, despite
the name, are unsuited for preserving general polarisation states as their
strong birefringence scrambles the phase between the two polarisation
eigenstates of the fibre, a variety of techniques typically based on, or
incorporating active feedback control, have been developed to tackle the
polarisation compensation problem in SM fibres [23, 24, 25, 26, 27, 28, 29].

In laboratory-scale optical setups, however, active feedback control on the
polarisation is often not employed due to cost and complexity reasons, or
because the time scale of the polarisation fluctuations is long enough that
initial post-alignment corrections to the polarisation suffice. Since these
corrections are typically either done manually, or with low-bandwidth
mechanical components, it is desirable to have a prescriptive method for
compensating the polarisation. When using fibre polarisation controllers this
is complicated by the fact that the input state to the controller is both
random and unknown, and the degrees of freedom (DOFs) of the polarisation
controller therefore map to the output polarisation state in an unpredictable
way. Practically, this means that all the controller DOFs couple to both
minimisation problems, making it challenging to simultaneously satisfy both of
them. This problem is exacerbated by the fact that the two conditions are
typically not measured in parallel. Here we review a method to decouple the
two minimzation problems, thereby allowing for a simple step-by-step procedure
for polarisation compensation.

##  II The method

As the method presented here is particularly suited to quantum optics
laboratories, we will use the language of quantum mechanics to describe the
polarisation states, letting $\ket{\cdot}$ represent a single-photon or
coherent state with a given polarisation. This description is equivalent to a
formulation using Jones calculus in classical optics.

The polarisation compensation problem under consideration consists of ensuring
that all polarisation states are mapped to themselves after propagating
through a fibre, or in other words that the total polarisation transformation
of the fibre should be the identity transformation. This condition can be
satisfied by ensuring that two fixed non-orthogonal states are correctly
transformed. For example:

$\ket{H}\xmapsto{U_{f}}\ket{H},\qquad\ket{+}\xmapsto{U_{f}}\ket{+},$ (1)

where $U_{f}$ is the fibre tranformation, $\ket{H}$ is a horizontally
polarised state, $\ket{+}=(\ket{H}+\ket{V})/\sqrt{2}$ is a diagonally
polarised state, and $\ket{V}$ is a vertically polarised state.
Experimentally, this is done by using a polariser at the fibre input to
prepare the state $\ket{H}$ ($\ket{+}$) and minimising the transmission
through an orthogonal polariser $\outerproduct{V}{V}$ ($\outerproduct{-}{-}$)
after the fibre, thereby ensuring

$\displaystyle\lvert\langle V|U_{f}(\alpha,\beta,\gamma)|H\rangle\rvert^{2}$
$\displaystyle\approx 0,$ (2)
$\displaystyle\lvert\langle-|U_{f}(\alpha,\beta,\gamma)|+\rangle\rvert^{2}$
$\displaystyle\approx 0,$ (3)

where $\alpha$, $\beta$, $\gamma$ are free parameters of the polarisation
controller for the fibre. If these parameters are experimentally adjusted such
that (2) is satisfied, then attempting to subsequently satisfy (3) will
generally break the condition (2). As illustrated in Fig. 1, this problem can
be solved by using two wave plates, placed before the fibre, to introduce an
additional degree of freedom that is decoupled from the condition (2).
Specifically, a quarter-wave plate (QWP) fixed at
$45\text{\,}\mathrm{\SIUnitSymbolDegree}$ from the vertical axis, followed by
a half-wave plate (HWP) at a variable angle $\theta$. The action of these wave
plates is described by the following unitary transformations:

$\displaystyle\mathrm{QWP}(\varphi)$
$\displaystyle=\mathrm{exp}\bigl{[}-i\frac{\pi}{4}(\sin(2\varphi)\sigma_{x}+\cos(2\varphi)\sigma_{z})\bigr{]},$
(4) $\displaystyle\mathrm{HWP}(\theta)$
$\displaystyle=\mathrm{exp}\bigl{[}-i\frac{\pi}{2}(\sin(2\theta)\sigma_{x}+\cos(2\theta)\sigma_{z})\bigr{]},$
(5)

where

$\sigma_{x}=\begin{bmatrix}0&\phantom{-}1\\\
1&\phantom{-}0\end{bmatrix},\qquad\sigma_{z}=\begin{bmatrix}[r]1&0\\\
0&-1\end{bmatrix}.$ (6)

Here the convention that $\ket{H}$ ($\ket{+}$) is the eigenvector
corresponding to the positive eigenvalue of $\sigma_{z}$ ($\sigma_{x}$) is
used. The quarter-wave plate at $45\text{\,}\mathrm{\SIUnitSymbolDegree}$
transforms the horizontally-polarised state to right-handed circularly
polarised light ($\ket{R}=(\ket{H}-i\ket{V})/\sqrt{2}$), and leaves the
diagonally-polarised light unchanged:

$\mathrm{QWP}($45\text{\,}\mathrm{\SIUnitSymbolDegree}$)\ket{H}=\ket{R},\qquad\mathrm{QWP}($45\text{\,}\mathrm{\SIUnitSymbolDegree}$)\ket{+}=\ket{+}.$
(7)

The half-wave plate then, independently of its angle, flips the handedness of
the circularly polarised light, and rotates the diagonally polarised light to
another linear polarisation:

$\displaystyle\mathrm{HWP}(\theta)\ket{R}$ $\displaystyle=\ket{L},$ (8)
$\displaystyle\mathrm{HWP}(\theta)\ket{+}$
$\displaystyle=\sin(2\theta)\ket{+}+\cos(2\theta)\ket{-}.$ (9)

Note that, as will become relevant shortly, the transformed diagonally
polarised state can equivalently be expressed in terms of the circularly
polarised states:

$\mathrm{HWP}(\theta)\ket{+}=\frac{1}{\sqrt{2}}(\ket{L}+e^{i(4\theta-\pi/2)}\ket{R}).$
(10)

Using (7) and (8) the first minimisation condition reads

$\displaystyle\lvert\langle
V|U_{f}(\alpha,\beta,\gamma)\mathrm{HWP}(\theta)\mathrm{QWP}($45\text{\,}\mathrm{\SIUnitSymbolDegree}$)|H\rangle\rvert^{2}$
$\displaystyle\approx 0$ (11) $\displaystyle\iff\lvert\langle
V|U_{f}(\alpha,\beta,\gamma)|L\rangle\rvert^{2}$ $\displaystyle\approx 0$

and is independent of the HWP angle $\theta$. Satisfying this condition
implies that

$\displaystyle U_{f}(\alpha,\beta,\gamma)\ket{L}$
$\displaystyle=e^{-i\phi/2}\ket{H}$ (12) $\displaystyle
U_{f}(\alpha,\beta,\gamma)\ket{R}$ $\displaystyle=e^{i\phi/2}\ket{V},$ (13)

for some unknown phase $\phi$. The minimisation condition for the diagonal
polarisation can be expressed as

$\lvert\langle-|U_{f}(\alpha,\beta,\gamma)\mathrm{HWP}(\theta)\mathrm{QWP}($45\text{\,}\mathrm{\SIUnitSymbolDegree}$)|+\rangle\rvert^{2}\approx
0.$ (14)

Using (10) together with (12) and (13) this can be re-written as

$\begin{gathered}\begin{aligned}
\frac{1}{4}\lvert(\bra{H}-\bra{V})(\ket{H}&+e^{i(4\theta-\pi/2+\phi)}\ket{V})\rvert^{2}\approx
0\\\ \iff 4\theta&+\phi-\pi/2\approx 0.\end{aligned}\end{gathered}$ (15)

This condition can always be satisfied by tuning the HWP angle $\theta$,
without affecting the first condition (11).

Figure 1: (Top, centre) Minimal optical setup for the polarisation
compensation. The labels above and below the beam path indicate the evolution
of the two input polarisation states throughout the setup after the
compensation has been performed. Here $\ket{\mathcal{L}}$ refers to a general
linearly polarised state, not to be confused with the left-handed circularly
polarised state $\ket{L}$. (Top, left) The two input states $\ket{H}$ (blue)
and $\ket{+}$ (red) before the two wave plates, drawn on the Poincaré sphere.
(Bottom, left) Polarisation states after the two wave plates and immediately
before the fibre. This figure represents the image of the two states for all
possible choices of HWP angle $\theta$. The state $\ket{H}$ has been mapped to
$\ket{L}$, and $\ket{+}$ has been mapped to a state somewhere on the great
circle of linearly polarised states. (Bottom, centre) Without compensation the
input states get mapped to random states on the Poincaré sphere by the fibre
transformation $U_{f}$. (Bottom, right) Using the fibre polarisation
controller the input state $\ket{H}$ is mapped to itself after the fibre, and
$\ket{+}$ is mapped to the equator of the Poincaré sphere. (Top, right) By
tuning the angle $\theta$ of HWP before the fibre the ellipticity angle of the
image of $\ket{+}$ can be set to zero, thereby ensuring that the identity
transformation is realised.

The decoupling of the two conditions has a simple visual interpretation,
illustrated in Fig. 1: the image of $\ket{+}$ under the two wave plates is the
great circle of linear polarisation on the Poincaré sphere, which gets mapped
to a randomly oriented great circle by the fibre. After using the fibre
polarisation controller to satisfy the condition (11), thereby mapping
$\ket{H}$ to itself, this great circle is mapped to the equator, since the
unitary rotation of the fibre preserves the
$90\text{\,}\mathrm{\SIUnitSymbolDegree}$ angle between the states.
Consequently the HWP angle $\theta$ is mapped to the ellipticity angle $\chi$
(modulo a random offset), or equivalently the angle in the equatorial plane,
which can always be chosen such that $\ket{+}\mapsto\ket{+}$.

The steps for practically carrying out the compensation using the setup
illustrated in Fig. 1 are the following:

  1. 1.

Inject classical light into the fibre.

  2. 2.

Place a horizontal polariser before the two wave plates to prepare the state
$\ket{H}$, and place a vertical polariser in front of the fibre output.

  3. 3.

Use a powermeter to measure the transmission through the vertical polariser,
and minimise the optical power with the fibre polarisation controller.

  4. 4.

Replace the polariser before (after) the fibre with a diagonal (anti-diagonal)
polariser.

  5. 5.

Use the half-wave plate to minimise the transmission through the measurement
polariser.

  6. 6.

Put back the horizontal (vertical) polariser to re-check the polarisation
contrast, and repeat steps 3-6 if necessary.

Figure 2: a) In the presence of imperfections rotating the HWP slightly
affects the state $\ket{H}$. This is illustrated above with a measurement of
the polarisation contrast for the input state $\ket{H}$ after the fibre. This
contrast remains well above $30\text{\,}\mathrm{dB}$ for all HWP angles,
indicating that the rejected power changes by less than one part in 1000, and
the state remains almost unaffected. b)  (Left, discs) Repeating the
compensation protocol can lead to higher polarisation contrasts. This is
illustrated here by showing two examples of the extinction ratio (ER) for both
input polarisation states at every step of several full protocol iterations.
Initially the fibre transforms the states randomly resulting in a low ER. In
the first step the state $\ket{H}$ (blue) is compensated with the fibre
polarisation controller (FPC). Next, the HWP is used to compensate $\ket{+}$
(red), which in the process generally slightly degrades the contrast for
$\ket{H}$ due to experimental imperfections. In the third step the FPC is once
again used to compensate $\ket{H}$, and after adjusting $\ket{+}$ with the HWP
ERs of 41 and $37\text{\,}\mathrm{dB}$ (42 and $38\text{\,}\mathrm{dB}$) are
reached for $\ket{H}$ and $\ket{+}$ in the top (bottom) figures, respectively.
A third repetition of the protocol does, in this case, not increase the
extinction ratio further. (Right, circles) When only using an FPC,
compensating one input state strongly affects the other, leading to a
nondeterministic procedure that converges slowly (bottom), or not at all
(top). This results in worse overall polarisation contrast.

We remarked earlier that due to the random polarisation state inside the
fibre, the polarisation controller DOFs map to the output polarisation in an
unpredictable way. This is still true in step 3 of the method described here.
However, in this method the polarisation controller is only used to satisfy a
single minimisation condition, and the redundant DOF of the controller means
that there is not a single minimum, but rather a one-dimensional parameter
space satisfying the condition. In practice, the minimisation is therefore
simple to carry out.

Note that, while the description of the method here assumed the two wave
plates to be on the input side of the fibre, the compensation procedure can
also be carried out with light launched in the opposite direction.

##  III Practical considerations

The decoupling of the two minimisation conditions relies on the two wave
plates having the correct retardances, and the QWP being at
$45\text{\,}\mathrm{\SIUnitSymbolDegree}$ from the horizontal polariser. In
practice, these conditions are never satisfied exactly, and as a consequence
rotating the HWP will slightly affect the minimisation condition (11). With
high quality optical components and careful alignment, however, this effect
can be made small. An example measurement of the polarisation contrast for the
$\ket{H}$ polarisation as a function of the HWP angle $\theta$ is shown in
Fig. 2(a). The contrast is defined as the extinction ratio (ER), which is the
ratio between the power (P) incident on and transmitted through a polariser:
$\mathrm{ER}=\mathrm{P}_{\mathrm{total}}/\mathrm{P}_{\mathrm{transmitted}}$.
It can be seen that the polarisation state is largely insensitive to the
rotation of the HWP. In situations where high polarisation contrast is needed,
it is nevertheless prudent to re-check the ER in the $\ket{H}$/$\ket{V}$ basis
after completing one round of the procedure. It has been our experience that
iteratively performing two, or sometimes three rounds of compensation can
result in higher simultaneous contrasts. This is illustrated in Fig. 2(b),
showing the ER for both states for each step in the iterative method, as well
as a comparison to only using an FPC.

To achieve high polarisation contrasts the relative angle of all polarisers is
also of high importance, and it is therefore recommended to use pre-calibrated
polarisers in locking rotation mounts for all four polarisation states. A
vertical polariser is easily produced by extinguishing a horizontal polariser
taken as reference, while a diagonal polariser can be set either by balancing
the transmission through two crossed polarisers sandwiching it, or by using a
high-precision motorized rotation mount to accurately rotate a polariser to
$-45\text{\,}\mathrm{\SIUnitSymbolDegree}$ from the horizontal reference,
against which the diagonal polariser is then extinguished. Finally, an anti-
diagonal polariser is set by extinguishing the diagonal polariser. An initial
guess for the QWP angle, which should be
$45\text{\,}\mathrm{\SIUnitSymbolDegree}$, can be found from a calibration
curve of the wave plate. Better performance can sometimes be achieved by minor
adjustments to the wave-plate angle. Such adjustments should be carried out by
first performing steps 1-2 of the method, and then attempting to minimise the
observed change in polarisation contrast when rotating the HWP. Spatial non-
uniformities in the wave plate can also give rise to an asymmetry whereby
rotating the QWP by $180\text{\,}\mathrm{\SIUnitSymbolDegree}$ lowers the
coupling between the two bases. Similarly, the
$90\text{\,}\mathrm{\SIUnitSymbolDegree}$ periodicity of an ideal HWP implies
that (3) should have four minima, but in practice one might result in a higher
extinction ratio than the others.

##  IV Discussion

We have recalled a prescriptive step-by-step method for fibre polarisation
compensation, particularly suited for table-top quantum optics experiments, in
which the two measurement bases are decoupled. This is accomplished by mapping
a HWP before the fibre to a source of tunable birefringence after the fibre.
The compensation procedure could therefore be also carried out with a direct
source of tunable birefringence, such as electro-optic devices, or strongly
birefringent optics with a tilt degree of freedom. The former have drawbacks
in terms of cost and complexity, while the latter can cause unwanted beam
distortions due to non-normal incidence or spatial walk-off. Tunable
birefringence can alternatively be achieved with birefringent wedge pairs,
while maintaining near-normal incidence and small walk-off. Setting aside the
fact that wave plates are a more common optical element and thus more likely
to be on hand, this approach has minor practical drawbacks, requiring a more
onerous pre-alignment and more complex opto-mechanical components.

Compared to only using a single fibre polarisation controller the method
presented here requires two additional optical elements, but is significantly
easier to carry out or automate, leading to higher achieved polarisation
contrasts in practical scenarios. The higher performance is also related to
the fact that mechanical fibre polarisation controllers based on spooled
fibres [9] typically exhibit non-negligible retardance errors, causing them to
not span the full space of polarisation rotations. When only using the fibre
polarisation controller to satisfy one of the minimisation conditions such
imperfections do not have as adverse an effect on the device performance. This
is because an ideal three-parameter polarisation controller is overcomplete
for this task, and the redundant DOF can be used to compensate for the
imperfections. Finally, we conclude by reiterating that, while it was briefly
touched on in [30], the exact origins of this method remain unknown to us, and
we encourage the knowledgeable reader to inform us about earlier instances of
it being used.

## References

  * Imai and Matsumoto [1988] T. Imai and T. Matsumoto, Journal of Lightwave Technology 6, 1366 (1988).
  * Smith [1987] D. W. Smith, Journal of Lightwave Technology 5, 1466 (1987).
  * Sheem and Giallorenzi [1979] S. K. Sheem and T. G. Giallorenzi, Applied Physics Letters 35, 914 (1979).
  * Stowe  _et al._ [1982] D. W. Stowe, D. R. Moore, and R. G. Priest, IEEE Transactions on Microwave Theory Techniques 30, 1632 (1982).
  * Okoshi [1985] T. Okoshi, Journal of Lightwave Technology 3, 1232 (1985).
  * Ulrich [1979] R. Ulrich, Applied Physics Letters 35, 840 (1979).
  * Kersey  _et al._ [1991] A. D. Kersey, M. J. Marrone, and M. A. Davis, Electronics Letters 27, 518 (1991).
  * Kidoh  _et al._ [1981] Y. Kidoh, Y. Suematsu, and K. Furuya, IEEE Journal of Quantum Electronics 17, 991 (1981).
  * Lefevre [1980] H. C. Lefevre, Electronics Letters 16, 778 (1980).
  * Shimizu  _et al._ [1991] H. Shimizu, S. Yamazaki, T. Ono, and K. Emura, Journal of Lightwave Technology 9, 1217 (1991).
  * Shimizu and Kaede [1988] H. Shimizu and K. Kaede, Electronics Letters 24, 412 (1988).
  * Heismann [1994] F. Heismann, Journal of Lightwave Technology 12, 690 (1994).
  * Chen and Murphy [2011] A. Chen and E. Murphy,  _Broadband optical modulators: science, technology, and applications_ (CRC press, 2011).
  * Reddy  _et al._ [2016] S. G. Reddy, S. Prabhakar, P. Chithrabhanu, R. P. Singh, and R. Simon, Appl. Opt. 55, B14 (2016), arXiv:1412.7805 [quant-ph] .
  * Simon and Mukunda [1990] R. Simon and N. Mukunda, Physics Letters A 143, 165 (1990).
  * Lefevre [2022] H. C. Lefevre,  _The fiber-optic gyroscope_ (Artech house, 2022).
  * Noda  _et al._ [1986] J. Noda, K. Okamoto, and Y. Sasaki, Journal of Lightwave Technology 4, 1071 (1986).
  * Flamini  _et al._ [2018] F. Flamini, N. Spagnolo, and F. Sciarrino, Reports on Progress in Physics 82, 016001 (2018), arXiv:1803.02790 [quant-ph] .
  * Gisin  _et al._ [2002] N. Gisin, G. Ribordy, W. Tittel, and H. Zbinden, Rev. Mod. Phys. 74, 145 (2002), arXiv:quant-ph/0101098 [quant-ph] .
  * Kersey  _et al._ [1988] A. D. Kersey, M. J. Marrone, and A. Dandridge, Optics Letters 13, 847 (1988).
  * Yao  _et al._ [2019] X. S. Yao, H. Xuan, X. Chen, H. Zou, X. Liu, and X. Zhao, Optics Express 27, 19984 (2019).
  * Silvestri  _et al._ [2023] R. Silvestri, H. Yu, T. Strömberg, C. Hilweg, R. W. Peterson, and P. Walther, arXiv e-prints , arXiv:2310.16903 (2023), arXiv:2310.16903 [quant-ph] .
  * Chen  _et al._ [2007] J. Chen, G. Wu, Y. Li, E. Wu, and H. Zeng, Optics Express 15, 17928 (2007).
  * Xavier  _et al._ [2008] G. B. Xavier, G. Vilela de Faria, G. P. Temporão, and J. P. von der Weid, Optics Express 16, 1867 (2008), arXiv:0710.4093 [quant-ph] .
  * Chen  _et al._ [2009] J. Chen, G. Wu, L. Xu, X. Gu, E. Wu, and H. Zeng, New Journal of Physics 11, 065004 (2009).
  * Pan  _et al._ [2017] L. Pan, K. Liu, J. Jiang, C. Ma, P. Ma, and T. Liu, IEEE Photonics Technology Letters 29, 834 (2017).
  * Shi  _et al._ [2021] Y. Shi, H. S. Poh, A. Ling, and C. Kurtsiefer, Optics Express 29, 37075 (2021), arXiv:2107.07654 [quant-ph] .
  * Ramos  _et al._ [2022] M. F. Ramos, N. A. Silva, N. J. Muga, and A. N. Pinto, Optics Express 30, 6907 (2022).
  * Peranić  _et al._ [2022] M. Peranić, M. Clark, R. Wang, S. Bahrani, O. Alia, S. Wengerowsky, A. Radman, M. Lončarić, M. Stipčević, J. Rarity, R. Nejabati, and S. K. Joshi, arXiv e-prints , arXiv:2208.13584 (2022), arXiv:2208.13584 [quant-ph] .
  * Prevedel [2009] R. Prevedel,  _Experimental all-optical one-way quantum computing_ , Ph.D. thesis, University of Vienna (2009).