# On the Nash Equilibria
of a Simple Discounted Duel

Athanasios Kehagias

###### Abstract

We formulate and study a two-player _static duel_ game as a _nonzero-sum
discounted stochastic game._ Players $P_{1},P_{2}$ are standing in place and,
in each turn, one or both _may_ shoot at the “other” player. If $P_{n}$ shoots
at $P_{m}$ ($m\neq n$), either he hits and kills him (with probability
$p_{n}$) or he misses him and $P_{m}$ is unaffected (with probability
$1-p_{n}$). The process continues until at least one player dies; if nobody
ever dies, the game lasts an infinite number of turns. Each player receives
unit payoff for each turn in which he remains alive; no payoff is assigned to
killing the opponent. We show that the the always-shooting strategy is a NE
but, in addition, the game also possesses “ _cooperative_ ” (i.e., non-
shooting) Nash equilibria in both stationary and nonstationary strategies. A
certain similarity to the repeated Prisoner’s Dilemma is also noted and
discussed.

##  1 Introduction

In this paper we study a two-player _static duel_ game played in turns.
Players $P_{1},P_{2}$ are standing in place and, in each turn, one or both
_may_ shoot at the “other” player. If $P_{n}$ shoots at $P_{m}$ ($m\neq n$),
either he hits and kills him or he misses him and $P_{m}$ is unaffected; the
respective probabilities are $p_{n}$ and $1-p_{n}$. The process continues
until at least one player dies; it is possible that nobody ever dies and the
game lasts an infinite number of turns. We formulate the above as a _nonzero-
sum discounted stochastic game._ The game rules and the players’ payoff
function will be presented in the next section.

Little work has been done on the static duel. Actually, as far as we know, it
has only been studied as a preliminary step in the study of the “static
_truel_ ”, in which _three_ stationary players shoot at each other. Early
works on the static truel are [11, 16, 18, 19, 20] in which the postulated
game rules guarantee the existence of _exactly one_ survivor (“winner”). A
more general analysis appears in [17] which considers the possibility of
“cooperation” between the players. This idea is further studied in [13, 14,
15, 25]. Recent papers on the truel include [1, 2, 3, 5, 6, 7, 8, 9, 22, 23,
24]. 111Let us also note the existence of an extensive literature on a quite
different type of duel games, which essentially are _games of timing_ [4, 10,
12]. However, this literature is not relevant to the game studied in this
paper.

While the above papers focus on various forms of the static truel, we believe
that the static duel is interesting in its own right and has not received the
attention it deserves. In particular we will show that, under our formulation,
the static duel has a certain similarity to the _repeated Prisoner’s Dilemma_
and possesses “ _cooperative_ ” Nash equilibria in _nonstationary strategies_.

This paper is structured as follows. In Section 2 we define the game
rigorously. In Section 3 we introduce several stationary and nonstationary
strategies and compute their expected payoffs. In Section 4 we prove that
certain pairs of the previously defined strategies are Nash equilibria. In
Section 5 we discuss the obtained results and the connection of the static
duel to the repeated Prisoner’s Dilemma. Finally, in Section 6 we summarize
our results and propose some future research directions.

##  2 The Game

The game involves players $P_{1},P_{2}$ and proceeds at discrete time steps
(_rounds_) $t\in\left\\{1,2,...\right\\}$. The _state_ at time $t$ is

$s\left(t\right)=\left(s_{1}\left(t\right),s_{2}\left(t\right)\right)\in
S=\left\\{\left(1,1\right),\left(1,0\right),\left(0,1\right),\left(0,0\right),\left(\tau,\tau\right)\right\\}.$

For $n\in\left\\{1,2\right\\}$, $s_{n}\left(t\right)$ is $P_{n}$’s _state_ at
$t\in\left\\{0,1,2,...\right\\}$ and can be

$\begin{array}[c]{ll}1:&\text{when }P_{n}\text{ is alive,}\\\ 0:&\text{when
}P_{n}\text{ dies in the current round,}\\\ \tau:&\text{when one or both
players have died in a previous round.}\end{array}$

$P_{n}$’s _action_ at $t\in\left\\{1,2,...\right\\}$ is $f_{n}\left(t\right)$,
which can be $1$ ($P_{n}$ is shooting) or $0$ ($P_{n}$ is not shooting). If
$s_{n}\left(t-1\right)\neq 1$, $P_{n}$ cannot shoot at $t$ and
$f_{n}\left(t\right)$ must equal $0$; if $s_{n}\left(t-1\right)=1$ then
$f_{n}\left(t\right)$ can be either $0$ or $1$. When $f_{n}\left(t\right)=1$,
$s_{-n}\left(t\right)=0$ (i.e., $P_{-n}$ dies222In the sequel we use the
standard game theoretic notation by which $s_{-1}=s_{2}$, $s_{-2}=s_{1}$. The
same notation is used for players, actions etc.) with probability
$p_{n}\in\left(0,1\right)$ and $s_{-n}\left(t\right)=1$ with probability
$1-p_{n}$. We set
$f\left(t\right)=\left(f_{1}\left(t\right),f_{2}\left(t\right)\right)$ and
$\mathbf{p}=\left(p_{1},p_{2}\right)$. Note that we have assumed that $p_{1}$,
$p_{2}$ are different from both zero and one.

The game starts at an initial state $s\left(0\right)$; obviously, the main
case of interest is $s\left(0\right)=\left(1,1\right)$. At times
$t\in\left\\{1,2,...\right\\}$ the players choose simultaneously the actions
$f_{1}\left(t\right)$, $f_{2}\left(t\right)$ and the game moves to state
$s\left(t\right)$ according to the conditional _state transition probability_
$\Pr\left(s\left(t\right)|s\left(t-1\right),f\left(t\right)\right)$. In Figure
1 we present the state transition diagram, in which the action-dependent
transition probabilities are written next to the edges; it is easily verified
that these probabilities conform to the game rules. The figure shows that the
game starting at $\left(1,1\right)$, lasts an infinite number of rounds and
two possibilities exist.

  1. 1.

The game always stays in $\left(1,1\right)$ (no player is ever killed).

  2. 2.

At some $t^{\prime}$ the game moves to a state
$s\in\left\\{\left(1,0\right),\left(0,1\right),\left(0,0\right)\right\\}$ (one
or both players are killed) and at $t^{\prime}+1$ the game moves to the
_terminal_ state $\left(\tau,\tau\right)$, where it stays for ever after.

Figure 1: State transition diagram of the static duel game.

A _finite history_ is a sequence
$h=s\left(0\right)f\left(1\right)s\left(1\right)...f\left(T\right)s\left(T\right)$;
an _infinite history_ is an
$h=s\left(0\right)f\left(1\right)s\left(1\right)...\ $. An _admissible_
history is one which conforms to the game rules; the set of all admissible
finite (resp. infinite) histories is denoted by $H$ (resp. $H^{\infty}$). For
every history $h$ and for $n\in\left\\{1,2\right\\}$, we define $P_{n}$’s
_total payoff function_ to be

$Q_{n}\left(h\right)=\sum_{t=0}^{\infty}\gamma^{t}q_{n}\left(s\left(t\right)\right)$

where $\gamma\in\left(0,1\right)$ is the _discounting factor_ and
$q_{n}:S\rightarrow\mathbb{R}$ is $P_{n}$’s _stage payoff function_ , defined
as follows.

$q_{1}\left(\tau,\tau\right)=0,$ | $q_{2}\left(\tau,\tau\right)=0,$
---|---
$q_{1}\left(1,1\right)=1,$ | $q_{2}\left(1,1\right)=1,$
$q_{1}\left(1,0\right)=\frac{1}{1-\gamma},$ | $q_{2}\left(1,0\right)=0,$
$q_{1}\left(0,1\right)=0,$ | $q_{2}\left(0,1\right)=\frac{1}{1-\gamma},$
$q_{1}\left(0,0\right)=0,$ | $q_{2}\left(0,0\right)=0.$

The above values indicate that each player receives one payoff unit for every
turn in which he stays alive; the payoff
$q_{1}\left(1,0\right)=\frac{1}{1-\gamma}$ incorporates the infinite payoff
sequence $\sum_{t=0}^{\infty}\gamma^{t}1=\frac{1}{1-\gamma}$ (this will result
when $P_{1}$ kills $P_{2}$ and stays alive for the infinite number of
subsequent turns). Note that a player receives no direct payoff from killing
his opponent, but he has the indirect benefit of removing the possibility of
being killed himself.

A _strategy_ for $P_{n}\ $is a function
$\sigma_{n}:H\rightarrow\left[0,1\right]$ which corresponds to every finite
history $h$ the probability

$x_{n}=\sigma_{n}\left(h\right)=\Pr\left(\text{\textquotedblleft}P_{n}\text{
shoots at }P_{-n}\text{\textquotedblright}\right).$

A _stationary strategy_ is a $\sigma_{n}$ depending only on the current state
$s$, hence we simply write $x_{n}=\sigma_{n}\left(s\right)$. A _strategy
profile_ is a vector $\sigma=\left(\sigma_{1},\sigma_{2}\right)$. We denote
the set of all _admissible_ strategies (those which are compatible with the
game rules) by $\Sigma$ and the set of all admissible stationary strategies by
$\overline{\Sigma}$.

Given the initial state $s\left(0\right)$ and the strategies $\sigma_{1}$ and
$\sigma_{2}$, used by $P_{1}$ and $P_{2}$ respectively, a probability measure
is defined on the set of all infinite histories. Since
$\gamma\in\left(0,1\right)$, the _total expected payoffs_

$\forall
n\in\left\\{1,2\right\\}:\overline{Q}_{n}\left(s\left(0\right),\sigma_{1},\sigma_{2}\right)=\mathbb{E}\left(Q_{n}\left(h\right)|s\left(0\right),\sigma_{1},\sigma_{2}\right)$

are well defined.

We have thus formulated the simultaneous static duel as a discounted
stochastic game, which we will denote by
$\Gamma\left(s\left(0\right),\gamma,\mathbf{p}\right)$ or simpl;y
$\Gamma\left(s\left(0\right),\gamma\right)$, when $\left(p_{1},p_{2}\right)$
is fixed. Our main interest is in the _nonzero-sum_ game
$\Gamma\left(\left(1,1\right),\gamma\right)$. We assume that $P_{1}$ and
$P_{2}$ attempt to reach a _Nash equilibrium_ (NE), i.e., a strategy profile
$\left(\widehat{\sigma}_{1},\widehat{\sigma}_{2}\right)$ such that

$\forall
n\in\left\\{1,2\right\\}:\forall\sigma_{n}\in\Sigma:\overline{Q}_{n}\left(\left(1,1\right),\widehat{\sigma}_{n},\widehat{\sigma}_{-n}\right)\geq\overline{Q}_{n}\left(\left(1,1\right),\sigma_{n},\widehat{\sigma}_{-n}\right).$

##  3 Some Basic Strategies and Their Payoffs

In this section we introduce several strategies which we will use in our later
exploration of Nash equilibria.

###  3.1 The Stationary Strategy $\sigma^{S}$

When $P_{n}$ ($n\in\left\\{1,2\right\\}$) uses a stationary admissible
strategy $\sigma_{n}$, we have $\sigma_{n}\left(s\right)=0$ for
$s\in\left\\{\left(1,0\right),\left(0,1\right),\left(0,0\right),\left(\tau,\tau\right)\right\\}$
and $\sigma_{n}$ is fully specified by the value
$\sigma_{n}\left(1,1\right)=x_{n}$. Hence we will sometimes write
$\overline{Q}_{n}\left(\left(1,1\right),x_{1},x_{2}\right)$ in place of
$\overline{Q}_{n}\left(\left(1,1\right),\sigma_{1},\sigma_{2}\right)$.

Let
$V_{1}^{S}\left(x_{1},x_{2}\right)=\overline{Q}_{1}\left(\left(1,1\right),x_{1},x_{2}\right)$;
for brevity we will also write simply $V_{1}^{S}$. Then $V_{1}^{S}$ satisfies
the equation

$\displaystyle V_{1}^{S}$ $\displaystyle=1+\gamma
p_{1}x_{1}\left(x_{2}\left(1-p_{2}\right)+(1-x_{2})\right)\frac{1}{1-\gamma}$
(1)
$\displaystyle\qquad\qquad\qquad+\gamma\left(x_{1}\left(1-p_{1}\right)+\left(1-x_{1}\right)\right)\left(x_{2}\left(1-p_{2}\right)+\left(1-x_{2}\right)\right)V_{1}^{S},$

obtained by the following reasoning. When the game is in state
$s=\left(1,1\right)$, $P_{1}$’s expected payoff is one unit for the current
state plus the discounted expected payoff from the subsequent state
$s^{\prime}$, for which we have the following possibilities.

  1. 1.

$s^{\prime}=\left(1,0\right)$ when $P_{1}$ shoots and hits $P_{2}$ and $P_{2}$
either shoots and misses or does not shoot; the respective probability is
$p_{1}x_{1}\left(x_{2}\left(1-p_{2}\right)+(1-x_{2})\right)$. The total
expected payoff of this case is
$\overline{Q}_{1}\left(\left(1,0\right),x_{1},x_{2}\right)=\frac{1}{1-\gamma}$.

  2. 2.

$s^{\prime}=\left(1,1\right)$ when _each of_ $P_{1}$ and $P_{2}$ either shoots
and misses or does not shoot; the respective probability is
$\left(x_{1}\left(1-p_{1}\right)+\left(1-x_{1}\right)\right)\left(x_{2}\left(1-p_{2}\right)+\left(1-x_{2}\right)\right)$.
In this case we have returned to the starting state $\left(1,1\right)$ and the
additional total expected payoff is again
$\overline{Q}_{1}\left(\left(1,1\right),x_{1},x_{2}\right)$.

  3. 3.

We also have the possibilities of moving into $\left(0,1\right)$ and
$\left(0,0\right)$, but these yield zero payoff to $P_{1}$, so they are not
included in (1).

Solving (1) we get, after some algebraic calculations333The calculations
required to obtain the solution have been performed by the computer algebra
system Maple and then verified by hand. This is also true of additional
(sometimes quite complicated) calculations required in the rest of the paper.,
that

$V_{1}^{S}\left(x_{1},x_{2}\right)=\frac{1-\gamma\left(1-p_{1}x_{1}\left(1-p_{2}x_{2}\right)\right)}{\left(1-\gamma\right)\left(1-\gamma\left(1-p_{1}x_{1}\right)\left(1-p_{2}x_{2}\right)\right)}.$
(2)

In what follows we will often work with the _normalized_ total expected
payoff. In this case, it is

$v_{1}^{S}\left(x_{1},x_{2}\right)=\left(1-\gamma\right)\overline{Q}_{1}\left(\left(1,1\right),x_{1},x_{2}\right)=\frac{1-\gamma\left(1-p_{1}x_{1}\left(1-p_{2}x_{2}\right)\right)}{1-\gamma\left(1-p_{1}x_{1}\right)\left(1-p_{2}x_{2}\right)}$
(3)

Formulas for
$V_{2}^{S}\left(x_{1},x_{2}\right)=\overline{Q}_{2}\left(\left(1,1\right),x_{1},x_{2}\right)$
and
$v_{2}^{S}\left(x_{1},x_{2}\right)=\left(1-\gamma\right)\overline{Q}_{2}\left(\left(1,1\right),x_{1},x_{2}\right)$
can be obtained by interchanging the indices $1$ and $2\ $in (2)-(3).

###  3.2 The Cooperating Strategy $\sigma^{C}$

The stationary “cooperating” (the name will be justified in Section 5)
strategy $\sigma^{C}$ is defined by

$\sigma^{C}\left(1,1\right)=0\text{, which means the player never shoots.}$

Obviously, $\sigma^{C}$ is $\sigma^{S}$ with $x_{n}=0$ and
$\overline{Q}_{n}\left(\left(1,1\right),\sigma^{C},\sigma^{C}\right)=\overline{Q}_{n}\left(\left(1,1\right),0,0\right)$.
Hence we obtain
$V_{1}^{C}=\overline{Q}_{1}\left(\left(1,1\right),\sigma^{C},\sigma^{C}\right)=\overline{Q}_{1}\left(\left(1,1\right),0,0\right)$
by setting $x_{1}=x_{2}=0$ in (2). Consequently the expected and normalized
expected total payoff are

$V_{1}^{C}=\frac{1}{1-\gamma},\qquad
v_{1}^{C}=\left(1-\gamma\right)V_{1}^{C}=1$

Formulas for $V_{2}^{C}=\overline{Q}_{2}\left(\sigma^{C},\sigma^{C}\right)$,
$v_{2}^{c}=\left(1-\gamma\right)V_{2}^{C}$ are obtained by exchanging the
indices $1$ and $2$ in the above formulas.

###  3.3 The Defecting Strategy $\sigma^{D}$

The stationary “defecting” (the name will be justified in Section 5) strategy
$\sigma^{D}$ is defined by

$\sigma^{D}\left(1,1\right)=1\text{, which means the player always shoots with
probability one.}$

Obviously, $\sigma^{D}$ is $\sigma^{S}$ with $x_{n}=1$ and
$\overline{Q}_{n}\left(\left(1,1\right),\sigma^{D},\sigma^{D}\right)=\overline{Q}_{n}\left(\left(1,1\right),1,1\right)$.
Hence we obtain
$V_{1}^{D}=\overline{Q}_{1}\left(\left(1,1\right),\sigma^{D},\sigma^{D}\right)=\overline{Q}_{1}\left(\left(1,1\right),1,1\right)$
by setting $x_{1}=x_{2}=1$ in (2). We then get the expected and normalized
expected total payoff to be

$\displaystyle V_{1}^{D}$
$\displaystyle=\frac{1-\gamma\left(1-p_{1}\left(1-p_{2}\right)\right)}{\left(1-\gamma\right)\left(1-\gamma\left(1-p_{1}\right)\left(1-p_{2}\right)\right)}$
$\displaystyle v_{1}^{D}$
$\displaystyle=\left(1-\gamma\right)V_{1}^{D}\left(\gamma\right)=\frac{1-\gamma\left(1-p_{1}\left(1-p_{2}\right)\right)}{1-\gamma\left(1-p_{1}\right)\left(1-p_{2}\right)}$

Formulas for $V_{2}^{D}=\overline{Q}_{2}\left(\sigma^{D},\sigma^{D}\right)$,
$v_{2}^{D}=\left(1-\gamma\right)V_{2}^{D}$ are obtained by exchanging the
indices $1$ and $2$ in the above formulas.

###  3.4 The Early-Shooting Strategy $\sigma^{DC\left(K\right)}$

The nonstationary “early-shooting” strategy $\sigma^{DC\left(K\right)}$ is to
shoot (with probability one) only at times $1,2,...,K$, where $K$ is a
parameter of the strategy. Let
$V_{1}^{DC\left(K\right)}=Q_{1}\left(\left(1,1\right),\sigma^{DC\left(K\right)},\sigma^{DC\left(K\right)}\right)$;
then $V_{1}^{DC\left(K\right)}$ satisfies the equation:

$\displaystyle V_{1}^{DC\left(K\right)}$ $\displaystyle=1$
$\displaystyle+\gamma\left(p_{1}\left(1-p_{2}\right)\frac{1}{1-\gamma}+\left(1-p_{1}\right)\left(1-p_{2}\right)\right)$
$\displaystyle+\gamma^{2}\left(\left(1-p_{1}\right)p_{1}\left(1-p_{2}\right)^{2}\frac{1}{1-\gamma}+\left(1-p_{1}\right)^{2}\left(1-p_{2}\right)^{2}\right)$
$\displaystyle+...$ (4)
$\displaystyle+\gamma^{K-1}\left(\left(1-p_{1}\right)^{K-2}p_{1}\left(1-p_{2}\right)^{K-1}\frac{1}{1-\gamma}+\left(1-p_{1}\right)^{K-1}\left(1-p_{2}\right)^{K-1}\right)$
$\displaystyle+\gamma^{K}\left(\left(1-p_{1}\right)^{K-1}p_{1}\left(1-p_{2}\right)^{K}\frac{1}{1-\gamma}+\left(1-p_{1}\right)^{K}\left(1-p_{2}\right)^{K}V_{1}^{C}\right)$

This equation is justified as follows.

  1. 1.

At time $t=0$, $P_{1}$ receives a payoff of one unit.

  2. 2.

At times $t=1,...,K-1$, the expected payoffs are the following.

    1. (a)

With probability $\left(1-p_{1}\right)^{t-1}p_{1}\left(1-p_{2}\right)^{t}$,
$P_{1}$ misses at times $t^{\prime}=1,...,t-1$ and succeeds at time
$t^{\prime}$, while $P_{2}$ misses as times $t^{\prime}=1,...,t$. In this case
$P_{1}$ receives payoff $\frac{1}{1-\gamma}$.

    2. (b)

With probability $\left(1-p_{1}\right)^{t}\left(1-p_{2}\right)^{t}$, both
$P_{1}$ and $P_{2}$ miss at times $t^{\prime}=1,...,t$. In this case $P_{1}$
receives payoff $1$.

    3. (c)

All other possibilities yield zero payoff, so they are not included in the
equation.

  3. 3.

At time $t=K$, the expected payoffs are the following.

    1. (a)

With probability $\left(1-p_{1}\right)^{K-1}p_{1}\left(1-p_{2}\right)^{K}$,
$P_{1}$ misses at times $t^{\prime}=1,...,K-1$ and succeeds at time
$t^{\prime}=K$, while $P_{2}$ misses as times $t^{\prime}=1,...,K$. In this
case $P_{1}$ receives payoff $\frac{1}{1-\gamma}$.

    2. (b)

With probability $\left(1-p_{1}\right)^{K}\left(1-p_{2}\right)^{K}$, both
$P_{1}$ and $P_{2}$ miss at times $t^{\prime}=1,...,K$. In this case both
players will never shoot at subsequent times, so we have returned to the
starting state $\left(1,1\right)$ and the additional total expected payoff is
$V_{1}^{C}=\overline{Q}_{1}\left(\left(1,1\right),\sigma^{C},\sigma^{C}\right)$.

    3. (c)

All other possibilities yield zero payoff, so they are not included in the
equation.

Substituting in (4) the expression for $V_{1}^{C}$ we obtain the following
expressions for expected total and normalized expected total payoff:

$\displaystyle V_{1}^{DC\left(K\right)}$
$\displaystyle=\frac{1+\gamma^{K+1}(1-p_{1})^{K}(1-p_{2})^{K}p_{2}-\gamma(1-p_{1}+p_{1}p_{2})}{\left(1-\gamma\right)\left(1-\gamma\left(1-p_{1}\right)\left(1-p_{2}\right)\right)}$
$\displaystyle v_{1}^{DC\left(K\right)}$
$\displaystyle=\left(1-\gamma\right)V_{1}^{DC\left(K\right)}=\frac{1+\gamma^{K+1}(1-p_{1})^{K}(1-p_{2})^{K}p_{2}-\gamma(1-p_{1}+p_{1}p_{2})}{1-\gamma\left(1-p_{1}\right)\left(1-p_{2}\right)}$

Formulas for $V_{2}^{DC\left(K\right)}$, $v_{2}^{DC\left(K\right)}$ are
obtained by exchanging the indices $1$ and $2$ in the above formulas.

###  3.5 The Late-Shooting Strategy $\sigma^{CD\left(K\right)}$

The nonstationary “late-shooting” strategy $\sigma^{CD\left(K\right)}$ is to
shoot (with probability one) only at times $K,K+1,...$, where $K$ is a
parameter of the strategy. Let
$V_{1}^{CD\left(K\right)}=Q_{1}\left(\left(1,1\right),\sigma^{CD\left(K\right)},\sigma^{CD\left(K\right)}\right)$;
then $V_{1}^{CD\left(K\right)}$ satisfies the equation:

$V_{1}^{CD\left(K\right)}=1+\gamma+...+\gamma^{K-1}+\gamma^{K}\left(p_{1}\left(1-p_{2}\right)\frac{1}{1-\gamma}+\left(1-p_{1}\right)\left(1-p_{2}\right)V_{1}^{D}\right)$
(5)

This equation is justified as follows.

  1. 1.

At times $t=0,1,...,K-1$, $P_{1}$ receives discounted payoff of one unit.

  2. 2.

At time $t=K$ we have the following possibilities.

    1. (a)

With probability $p_{1}\left(1-p_{2}\right)$, $P_{1}$ hits $P_{2}$, while
$P_{2}$ misses. In this case $P_{1}$ receives payoff $\frac{1}{1-\gamma}$.

    2. (b)

With probability $\left(1-p_{1}\right)\left(1-p_{2}\right)$, both $P_{1}$ and
$P_{2}$ miss. In this case both $P_{1}$ and $P_{2}$ revert to strategy
$\sigma^{D}$ and $P_{1}$ receives total expected payoff
$V_{1}^{D}=\overline{Q}_{1}\left(\left(1,1\right),\sigma^{D},\sigma^{D}\right)$.

    3. (c)

All other possibilities yield zero payoff, so they are not included in the
equation.

Substituting in (5) the previously obtained expression for $V_{1}^{D}$ we get
the following expressions for expected total and normalized expected total
payoff:

$\displaystyle V_{1}^{CD\left(K\right)}$
$\displaystyle=\frac{1-\gamma^{K}p_{2}-\gamma(1-p_{1})\left(1-p_{2}\right)}{\left(1-\gamma\right)\left(1-\gamma\left(1-p_{1}\right)\left(1-p_{2}\right)\right)}$
$\displaystyle v_{1}^{CD\left(K\right)}$
$\displaystyle=\left(1-\gamma\right)V_{1}^{CD\left(K\right)}=\frac{1-\gamma^{K}p_{2}-\gamma(1-p_{1})\left(1-p_{2}\right)}{1-\gamma\left(1-p_{1}\right)\left(1-p_{2}\right)}$

Formulas for $V_{2}^{CD\left(K\right)}$, $v_{2}^{CD\left(K\right)}$ are
obtained by exchanging the indices $1$ and $2$ in the above formulas.

###  3.6 The Periodic-Shooting Strategy $\sigma^{P\left(M\right)}$

The nonstationary “periodic-shooting” strategy $\sigma^{P\left(M\right)}$ is
to shoot only at times $M+1,2M+2,...$, where $M$ is strategy parameter. Let
$V_{1}^{P\left(M\right)}=Q_{1}\left(\left(1,1\right),\sigma^{M},\sigma^{M}\right)$;
by reasoning similar to that of the previous cases, we see that
$V_{1}^{P\left(M\right)}$ satisfies the equation

$\displaystyle V_{1}^{P\left(M\right)}$
$\displaystyle=1+\gamma+...+\gamma^{M}$
$\displaystyle+\gamma^{M+1}\left(p_{1}\left(1-p_{2}\right)\frac{1}{1-\gamma}+\left(1-p_{1}\right)\left(1-p_{2}\right)V_{1}^{P\left(M\right)}\right)$
(6)

Solving (6) we get the following expressions for expected total and normalized
expected total payoff:

$\displaystyle V_{1}^{P\left(M\right)}$
$\displaystyle=\frac{1-\gamma^{M+1}\left(1-p_{1}\left(1-p_{2}\right))\right)}{\left(1-\gamma\right)\left(1-\gamma^{M+1}\left(1-p_{1}\right)\left(1-p_{2}\right)\right)}$
$\displaystyle v_{1}^{P\left(M\right)}$
$\displaystyle=\frac{1-\gamma^{M+1}\left(1-p_{1}\left(1-p_{2}\right)\right)}{1-\gamma^{M+1}\left(1-p_{1}\right)\left(1-p_{2}\right)}$

Formulas for $V_{2}^{P\left(M\right)}$, $v_{2}^{P\left(M\right)}$ are obtained
by exchanging the indices $1$ and $2$ in the above formulas.

###  3.7 Grim Strategies

Any $P_{n}$’s strategy $\sigma_{n}$ can be used to define a corresponding
_grim_ strategy $\widetilde{\sigma}_{n}$ as follows:

$\begin{array}[c]{ll}\widetilde{\sigma}_{n}:&\text{As long as }P_{-n}\text{
uses }\sigma_{n}\text{, }P_{n}\text{ also uses }\sigma_{n}\text{;}\\\
&\text{if at the }t\text{-th turn }P_{-n}\text{ deviates from
}\sigma_{n}\text{, }P_{n}\text{\ uses }\sigma^{D}\text{ in all subsequent
turns.}\end{array}$

For example, the grim-cooperating strategy $\widetilde{\sigma}^{C}$ dictates
that: $P_{n}$ never shoots, as long as $P_{-n}$ does not shoot either; if at
the $t$-th turn $P_{-n}$ shoots then, starting at the $\left(t+1\right)$-th
turn, $P_{n}$ will always shoot with probability one. Similarly we can get:

  1. 1.

the grim-defecting strategy $\widetilde{\sigma}^{D}$ (it is identical to
$\sigma^{D}$),

  2. 2.

the grim-early-shooting strategy $\widetilde{\sigma}^{DC\left(K\right)}$,

  3. 3.

the grim-late-shooting strategy $\widetilde{\sigma}^{CD\left(K\right)}$,

  4. 4.

the grim-periodic-shooting strategy $\widetilde{\sigma}^{P\left(M\right)}$.

##  4 Nash Equilibria

We will now pesent a sequence of propositions; each one indicates that a
certain strategy pair is a (stationary or nonstationary) NE; sometimes this
will only hold for a certain range of $\gamma$ and possibly $p_{1},p_{2}$
values.

###### Proposition 4.1

For every $\gamma\in\left(0,1\right)$, the only stationary NE of
$\Gamma\left(\left(1,1\right),\gamma\right)$ are
$\left(\sigma^{C},\sigma^{C}\right)$ and $\left(\sigma^{D},\sigma^{D}\right)$.

Proof. Suppose that $P_{1}$ (resp. $P_{2}$) uses the stationary strategy
$\sigma^{S}$ with $\sigma^{S}\left(1,1\right)=x_{1}$ (resp. $\sigma^{S}$ with
$\sigma^{S}\left(1,1\right)=x_{2}$ ). Then $P_{1}$’s payoff is

$V_{1}^{S}\left(x_{1},x_{2}\right)=\frac{1-\gamma\left(1-p_{1}x_{1}\left(1-p_{2}x_{2}\right)\right)}{\left(1-\gamma\right)\left(1-\gamma\left(1-p_{1}x_{1}\right)\left(1-p_{2}x_{2}\right)\right)}.$

Now suppose $P_{1}$ switches to $\sigma_{S}\left(1,1\right)=y_{1}$; his payoff
becomes

$V_{1}^{S}\left(y_{1},x_{2}\right)=\frac{1-\gamma\left(1-p_{1}y_{1}\left(1-p_{2}x_{2}\right)\right)}{\left(1-\gamma\right)\left(1-\gamma\left(1-p_{1}y_{1}\right)\left(1-p_{2}x_{2}\right)\right)}.$

Let us look at the difference of normalized payoffs

$\displaystyle\delta v_{1}$
$\displaystyle=\left(1-\gamma\right)\left(Q_{1}\left(\left(1,1\right),x_{1},x_{2}\right)-Q_{1}\left(\left(1,1\right),y_{1},x_{2}\right)\right)$
$\displaystyle=\frac{1-\gamma\left(1-p_{1}x_{1}\left(1-p_{2}x_{2}\right)\right)}{1-\gamma\left(1-p_{1}x_{1}\right)\left(1-p_{2}x_{2}\right)}-\frac{1-\gamma\left(1-p_{1}y_{1}\left(1-p_{2}x_{2}\right)\right)}{1-\gamma\left(1-p_{1}y_{1}\right)\left(1-p_{2}x_{2}\right)}$
$\displaystyle=\frac{\gamma^{2}p_{1}p_{2}x_{2}(x_{1}-y_{1})(1-p_{2}x_{2})}{((1-\gamma(1-p_{2}x_{2})(1-p_{1}y_{1}))(1-\gamma(1-p_{2}x_{2})(1-p_{1}x_{1})))}$

Now, $P_{1}$ has no incentive to switch from $x_{1}$ to $y_{1}$ iff $\delta
v_{1}\geq 0$ which is equivalent to

$\gamma^{2}p_{1}p_{2}x_{2}(x_{1}-y_{1})(1-p_{2}x_{2})\geq 0$

Similarly, $P_{2}$ has no incentive to switch from $x_{2}$ to $y_{2}$ iff

$\gamma^{2}p_{1}p_{2}x_{1}(x_{2}-y_{2})(1-p_{1}x_{1})\geq 0$

Hence, the following hold for $n\in\left\\{1,2\right\\}$.

  1. 1.

If $\left(x_{1},x_{2}\right)=\left(0,0\right)$, $P_{n}$ has no incentive to
change $x_{n}$; $\left(x_{1},x_{2}\right)=\left(0,0\right)$; hence
$\left(\sigma^{C},\sigma^{C}\right)$ is a NE.

  2. 2.

If $\left(x_{1},x_{2}\right)=\left(1,1\right)$, $P_{n}$ has no incentive to
change $x_{n}$; $\left(x_{1},x_{2}\right)=\left(1,1\right)$; hence
$\left(\sigma^{D},\sigma^{D}\right)$ is a NE.

  3. 3.

If $\left(x_{1},x_{2}\right)\in\left(0,1\right)\times\left(0,1\right)$ then it
cannot be a NE, because $P_{n}$ has incentive to change (unilaterally) from
$x_{n}$ to $1$.

This completes the proof.

Now we will start looking at NE obtained from combinations of grim strategies.

###### Proposition 4.2

For every $\gamma\in\left(0,1\right)$,
$\left(\widetilde{\sigma}^{C},\widetilde{\sigma}^{C}\right)$ is a NE of
$\Gamma\left(\left(1,1\right),\gamma\right)$.

Proof. Suppose that both $P_{1}$ and $P_{2}$ use $\widetilde{\sigma}^{C}$.
Then $P_{1}$’s payoff is

$V_{1}^{C}=Q_{1}\left(\widetilde{\sigma}^{C},\widetilde{\sigma}^{C}\right)=Q_{1}\left(\sigma^{C},\sigma^{C}\right)=\frac{1}{1-\gamma}.$

Now suppose $P_{1}$ deviates from $\widetilde{\sigma}^{C}$. It suffices to
examine the case in which $P_{1}$ deviates at $t=1$; furthermore, after
$P_{1}$ deviates (i.e., starting at $t=2$) $P_{2}$ will switch to $\sigma^{D}$
and $P_{1}$ has no incentive to not shoot at any $t\geq 2$. 444This is a
consequence of the following fact, which we will often use in the remainder of
the paper. If $P_{n}$ starts using a stationary strategy $\sigma_{n}$ at some
time $t$, then $P_{-n}$’s best response is also a stationary strategy. This is
the case because, for a fixed stationary $\sigma_{n}$, $P_{-n}$ has to solve a
_Markov Decision Process_ , for which the optimal strategy is stationary. For
more details see [21]. Hence $P_{1}$ is essentially using the strategy
$\sigma_{1}=\sigma^{D}$ and his total expected payoff will then be

$\displaystyle V_{1}$
$\displaystyle=Q_{1}\left(\sigma^{D},\widetilde{\sigma}^{C}\right)=1+\gamma\left(p_{1}\frac{1}{1-\gamma}+\left(1-p_{1}\right)\left(1+\gamma
Q_{1}\left(\sigma^{D},\sigma^{D}\right)\right)\right)$
$\displaystyle=1+\gamma\left(p_{1}\frac{1}{1-\gamma}+\left(1-p_{1}\right)\left(1+\gamma\frac{1-\gamma\left(1-p_{1}\left(1-p_{2}\right)\right)}{\left(1-\gamma\right)\left(1-\gamma\left(1-p_{1}\right)\left(1-p_{2}\right)\right)}\right)\right)$
$\displaystyle=\frac{1-p_{2}(1-p_{1})\gamma^{3}-(1-p_{2})(1-p_{1})\gamma}{\left(1-\gamma\right)\left(1-\gamma\left(1-p_{1}\right)\left(1-p_{2}\right)\right)}$

Now

$\displaystyle\left(1-\gamma\right)\left(Q_{1}\left(\widetilde{\sigma}^{C},\widetilde{\sigma}^{C}\right)-Q_{1}\left(\sigma^{D},\widetilde{\sigma}^{C}\right)\right)$
$\displaystyle=\left(1-\gamma\right)\left(V_{1}^{C}-V_{1}\right)$
$\displaystyle=1-\frac{1-p_{2}(1-p_{1})\gamma^{3}-(1-p_{2})(1-p_{1})\gamma}{1-\gamma\left(1-p_{1}\right)\left(1-p_{2}\right)}$
$\displaystyle=\allowbreak\frac{\gamma^{3}p_{2}\left(1-p_{1}\right)}{1-\gamma\left(1-p_{1}\right)\left(1-p_{2}\right)}>0$

Hence $P_{1}$ has no incentive to deviate from $\widetilde{\sigma}^{C}$. The
same can be proved for $P_{2}$. Consequently
$\left(\widetilde{\sigma}^{C},\widetilde{\sigma}^{C}\right)$ is a NE.

In the next proposition the strategy profile is a NE only for “large enough”
$\gamma$.

###### Proposition 4.3

There exist some $\gamma_{0}\in\left(0,1\right)$ such that: for all
$\gamma\in\left(\gamma_{0},1\right)$, and for all $K\in\mathbb{N}$,
$\left(\widetilde{\sigma}^{DC\left(K\right)},\widetilde{\sigma}^{DC\left(K\right)}\right)\
$is a NE of $\Gamma\left(\left(1,1\right),\gamma\right)$.

Proof. Recall that, when both players use
$\widetilde{\sigma}^{DC\left(K\right)}$, $P_{1}$ receives payoff

$V_{1}^{DC\left(K\right)}=Q_{1}\left(\left(1,1\right),\widetilde{\sigma}^{DC\left(K\right)},\widetilde{\sigma}^{DC\left(K\right)}\right)=\frac{1+\gamma^{K+1}(1-p_{1})^{K}(1-p_{2})^{K}p_{2}-\gamma(1-p_{1}+p_{1}p_{2})}{\left(1-\gamma\right)\left(1-\gamma\left(1-p_{1}\right)\left(1-p_{2}\right)\right)}$

Let us show that $P_{1}$ has no incentive to use a deviating strategy
$\sigma_{1}$.

  1. 1.

Case I: Let us first consider strategies which deviate at times
$t\in\left\\{K+1,K+2,...\right\\}$; i.e., they shoot after the game has
entered the no-shooting phase. We actually need to consider only $\sigma_{1}$
which will shoot at $t=K+1$ and with probability one. In this case

$\displaystyle
Q_{1}\left(\left(1,1\right),\widetilde{\sigma}^{DC\left(K\right)},\widetilde{\sigma}^{DC\left(K\right)}\right)$
$\displaystyle=A+\gamma^{K+1}Q_{1}\left(\left(1,1\right),\widetilde{\sigma}^{DC\left(K\right)},\widetilde{\sigma}^{DC\left(K\right)}\right)$
$\displaystyle=A+\gamma^{K+1}Q_{1}\left(\left(1,1\right),\sigma^{C},\sigma^{C}\right)=A+\gamma^{K+1}V_{1}^{C}$
$\displaystyle
Q_{1}\left(\left(1,1\right),\sigma^{1},\widetilde{\sigma}^{DC\left(K\right)}\right)$
$\displaystyle=A+\gamma^{K+1}Q_{1}\left(\left(1,1\right),\sigma^{1},\widetilde{\sigma}^{DC\left(K\right)}\right)$
$\displaystyle=A+\gamma^{K+1}Q_{1}\left(\left(1,1\right),\sigma^{1},\widetilde{\sigma}^{DC\left(K\right)}\right)$

where $A$ is the expected payoff summed over times
$t\in\left\\{0,...,K\right\\}$ and is the same for both strategies used by
$P_{1}$. Now, for the usual reasons, $P_{1}$ will keep shooting at
$t\in\left\\{K+2,K+3,...\right\\}$ and we will have

$\displaystyle V_{1}$
$\displaystyle=Q_{1}\left(\left(1,1\right),\sigma^{1},\widetilde{\sigma}^{DC\left(K\right)}\right)=p_{1}\frac{1}{1-\gamma}+\left(1-p_{1}\right)\left(1+\gamma
Q_{1}\left(\sigma^{D},\sigma^{D}\right)\right)$
$\displaystyle=p_{1}\frac{1}{1-\gamma}+\left(1-p_{1}\right)\left(1+\gamma\frac{1-\gamma\left(1-p_{1}\left(1-p_{2}\right)\right)}{\left(1-\gamma\right)\left(1-\gamma\left(1-p_{1}\right)\left(1-p_{2}\right)\right)}\right)$
$\displaystyle=\frac{1-p_{2}(1-p_{1})\gamma^{2}-(1-p_{2})(1-p_{1})\gamma}{\left(1-\gamma\right)\left(1-\gamma\left(1-p_{1}\right)\left(1-p_{2}\right)\right)}$

Then we have

$\displaystyle\left(1-\gamma\right)\left(Q_{1}\left(\left(1,1\right),\widetilde{\sigma}^{C},\widetilde{\sigma}^{C}\right)-Q_{1}\left(\left(1,1\right),\sigma^{D},\widetilde{\sigma}^{C}\right)\right)$
$\displaystyle=\left(1-\gamma\right)\left(V_{1}^{C}-V_{1}\right)$
$\displaystyle=1-\frac{1-p_{2}(1-p_{1})\gamma^{2}-(1-p_{2})(1-p_{1})\gamma}{1-\gamma\left(1-p_{1}\right)\left(1-p_{2}\right)}$
$\displaystyle=\frac{p_{2}(1-p_{1})\gamma^{2}}{1-\gamma\left(1-p_{1}\right)\left(1-p_{2}\right)}>0$

Hence $P_{1}$ has no incentive to shoot at $t>K$.

  2. 2.

Case II: Let us next consider strategies which deviate at times
$t\in\left\\{1,2,...,K\right\\}$, i.e., they do not shoot during the shooting
phase. Again, after the first deviation $P_{1}$ has no incentive to not shoot.
So we only need to consider strategies $\sigma_{1}$ which (a) do not shoot at
some $t=L\in\left\\{1,2,...,K\right\\}$ and (b) shoot at all
$t\in\left\\{1,2,...,L-1,L+1,...\right\\}$. Then, by the usual arguments,

$\displaystyle V_{1}$
$\displaystyle=Q_{1}\left(\left(1,1\right),\sigma_{1},\widetilde{\sigma}^{DC\left(K\right)}\right)$
$\displaystyle=1$
$\displaystyle+\gamma\left(p_{1}\left(1-p_{2}\right)\frac{1}{1-\gamma}+\left(1-p_{1}\right)\left(1-p_{2}\right)\right)$
$\displaystyle+\gamma^{2}\left(\left(1-p_{1}\right)p_{1}\left(1-p_{2}\right)^{2}\frac{1}{1-\gamma}+\left(1-p_{1}\right)^{2}\left(1-p_{2}\right)^{2}\right)$
$\displaystyle+...$
$\displaystyle+\gamma^{L-1}\left(\left(1-p_{1}\right)^{L-2}p_{1}\left(1-p_{2}\right)^{L-1}\frac{1}{1-\gamma}+\left(1-p_{1}\right)^{L-1}\left(1-p_{2}\right)^{L-1}\right)$
$\displaystyle+\gamma^{L}\left(\left(1-p_{1}\right)^{L-1}p_{1}\left(1-p_{2}\right)^{L}\frac{1}{1-\gamma}+\left(1-p_{1}\right)^{L}\left(1-p_{2}\right)^{L}\left(1+\gamma
V_{1}^{D}\right)\right)$
$\displaystyle=1+\sum_{k=1}^{L-1}\gamma^{k}\left(\left(1-p_{1}\right)^{k-1}p_{1}\left(1-p_{2}\right)^{k}\frac{1}{1-\gamma}+\left(1-p_{1}\right)^{k}\left(1-p_{2}\right)^{k}\right)$
$\displaystyle+\gamma^{L}\left(1-p_{1}\right)^{L-1}\left(1-p_{2}\right)^{L}p_{1}\frac{1}{1-\gamma}$
$\displaystyle+\gamma^{L}\left(1-p_{1}\right)^{L}\left(1-p_{2}\right)^{L}\left(1+\gamma\frac{1-\gamma\left(1-p_{1}\left(1-p_{2}\right)\right)}{\left(1-\gamma\right)\left(1-\gamma\left(1-p_{1}\right)\left(1-p_{2}\right)\right)}\right)$

Let

$\displaystyle\delta v_{1}\left(\gamma\right)$
$\displaystyle=\left(1-\gamma\right)\left(Q_{1}\left(\left(1,1\right),\widetilde{\sigma}^{DC\left(K\right)},\widetilde{\sigma}^{DC\left(K\right)}\right)-Q_{1}\left(\left(1,1\right),\sigma_{1},\widetilde{\sigma}^{DC\left(K\right)}\right)\right)$
$\displaystyle=V_{1}^{DC\left(K\right)}-V_{1}.$

Note that $\delta v_{1}\left(\gamma\right)$ is well defined and continuous for
all $\gamma\in\left[0,1\right]$, because the factor $\left(1-\gamma\right)$
cancels the $\left(1-\gamma\right)$ factor in the denominator of

$Q_{1}\left(\left(1,1\right),\widetilde{\sigma}^{DC\left(K\right)},\widetilde{\sigma}^{DC\left(K\right)}\right)-Q_{1}\left(\left(1,1\right),\sigma_{1},\widetilde{\sigma}^{DC\left(K\right)}\right).$

After a considerable amount of algebra555Using Maple once again. we find that

$\delta
v_{1}\left(1\right)=\frac{\left(1-p_{1}\right)^{K}\left(1-p_{2}\right)^{K}p_{2}}{p_{1}+\left(1-p_{1}\right)p_{2}}>0.$

Since $\delta v_{1}\left(\gamma\right)$ is continuous, there will exist some
$\gamma_{0}\in\left(0,1\right)$ such that $\delta v_{1}\left(\gamma\right)$
will be positive for every $\gamma\in\left(\gamma_{0},1\right)$ and for every
$K\in\mathbb{N}$. Hence, for such values, $P_{1}$ has no incentive to deviate
during the shooting phase.

Putting together Cases I and II we see that $P_{1}$ has no incentive to
deviate from $\widetilde{\sigma}^{DC\left(K\right)}$. The same is proved,
similarly, for $P_{2}$. Hence
$\left(\widetilde{\sigma}^{DC\left(K\right)},\widetilde{\sigma}^{DC\left(K\right)}\right)$
is a NE.

Next we present a negative result: mutual late shooting is not a NE.

###### Proposition 4.4

For every $\gamma\in\left(0,1\right)$ and every $K\in\mathbb{N}$,
$\left(\widetilde{\sigma}^{CD\left(K\right)},\widetilde{\sigma}^{CD\left(K\right)}\right)$
is not a NE of $\Gamma\left(\left(1,1\right),\gamma\right)$.

Proof. Recall that

$V_{1}^{CD\left(K\right)}=Q_{1}\left(\widetilde{\sigma}^{CD\left(K\right)},\widetilde{\sigma}^{CD\left(K\right)}\right)=\frac{1-\gamma^{K}p_{2}-\gamma(1-p_{1})\left(1-p_{2}\right)}{\left(1-\gamma\right)\left(1-\gamma\left(1-p_{1}\right)\left(1-p_{2}\right)\right)}$

We just need to show that $P_{1}$ has one profitable deviating strategy
$\sigma_{1}$. Let $\sigma_{1}$ be: do not shoot at
$t\in\left\\{1,2,...,K-2\right\\}$, shoot at $t\in\left\\{K-1,K,...\right\\}$;
in other words start shooting one turn before the shooting phase starts. Then,
by the usual arguments, $P_{1}$’s payoff is

$\displaystyle V_{1}$
$\displaystyle=Q_{1}\left(\left(1,1\right),\sigma_{1},\widetilde{\sigma}^{CD\left(K\right)}\right)=\sum_{k=0}^{K-2}\gamma^{k}+\gamma^{K-1}\left(p_{1}\frac{1}{1-\gamma}+\left(1-p_{1}\right)\left(1+\gamma
V_{D}\right)\right)$
$\displaystyle=\frac{\left(-\gamma^{K+1}p_{2}(1-p_{1})+1-\gamma(1-p_{2})(1-p_{1})\right)}{\left(1-\gamma\right)(1-\gamma(1-p_{2})(1-p_{1}))}$

By appropriate substitutions and algebraic calculations, we get

$\displaystyle\delta v_{1}$
$\displaystyle=\left(1-\gamma\right)\left(Q_{1}\left(\widetilde{\sigma}^{CD\left(K\right)},\widetilde{\sigma}^{CD\left(K\right)}\right)-Q_{1}\left(\sigma_{1},\widetilde{\sigma}^{CD\left(K\right)}\right)\right)$
$\displaystyle=-\frac{p_{2}\gamma^{K}\left(1-\gamma\left(1-p_{1}\right)\right)}{(1-\gamma(1-p_{2})(1-p_{1}))}<0$

Hence $P_{1}$ has incentive to switch to $\sigma_{1}$ and
$\left(\widetilde{\sigma}^{CD\left(K\right)},\widetilde{\sigma}^{CD\left(K\right)}\right)$
is not a NE.

###### Proposition 4.5

For every $M\in\mathbb{N}$, there exists a $\delta_{M}>0$ such that: if

$\displaystyle\gamma_{M}$ $\displaystyle=\frac{9}{10},$ $\displaystyle p_{M}$
$\displaystyle=\frac{1-e^{-M}}{10},$ $\displaystyle I_{M}$
$\displaystyle=\left(\gamma_{M}-\delta_{M},\gamma_{M}+\delta_{M}\right)\times\left(p_{M}-\delta_{M},p_{M}+\delta_{M}\right)\times\left(p_{M}-\delta_{M},p_{M}+\delta_{M}\right),$

then
$\left(\widetilde{\sigma}^{P\left(M\right)},\widetilde{\sigma}^{P\left(M\right)}\right)$
is a NE of $\Gamma\left(\left(1,1\right),\gamma,\mathbf{p}\right)$ for every
$\left(\gamma,p_{1},p_{2}\right)\in I_{M}$.

Proof. Recall that

$V^{P\left(M\right)}=Q_{1}\left(\widetilde{\sigma}^{P\left(M\right)},\widetilde{\sigma}^{P\left(M\right)}\right)\text{
}=\frac{1-\gamma^{M+1}\left(1-p_{1}\left(1-p_{2}\right))\right)}{\left(1-\gamma\right)\left(1-\gamma^{M+1}\left(1-p_{1}\right)\left(1-p_{2}\right)\right)}$

We will prove that, for every $\left(\gamma,p_{1},p_{2}\right)\in I_{M}$,
$P_{1}$ has no incentive to deviate from
$\widetilde{\sigma}^{P\left(M\right)}$ (the proof for$P_{2}$ is identical).

Suppose that $P_{1}$ uses some strategy $\sigma_{1}$ by which he shoots at
$P_{2}$ at some $t\neq i\cdot\left(M+1\right)$. For the usual reasons, it
suffices to consider strategies by which $P_{1}$ shoots in the first period
and with probability one. So suppose that $P_{1}$ abstains for all
$t\in\left(1,...,K\right)$ and then shoots at $P_{2}$ at some
$t^{\prime}=K+1\leq M$. Then the following two possibilities exist.

  1. 1.

With probability $p_{1}$: $P_{2}$ is killed and $P_{1}$ receives payoff
$\frac{1}{1-\gamma}$.

  2. 2.

With probability $1-p_{1}$: $P_{2}$ is missed, $P_{1}$ receives payoff one and
for all subsequent rounds $P_{2}$ will always shoot at $P_{1}$ with
probability one. In this case $P_{1}$’s best response at time
$t^{\prime\prime}>t^{\prime}$ is to always shoot at $P_{2}$ with probability
one; hence, starting at the $\left(t^{\prime}+1\right)$-th round, both players
use the $\sigma^{D}$ strategy. The total expected payoff received by $P_{1}$
in this case is $Q_{1}\left(\sigma^{D},\sigma^{D}\right)$.

Hence, assuming $P_{1}$ will first shoot at
$t=K+1\in\left\\{1,...,M\right\\}$, by the above reasoning $P_{1}$’s expected
total payoff will be

$V_{1}=Q_{1}\left(\sigma_{1},\widetilde{\sigma}^{P\left(M\right)}\right)\text{
}=\left(\sum_{k=0}^{K}\gamma^{k}\right)+\gamma^{K+1}\left(p_{1}\frac{1}{1-\gamma}+\left(1-p_{1}\right)Q_{1}\left(\sigma^{D},\sigma^{D}\right)\right)$

Substituting the
$Q_{1}\left(\widetilde{\sigma}^{P\left(M\right)},\widetilde{\sigma}^{P\left(M\right)}\right)$
and $Q_{1}\left(\sigma^{D},\sigma^{D}\right)$ values and performing a
considerable amount of algebra we get

$\displaystyle\delta v_{1}\left(\gamma,p_{1},p_{2}\right)$
$\displaystyle=\left(1-\gamma\right)\left(Q_{1}\left(\widetilde{\sigma}^{P\left(M\right)},\widetilde{\sigma}^{P\left(M\right)}\right)-Q_{1}\left(\sigma_{1},\widetilde{\sigma}^{P\left(M\right)}\right)\text{
}\right)$
$\displaystyle=\frac{p_{2}\gamma^{K+2}\left(-\left(1-p_{1}\right)^{2}\left(1-p_{2}\right){\gamma}^{M+1}+\left(1-p_{1}\right)\left(1-p_{2}\right){\gamma}^{M-K}-{\gamma}^{M-K-1}+1-p_{1}\right)}{\left(1-\gamma^{M+1}\left(1-p_{1}\right)\left(1-p_{2}\right)\right)\left(1-\gamma\left(1-p_{1}\right)\left(1-p_{2}\right)\right)}$

Setting $p_{1}=p_{2}=p$ we get

$\delta
v_{1}\left(\gamma,p,p\right)=\frac{p\gamma^{K+2}\left(-\left(1-p\right)^{3}{\gamma}^{M+1}+\left(1-p\right)^{2}{\gamma}^{M-K}-{\gamma}^{M-K-1}+1-p\right)}{\left(1-\gamma^{M+1}\left(1-p\right)^{2}\right)\left(1-\gamma\left(1-p\right)^{2}\right)}$

The sign of $\delta v_{1}\left(\gamma,p,p\right)$ is the same as that of

$\displaystyle f_{M,K}\left(\gamma,p\right)$
$\displaystyle=-\left(1-p\right)^{3}{\gamma}^{M+K+3}+\left(1-p\right)^{2}{\gamma}^{M+2}-{\gamma}^{M+1}+\left(1-p\right)\gamma^{K+2}$
$\displaystyle=f_{1,M,K}\left(\gamma,p\right)+f_{2,M,K}\left(\gamma,p\right)$

with

$\displaystyle f_{M,K,1}\left(\gamma,p\right)$
$\displaystyle=\left(1-p\right)^{2}{\gamma}^{M+2}-\left(1-p\right)^{3}{\gamma}^{M+K+3}$
$\displaystyle f_{M,K,2}\left(\gamma,p\right)$
$\displaystyle=-{\gamma}^{M+1}+\left(1-p\right)\gamma^{K+2}$

Now we consider the following cases.

  1. 1.

Case I: $K\leq M-2$. Then $M-K-1\geq 1$. For all $M$ and
$K\in\left\\{1,...,M-2\right\\}$ we have

$\left(1-p\right)^{2}>\left(1-p\right)^{3}\text{ and
}{\gamma}^{M+2}>{\gamma}^{M+K+3}$

hence we will always have $f_{1,M,K}\left(\gamma,p\right)>0$. To also have
$f_{M,K,2}\left(\gamma,p\right)>0$ for a specific $K$, it suffices that

${\gamma}^{M-K-1}<1-p\Leftrightarrow\gamma<\left(1-p\right)^{\frac{1}{M-K-1}}$

To have $f_{M,K,2}\left(\gamma,p\right)>0$ for _all_
$K\in\left\\{1,...,M-2\right\\}$, it suffices that

$\gamma<\left(1-p\right)^{\frac{1}{M-2}}$ (7)

In other words, for all $M$ we have:

$\displaystyle\gamma$
$\displaystyle\in\left(0,\left(1-p\right)^{\frac{1}{M-2}}\right)\Rightarrow\left(\forall
K\in\left\\{1,...,M-2\right\\}:f_{M,K}\left(\gamma,p\right)>0\right)$
$\displaystyle\gamma$
$\displaystyle\in\left(0,\left(1-p\right)^{\frac{1}{M-2}}\right)\Rightarrow\left(\forall
K\in\left\\{1,...,M-2\right\\}:\delta v_{1}\left(\gamma,p,p\right)>0\right)$

  2. 2.

Case II: $K=M-1$. In this case we want

$\displaystyle-\left(1-p\right)^{3}{\gamma}^{M+K+3}+\left(1-p\right)^{2}{\gamma}^{M+2}-{\gamma}^{M+1}+\left(1-p\right)\gamma^{K+2}$
$\displaystyle>0\Leftrightarrow$
$\displaystyle-\left(1-p\right)^{3}{\gamma}^{M+M-1+3}+\left(1-p\right)^{2}{\gamma}^{M+2}-{\gamma}^{M+1}+\left(1-p\right)\gamma^{M-1+2}$
$\displaystyle>0\Leftrightarrow$
$\displaystyle-\left(1-p\right)^{3}{\gamma}^{2M+2}+\left(1-p\right)^{2}{\gamma}^{M+2}-{\gamma}^{M+1}+\left(1-p\right)\gamma^{M+1}$
$\displaystyle>0\Leftrightarrow$
$\displaystyle-\left(1-p\right)^{3}{\gamma}^{M+1}+\left(1-p\right)^{2}{\gamma}-{1}+\left(1-p\right)$
$\displaystyle>0\Leftrightarrow$
$\displaystyle-\left(1-p\right)^{3}{\gamma}^{M+1}+\left(1-p\right)^{2}{\gamma}-p$
$\displaystyle>0\Leftrightarrow$
$\displaystyle-\left(1-p\right)^{3}{\gamma}^{M+1}+{\gamma}p^{2}-\left(2\gamma+1\right)p+\gamma$
$\displaystyle>0$

Let us define the function

$\overline{f}_{M}\left(\gamma,p\right)=-\left(1-p\right)^{3}{\gamma}^{M+1}+{\gamma}p^{2}-\left(2\gamma+1\right)p+\gamma$

By continuity, in a sufficiently small neighborhood of
$\left(\gamma_{M},p_{M}\right)=\left(\frac{9}{10},\frac{1-e^{-M}}{10}\right)$,
the sign of $\overline{f}_{M}\left(\gamma,p\right)$ will be the same as that
of

$h_{1}\left(M\right)=\overline{f}_{M}\left(\gamma_{M},p_{M}\right)=-\frac{\left(9+e^{-M}\right)^{3}\left(\frac{9}{10}\right)^{M+1}}{1000}+\frac{9\left(1-e^{-M}\right)^{2}}{1000}+\frac{31}{50}+\frac{7e^{-M}}{25}$

and it suffices to show that $h_{1}\left(M\right)>0$ for all $M$. To this end
we first note that

$h_{1}\left(1\right)=-\frac{\left(9+e^{-1}\right)^{3}\left(\frac{9}{10}\right)^{2}}{1000}+\frac{9\left(1-e^{-1}\right)^{2}}{1000}+\frac{31}{50}+\frac{7e^{-1}}{25}=\allowbreak
0.6\allowbreak 0703...>0$

Also, letting

$h_{2}\left(M\right)=-\frac{\left(9+e^{-M}\right)^{3}\left(\frac{9}{10}\right)^{M+1}}{1000}+\frac{31}{50}$

we have

$\forall M:h_{1}\left(M\right)>h_{2}\left(M\right).$

Now, $h_{2}\left(M\right)$ is strictly increasing in $M$ and
$h_{2}\left(2\right)=0.06422\,2...$ . Consequently

$\forall M\geq
2:h_{1}\left(M\right)>h_{2}\left(M\right)>h_{2}\left(2\right)>0$

Hence finally we have

$\forall M\geq
1:\overline{f}_{M}\left(\gamma_{M},p_{M}\right)=h_{1}\left(M\right)>0.$

Now, to have

$\forall M,\forall
K\in\left\\{1,...,M-1\right\\}:f_{M,K}\left(\gamma_{M},p_{M}\right)>0$

we must ensure that (7) holds for $\left(\gamma,p\right)=$
$\left(\gamma_{M},p_{M}\right)$. In other words, we want
$\gamma_{M}<\left(1-p_{M}\right)^{\frac{1}{M-2}}$ or, equivalently,

$\frac{9}{10}<\left(1-\frac{1-e^{-M}}{10}\right)^{\frac{1}{M-2}}=\left(\frac{9}{10}+\frac{e^{-M}}{10}\right)^{\frac{1}{M-2}}.$

This holds: since for all $M\in\mathbb{N}$ we have
$\frac{9}{10}+\frac{e^{-M}}{10}<1$, we also have

$\frac{9}{10}<\left(\frac{9}{10}+\frac{e^{-M}}{10}\right)<\left(\frac{9}{10}+\frac{e^{-M}}{10}\right)^{\frac{1}{M-2}}.$

In short we have shown that

$\displaystyle\forall M,\forall K$
$\displaystyle\in\left\\{1,...,M-1\right\\}:f_{M,K}\left(\gamma_{M},p_{M}\right)>0$
$\displaystyle\forall M,\forall K$
$\displaystyle\in\left\\{1,...,M-1\right\\}:\delta
v_{1}\left(\gamma_{M},p_{M},p_{M}\right)>0$

For all $M$ and $K$, $\delta v_{1}\left(\gamma,p_{1},p_{2}\right)$ is a
continuous function. Hence, for all $M$, there exists some $\delta_{M}>0$ such
that

$\forall
K\in\left\\{1,...,M-1\right\\},\forall\left(\gamma,p_{1},p_{2}\right)\in
I_{M}:\delta v_{1}\left(\gamma,p_{1},p_{2}\right)>0$

which shows that $P_{1}$ has no incentive to deviate from
$\widetilde{\sigma}^{P\left(M\right)}$. The same argument can be applied to
$P_{2}$. Hence, for every $\left(\gamma,p_{1},p_{2}\right)\in I_{M}$ ,
$\left(\widetilde{\sigma}^{P\left(M\right)},\widetilde{\sigma}^{P\left(M\right)}\right)$
is a NE of $\Gamma\left(\left(1,1\right),\gamma,\mathbf{p}\right)$.

##  5 Some Additional Remarks

Let us now justify our terms “cooperating” and “defecting” strategy. From the
results of Section 3, for $n\in\left\\{1,2\right\\}$, we have

$\displaystyle\overline{Q}_{n}\left(\left(1,1\right),\sigma^{C},\sigma^{C}\right)$
$\displaystyle=\frac{1}{1-\gamma}$
$\displaystyle\overline{Q}_{n}\left(\left(1,1\right),\sigma^{D},\sigma^{D}\right)$
$\displaystyle=\frac{1-\gamma\left(1-p_{n}\left(1-p_{-n}\right)\right)}{\left(1-\gamma\right)\left(1-\gamma\left(1-p_{1}\right)\left(1-p_{2}\right)\right)}.$

It follows that

$\overline{Q}_{n}\left(\left(1,1\right),\sigma^{C},\sigma^{C}\right)-\overline{Q}_{n}\left(\left(1,1\right),\sigma^{D},\sigma^{D}\right)=\frac{\gamma
p_{-n}}{\left(1-\gamma\right)\left(1-\gamma\left(1-p_{1}\right)\left(1-p_{2}\right)\right)}>0.$

In short, just like in PD, it is more profitable for both players to not-shoot
rather than shoot. Because in our formulation there is no direct profit from
killing the opponent, both $\left(\sigma^{C},\sigma^{C}\right)$ and
$\left(\sigma^{D},\sigma^{D}\right)$ are NE; however, for both players,
$\left(\sigma^{C},\sigma^{C}\right)$ is more profitable NE than
$\left(\sigma^{D},\sigma^{D}\right)$. This is the reason for calling
$\left(\sigma^{C},\sigma^{C}\right)$ a cooperating, and
$\left(\sigma^{D},\sigma^{D}\right)$ a defecting strategy.

All this may be surprising, since one would expect that, in a duel, each
player’s goal will be to eliminate his opponent. It may be supposed that the
higher profitability of $\left(\sigma^{C},\sigma^{C}\right)$ follows from our
choice of not assigning any direct payoff to killing one’s opponent. But this
is not true. Even with a positive “killing payoff”,
$\overline{Q}_{n}\left(\left(1,1\right),\sigma^{C},\sigma^{C}\right)$ can
still be greater than
$\overline{Q}_{n}\left(\left(1,1\right),\sigma^{D},\sigma^{D}\right)$,
provided $\gamma$ is sufficiently close to one666This, as well as additional
results regarding the positive killing payoff case, will be reported in a
future publication.. The reason for the superiority of
$\left(\sigma^{C},\sigma^{C}\right)$ is this: if a positive payoff is assigned
to survival, this, compounded over an infinite number of turns, can always
outweigh the killing payoff. Hence our model can be understood as a more
“pacifist” version than the usual duel model777This point has also been raised
by Donald Knuth in the context of the truel [17]. For example, he remarks that
“a player who passes is guaranteeing that his opponent has no reason to shoot
back, as far as the opponent’s survival is concerned ”..

Let us now compare our static duel to the PD. In both the PD and the duel,
cooperation is more profitable than defection. While
$\left(\sigma^{C},\sigma^{C}\right)$ is not a NE in PD,
$\left(\sigma^{D},\sigma^{D}\right)$ is a NE in both of them. However, both
the duel and the repeated version of PD, possess several NE in grim
strategies; the common characteristic of all such equilibria is that they
promote cooperation or, in other words, punish defection (shooting). In fact,
similarly to the case of repeated PD, it might be possible to prove a “Folk
Theorem” for the static duel as well; namely that every feasible and
individually rational payoff is a NE for $\gamma$ sufficiently close to one.
We intend to study this question in the future.

##  6 Conclusion

We have formulated the simultaneous shooting static duel as a discounted
stochastic game. We have shown that it has two Nash equilibria in stationary
strategies, namely the “always-shooting” and the “never-shooting” strategies;
in addition several nonstationary, “cooperation-promoting” Nash equilibria
also exist. In the future we intend to extend the study of the static duel in
several directions.

First, we want to extend our study and obtain similar results for two
variants: (a) the case of non-zero killing payoff and (b) the case of
terminal-only payoffs. In addition, we want to formulate and study a version
of the static duel in which each player wants to kill his opponent in the
_shortest possible time_.

Secondly, we hope to prove a form of “ _Folk Theorem_ ”, namely that every
every feasible and individually rational payoff is a NE for $\gamma$
sufficiently close to one.

Finally, we want to formulate the static _Nuel_ (i.e., the duel-like game
which involves $N$ players shooting at each other) as a discounted stochastic
game and extend our results for this case.

## References

  * [1] Amengual, P. and Toral, R. “Distribution of winners in truel games”. _AIP Conference Proceedings_ (2005), pp. 128–141.
  * [2] Amengual, P. and Toral, R. “A Markov chain analysis of truels”. _Proceedings of the 8th Granada Seminar on Computational Physics_ (2005).
  * [3] Amengual, P. and Toral, R. “Truels, or survival of the weakest.” _Computing in Science_.
  * [4] Barron, E. N. _Game theory: an introduction_. John Wiley & Sons (2013).
  * [5] Bossert, W., Brams S.J. and Kilgour, D.M. “Cooperative vs non-cooperative truels: little agreement, but does that matter?.” _Games and Economic Behavior_ , vol. 40 (2002), pp. 185-202.
  * [6] Brams, S.J., and Kilgour, D.M. “The truel”. _Mathematics Magazine_ , vol. 70 (1997), pp. 315-326.
  * [7] Brams, S.J., and Kilgour, D.M. “Games that End in a Bang or a Whimper”. preprint, CV Starr Center for Applied Economics (2001).
  * [8] Brams, S.J., Kilgour, D.M. and Dawson, B. “Truels and the Future.” _Math Horizons_ , vol. 10 (2003), pp. 5-8.
  * [9] Dorraki, M., Allison, A. and Abbott, D.. “Truels and strategies for survival.” _Scientific Reports_ , vol. 9 (2019), pp. 1-7.
  * [10] Dresher, M. _Games of strategy: theory and applications_. Rand Corp. (1961).
  * [11] Gardner, M. : _New Mathematical Puzzles and Diversions_. (1966), pp. 42-49.
  * [12] Karlin, S., _Mathematical Methods and Theory in Games, Programming, and Economics_ , vol. 2, Addison- Wesley (1959).
  * [13] Kilgour, D. M. “The simultaneous truel.” _International Journal of Game Theory_ , vol. 1 (1971), pp. 229-242.
  * [14] Kilgour, D. M. “The sequential truel.” _International Journal of Game Theory_ , vol. 4 (1975), pp. 151-174.
  * [15] Kilgour, D. M. “Equilibrium points of infinite sequential truels.” _International Journal of Game Theory_ , vol. 6 (1977), pp. 167-180.
  * [16] Kinnaird, C. _Encyclopedia of puzzles and pastimes_. Secaucus (1946).
  * [17] Knuth, D.E. “The Triel: A New Solution.” _Journal of Recreational Mathematics_ , vol. 6 (1972), pp. 1-7.
  * [18] Larsen, H.D. “A Dart Game.” _American Mathematical Monthly_ , (1948) pp. 640-41.
  * [19] Mosteller, F. _Fifty challenging problems in probability with solutions_. Courier Corporation (1987).
  * [20] Shubik, M. “Does the Fittest Necessarily Survive?”, _Readings in Game Theory and Political Behavior_ , Doubleday.
  * [21] Sobel, M.J. “Noncooperative stochastic games.” _The Annals of Mathematical Statistics_ , vol. 42 (1971), pp. 1930-1935.
  * [22] Toral, R., and Amengual, P.. “Distribution of winners in truel games.” _AIP Conference Proceedings_ , vol. 779. American Institute of Physics (2005).
  * [23] Wegener, M. and Mutlu, E.. “The good, the bad, the well-connected.” _International Journal of Game Theory_ , vol. 50 (2021), pp. 759-771.
  * [24] Xu, X. “Game of the truel.” _Synthese_ , vol. 185 (2012), pp. 19-25.
  * [25] Zeephongsekul, P. “Nash Equilibrium Points Of Stochastic $N$-Uels.” _Recent Developments in Mathematical Programming_. CRC Press (1991), pp. 425-452.


* [BHHS11] Boaz Barak, Moritz Hardt, Thomas Holenstein, and David Steurer.  Subsampling mathematical relaxations and average-case complexity.  In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 512–531. SIAM, 2011.
  * [BKW17] Karl Bringmann, Pavel Kolev, and David P. Woodruff.  Approximation algorithms for $\ell_{0}$-low rank approximation.  Advances in Neural Information Processing Systems, 30, 2017.
  * [BPR10] Sugata Basu, Richard Pollack, and Marie-Françoise Roy.  Algorithms in Real Algebraic Geometry.  Algorithms and Computation in Mathematics. Springer Berlin, Heidelberg, 2010.
  * [BRS11] Boaz Barak, Prasad Raghavendra, and David Steurer.  Rounding semidefinite programming hierarchies via global correlation.  In IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), pages 472–481. IEEE, 2011.
  * [BWZ19] Frank Ban, David Woodruff, and Richard Zhang.  Regularized weighted low rank approximation.  Advances in Neural Information Processing Systems, 32, 2019.
  * [CFLM22] Vincent Cohen-Addad, Chenglin Fan, Euiwoong Lee, and Arnaud de Mesmay.  Fitting metrics and ultrametrics with minimum disagreements.  In IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 301–311. IEEE, 2022.
  * [CGK+17] Flavio Chierichetti, Sreenivas Gollapudi, Ravi Kumar, Silvio Lattanzi, Rina Panigrahy, and David P. Woodruff.  Algorithms for $\ell_{p}$ low-rank approximation.  In International Conference on Machine Learning, pages 806–814. PMLR, 2017.
  * [CLMW11] Emmanuel J. Candès, Xiaodong Li, Yi Ma, and John Wright.  Robust principal component analysis?  Journal of the ACM (JACM), 58(3):1–37, 2011.
  * [COCF10] Amin Coja-Oghlan, Colin Cooper, and Alan Frieze.  An efficient sparse regularity concept.  SIAM Journal on Discrete Mathematics, 23(4):2000–2034, 2010.
  * [Cox11] David A Cox.  Galois Theory, volume 61.  John Wiley & Sons, 2011.
  * [CP10] Emmanuel J. Candes and Yaniv Plan.  Matrix completion with noise.  Proceedings of the IEEE, 98(6):925–936, 2010.
  * [CW17a] Kenneth L. Clarkson and David P. Woodruff.  Low-rank approximation and regression in input sparsity time.  Journal of the ACM (JACM), 63(6):1–45, 2017.
  * [CW17b] Kenneth L. Clarkson and David P. Woodruff.  Low-rank PSD approximation in input-sparsity time.  In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2061–2072. SIAM, 2017.
  * [DHJ+18] Chen Dan, Kristoffer Arnsfelt Hansen, He Jiang, Liwei Wang, and Yuchen Zhou.  Low rank approximation of binary matrices: Column subset selection and generalizations.  In 43rd International Symposium on Mathematical Foundations of Computer Science, 2018.
  * [dlVKKV05] W. Fernandez de la Vega, Marek Karpinski, Ravi Kannan, and Santosh Vempala.  Tensor decomposition and approximation schemes for constraint satisfaction problems.  In Proceedings of the 37th annual ACM Symposium on Theory of Computing (STOC), pages 747–754, 2005.
  * [dlVKM07] Wenceslas Fernandez de la Vega and Claire Kenyon-Mathieu.  Linear programming relaxations of maxcut.  In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 53–61. SIAM, 2007.
  * [DS14] Irit Dinur and David Steurer.  Analytical approach to parallel repetition.  In Proceedings of the 46th annual ACM symposium on Theory of computing, pages 624–633, 2014.
  * [ES83] Paul Erdős and Miklós Simonovits.  Supersaturated graphs and hypergraphs.  Combinatorica, 3(2):181–192, 1983.
  * [Fei98] Uriel Feige.  A threshold of ln n for approximating set cover.  Journal of the ACM (JACM), 45(4):634–652, 1998.
  * [FGL+19] Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh.  Approximation schemes for low-rank binary matrix approximation problems.  ACM Transactions on Algorithms (TALG), 16(1):1–39, 2019.
  * [FGP20] Fedor V. Fomin, Petr A. Golovach, and Fahad Panolan.  Parameterized low-rank binary matrix approximation.  Data Mining and Knowledge Discovery, 34:478–532, 2020.
  * [FK96] Alan Frieze and Ravi Kannan.  The regularity lemma and approximation schemes for dense problems.  In IEEE 37th Annual Symposium on Foundations of Computer Science (FOCS), pages 12–20. IEEE, 1996.
  * [FLM+17] Fedor V. Fomin, Daniel Lokshtanov, S. M. Meesum, Saket Saurabh, and Meirav Zehavi.  Matrix Rigidity from the Viewpoint of Parameterized Complexity.  In Heribert Vollmer and Brigitte Vallée, editors, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), volume 66 of Leibniz International Proceedings in Informatics (LIPIcs), pages 32:1–32:14, Dagstuhl, Germany, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [FM06] Uriel Feige and Mohammad Mahdian.  Finding small balanced separators.  In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pages 375–384, 2006.
  * [FRVB18] Chenglin Fan, Benjamin Raichel, and Gregory Van Buskirk.  Metric violation distance: Hardness and approximation.  In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 196–209. SIAM, 2018.
  * [Gri76] D. Yu Grigoriev.  Using the notions of separability and independence for proving the lower bounds on the circuit complexity. Notes of the Leningrad branch of the Steklov Mathematical Institute, 1976.
  * [GS11] Venkatesan Guruswami and Ali Kemal Sinop.  Lasserre hierarchy, higher eigenvalues, and approximation schemes for graph partitioning and quadratic integer programming with PSD objectives.  In IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), pages 482–491. IEEE, 2011.
  * [GV18] Nicolas Gillis and Stephen A. Vavasis.  On the complexity of robust PCA and $\ell_{1}$-norm low-rank matrix approximation.  Mathematics of Operations Research, 43(4):1072–1084, 2018.
  * [JLS+21] Yifei Jiang, Yi Li, Yiming Sun, Jiaxin Wang, and David P. Woodruff.  Single pass entrywise-transformed low rank approximation.  In International Conference on Machine Learning, pages 4982–4991. PMLR, 2021.
  * [Joh90] Charles R. Johnson.  Matrix completion problems: A survey.  In Matrix theory and applications, volume 40, pages 171–198, 1990\.
  * [KMM23] Eunjung Kim, Arnaud de Mesmay, and Tillmann Miltzow.  Representing matroids over the reals is $\exists\mathbb{R}$-complete.  arXiv preprint arXiv:2301.03221, 2023.
  * [KMO10] Raghunandan H. Keshavan, Andrea Montanari, and Sewoong Oh.  Matrix completion from a few entries.  IEEE Transactions on Information Theory, 56(6):2980–2998, 2010\.
  * [KS09] Marek Karpinski and Warren Schudy.  Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems.  In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), pages 313–322, 2009.
  * [KST54] P. Kővári, Vera T. Sós, and Paul Turán.  On a problem of Zarankiewicz.  In Colloquium Mathematicum, volume 3, pages 50–57. Polska Akademia Nauk, 1954.
  * [LW20] Yi Li and David P. Woodruff.  Input-sparsity low rank approximation in Schatten norm.  In International Conference on Machine Learning, pages 6001–6009. PMLR, 2020.
  * [MM15] Pasin Manurangsi and Dana Moshkovitz.  Approximating dense max 2-CSPs.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015.
  * [MMMN23] Antoine Méot, Arnaud de Mesmay, Moritz Mühlenthaler, and Alantha Newman.  Voting algorithms for unique games on complete graphs.  In Symposium on Simplicity in Algorithms (SOSA), pages 124–136. SIAM, 2023.
  * [MR17] Pasin Manurangsi and Prasad Raghavendra.  A birthday repetition theorem and complexity of approximating dense CSPs.  In 44th International Colloquium on Automata, Languages, and Programming (ICALP). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017.
  * [MS08] Claire Mathieu and Warren Schudy.  Yet another algorithm for dense max cut: Go greedy.  In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 176–182. SIAM, 2008.
  * [MW17] Cameron Musco and David P. Woodruff.  Sublinear time low-rank approximation of positive semidefinite matrices.  In IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 672–683. IEEE, 2017.
  * [MW21] Arvind V. Mahankali and David P. Woodruff.  Optimal $\ell_{1}$ column subset selection and a fast PTAS for low rank approximation.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 560–578. SIAM, 2021.
  * [Oxl06] James G. Oxley.  Matroid Theory, volume 3.  Oxford University Press, USA, 2006.
  * [Rec11] Benjamin Recht.  A simpler approach to matrix completion.  Journal of Machine Learning Research, 12(12), 2011.
  * [RSW16] Ilya Razenshteyn, Zhao Song, and David P. Woodruff.  Weighted low rank approximations with provable guarantees.  In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), pages 250–263, 2016.
  * [SWZ17] Zhao Song, David P. Woodruff, and Peilin Zhong.  Low rank approximation with entrywise $\ell_{1}$-norm error.  In Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC), pages 688–701, 2017.
  * [SWZ19] Zhao Song, David P. Woodruff, and Peilin Zhong.  Relative error tensor low rank approximation.  In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2772–2789. SIAM, 2019.
  * [Val77] Leslie G. Valiant.  Graph-theoretic arguments in low-level complexity.  In Mathematical Foundations of Computer Science 1977: Proceedings, 6th Symposium, Tatranská Lomnica September 5–9, 1977 6, pages 162–176. Springer, 1977.
  * [Ver18] Roman Vershynin.  High-dimensional probability: An introduction with applications in data science, volume 47.  Cambridge University Press, 2018.
  * [WY22] David P. Woodruff and Taisuke Yasuda.  Improved algorithms for low rank approximation from sparsity.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2358–2403. SIAM, 2022.
  * [Yar14] Grigory Yaroslavtsev.  Going for speed: Sublinear algorithms for dense r-CSPs.  arXiv preprint arXiv:1407.7887, 2014.
  * [YZ14] Yuichi Yoshida and Yuan Zhou.  Approximation schemes via Sherali-Adams hierarchy for dense constraint satisfaction problems and assignment problems.  In Proceedings of the 5th Conference on Innovations in Theoretical Computer Science, pages 423–438, 2014.