# Strategies for quantum races

Troy Lee Centre for Quantum Software and Information, School of Software,
Faculty of Engineering and Information Technology, University of Technology
Sydney, Australia<EMAIL_ADDRESS>Maharshi Ray Centre for Quantum
Technologies, National University of Singapore, Singapore
<EMAIL_ADDRESS>Miklos Santha IRIF, Univ. Paris Diderot, CNRS, 75205
Paris, France; and Centre for Quantum Technologies and MajuLab, National
University of Singapore, Singapore<EMAIL_ADDRESS>
###### Abstract

We initiate the study of _quantum races_ , games where two or more quantum
computers compete to solve a computational problem. While the problem of
dueling algorithms has been studied for classical deterministic algorithms
[IKL+11], the quantum case presents additional sources of uncertainty for the
players. The foremost among these is that players do not know if they have
solved the problem until they measure their quantum state. This question of
“when to measure?” presents a very interesting strategic problem. We develop a
game-theoretic model of a multiplayer quantum race, and find an approximate
Nash equilibrium where all players play the same strategy. In the two-party
case, we further show that this strategy is nearly optimal in terms of payoff
among all symmetric Nash equilibria. A key role in our analysis of quantum
races is played by a more tractable version of the game where there is no
payout on a tie; for such races we completely characterize the Nash equilibria
in the two-party case.

One application of our results is to the stability of the Bitcoin protocol
when mining is done by quantum computers. Bitcoin mining is a race to solve a
computational search problem, with the winner gaining the right to create a
new block. Our results inform the strategies that eventual quantum miners
should use, and also indicate that the collision probability—the probability
that two miners find a new block at the same time—would not be too high in the
case of quantum miners. Such collisions are undesirable as they lead to
forking of the Bitcoin blockchain.

##  1 Introduction

We study the scenario of two or more quantum computers competing to solve a
computational task, which we call a _quantum race_. This setting presents a
different problem to finding the fastest algorithm for a task, as the only
goal is to solve the task before the competition. For example, imagine a
search race where Alice and Bob, each armed with identical quantum computers,
compete to find a marked item in a database. The first person to find the
marked item wins $1, with the payout being split in the case of a tie. The
first natural idea is for Alice to run Grover’s algorithm [Gro96], which can
find a marked item in a database of size $N$ with high probability in time
$O(\sqrt{N})$. However, if Alice’s strategy is to run Grover’s algorithm and
measure after the specified number of steps to maximize her success
probability, Bob will have an advantage by measuring after running Grover’s
algorithm for a few less steps. Although this way Bob has a slightly lower
success probability, he gains a huge advantage in always answering first. This
simple example shows that the optimal algorithm to solve a problem can be
different from the optimal strategy to employ when the goal is to solve the
problem before an opponent.

The scenario of competing algorithms has been studied before in the classical
deterministic setting [IKL+11]. In a classical game, the uncertainty is
provided by an unknown probability distribution over the inputs: depending on
what the input is, one algorithm may perform better than another. The quantum
setting inherently has additional sources of uncertainty, most interestingly
that players do not know if they have solved the problem until they _measure_
their quantum state. Going back to the search game, in the classical version
the players know at every instant if they have found the marked item or not.
This is not the case in the quantum setting, where a player can only tell if
she has found the desired item by measuring her quantum state. Furthermore, if
she measures her state and does not find the marked item, then she must begin
the search again from scratch. In the quantum case there is a natural tension
between waiting to measure, and thereby building up the probability of success
upon measuring, and measuring sooner, to answer before one’s competitors. We
study this game theoretic problem to develop strategies for players to use in
quantum races.

One of our main motivations for studying quantum races is to model quantum
computers mining the decentralized currency Bitcoin [Nak09]. Mining is the
process by which new blocks of transactions are added to the history of
Bitcoin transactions, called the blockchain. The winner of a race to solve a
computational search problem gains the right to add a new block of
transactions to the blockchain, and participants in this race are called
miners. Quantum miners could use Grover’s algorithm to solve the search
problem with quadratically fewer search queries than needed classically. But
what should the strategy of quantum miners be when competing against each
other?

######  Question 1.

What is the optimal strategy for quantum miners?

Figuring out the optimal strategy for quantum miners is important to analyze
the impact of quantum mining on the stability of the Bitcoin protocol. When
two miners solve the computational search problem at (nearly) the same time,
the blockchain can fork as it is unclear which new block is the “correct”
history of Bitcoin transactions. Forking is bad for the security of Bitcoin as
it can decrease the cost of attacks [GKW+16], increase the gain from deviating
from the intended mining protocol [EGS14], and generally decreases chain
growth and wastes resources. In the classical case, each search query has the
same probability of success. In the quantum case, however, because of Grover’s
algorithm the success probability grows roughly quadratically with the number
of search queries. Does this lead to many quantum miners finding blocks at the
same time?

######  Question 2.

What is the probability that two or more quantum miners playing the optimal
strategy find a block at the same time?

In the next subsections, we describe our model and results in more detail and
the impact it has on these questions.

###  1.1 The model and results

In a _symmetric_ game all players have the same payoff function. In his
original paper defining a Nash equilibrium, Nash showed that every symmetric
multiparty finite game has a symmetric equilibrium, i.e. one where all players
play the same strategy [Nas51]. When all players have identical quantum
computers, a quantum race is naturally a symmetric race, and we describe this
scenario first.

We model a symmetric multiplayer quantum race in the following way. The pure
strategies available to a player are the possible times at which she can
measure $1,2,3,\ldots,K$. For each time $t$, a player has an algorithm that
she can run for $t$ steps and for which the success probability is $p_{t}$.
Without loss of generality, we assume that these probabilities form an
increasing sequence $0<p_{1}<p_{2}<\cdots<p_{K}\leq 1$. A general strategy is
a probability distribution over the possible times to measure. The player who
succeeds first receives a payoff of 1. In the case of a tie, the payoff is
split amongst all players who succeed first at the same time. Our model can be
thought of as a “one-shot” race, as if a player measures and does not succeed,
she does not get a chance to restart and try again. While a race where players
are allowed to repeatedly restart until someone wins would be more realistic,
it becomes much more difficult to analyze due to the proliferation of possible
stategies, and we leave this for future work.

##### Two-player case

We begin explaining our model and results in more detail in the two-player
case. In this case, a game defined by the probabilities $p_{1},\ldots,p_{K}$
can be represented by the payoff matrix for Alice, given by the $K$-by-$K$
matrix $A$, and the payoff matrix for Bob $B$. The $(s,t)$ entry of $A$ gives
Alice’s payoff when she runs an algorithm for time $s$ and Bob plays time $t$.
In the case of a quantum race, this is defined as

$A(s,t)=\begin{cases}p_{s}&\mbox{ if }s<t\\\
p_{s}(1-p_{s})+\frac{1}{2}p_{s}^{2}&\mbox{ if }s=t\\\ p_{s}(1-p_{t})&\mbox{ if
}s>t\enspace.\end{cases}$ (1)

As the game is symmetric, Bob’s payoff matrix is $B=A^{\mathrm{T}}$.

Our analysis of quantum races begins in Section 3 by analyzing a more
tractable variant of the game we call a _stingy_ quantum race. In a stingy
quantum race, there is no payout in the case of a tie (the game organizer is
stingy). A Nash equilibrium of a two-party stingy quantum race has very strong
constraints on its support structure (see Corollary 16). In particular, if
$(x,y)$ is a Nash equilibrium in a two-party stingy quantum race, then the
union of the supports of $x$ and $y$ must be an interval
$\\{T,T+1,\ldots,K\\}$ that contains the maximum running time $K$. There are 3
possible types of Nash equilibria in a two-party stingy quantum race, and we
characterize all of them (see Theorem 22, Theorem 53, and Theorem 59).

One particularly nice type of equilibrium is what we call a _coinciding_
equilibrium. In a coinciding equilibrium, the support of all player’s
strategies is the same, but the strategies do not have to be identical. This
is a more general notion than a symmetric equilibrium where all strategies are
the same. In a coinciding equilibrium for a stingy quantum race, the support
of each player’s strategy is an interval $\\{T,T+1,\ldots,K\\}$. This leaves
the problem of determining the starting point $T$ of this interval in a Nash
equilibrium. We are able to show that there is always exactly one $T$ such
that there is a Nash equilibrium with support $\\{T,T+1,\ldots,K\\}$.

######  Theorem 3 (Informal, see Theorem 22).

In a two-party stingy quantum race defined by probabilities
$p_{1},\ldots,p_{K}$, there is a unique coinciding Nash equilibrium. In this
equilibrium all players play the same strategy, and the support of the
strategies is an interval $\\{T^{*},T^{*}+1,\ldots,K\\}$.

We also explicitly find this Nash equilibrium.

This result begs the question: what is this value of $T^{*}$? At what success
probability does it become worthwhile to start measuring? By putting an
additional restriction on the probabilities $p_{1},\ldots,p_{K}$, we can give
quite a precise answer to this question. We say $p_{1},\ldots,p_{K}$ is an
$\ell$-_dense_ sequence (see Definition 13) if
$p_{1}\leq\frac{\ell}{K},p_{K}\geq 1-\frac{\ell}{K}$, and
$p_{i+1}-p_{i}\leq\frac{\ell}{K}$ for $i=2,\ldots,K-1$. This is quite a
natural restriction that is satisfied for many races. In the quantum search
race, where the $p_{i}$ are the Grover success probabilities, and therefore
also in the application to Bitcoin, the $\ell$-density condition is satisfied
with $\ell=\pi/2$. In the $\ell$-dense case, we can give the following bound
on $T^{*}$.

######  Theorem 4 (Informal, see Corollary 25 and Corollary 28).

Let $p_{1},\ldots,p_{K}$ be an $\ell$-dense sequence with $K\geq 6\ell$. Then
the starting point $T^{*}$ of the unique coinciding Nash equilibrium in the
stingy quantum race defined by these probabilities is such that
$p_{T^{*}}=\sqrt{2}-1+\Theta\left(\frac{\ell}{K}\right)$.

Thus it is worthwhile to start measuring once the success probability becomes
around $\sqrt{2}-1$, and this is largely independent of the actual values of
$p_{1},\ldots,p_{K}$.

In Section 4, we apply our analysis of two-player stingy quantum races to the
case of general quantum races. As the only difference between a stingy quantum
race and a quantum race is the payout on ties, intuitively strategies in these
two kinds of races should have similar payoffs when the probability of ties is
small. We follow this intuition and show that when $p_{1},\ldots,p_{K}$ form
an $\ell$-dense sequence the probability of a tie is $O(\frac{\ell}{K})$ (see
Theorem 27) when players use the unique coinciding equilibrium from the stingy
race, and this strategy is an $O(\frac{\ell}{K})$-approximate Nash equilibrium
of the corresponding quantum race.

Approximate Nash equilibria are naturally an imperfect lens into true Nash
equilibria. The approximate Nash equilibrium we give would not be a reasonable
suggestion for the actual strategies of quantum players if there were other
equilibria with much higher payoff, for example. We show that this is not the
case, and the approximate Nash equilibrium we give is nearly optimal in terms
of payoff amongst all symmetric equilibria.

######  Theorem 5 (Informal, see Theorem 32 and Theorem 34).

Let $p_{1},\ldots,p_{k}$ be an $\ell$-dense sequence with $K\geq 6\ell$. Then
the unique coinciding equilibrium of the two-player stingy quantum race
defined by these probabilities is an $O(\frac{\ell}{K})$-approximate Nash
equilibrium in the corresponding quantum race. Moreover, the payoff achieved
by this strategy is within $O(\sqrt{\frac{\ell}{K}})$ of the largest payoff
achievable by any symmetric Nash equilibrium.

To show that the approximate Nash equilibrium we give is nearly optimal in
terms of payoff (Theorem 34), we use the bilinear programming formulation of
Nash equilbria due to Mangasarian and Stone [MS64]. Luckily, in our case the
sum of Alice’s and Bob’s payoff matrices $A+A^{\mathrm{T}}$ (from Eq. 1) turns
out to be negative semidefinite. When optimizing over symmetric strategies
this makes the Mangasarian and Stone bilinear program (which is a maximization
problem) into a convex quadratic program. We then use Dorn’s [Dor60]
equivalent dual formulation of a convex quadratic program (see Eq. 37), which
is a minimization problem. We explicitly construct a feasible solution to this
dual minimization problem to upper bound the payoff of any symmetric Nash
equilibrium. Our construction of this dual solution again makes use of our
analysis of stingy quantum races.

##### Multiplayer case

The case of many players is what we are interested in for the application to
Bitcoin. Luckily, we are able to recover analogs of many of the results from
the two-player case in the multiplayer case as well. We start in Section 5 by
analyzing $n$-player stingy quantum races, and show the following.

######  Theorem 6 (Informal, see Theorem 46).

Let $p_{1},\ldots,p_{K}$ define an $n$-player stingy quantum race. This race
has a unique coinciding Nash equilibrium, and in this equilibrium all players
play the same strategy. The support of each strategy is an interval
$\\{T^{*},T^{*}+1,\ldots,K\\}$.

To show that an $n$-player stingy quantum race has a unique coinciding Nash
equilibrium, our proof proceeds through a 2-player _asymmetric_ stingy quantum
race. In a 2-player asymmetric race, Alice has probabilities
$p_{1},\ldots,p_{K}$ of succeeding after $t$ steps and Bob has a (potentially
different) sequence of probabilities $P_{1},\ldots,P_{K}$. An asymmetric race
models the case where Alice and Bob have quantum computers of potentially
different speeds. We relate the payoff for Alice in a $n$-player stingy
quantum race to the payoff for Alice in a 2-player quantum race against a more
powerful opponent (see Lemma 45). We can then refer to Lemma 21 in Section 3
which completely characterizes coinciding equilibria in asymmetric 2-player
stingy quantum races. This gives Theorem 6.

When the sequence $p_{1},\ldots,p_{K}$ is $\ell$-dense, we can also say
something about the starting point $T^{*}$ of the $n$-player coinciding
equilibrium, though not as precisely as in the two-party case.

######  Theorem 7 (Informal, see Theorem 49).

Let $p_{1},\ldots,p_{K}$ be an $\ell$-dense sequence defining a stingy
$n$-player quantum race with $n\geq 2$. If $K\geq 4\mathrm{e}\ell n$ then the
starting point $T^{*}$ of the unique coinciding equilibrium is such that
$p_{T^{*}}=\Theta(\frac{1}{n})$.

This means that the more players there are in a game, the earlier one starts
to measure in the unique coinciding equilibrium.

In light of 2 we also want to see what the probability of more than one player
succeeding at the same time in this unique coinciding equilibrium. We show the
following.

######  Theorem 8.

Let $P_{1},....,P_{K}$ define an $\ell$-dense stingy $n$-player quantum race
such that $4\mathrm{e}n\ell\leq K$. When the players play the coinciding
equilibrium of the stingy race, the probability that two or more players
succeed at the same time is at most $\frac{8\mathrm{e}n\ell}{K}$.

Finally, as in the two-party case, we show that the unique coinciding
equilibrium of a stingy race is also an approximate Nash equilibrium in the
corresponding quantum race, provided the sequence of probabilities is
$\ell$-dense.

######  Theorem 9.

Let $P_{1},....,P_{K}$ define an $\ell$-dense stingy $n$-player quantum race,
$n\geq 2$, with $4\mathrm{e}n\ell\leq K$. If $x=(x_{1},...,x_{n})$ is the
coinciding Nash equilibrium for this stingy race, then $x$ is an
$\frac{8\mathrm{e}\ell}{K}$\- approximate Nash equilibrium of the
corresponding quantum race.

###  1.2 Application to Bitcoin

One application of our study of quantum races is to the decentralized digital
currency Bitcoin, developed in 2008 by Satoshi Nakamoto [Nak09]. Bitcoin
transactions are packaged into blocks and stored in a public ledger called the
blockchain. A major obstacle in creating a decentralized currency is to find a
way for all parties to agree on the history of transactions. In Bitcoin, this
is done through _Nakamoto consensus_ : the right to create a new block is
decided through proof-of-work, a contest to solve a computational problem. The
winner of this contest has the right to make a new block of transactions, is
given a reward in bitcoin, and then the process repeats itself. The players
competing in this process are called miners. Nakamato consensus remains the
primary means of achieving consensus across all cryptocurrencies, although
there are coins using other consensus mechanisms such as proof-of-stake
[KRDO17] or Byzantine agreement [CL99].

The proof-of-work task used in Bitcoin (originally developed in a system
called Hashcash [Bac02]) is essentially a search problem. The problem is to
find a value $x$ (called a nonce) such that $h(H\parallel x)\leq t$, where $h$
is a hash function (doubly iterated SHA-256 in the case of Bitcoin), $H$ is
the header of the block of transactions to be processed, and $t$ is a hardness
parameter that can be varied so that the entire network takes 10 minutes to
solve this task, on average.

Several works have studied the impact that quantum computers would have on the
Bitcoin protocol [But13, ABL+17, Sat18], both on the mining process we have
described above and on the digital signatures used in Bitcoin to authenticate
ownership of coins. We will focus here on the impact of quantum computers on
Bitcoin mining.

As the Bitcoin proof-of-work is a search task, quantum miners could use
Grover’s algorithm to find a nonce $x$ satisfying $h(H\parallel x)\leq t$ with
quadratically fewer evaluations of the hash function $h$ than is needed by a
classical computer 111While this seems to give quantum computers a huge
advantage for Bitcoin mining, specialized classical Bitcoin mining hardware
currently can perform14 trillion hashes per second [Bit18] and would
outperform a near-term quantum computer with gate speeds of 100MHz [ABL+17].
The use of Grover’s algorithm creates new issues for proof-of-work that do not
exist in the classical case. Desirable properties of a proof-of-work task have
been studied from an axiomatic point of view by Biryukov and Khovratovich
[BK17]. One property they give is _progress-freeness_ : the probability of a
miner solving the proof-of work task in any moment is independent of previous
events. This is achieved for a classical miner in the Bitcoin proof of work,
as every call to the hash function is equally likely to find a good nonce $x$.
Progress-freeness is not achieved for a quantum miner running Grover’s
algorithm, as the success probability grows roughly quadratically with the
amount of time the algorithm is run.

Sattath [Sat18] points out that this gives a way for quantum miners to deviate
from the prescribed protocol in order to increase their chance of winning a
block. To explain this deviation, imagine a simplified case where the proof-
of-work is to find a unique marked item in a database of size $N$. Say that
Alice, a quantum miner, receives a new block from the network which was found
by Bob. When Alice receives this block she will be in the middle of running
Grover’s algorithm to find the marked item herself. The prescribed protocol
says that she should immediately halt this run of Grover’s algorithm and begin
working on a new search problem by mining on top of Bob’s new block. However,
if Alice has run Grover algorithm for $c\sqrt{N}$ steps, for a constant $c$,
she will have already built up a constant probability of finding the marked
item upon measuring. From the point of view of maximizing her payoff, there is
no harm in just measuring to see if she finds the marked item. If Alice gets
lucky and indeed finds the marked item, then she can broadcast her new block
to the network. Depending on her connectivity to the network, some other
miners may receive Alice’s block before Bob’s, and there is some probability
that Alice’s new block eventually becomes the block accepted by the network
rather than Bob’s, meaning that Alice will receive the bitcoin reward. Note
that this does not happen in the classical case, where after Alice receives
Bob’s block she would still just have probability $1/N$ to find the marked
item with each additional search query. In this case it makes sense to
immediately start mining on top of the new block.

Luckily, Sattath also provides an easy fix for the Bitcoin protocol to remedy
this problem. Without going into the technical details, this fix essentially
forces miners to commit to how long they will run Grover’s algorithm _before
they begin_. Thus if Alice commits to running Grover’s algorithm for time
$\sqrt{N}/100$, yet receives Bob’s block after time $\sqrt{N}/200$, if she
tries to immediately measure and publish her own block, the network will
reject it because of the timing discrepancy. This fix fits in very well with
our model of quantum races, as a strategy is exactly a probability
distribution over choices of times to measure.

The quantum race that captures the case of Bitcoin mining is what we call the
_Grover race_ (see Definition 12). In this race, the success probability
$p_{t}$ is given by the success probability of $t$-iterations of Grover’s
algorithm 222It is known that $t$ queries of Grover’s algorithm maximizes the
probability of success in a search problem over all $t$-query quantum
algorithms [DH08].. This race is an $\ell$-dense race for $\ell=\pi/2$. The
size of the search space, and thus the maximum number of iterations $K$ to run
Grover’s algorithm, is determined by the _difficulty_ setting of the Bitcoin
protocol. Currently the difficulty (as of September 7, 2018) is approximately
$7\cdot 10^{12}$, which, by Bitcoin’s definition of difficulty, means that the
network has to do roughly $2^{32}\cdot 7\cdot 10^{12}$ many hashes to succeed,
in expectation. This leads to a value of $K$ of approximately $10^{11}$. Thus
for this application $\frac{\ell}{K}$ is very small, and Theorem 9 implies
that the unique coinciding equilibrium for the stingy Grover race is an
$\epsilon$-approximate Nash equilibrium in the Grover race for $\epsilon\leq
3\cdot 10^{-10}$. This gives a reasonable answer to 1 for what a good strategy
would be for quantum miners, and moreover has the desirable property that all
miners run the same algorithm. By Theorem 8, when there are $n$ miners running
this strategy the probability of a tie is at most $3n\cdot 10^{-10}$. This
gives an answer to 2, that quantum mining is not likely to produce a high
forking rate and thereby destabilize the Bitcoin protocol.

##  2 Preliminaries

We use $\mathrm{e}\approx 2.71828$ for Euler’s number. For ease of reference,
we state some simple inequalities we will make use of here:

$\displaystyle\frac{1}{1-x}$ $\displaystyle\leq 1+2x\mbox{ for }0\leq
x\leq\frac{1}{2}\enspace,$ (2) $\displaystyle\frac{1}{a+x}$
$\displaystyle\geq\frac{1}{a}-\frac{x}{a^{2}}\mbox{ for }a>0\mbox{ and
}x>-a\enspace,$ (3) $\displaystyle\sqrt{a+x}$
$\displaystyle\leq\sqrt{a}+\frac{x}{2\sqrt{a}}\mbox{ for }a>0\mbox{ and
}x\geq-a\enspace,$ (4) $\displaystyle\sqrt{a-x}$
$\displaystyle\leq\sqrt{a}-\frac{x}{2\sqrt{a}}-\frac{x^{2}}{8a^{3/2}}\mbox{
for }a>0\mbox{ and }0\leq x\leq a\enspace.$ (5)

For a probability $0\leq p\leq 1$, we set $\bar{p}=1-p$. For a natural number
$n$, we let $[n]=\\{1,...,n\\}$. We let
$\Delta_{n}=\\{x\in\mathbb{R}^{n}:x\geq 0,\sum_{i=1}^{n}x_{i}=1\\}$ be the
probability simplex. For $x\in\Delta_{n}$ we let
$\sup(x)=\\{i\in[n]:x_{i}>0\\}$ be the support of $x$.

By a vector we mean a column vector, so an $n$-dimensional vector is an
$n$-by-$1$ matrix. We use $\mathbf{0}$ for the all zeros vector and
$\mathbf{1}$ for the all ones vector, where the dimension is implied from the
context. The transpose of a matrix $M$ is denoted by $M^{\mathrm{T}}$. A
$2$-player game between players Alice and Bob is specified by two $m\times n$
real matrices $A$ and $B$. We call $A$ the payoff matrix of Alice, and $B$ the
payoff matrix of Bob. We sometimes refer to Alice as the row player and to Bob
as the column player. A pure strategy of Alice is an element of $[m]$, and a
pure strategy of Bob is an element of $[n]$. We can think of pure strategies
of the players as their choice of a row and of a column of an $m\times n$
matrix, respectively. When Alice chooses $i$ and Bob chooses $j$, their
respective payoffs are $a_{ij}$ and $b_{ij}$. A mixed strategy of the row
player is a probability distribution $x$ over $[m]$ written as an $m$-vector.
Similarly, a mixed strategy of the column player is an $n$-vector $y$
describing a probability distribution over columns. The support of a mixed
strategy is the set of pure strategies (indices) that have positive
probabilities. We denote the support of a mixed strategy $z$ by $\sup(z)$.
When Alice plays the mixed strategy $x$ and Bob plays the mixed strategy $y$,
their expected payoffs are $x^{\mathrm{T}}Ay$ and $x^{\mathrm{T}}By$,
respectively. When Alice uses the pure strategy $i$ against $y$, her payoff is
$e_{i}^{\mathrm{T}}Ay$, where $e_{i}$ denotes the $i^{th}$ standard basis
vector. The purpose of both players in the game is to maximize their
respective expected payoffs.

A pure strategy $i$ of Alice is a best response to the mixed strategy $y$ of
Bob if it maximizes her payoff against $y$. The set of best responses of Alice
against $y$ is denoted by $\mathrm{br}(y)$. A mixed strategy $x$ of Alice is a
best response to the mixed strategy $y$ of Bob if it contains only best
responses, that is $\sup(x)\subseteq\mathrm{br}(y)$. Analogous definitions
hold with the roles of the players exchanged. A pair of mixed strategies
$(x,y)$ is a Nash equilibrium if they are best responses to each other. It is
quite easy to see that $(x,y)$ is a Nash equilibrium exactly when the
strategies $x$ and $y$ maximize, for both players, their expected payoff
against the strategy of the other player.

######  Definition 10 (quantum race).

A 2-player quantum race is specified by two sequences of increasing
probabilities $0<p_{1}<p_{2}<\cdots<p_{K}\leq 1$, and
$0<P_{1}<P_{2}<\cdots<P_{K}\leq 1$ for some integer $K\geq 2$. The set of pure
strategies of both players is $[K]$. The $K\times K$ payoff matrix $A$ of
Alice is defined as

$A(i,j)=\begin{cases}p_{i}&\text{if}~{}i<j,\\\
p_{i}\bar{P}_{j}+\frac{1}{2}p_{i}P_{i}&\text{if}~{}i=j,\\\
p_{i}\bar{P}_{j}&\text{otherwise.}\end{cases}$

The payoff matrix $B$ is defined as

$B(i,j)=\begin{cases}P_{j}&\text{if}~{}j<i,\\\
P_{j}\bar{p}_{i}+\frac{1}{2}p_{i}P_{i}&\text{if}~{}i=j,\\\
P_{j}\bar{p}_{i}&\text{otherwise.}\end{cases}$

If $p_{i}=P_{i}$ for all $i=1,\ldots,K$ then we call the game a _symmetric_
quantum race. Note that in this case $B=A^{\mathrm{T}}$.

In our study of quantum races, a key role will be played by an auxiliary game
that is easier to analyze called a stingy quantum race. A stingy quantum race
differs from a quantum race only in that no payout is given in the case of a
tie.

######  Definition 11 (stingy quantum race).

A 2-player stingy quantum race is specified by two sequences of increasing
probabilities $0<p_{1}<p_{2}<\cdots<p_{K}\leq 1$, and
$0<P_{1}<P_{2}<\cdots<P_{K}\leq 1$ for some integer $K\geq 2$. The set of pure
strategies of both players is $[K]$. The $K\times K$ payoff matrix $A_{0}$ of
Alice is defined as

$A_{0}(i,j)=\begin{cases}p_{i}&\text{if}~{}i<j,\\\
p_{i}\bar{P}_{j}&\text{otherwise.}\end{cases}$

The payoff matrix of Bob $B_{0}$ is defined as

$B_{0}(i,j)=\begin{cases}P_{j}&\text{if}~{}j<i,\\\
P_{j}\bar{p}_{i}&\text{otherwise.}\end{cases}$

If $p_{i}=P_{i}$ for all $i=1,\ldots,K$ then we call the game a _symmetric_
stingy quantum race. Note that in this case $B_{0}=A_{0}^{\mathrm{T}}$.

The main specific quantum race we will be interested in is the _Grover race_.
This results from two players competing to find a marked item in a database
and playing by running Grover’s algorithm for a certain amount of time and
then measuring. Formally, the race is defined as follows.

######  Definition 12 (Grover race).

We define the (stingy) Grover race on $N$ items as the symmetric (stingy)
quantum race with $K=\left\lceil\tfrac{\pi}{4}\sqrt{N}-3/2\right\rceil$ and

$p_{t}=\sin^{2}\left(2(t+1/2)\arcsin\left(\frac{1}{\sqrt{N}}\right)\right)\enspace,$

for $1\leq t\leq K$.

Here $p_{t}$ is the success probability of Grover’s algorithm of finding a
unique marked item in a database of $N$ items. It is known that $p_{t}$ is the
highest success probability for finding a marked item for any quantum
algorithm making $t$ many calls to the database [DH08].

The Grover race has many nice properties, and we will abstract out one of them
here. This allows us to show results for a general class of quantum races,
rather than just the Grover race.

######  Definition 13 (dense race).

Let $p_{1}<p_{2}<\cdots<p_{K}\leq 1$. We call the sequence
$(p_{1},\ldots,p_{K})$ $\ell$-dense if $p_{1}\leq\frac{\ell}{K}$, $p_{K}\geq
1-\frac{\ell}{K}$, and $p_{i+1}-p_{i}\leq\tfrac{\ell}{K}$ for all
$i=1,\ldots,K-1$. For a dense sequence $(p_{1},\ldots,p_{K})$ will similarly
call the symmetric (stingy) quantum race defined by this sequence a symmetric
(stingy) $\ell$-dense quantum race.

The (stingy) Grover race is an $\ell$-dense race with $\ell=\pi/2$.

##  3 Two-player stingy quantum races

We will first analyze Nash equilibria in stingy quantum races. We can show
several structural properties about the support of Nash equilibria in stingy
quantum races that make them easier to analyze than quantum races. After our
analysis in this section, we will bootstrap our knowledge of Nash equilibria
in stingy quantum races to find an approximate Nash equilibrium for quantum
races.

Consider a stingy quantum race given by the probabilities
$0<p_{1}<p_{2}<\cdots<p_{K}\leq 1$ and $0<P_{1}<P_{2}<\cdots<P_{K}$, and let
$y$ be a mixed strategy of Bob. For $t\leq K$, we let $\sup_{\leq
t}(y)=\\{j\in\sup(y):j\leq t\\}$ be the set of times played by Bob that are at
most $t$, and similarly, we let $\sup_{>t}(y)=\\{j\in\sup(y):j>t\\}$ be the
set of times played by Bob that are greater than $t$. Observe that when Alice
plays the pure strategy $t$ against $y$, her payoff is

$e_{t}^{\mathrm{T}}Ay=p_{t}\left(\sum_{j\in\sup_{\leq
t}(y)}y_{j}\bar{P}_{j}+\sum_{j\in\sup_{>t}(y)}y_{j}\right).$

######  Claim 14.

Let $(x,y)$ be a Nash equilibrium of a 2-player stingy quantum race. If
$t_{1}\in\sup(x)$ then there does not exist $t_{2}>t_{1}$ with $\sup_{\leq
t_{1}}(y)=\sup_{\leq t_{2}}(y)$.

###### Proof.

Say that the game is defined by probabilities $0<p_{1}<p_{2}<\cdots<p_{K}\leq
1$ and $0<P_{1}<P_{2}<\cdots<P_{k}$ If $\sup_{\leq t_{1}}(y)=\sup_{\leq
t_{2}}(y)$ then

$e_{t_{2}}^{\mathrm{T}}Ay=\frac{p_{t_{2}}}{p_{t_{1}}}e_{t_{1}}^{\mathrm{T}}Ay.$

As $p_{t_{1}}<p_{t_{2}}$, the payoff for playing $t_{2}$ is strictly larger
than that for playing $t_{1}$. Therefore $t_{1}$ is not a best response for
$y$, in contradiction with the definition of a Nash equilibrium.

∎

This claim implies that the support structure of Nash equilibria in stingy
quantum races is relatively simple. We first make the following definition.

######  Definition 15.

A pair of strategies $(x,y)$ is called coinciding if $\sup(x)=\sup(y)$. A pair
of strategies $(x,y)$ is called alternating if there exists $1\leq
t_{1}<t_{2}\leq K$ such that the support of one player is
$\\{t_{1},t_{1}+2,\ldots,t_{2}-1\\}$ and the support of the other is
$\sup(y)=\\{t_{1}+1,t_{1}+3,\ldots,t_{2}\\}$. A pair of strategies $(x,y)$ is
called $(t_{1},c,t_{2})$-alternating-coinciding if there are natural numbers
$1\leq t_{1}<t_{2}\leq K$ and $t_{1}+2\leq c\leq t_{2}$ such that the support
of one player is $\\{t_{1},t_{1}+2,\ldots,c-2,c,c+1,c+2,\ldots,t_{2}\\}$ and
the support of the other is
$\sup(y)=\\{t_{1}+1,t_{1}+3,\ldots,c-3,c-1,c,c+1,c+2,\ldots,t_{2}\\}$.

######  Corollary 16.

Let $(x,y)$ be a Nash equilibrium of a stingy quantum race specified by
probabilities $0<p_{1}<p_{2}<\cdots<p_{K}\leq 1$ and
$0<P_{1}<P_{2}<\cdots<P_{k}$. Then there is some $1\leq T\leq K$ such that

  * •

$\sup(x)\cup\sup(y)=[T,K]$ ,

  * •

$(x,y)$ is either coinciding, alternating, or alternating-coinciding.

###### Proof.

From 14 we can easily derive the following two statements:

  * •

$\sup(x)\cup\sup(y)$ is an interval containing the time with maximum success
probability,

  * •

For every $t_{1},t_{2}\in\sup(x)$ there must be $t\in\sup(y)$ with
$t_{1}<t\leq t_{2}$.

These statements immediately imply the claim. ∎

We now study the particularly simple coinciding equilibria. In Section A.1 we
give a full characterization of all Nash equilibria in a symmetric stingy
quantum race.

###  3.1 Unique coinciding equilibrium

We first look for Nash equilibria where the mixed strategies of Alice and Bob
have the same support. If the number of strategies is $K$, we know by
Corollary 16 that this support must be a set $\\{T,T+1,\ldots,K\\}$, for some
$1\leq T\leq K$.

######  Lemma 17.

Consider a stingy quantum race defined by $0<p_{1}<\ldots<p_{K}\leq 1$ and
$0<P_{1}<P_{2}<\cdots<P_{k}$. Let $x,y\in\mathbb{R}^{K}$. Then $(x,y)$ is a
Nash equilibrium for this game with support $\\{T,T+1,\ldots,K\\}$, for some
$1\leq T\leq K$, if and only if $x$ and $y$ satisfy the following system of
equations and inequalities.

$\displaystyle e_{t}^{\mathrm{T}}Ay$ $\displaystyle=e_{T}^{\mathrm{T}}Ay,~{}$
$\displaystyle\text{for}~{}~{}T<t\leq K~{},$ (6) $\displaystyle
e_{T-1}^{\mathrm{T}}Ay$ $\displaystyle\leq e_{T}^{\mathrm{T}}Ay,$ (7)
$\displaystyle y_{t}$ $\displaystyle=0$
$\displaystyle\text{for}~{}~{}0<t<T~{},$ (8) $\displaystyle y_{t}$
$\displaystyle>0$ $\displaystyle\text{for}~{}~{}T\leq t\leq K~{},$ (9)
$\displaystyle\sum_{t=T}^{K}y_{t}$ $\displaystyle=1$ (10) $\displaystyle
x^{\mathrm{T}}Be_{t}$ $\displaystyle=x^{\mathrm{T}}Be_{T},~{}$
$\displaystyle\text{for}~{}~{}T<t\leq K~{},$ (11) $\displaystyle\
x^{\mathrm{T}}Be_{T-1}$ $\displaystyle\leq x^{\mathrm{T}}Be_{T},$ (12)
$\displaystyle x_{t}$ $\displaystyle=0$
$\displaystyle\text{for}~{}~{}0<t<T~{},$ (13) $\displaystyle x_{t}$
$\displaystyle>0$ $\displaystyle\text{for}~{}~{}T\leq t\leq K~{},$ (14)
$\displaystyle\sum_{t=T}^{K}x_{t}$ $\displaystyle=1~{}.$ (15)

###### Proof.

Eq. 8–(10) and (13)–(15) express that $x$ and $y$ are probability
distributions with support $\\{T,T+1,\ldots,K\\}$. The other conditions for a
Nash equilibrium are that all strategies in the support of $x$ are best
responses against $y$ and vice versa. That all strategies in the support of
$x$ are best responses against $y$ means

$\displaystyle e_{t}^{\mathrm{T}}Ay$ $\displaystyle=e_{T}^{\mathrm{T}}Ay,~{}$
$\displaystyle\text{for}~{}~{}T<t\leq K~{},$ $\displaystyle
e_{t-1}^{\mathrm{T}}Ay$ $\displaystyle\leq e_{t}^{\mathrm{T}}Ay,$
$\displaystyle\text{for}~{}~{}1\leq t<T$

The first equation here is exactly Eq. 6. The inequality here is implied by
Eq. 7. This is because for $t<T-1$

$e_{t}^{\mathrm{T}}Ay=\frac{p_{t}}{p_{T-1}}e_{T-1}^{\mathrm{T}}Ay$

as $\sup_{\leq T-1}(y)=\sup_{\leq t}(y)$. A similar argument show that Eq.
11–(12) show that all strategies in the support of $y$ are best responses
against $x$. ∎

When $P_{K}=1$, then Alice has zero payoff on playing time $K$. Thus as long
as $K\geq 2$, when $P_{K}=1$ there is no coinciding Nash equilibrium $(x,y)$
where $\sup(x)=\sup(y)=\\{K\\}$. A similar argument applies when $p_{K}=1$. We
will therefore exclude the case $T=K$ and either $p_{K}=1$ or $P_{K}=1$ for
the next definition and Lemma 19.

######  Definition 18.

We define the values $q_{T}^{A},q_{T}^{B}$, for $T=2,\ldots,K$, and
$r_{T}^{A},r_{T}^{B},z_{T}^{A},z_{T}^{B}$, for $T=1,\ldots,K-1$. The values
$z_{K}^{A},r_{K}^{A}$ are not defined when $T=K,p_{K}=1$ and
$z_{K}^{B},r_{K}^{B}$ are not defined when $T=K,P_{K}=1$.

$\displaystyle q_{i}^{A}$
$\displaystyle=\frac{1}{p_{i}}\left(\frac{1}{P_{i-1}}-\frac{1}{P_{i}}\right)$
(16) $\displaystyle q_{i}^{B}$
$\displaystyle=\frac{1}{P_{i}}\left(\frac{1}{p_{i-1}}-\frac{1}{p_{i}}\right)$
(17) $\displaystyle r_{T}^{A}$
$\displaystyle=\frac{1}{\bar{p}_{T}}\left(\frac{1}{P_{K}}-\sum_{i=T+1}^{K}\bar{p}_{i}q_{i}^{A}\right)$
(18) $\displaystyle r_{T}^{B}$
$\displaystyle=\frac{1}{\bar{P}_{T}}\left(\frac{1}{p_{K}}-\sum_{i=T+1}^{K}\bar{P}_{i}q_{i}^{B}\right)$
(19) $\displaystyle z_{T}^{A}$
$\displaystyle=r_{T}^{A}+\sum_{i=T+1}^{K}q_{i}^{A}$ (20) $\displaystyle
z_{T}^{B}$ $\displaystyle=r_{T}^{B}+\sum_{i=T+1}^{K}q_{i}^{B}$ (21)

######  Lemma 19.

For every $1\leq T\leq K-1$, and the case $T=K$ and $P_{K}\neq 1$, the system
of linear equations composed of the Eq. 6, (8) and (10) of Lemma 17 has a
unique solution given by

$y_{t}=\begin{cases}{r_{T}^{B}}/{z_{T}^{B}}&\text{if}~{}~{}~{}t=T,\\\
{q_{t}^{B}}/{z_{T}^{B}}&\text{if}~{}~{}~{}T<t\leq K,\\\
0&\text{otherwise}\enspace.\end{cases}$

###### Proof.

For convenience, we drop the normalization condition $\sum_{t=T}^{K}y_{t}=1$
and instead scale $y$ such that the expected payoff of a best response is 1.
That is, we replace Eq. 10 by Eq. 22:

$e_{T}^{\mathrm{T}}Ay=1.$ (22)

Clearly the solutions of Eq. 6,(8),(10) and the solutions of Eq. 6,(8),(22)
differ only by a constant multiplicative factor, and from a solution of the
latter system a solution of the former one can be obtained by dividing it
coordinate-wise by $\sum_{t=T}^{K}y_{t}$.

We first want to find the solutions of Eq. 6 and (22). Together, they can be
expressed in matrix form as:

$\begin{bmatrix}p_{T}\bar{P}_{T}&p_{T}&p_{T}&\cdots&p_{T}\\\
p_{T+1}\bar{P}_{T}&p_{T+1}\bar{P}_{T+1}&p_{T+1}&\cdots&p_{T+1}\\\
p_{T+2}\bar{P}_{T}&p_{T+2}\bar{P}_{T+1}&p_{T+2}\bar{P}_{T+2}&\cdots&p_{T+2}\\\
\vdots&&&\ddots&\vdots\\\
p_{K}\bar{P}_{T}&p_{K}\bar{p}_{T+1}&p_{K}\bar{P}_{T+2}&\cdots&p_{K}\bar{P}_{K}\\\
\end{bmatrix}\begin{bmatrix}y_{T}\\\ y_{T+1}\\\ y_{T+2}\\\ \vdots\\\
y_{K}\end{bmatrix}=\begin{bmatrix}1\\\ 1\\\ 1\\\ \vdots\\\ 1\end{bmatrix}.$
(23)

We can simplify the above system of linear equations as follows:

$\begin{bmatrix}\bar{P}_{T}&1&1&\cdots&1\\\
\bar{P}_{T}&\bar{P}_{T+1}&1&\cdots&1\\\
\bar{P}_{T}&\bar{P}_{T+1}&\bar{P}_{T+2}&\cdots&1\\\ \vdots&&&\ddots&\vdots\\\
\bar{P}_{T}&\bar{P}_{T+1}&\bar{P}_{T+2}&\cdots&\bar{P}_{K}\\\
\end{bmatrix}\begin{bmatrix}y_{T}\\\ y_{T+1}\\\ y_{T+2}\\\ \vdots\\\
y_{K}\end{bmatrix}=\begin{bmatrix}1/p_{T}\\\ 1/p_{T+1}\\\ 1/p_{T+2}\\\
\vdots\\\ 1/p_{K}\end{bmatrix}.$

Now for each row before the last we subtract from it the next row, which
gives:

$\begin{bmatrix}0&P_{T+1}&0&\cdots&0\\\ 0&0&P_{T+2}&\cdots&0\\\
0&0&0&\cdots&0\\\ \vdots&&&\ddots&\vdots\\\
\bar{P}_{T}&\bar{P}_{T+1}&\bar{P}_{T+2}&\cdots&\bar{P}_{K}\\\
\end{bmatrix}\begin{bmatrix}y_{T}\\\ y_{T+1}\\\ y_{T+2}\\\ \vdots\\\
y_{K}\end{bmatrix}=\begin{bmatrix}1/p_{T}-1/p_{T+1}\\\ 1/p_{T+1}-1/p_{T+2}\\\
1/p_{T+2}-1/p_{T+3}\\\ \vdots\\\ 1/p_{K}\end{bmatrix}.$

From this we can see that, for every $1\leq T\leq K$, Eq. 23 has a unique
solution, given by $y_{T}=r_{T}^{B}$, and $y_{t}=q_{t}^{B}$, for $T<t\leq K$.
∎

######  Definition 20.

Define $T^{*}_{A}$ (respectively $T^{*}_{B}$) as the smallest integer $1\leq
T\leq K$ such that $r_{T}^{A}>0$ (respectively $r_{T}^{B}>0$). When
$T^{*}_{A}=T^{*}_{B}$ we denote their common value as $T^{*}$.

This definition makes sense as in the case $p_{K}=1$ (when $r_{K}^{A}$ is not
defined) we see that $r_{K-1}^{A}>0$ and otherwise
$r_{K}^{A}=\tfrac{1}{\bar{p}_{K}P_{K}}>0$. A similar argument applies for
$r_{K}^{B}$.

The following theorem characterizes the coinciding Nash equilibria in a stingy
quantum race.

######  Lemma 21.

Eq. 6–(10) have a solution if and only if $T=T^{*}_{B}$. In the case
$T=T^{*}_{B}$, the solution is unique and is given by

$y_{t}=\begin{cases}{r_{T^{*}_{B}}^{B}}/{z_{T^{*}_{B}}^{B}}&\text{if}~{}~{}~{}t=T^{*}_{B},\\\
{q_{t}^{B}}/{z_{T^{*}_{B}}^{B}}&\text{if}~{}~{}~{}T^{*}_{B}<t\leq
K.\end{cases}$

###### Proof.

If $K\geq 2$ and $P_{K}=1$ then $e_{K}^{T}Ae_{K}=0$ and $e_{K-1}^{T}Ae_{K}>0$.
Thus Eq. 6–(10) do not have a solution with $\sup(y)=\\{K\\}$ in this case. We
therefore exclude the case $T=K$ and $p_{K}=1$ from the discussion below.

By Lemma 19 we know that for every $1\leq T\leq K$, there exists a unique
solution to Eq. 6, (8) and (10). For a fixed $T$, the only possible solution
is given by Lemma 19. We now examine for which $T$ is it true that the this
solution $y$ also satisfies Eq. 7 and (9). First we claim that Eq. 9 is
satisfied if and only if $T\geq T^{*}_{B}$. To see that, observe that as the
$p_{t}$ form an increasing sequence, we have $q_{t}^{B}>0$, for all $2\leq
t\leq K$. Therefore Eq. 9 is satisfied if and only if $r_{T}^{B}>0$ which,
because $r_{T}^{B}$ is an increasing function of $T$, holds if and only if
$T\geq T^{*}_{B}$.

We now turn to Eq. 7, and we claim that it is satisfied if and only if $T\leq
T^{*}_{B}$. Substituting in the values of $y$ from Lemma 19, we can express
Eq. 7 as

$p_{T-1}\left(r_{T}^{B}+\sum_{i=T+1}^{K}q_{i}^{B}\right)\leq 1.$ (24)

Let us also observe that the first row of Eq. 23 applied with the start of the
interval at $T-1$ gives

$p_{T-1}\left(\bar{P}_{T-1}r_{T-1}^{B}+\sum_{i=T}^{K}q_{i}^{B}\right)=1,$ (25)

for $T=2,\ldots,K$.

Comparing Eq. 24 and (25), we see that Eq. 7 holds if and only if

$r_{T}^{B}\leq\bar{P}_{T-1}r_{T-1}^{B}+q_{T}^{B}.$ (26)

Note that for every $2\leq T\leq K$, we have

$\bar{P}_{T-1}r_{T-1}^{B}={\bar{P}_{T}}(r_{T}^{B}-q_{T}^{B})\enspace.$ (27)

Replacing $\bar{P}_{T-1}r_{T-1}^{B}$ by ${\bar{P}_{T}}(r_{T}^{B}-q_{T}^{B})$
in the right hand side of Eq. 26, we get that Eq. 7 is equivalent to

$r_{T}^{B}\leq\bar{P}_{T}r_{T}^{B}+P_{T}q_{T}^{B}.$ (28)

The right hand side of Eq. 28 is a convex combination of $r_{T}^{B}$ and
$q_{T}^{B}$, therefore it is at least $r_{T}$ if and only if

$r_{T}^{B}-q_{T}^{B}\leq 0.$ (29)

Looking again at Eq. 27, since both $\bar{P}_{T-1}$ and $\bar{P}_{T}$ are
positive, we can deduce that Eq. 29, and therefore also Eq. 7 holds exactly
when

$r_{T-1}^{B}\leq 0.$ (30)

By the definition of $T^{*}_{B}$, and the fact that $r_{T}^{B}$ is an
increasing function of $T$, Eq. 30 holds when $T\leq T^{*}_{B}$. Thus we
conclude that Eq. 6–(10) are satisfied if and only if $T=T^{*}_{B}$, in which
case the solution is given as in Lemma 19. ∎

The following theorem characterizes the coinciding Nash equilibria in a stingy
quantum race.

######  Theorem 22.

A stingy quantum race defined by probabilities $0<p_{1}<\ldots<p_{K}\leq 1$
and $0<P_{1}<\ldots<P_{K}\leq 1$ has a coinciding Nash equilibrium if and only
if $T_{A}^{*}=T_{B}^{*}$. In this case, letting $T^{*}=T^{*}_{A}=T^{*}_{B}$
there is a unique coinciding equilibrium given by

$x_{t}=\begin{cases}{r_{T^{*}}^{A}}/{z_{T^{*}}^{A}}&\text{if}~{}~{}~{}t=T^{*},\\\
{q_{t}^{A}}/{z_{T^{*}}^{A}}&\text{if}~{}~{}~{}T^{*}<t\leq K\end{cases},\qquad
y_{t}=\begin{cases}{r_{T^{*}}^{B}}/{z_{T^{*}}^{B}}&\text{if}~{}~{}~{}t=T^{*},\\\
{q_{t}^{B}}/{z_{T^{*}}^{B}}&\text{if}~{}~{}~{}T^{*}<t\leq
K\enspace.\end{cases}$

In particular, when $p_{i}=P_{i}$ for all $1\leq i\leq K$ then $(x,x)$ is the
unique coinciding Nash equilibrium.

###### Proof.

By Lemma 17 a coinciding Nash equilibrium $(x,y)$ supported on
$\\{T,T+1,\ldots,K\\}$ must satisfy Eq. 6–(15). By Lemma 21, Eq. 6–(10) are
satisfied if and only if $T=T^{*}_{B}$ and $y$ is given as in the Lemma. We
can also apply Lemma 21 to (the transpose of) Eq. 11–(15) to see that they
have a solution if and only if $T=T^{*}_{A}$ and $x$ is given by

$x_{t}=\begin{cases}{r_{T^{*}_{A}}^{A}}/{z_{T^{*}_{A}}^{A}}&\text{if}~{}~{}~{}t=T^{*}_{A},\\\
{q_{t}^{A}}/{z_{T^{*}_{A}}^{A}}&\text{if}~{}~{}~{}T^{*}_{A}<t\leq K,\\\
0&\text{otherwise}.\end{cases}$

As $x$ and $y$ must have the same support in a coinciding Nash equilibrium,
there can only exist a coinciding Nash equilibrium if $T^{*}_{A}=T^{*}_{B}$.

When $p_{i}=P_{i}$ for all $1\leq i\leq K$ then clearly $r_{T}^{A}=r_{T}^{B}$
and $q_{i}^{A}=q_{i}^{B}$ and it will always be the case that
$T^{*}_{A}=T^{*}_{B}$. Thus there will always exist a Nash equilibrium in this
case, given by the unique solution to Eq. 6–(15). ∎

###  3.2 Payoff and collision probability

In this section we will explore the consequences of the coinciding Nash
equilibrium we have found for the payoff of the game and for the probability
that the two players win at the same time, the collision probability. For
these results, we will only consider the symmetric case when there is always a
unique symmetric equilibrium whose support begins at
$T^{*}=T^{*}_{A}=T^{*}_{B}$. Note that the payoff for each player with this
strategy is $\frac{1}{z_{T^{*}}}$. Since a player receives payoff $1$ upon
winning, $\frac{1}{z_{T^{*}}}$ is also exactly the each player’s winning
probability.

To investigate the collision probability, we will also make the following
definitions.

######  Definition 23 (Unnormalized collision probability).

Define

$\sigma(T)=p_{T}^{2}r_{T}^{2}+\sum_{i=T+1}^{K}p_{i}^{2}q_{i}^{2}\enspace.$

With this definition, $\frac{1}{z_{T^{*}}^{2}}\sigma(T^{*})$ is the collision
probability we are interested in.

First we analyze the payoff in a symmetric stingy quantum race.

######  Theorem 24.

Let $p_{1}<p_{2}<\cdots<p_{K}$ define a stingy symmetric quantum race. Then

$z_{T^{*}}=1+\sqrt{1+\tfrac{1}{p_{K}^{2}}+\sigma(T^{*})}\enspace.$

In particular,

$\frac{1}{z_{T^{*}}}\leq\sqrt{2}-1\enspace.$

###### Proof.

We look at all different possible outcomes of the race: Alice wins, Bob wins,
or no one wins. There are two different ways in which no one wins: Alice and
Bob both succeed at the same time, or, no one succeeds. The probability that
Alice wins is $1/z_{T^{*}}$, and the same for Bob. Thus we have

$\displaystyle 1$
$\displaystyle=\frac{2}{z_{T^{*}}}+\frac{\sigma(T^{*})}{z_{T^{*}}^{2}}+\left(\frac{1}{z_{T}^{*}}\left(\bar{p}_{T^{*}}r_{T^{*}}+\sum_{i=T^{*}+1}^{K}\bar{p}_{i}q_{i}\right)\right)^{2}$
$\displaystyle=\frac{2}{z_{T^{*}}}+\frac{\sigma(T^{*})}{z_{T^{*}}^{2}}+\left(\frac{1}{p_{K}z_{T^{*}}}\right)^{2}\enspace.$

Taking the positive root gives

$z_{T^{*}}=1+\sqrt{1+\tfrac{1}{p_{K}^{2}}+\sigma(T^{*})}\enspace.$

The “in particular” statement follows by noting $z_{T^{*}}\geq 1+\sqrt{2}$. ∎

######  Corollary 25.

If $T^{*}\geq 2$ then

$p_{T^{*}-1}\leq\sqrt{2}-1\enspace.$

###### Proof.

As can be seen from Bob playing time $T^{*}-1$, we have
$p_{T^{*}-1}z_{T^{*}}\leq 1$, thus $p_{T^{*}-1}\leq\sqrt{2}-1$ by Theorem 24.
∎

Although Theorem 24 gives an exact expression for the payoff, we would like to
get a general lower bound on the payoff. This requires showing an upper bound
on the collision probability. Showing an upper bound on the collision
probability is also important for the application to Bitcoin, to estimate the
forking probability amongst quantum miners.

The first step to upper bounding the collision probability is to get a rough
lower bound on $p_{T^{*}}$. This is our initial bootstrap, which will then let
us upper bound the collision probability and then in turn get a sharper lower
bound on $p_{T^{*}}$ in Corollary 28. For these results we restrict to
$\ell$-dense stingy quantum races.

######  Lemma 26.

Let $p_{1},\ldots,p_{K}$ define an $\ell$-dense symmetric stingy quantum race.
If $K\geq 6\ell$ then $p_{T^{*}}>\tfrac{5}{21}$. In particular, $T^{*}\geq 2$.

###### Proof.

As $r_{T^{*}}>0$ we have

$\displaystyle\frac{1}{p_{K}}$
$\displaystyle>\sum_{i=T^{*}+1}^{K}\bar{p}_{i}q_{i}$
$\displaystyle=\sum_{i=T^{*}+1}^{K}\left(\frac{1}{p_{i}}-1\right)\left(\frac{1}{p_{i-1}}-\frac{1}{p_{i}}\right)$

Let $L=\max_{T}\ \\{T:p_{T}\leq 1/2\\}$. By assumption of an $\ell$-dense
quantum race, we have $p_{L}\geq\tfrac{1}{2}-\tfrac{\ell}{K}$. Whenever
$p_{i}\leq 1/2$ we have $(1/p_{i}-1)\geq 1$, thus

$\displaystyle\frac{1}{p_{K}}$
$\displaystyle>\sum_{i=T^{*}+1}^{L}\frac{1}{p_{i-1}}-\frac{1}{p_{i}}$
$\displaystyle=\frac{1}{p_{T^{*}}}-\frac{1}{p_{L}}$
$\displaystyle\geq\frac{1}{p_{T^{*}}}-3$

where for the last inequality we have used $\tfrac{1}{p_{L}}\leq 3$ by the
assumption $K\geq 6\ell$. This then implies that
$\tfrac{1}{p_{T^{*}}}\leq\tfrac{6}{5}+3$, again using the fact that $K\geq
6\ell$ and so $p_{K}\geq\tfrac{5}{6}$.

The “in particular” holds since $p_{1}\leq 1/6$ by the assumption of
$\ell$-density and that $K\geq 6\ell$, and $1/6<5/21$. ∎

######  Theorem 27.

Let $p_{1},\ldots,p_{K}$ define an $\ell$-dense symmetric stingy quantum race.
If $K\geq 6\ell$ then

$\frac{\sigma(T^{*})}{z_{T^{*}}^{2}}\leq\frac{6\ell}{K}\qquad\mbox{ and
}\qquad\sigma(T^{*})\leq\frac{196\ell}{K}\enspace.$

###### Proof.

We will actually prove a more general statement: for any probability
distribution $v$ on $[K]$ it holds that

$\frac{1}{z_{T^{*}}}\left(v_{T^{*}}p_{T^{*}}^{2}r_{T^{*}}+\sum_{i=T^{*}+1}^{K}v_{i}p_{i}^{2}q_{i}\right)\leq\frac{6\ell}{K}\enspace.$
(31)

Applying this with the distribution $v_{T^{*}}=\frac{r_{T^{*}}}{z_{T^{*}}}$
and $v_{T}=\frac{q_{T}}{z_{T^{*}}}$ for $T^{*}+1\leq T\leq K$ gives the first
inequality. We discuss how to derive the second inequality of the Theorem
after the proof of Eq. 31.

Now we turn to the proof of Eq. 31. First, note that $T^{*}\geq 2$ by Lemma 26
and thus it makes sense to talk about $T^{*}-1$. As $r_{T^{*}}\leq q_{T^{*}}$
we have:

$\displaystyle\frac{1}{z_{T^{*}}}\left(v_{T^{*}}p_{T^{*}}^{2}r_{T^{*}}+\sum_{i=T^{*}+1}^{K}v_{i}p_{i}^{2}q_{i}\right)$
$\displaystyle\leq\frac{1}{z_{T^{*}}}\sum_{i=T^{*}}^{K}v_{i}p_{i}^{2}q_{i}$
$\displaystyle=\frac{1}{z_{T^{*}}}\sum_{i=T^{*}}^{K}v_{i}p_{i}\left(\frac{1}{p_{i-1}}-\frac{1}{p_{i}}\right)$
$\displaystyle=\frac{1}{z_{T^{*}}}\sum_{i=T^{*}}^{K}v_{i}\left(\frac{p_{i}-p_{i-1}}{p_{i-1}}\right)$
$\displaystyle\leq\frac{\ell}{Kz_{T^{*}}}\sum_{i=T^{*}}^{K}v_{i}\left(\frac{1}{p_{i-1}}\right)$
$\displaystyle\leq\frac{\ell}{Kz_{T^{*}}}\frac{1}{p_{T^{*}-1}}\enspace,$

since $v$ is a probability distribution. Now note that
$p_{T^{*}-1}\geq\frac{5}{21}-\frac{1}{6}\geq\frac{1}{14}$ by Lemma 26 and the
assumption $\frac{\ell}{K}\leq\frac{1}{6}$. Eq. 31 now follows from the upper
bound $\frac{1}{z_{T^{*}}}\leq\sqrt{2}-1$ from Theorem 24.

To see the second inequality, note

$\sigma(T^{*})\leq\frac{\ell}{K}\frac{z_{T^{*}}}{p_{T^{*}-1}}\leq\frac{\ell}{K}\frac{1}{p_{T^{*}-1}^{2}}\leq\frac{196\ell}{K}\enspace.$

∎

Now that we have an upper bound on the collision probability, we obtain the
following corollary to Theorem 24.

######  Corollary 28.

Let $p_{1},\ldots,p_{K}$ define an $\ell$-dense symmetric stingy quantum race.
Let $\tau=\frac{50\sqrt{2}\ell}{K}$. If $K\geq 6\ell$ then

$z_{T^{*}}\leq\sqrt{2}+1+\tau,\qquad\frac{1}{z_{T^{*}}}\geq\sqrt{2}-1-\tau(\sqrt{2}-1)^{2},\qquad
p_{T^{*}}\geq\sqrt{2}-1-\tau(\sqrt{2}-1)^{2}\enspace.$

###### Proof.

By Theorem 24 we have

$\displaystyle z_{T^{*}}$
$\displaystyle=1+\sqrt{1+\frac{1}{p_{K}^{2}}+\sigma(T^{*})}$
$\displaystyle\leq 1+\sqrt{1+\frac{K^{2}}{(K-\ell)^{2}}+\frac{196\ell}{K}}$
$\displaystyle\leq 1+\sqrt{2+\frac{200\ell}{K}}\enspace,$

as $\frac{K^{2}}{(K-\ell)^{2}}\leq 1+\frac{4\ell}{K}$ by Eq. 2 (using the
assumption that $\frac{\ell}{K}\leq\frac{1}{6}$). Continuing by applying Eq. 4
we have

$z_{T^{*}}\leq\sqrt{2}+1+\frac{50\sqrt{2}\ell}{K}\enspace,$

giving the first inequality of the Corollary. The second inequality of the
Corollary follows by applying Eq. 3 to the first inequality.

The third inequality of the Corollary follows from the second inequality from
the observation that $p_{T^{*}}\geq\frac{1}{z_{T^{*}}}$. This is because

$\displaystyle\frac{1}{z_{T^{*}}}$
$\displaystyle=\frac{p_{T^{*}}}{z_{T^{*}}}\left(r_{T^{*}}\bar{p}_{T^{*}}+\sum_{t=T^{*}+1}^{K}q_{t}\right)$
$\displaystyle\leq\frac{p_{T^{*}}}{z_{T^{*}}}\left(r_{T^{*}}+\sum_{t=T^{*}+1}^{K}q_{t}\right)$
$\displaystyle=p_{T^{*}}\,.$

∎

##  4 Two-player quantum races

In this section, we bootstrap our results about symmetric stingy quantum races
to analyze symmetric quantum races. Our main results are two-fold.

  1. 1.

The unique coinciding Nash equilibrium in an $\ell$-dense symmetric stingy
quantum race is an approximate Nash equilibrium in the corresponding quantum
race.

  2. 2.

The approximate Nash equilibrium from (1) achieves a payoff which is nearly
optimal among all symmetric Nash equilibria in a symmetric quantum race.

The intuition for item (1) is clear. The only difference between a stingy
quantum race and a quantum race is the payoff on ties. For the unique
coinciding Nash equilibrium we have shown that the collision probability is
$O(\ell/K)$, thus the change in payoff on ties will make only a small change
to the payoffs under this strategy.

For item (2), we use the quadratic programming characterization of Nash
equilibria [MS64]. Consider a game $(A,B)$ where $A,B$ are $m$-by-$n$
matrices. The program

$\displaystyle\underset{x\in\Delta^{m},y\in\Delta^{n},\alpha,\beta\in\mathbb{R}}{\text{maximize}}$
$\displaystyle x^{T}(A+B)y-\alpha-\beta$ (32) subject to $\displaystyle
Ay\leq\alpha\mathbf{1},$ $\displaystyle B^{T}x\leq\beta\mathbf{1},$

has an optimal value of $0$, and any $(x,y)$ attaining the value $0$ is a Nash
equilibrium. In the case of a symmetric quantum race $(A,A^{T})$, when we
restrict to symmetric strategies $(x,x)$ the objective function in Eq. 32
becomes negative definite plus linear, making this a standard quadratic
program. We then use the tight dual formulation of a quadratic program [Dor60]
to give an upper bound on the payoff of any symmetric Nash equilibrium, by
explicitly constructing solutions to the dual problem. This allows us to show
that the payoff of the unique coinciding equilibrium in a stingy race achieves
a payoff which is within $O(\sqrt{\ell/K})$ of optimal amongst all symmetric
equilibria in the corresponding quantum race.

We now proceed to show these two results.

###  4.1 Approximate Nash equilibrium

######  Definition 29.

A two-player game described by payoff matrices $(A,B)$ is said to have an
$\epsilon$-approximate Nash equilibrium $(p,q)$, for $\epsilon\geq 0$, if the
following two conditions hold

$\displaystyle p^{\mathrm{T}}Aq\geq v^{\mathrm{T}}Aq-\epsilon\mbox{ for all
}v\in\Delta_{m}$ (33) $\displaystyle p^{\mathrm{T}}Bq\geq
p^{\mathrm{T}}Bu-\epsilon\mbox{ for all }u\in\Delta_{n}\enspace.$ (34)

######  Definition 30.

A two-player game described by payoff matrices $(A,B)$ is said to have an
$\epsilon$-well supported Nash equilibrium $(p,q)$, for $\epsilon\geq 0$ if

$\displaystyle e_{i}^{\mathrm{T}}Aq\geq e_{j}^{\mathrm{T}}Aq-\epsilon\mbox{
for all }i\in\sup(p)\mbox{ and }j\in[m]$ $\displaystyle
p^{\mathrm{T}}Be_{i}\geq p^{\mathrm{T}}Be_{j}-\epsilon\mbox{ for all
}i\in\sup(q)\mbox{ and }j\in[n]\enspace.$

Note that an $\epsilon$-well supported Nash equilibrium is also an
$\epsilon$-approximate Nash equilibrium, but the reverse does not hold.

Before showing that the unique coinciding equilibrium in an $\ell$-dense
symmetric stingy quantum race is a well supported equilibrium in the
corresponding $\ell$-dense symmetric quantum race, we need the following
claim.

######  Claim 31.

Let $p_{1},\ldots,p_{K}$ be an $\ell$-dense sequence such that $K\geq 6\ell$.
Then for all $T^{*}\leq i,j\leq K$

$\left|\frac{p_{i}}{p_{i-1}}-\frac{p_{j}}{p_{j-1}}\right|\leq\frac{14\ell}{K}\enspace.$

###### Proof.

Lemma 26 along with the $\ell$ dense condition gives us a lower bound on
$p_{T^{*}-1}\geq\frac{5}{21}-\frac{1}{6}=\frac{1}{14}.$ Now note that for all
$T^{*}\leq i\leq K,$ we have

$1\leq\frac{p_{i}}{p_{i-1}}\leq 1+\frac{\ell}{Kp_{i-1}}\leq
1+\frac{\ell}{Kp_{T^{*}-1}}\leq 1+\frac{14\ell}{K},$

thus proving the claim. ∎

######  Theorem 32.

Let $p_{1},\ldots,p_{K}$ be an $\ell$-dense sequence defining the symmetric
stingy quantum race $(A_{0},A_{0}^{T})$ and the symmetric quantum race
$(A,A^{T})$. Let $(x,x)$ be the unique coinciding Nash equilibrium for the
stingy quantum race $(A_{0},A_{0}^{T})$ given by Theorem 22. Then $(x,x)$ is a
$\tfrac{7(\sqrt{2}-1)\ell}{K}$-well supported Nash equilibrium in the quantum
race $(A,A^{T})$.

###### Proof.

To show that $(x,x)$ is an $\epsilon$-well supported Nash equilibrium in the
quantum race $(A,A^{T})$ it suffices to show that $e_{i}^{\mathrm{T}}Ax\geq
e_{j}^{\mathrm{T}}Ax-\epsilon$ for all $T^{*}\leq i\leq K$ and $j\in[K]$.

Note that

$e_{i}^{\mathrm{T}}A_{0}x=\begin{cases}\frac{1}{z_{T^{*}}}&\text{if}\
T^{*}\leq i\leq K\\\ p_{i}&\text{if}\ i<T^{*}\end{cases}\enspace.$ (35)

As $A=A_{0}+\tfrac{1}{2}\mathrm{diag}(p_{1}^{2},\ldots,p_{K}^{2})$ this means

$e_{i}^{\mathrm{T}}Ax=\begin{cases}\frac{1}{z_{T^{*}}}+\frac{1}{2}p_{i}^{2}x_{i}&\text{if}\
T^{*}\leq i\leq K\\\ p_{i}&\text{if}\ i<T^{*}\end{cases}\enspace.$ (36)

For $T^{*}\leq i\leq K$ and $j<T^{*}$ we have $e_{i}^{\mathrm{T}}Ax\geq
e_{i}^{\mathrm{T}}A_{0}x\geq e_{j}^{\mathrm{T}}A_{0}x=e_{j}^{\mathrm{T}}Ax$.

Now we show that for $T^{*}\leq i,j\leq K$ we have $e_{i}^{\mathrm{T}}Ax\geq
e_{j}^{\mathrm{T}}Ax-\tfrac{7(\sqrt{2}-1)\ell}{z_{T^{*}}K}$. First we consider
the case where $T^{*}<i\leq K$ and $T^{*}\leq j\leq K$. In this case

$\displaystyle e_{i}^{\mathrm{T}}Ax-e_{j}^{\mathrm{T}}Ax$
$\displaystyle=\frac{1}{2}\left(p_{i}^{2}x_{i}-p_{j}^{2}x_{j}\right)$
$\displaystyle\geq\frac{1}{2z_{T}^{*}}\left(\frac{p_{i}}{p_{i-1}}-\frac{p_{j}}{p_{j-1}}\right)$
$\displaystyle\geq-\frac{7(\sqrt{2}-1)\ell}{K}\enspace,$

by 31 along with Theorem 24. The second line holds with equality except for
the case $j=T^{*}$, where we have used the fact that $q_{T^{*}}\geq
r_{T^{*}}$.

Finally, consider the case where $i=T^{*}$ and $T^{*}<j\leq K$. Then

$\displaystyle e_{T^{*}}^{\mathrm{T}}Ax-e_{j}^{\mathrm{T}}Ax$
$\displaystyle=\frac{1}{2z_{T^{*}}}\left(p_{T^{*}}^{2}r_{T^{*}}-\frac{p_{j}}{p_{j-1}}+1\right)$
$\displaystyle\geq\frac{1}{2z_{T^{*}}}\left(1-\frac{p_{j}}{p_{j-1}}\right)$
$\displaystyle\geq-\frac{7(\sqrt{2}-1)\ell}{K}.$

∎

###  4.2 Upper bound on payoff

Let $(x,x)$ be the unique coinciding Nash equilibrium in an $\ell$-dense
symmetric stingy quantum race $(A_{0},A_{0}^{\mathrm{T}})$. We have just shown
that $(x,x)$ is a $\frac{7(\sqrt{2}-1)\ell}{K}$-well supported Nash
equilibrium in the corresponding quantum race $(A,A^{\mathrm{T}})$. By
Corollary 28, $(x,x)$ achieves payoff at least
$\sqrt{2}-1-50\sqrt{2}(\sqrt{2}-1)^{2}\frac{\ell}{K}$ in the game
$(A,A^{\mathrm{T}})$. In this section, we show that this payoff is within
$O(\sqrt{\ell/K})$ of optimal among all symmetric strategies $(y,y)$ for the
game $(A,A^{\mathrm{T}})$.

Our starting point is to use the program in Eq. 32 to provide a means to upper
bound the value of any symmetric equilibrium.

######  Lemma 33.

Let $(A,A^{T})$ be a symmetric game and define for $c\geq 0$

$\displaystyle\gamma_{A}(c)=$ $\displaystyle\underset{x}{\text{maximize}}$
$\displaystyle\frac{1}{2}x^{T}(A+A^{T})x$ subject to $\displaystyle Ax\leq
c\mathbf{1},$ $\displaystyle\mathbf{1}^{\mathrm{T}}x=1,x\geq\mathbf{0}.$

For all $c_{0}$, such that $\gamma_{A}(c)<c$ for all $c\geq c_{0}$, the payoff
of any symmetric Nash equilibrium in the game $(A,A^{\mathrm{T}})$ is less
than $c_{0}$.

###### Proof.

We show the contrapositive. Suppose there is a symmetric Nash equilibrium
$(x,x)$ with payoff $c\geq c_{0}$. Then $(x,x,c,c)$ is a feasible solution to
the program in Eq. 32 with objective value $0$. Thus $Ax\leq c$ and
$\frac{1}{2}x^{\mathrm{T}}(A+A^{\mathrm{T}})x=c$. ∎

This is the approach we take to upper bounding the payoff of symmetric Nash
equilibria in a quantum race.

######  Theorem 34.

Let $p_{1},\ldots,p_{K}$ be an $\ell$-dense sequence with $K\geq 6\ell$. Then
any symmetric Nash equilibrium $(x,x)$ in the two-player quantum race defined
by $p_{1},\ldots,p_{K}$ has payoff at most
$\sqrt{2}-1+5\sqrt{\frac{\ell}{K}}$.

###### Proof.

Let $(A,A^{\mathrm{T}})$ be the payoff matrices of a two-player quantum race
defined by $p_{1},\ldots,p_{K}$. We will show that $\gamma_{A}(c)<c$ for all
$c>\sqrt{2}-1+5\sqrt{\frac{\ell}{K}}$. By Lemma 33 this proves the theorem.

In the case of a quantum race
$A+A^{\mathrm{T}}=p1^{\mathrm{T}}+1p^{\mathrm{T}}-pp^{\mathrm{T}}$. This means
that over the probability simplex, the quadratic form
$x^{\mathrm{T}}(A+A^{\mathrm{T}})x=-x^{\mathrm{T}}(pp^{\mathrm{T}})x+2p^{\mathrm{T}}x$
is a negative-definite plus linear function. In this case, $\gamma_{A}(c)$ is
in the standard form of a quadratic program and has a dual program with
matching value [Dor60].

$\displaystyle\gamma_{A}(c)=$
$\displaystyle\underset{v\in\mathbb{R}^{K},\lambda,d\in\mathbb{R}}{\text{minimize}}$
$\displaystyle\frac{1}{2}\lambda^{2}+c\cdot\mathbf{1}^{\mathrm{T}}v+d$ (37)
subject to $\displaystyle A^{T}v\geq(1-\lambda)p-d\mathbf{1}\enspace,$
$\displaystyle v\geq\mathbf{0}.$

Our approach will be to construct a feasible solution to Eq. 37 to demonstrate
that $\gamma_{A}(c)<c$ for all $c>\sqrt{2}-1+5\sqrt{\frac{\ell}{K}}$.

First note that for $c>\tfrac{1}{2}$ there is a trivial solution where
$\lambda=1,d=0$ and $v$ is the all-zero vector which shows that $\gamma(c)<c$.
We now focus on the case $c\leq\tfrac{1}{2}$. Let $\sqrt{2}-1\leq
c\leq\tfrac{1}{2}$. We will develop a lower bound on $c$ which implies
$\gamma_{A}(c)<c$.

Let $S$ be the smallest index $i$ such that $p_{i}\geq c$. Note that as $A$ is
an $\ell$-dense quantum race we have $p_{S}\leq c+\tfrac{\ell}{K}$. We let

$d=(1-\lambda)\left(1+p_{K}-\frac{p_{K}}{p_{S}}\right)$

and

$v(i)=\begin{cases}0&\text{ if }1\leq i<S\\\
(1-\lambda-d)\frac{p_{S}}{\bar{p}_{S}}\frac{1}{p_{i}}\left(\frac{1}{p_{i}}-\frac{1}{p_{i+1}}\right)&\text{
if }S\leq i<K\\\
(1-\lambda-d)\frac{p_{S}}{p_{K}^{2}\bar{p}_{S}}-\frac{(1-\lambda)}{p_{K}}&\text{
if }i=K\enspace.\end{cases}$

The choice of $v$ comes from solving the system of linear equations
$(A_{0}^{\mathrm{T}}v)_{i}=(1-\lambda)p_{i}-d$ for $S\leq i\leq K$. The
parameter $\lambda$ will be chosen later.

Let us see that $v$ satisfies the constraints of Eq. 37. Note that

$1-\lambda-d=(1-\lambda)p_{K}\frac{\bar{p}_{S}}{p_{S}}$

thus $v(K)=0$ and $v\geq 0$ so long as $\lambda\leq 1$.

As mentioned, by construction $v$ satisfies
$(A_{0}^{T}v)_{i}=(1-\lambda)p_{i}-d$ for $S\leq i\leq K$. Thus as
$A=A_{0}+\tfrac{1}{2}\mathrm{diag}(p)^{2}$ and $v\geq 0$ we also have
$(A^{T}v)_{i}\geq(1-\lambda)p_{i}-d$ for $S\leq i\leq K$.

For $i<S$ we have that

$\displaystyle(A^{T}v)_{i}$ $\displaystyle\geq(A_{0}^{T}v)_{i}$
$\displaystyle=\bar{p}_{i}p^{T}v$ $\displaystyle\geq\bar{p}_{S}p^{T}v$
$\displaystyle=(1-\lambda)p_{S}-d$
$\displaystyle\geq(1-\lambda)p_{i}-d\enspace.$

Thus the constraint $A_{0}^{T}v\geq(1-\lambda)p-d\mathbf{1}$ is satisfied.

We have shown that $v$ is a feasible solution for any choice of $\lambda\leq
1$. We now choose $\lambda$ to minimize the objective value.

Substituting our choices of $v,d$ into the objective value we have

$\displaystyle\gamma_{A}(c)$
$\displaystyle\leq\frac{1}{2}\lambda^{2}+(1-\lambda)\left(1+p_{K}-\frac{p_{K}}{p_{S}}\right)+c(1-\lambda)p_{K}\sum_{i=S}^{K-1}\frac{1}{p_{i}}\left(\frac{1}{p_{i}}-\frac{1}{p_{i+1}}\right)$
$\displaystyle=\frac{1}{2}\lambda^{2}+(1-\lambda)\left(1+p_{K}\left(-\frac{\bar{p}_{S}}{p_{S}}+c\cdot\sum_{i=S}^{K-1}\frac{1}{p_{i}}\left(\frac{1}{p_{i}}-\frac{1}{p_{i+1}}\right)\right)\right)$

Define

$\beta(c)=1+p_{K}\left(-\frac{\bar{p}_{S}}{p_{S}}+c\cdot\sum_{i=S}^{K-1}\frac{1}{p_{i}}\left(\frac{1}{p_{i}}-\frac{1}{p_{i+1}}\right)\right)\enspace.$

The objective value $\tfrac{1}{2}\lambda^{2}+(1-\lambda)\beta(c)$ is minimized
over $\lambda$ by taking $\lambda=\beta(c)$. This makes the objective value
$\beta(c)-\beta(c)^{2}/2$.

We have now reduced the problem to showing

$\beta(c)-\beta(c)^{2}/2-c<0$

The roots of the corresponding quadratic equation are $1\pm\sqrt{1-2c}$. Note
that $c\leq 1/2$, thus the square root term will be real. Thus we will
simultaneously have $\beta(c)\leq 1$ and $\beta(c)-\beta(c)^{2}/2<c$ when
$\beta(c)<1-\sqrt{1-2c}$. In Lemma 35, we show that
$\beta(c)<1-\sqrt{1-2c^{*}}$ when $\sqrt{2}-1+5\sqrt{\frac{\ell}{K}}\leq
c\leq\tfrac{1}{2}$. This will conclude the proof. ∎

######  Lemma 35.

$\beta(c)<1-\sqrt{1-2c}$ for any $\sqrt{2}-1+5\sqrt{\frac{\ell}{K}}\leq
c\leq\tfrac{1}{2}$.

###### Proof.

The claim is equivalent to showing

$\sum_{i=S}^{K-1}\frac{1}{p_{i}}\left(\frac{1}{p_{i}}-\frac{1}{p_{i+1}}\right)<\frac{1}{c}\left(\frac{\bar{p}_{S}}{p_{S}}-\frac{\sqrt{1-2c}}{p_{K}}\right)\enspace,$
(38)

for all $\sqrt{2}-1+5\sqrt{\frac{\ell}{K}}<c\leq\frac{1}{2}$.

We proceed by a series of claims to simplify both the left hand side and the
right hand side of Eq. 38 until we can work the inequality into something
easier to prove.

We begin by simplifying the left hand side, for which we use the following
claim.

######  Claim 36.

Let $p_{1},\ldots,p_{K}$ be an $\ell$-dense sequence. If $K\geq 6\ell$ then

$\sum_{i=T^{*}}^{K-1}\frac{1}{p_{i}}\left(\frac{1}{p_{i}}-\frac{1}{p_{i+1}}\right)\leq\sqrt{2}+1+267\frac{\ell}{K}\enspace.$

###### Proof.

$\displaystyle\sum_{i=T^{*}}^{K-1}\frac{1}{p_{i}}\left(\frac{1}{p_{i}}-\frac{1}{p_{i+1}}\right)$
$\displaystyle=\sum_{i=T^{*}}^{K-1}\frac{1}{p_{i+1}}\left(\frac{1}{p_{i}}-\frac{1}{p_{i+1}}\right)+\sum_{i=T^{*}}^{K-1}\left(\frac{1}{p_{i}}-\frac{1}{p_{i+1}}\right)^{2}$
$\displaystyle\leq z_{T^{*}}+\sigma(T^{*})$
$\displaystyle\leq\sqrt{2}+1+(50\sqrt{2}+196)\frac{\ell}{K}\enspace,$

by Theorem 27 and Corollary 28. ∎

We now use 36 to upper bound the left hand side of Eq. 38.

######  Claim 37.

Let $\sqrt{2}-1\leq c\leq p_{S}\leq c+\tfrac{\ell}{K}$. Then

$\sum_{i=S}^{K-1}\frac{1}{p_{i}}\left(\frac{1}{p_{i}}-\frac{1}{p_{i+1}}\right)\leq\frac{1}{c}\left(\frac{1}{c}-(1-c)(\sqrt{2}+1)\right)+287\frac{\ell}{K}\enspace.$

###### Proof.

$\displaystyle\sum_{i=S}^{K-1}\frac{1}{p_{i}}\left(\frac{1}{p_{i}}-\frac{1}{p_{i+1}}\right)$
$\displaystyle=\sum_{i=T^{*}}^{K-1}\frac{1}{p_{i}}\left(\frac{1}{p_{i}}-\frac{1}{p_{i+1}}\right)-\sum_{i=T^{*}}^{S-1}\frac{1}{p_{i}}\left(\frac{1}{p_{i}}-\frac{1}{p_{i+1}}\right)$
$\displaystyle\leq\sqrt{2}+1+\frac{267\ell}{K}-\frac{1}{p_{S}}\sum_{i=T^{*}}^{S-1}\left(\frac{1}{p_{i}}-\frac{1}{p_{i+1}}\right)$
$\displaystyle=\sqrt{2}+1+\frac{267\ell}{K}-\frac{1}{p_{S}}\left(\frac{1}{p_{T^{*}}}-\frac{1}{p_{S}}\right)$
$\displaystyle\leq\sqrt{2}+1+\frac{267\ell}{K}+\frac{1}{p_{S}^{2}}-\frac{\sqrt{2}+1}{p_{S}}+\frac{\ell(\sqrt{2}+1)^{2}}{p_{S}K}$
$\displaystyle\leq\frac{1}{p_{S}}\left(\frac{1}{p_{S}}-\bar{p}_{S}(\sqrt{2}+1)\right)+\frac{\ell}{K}\left(267+\frac{(\sqrt{2}+1)^{2}}{p_{S}}\right)$
$\displaystyle\leq\frac{1}{c}\left(\frac{1}{c}-(1-c)(\sqrt{2}+1)\right)+\frac{\ell}{K}\left(267+(\sqrt{2}+1)^{2}+\frac{(\sqrt{2}+1)^{2}}{c}\right)\enspace.$

For the fourth line we used Corollary 25 that $p_{T^{*}-1}\leq\sqrt{2}-1$,
together with $\ell$-density to get $p_{T^{*}}\leq\sqrt{2}-1+\tfrac{\ell}{K}$.
This then implies
$\tfrac{1}{p_{T^{*}}}\geq\sqrt{2}+1-\tfrac{\ell(\sqrt{2}+1)^{2}}{K}$ by Eq. 3.
∎

Now that we have obtained an upper bound on the left hand side of Eq. 38, we
proceed to lower bound the right hand side. We use the following claim to do
this.

######  Claim 38.

Let $\sqrt{2}-1\leq c\leq\tfrac{1}{2}$ and $c\leq p_{S}\leq
c+\tfrac{\ell}{K}$. Then

$\frac{1}{c}\left(\frac{\bar{p}_{S}}{p_{S}}-\frac{\sqrt{1-2c}}{p_{K}}\right)\geq\frac{1}{c}\left(\frac{1-c}{c}-\frac{\sqrt{1-2c}}{p_{K}}\right)-\frac{\ell}{c^{3}K}\left(1-\frac{\ell}{K}\right)\enspace.$

###### Proof.

As $c\leq p_{S}\leq c+\tfrac{\ell}{K}$ we have

$\frac{\bar{p}_{S}}{p_{S}}\geq\frac{1-c-\frac{\ell}{K}}{c+\frac{\ell}{K}}\enspace.$

Applying Eq. 3 to $\frac{1}{c+\ell/K}$ gives

$\displaystyle\frac{\bar{p}_{S}}{p_{S}}$
$\displaystyle\geq\left(1-c-\frac{\ell}{K}\right)\left(\frac{1}{c}-\frac{\ell}{Kc^{2}}\right)$
$\displaystyle=\frac{1-c}{c}-\frac{(1-c)\ell}{Kc^{2}}-\frac{\ell}{Kc}+\frac{\ell^{2}}{K^{2}c^{2}}$
$\displaystyle=\frac{1-c}{c}-\frac{\ell}{Kc^{2}}+\frac{\ell^{2}}{K^{2}c^{2}}\enspace.$

∎

Putting 37 and 38 together and simplifying, it now suffices to show

$0<\sqrt{2}-c(\sqrt{2}+1)-\frac{\sqrt{1-2c}}{p_{K}}-\frac{\ell\tau}{K}\enspace,$
(39)

for any $\sqrt{2}-1+5\sqrt{\frac{\ell}{K}}<c\leq\frac{1}{2}$, where
$\tau=150$.

We find a lower bound on the value of $c$ for which this inequality holds with
the next claim.

######  Claim 39.

For any
$\sqrt{2}-1+\sqrt{\frac{2\ell(\sqrt{2}-1)^{3}\left(\tau+\frac{6(\sqrt{2}-1)}{5}\right)}{K}}<c\leq
1/2$

$0<\sqrt{2}-(\sqrt{2}+1)c-\frac{\sqrt{1-2c}}{p_{K}}-\frac{\ell\tau}{K}\enspace.$
(40)

###### Proof.

We will use Eq. 5 to bound $\sqrt{a-c}$, specifically in our context the
inequality

$\sqrt{3-2\sqrt{2}-2\delta}\leq\sqrt{2}-1-(\sqrt{2}+1)\delta-\frac{1}{2}(\sqrt{2}+1)^{3}\delta^{2}\enspace.$
(41)

Consider some $\delta\geq 0.$ By substituting $c=\sqrt{2}-1+\delta$ into the
left hand side of Eq. 40 and applying Eq. 41 we obtain

$\displaystyle\sqrt{2}-(\sqrt{2}+1)c-\frac{\sqrt{1-2c}}{p_{K}}-\frac{\ell\tau}{K}$
$\displaystyle=\sqrt{2}-1-(\sqrt{2}+1)\delta-\frac{\sqrt{3-2\sqrt{2}-2\delta}}{p_{K}}-\frac{\ell\tau}{K}$
$\displaystyle\geq(\sqrt{2}-1-(\sqrt{2}+1)\delta)\left(1-\frac{1}{p_{K}}\right)+\frac{\delta^{2}(\sqrt{2}+1)^{3}}{2p_{K}}-\frac{\ell\tau}{K}$
$\displaystyle\geq-\left(\sqrt{2}-1-(\sqrt{2}+1)\delta\right)\frac{6\ell}{5K}+\frac{\delta^{2}(\sqrt{2}+1)^{3}}{2}-\frac{\ell\tau}{K}$
$\displaystyle\geq-\frac{6(\sqrt{2}-1)\ell}{5K}+\frac{\delta^{2}(\sqrt{2}+1)^{3}}{2}-\frac{\ell\tau}{K}.\enspace$

For the second to last inequality, we use the observation that
$\frac{1}{p_{K}}\leq 1+\frac{6\ell}{5K}$, which follows from the condition
$K\geq 6\ell$. The last expression will be positive for

$\delta>\sqrt{\frac{2\ell(\sqrt{2}-1)^{3}\left(\tau+\frac{6(\sqrt{2}-1)}{5}\right)}{K}}\enspace,$

giving the claim. ∎

Applying 39 with the value $\tau=150$, we see that Eq. 39 will hold for any

$\sqrt{2}-1+5\sqrt{\frac{\ell}{K}}<c\leq\frac{1}{2}\enspace.$

This finishes the proof of Lemma 35. ∎

Let us summarize the results of this section. Let $(A_{0},A_{0}^{T})$ be a
$\ell$-dense symmetric stingy quantum race and let $(A,A^{T})$ be the
corresponding quantum race, and suppose that $\frac{\ell}{K}\leq\frac{1}{6}$.
Theorem 34 shows that the payoff of any symmetric strategy $(y,y)$ in the game
$(A,A^{T})$ is at most $\sqrt{2}-1+5\sqrt{\ell/{K}}$. On the other hand,
letting $(x,x)$ be the unique coinciding equilibrium in the game
$(A_{0},A_{0})$, this strategy achieves payoff at least $\sqrt{2}-1-O(\ell/K)$
in the game $(A,A^{T})$ by Corollary 28. Thus $(x,x)$ is an approximate Nash
equilibrium for the game $(A,A^{T})$ and moreover is nearly optimal in terms
of payoff (within $O(\sqrt{\ell/K})$ amongst all symmetric strategies.

##  5 Multiplayer quantum races

###  5.1 Basic properties

For an integer $n\geq 2,$ an $n$-player game is specified by a set of pure
strategies $S_{i}$, and payoff functions $u_{i}:S\rightarrow\mathbb{R},$ for
each player $i\in[n]$, where by definition $S=S_{1}\times\cdots\times S_{n}$
is the set of pure strategy profiles. For $s\in S$, the value $u_{i}(s)$ is
the payoff of player $i$ for pure strategy profile $s$. Let
$S_{-i}=S_{1}\times\cdots\times S_{i-1}\times S_{i+1}\times\cdots\times S_{n}$
be the set of all pure strategy profiles of players other than $i$. For $s\in
S$ and $i\in[n]$, we set the partial pure strategy profile $s_{-i}\in S_{-i}$
to be $(s_{1},\ldots s_{i-1},s_{i+1},\ldots,s_{n})$. For $s^{\prime}$ in
$S_{-i}$, and $s_{i}\in S_{i}$, we denote by $(s^{\prime},s_{i})$ the combined
pure strategy profile
$(s^{\prime}_{1},\ldots,s^{\prime}_{i-1},s_{i},s^{\prime}_{i+1},\ldots,s^{\prime}_{n})\in
S$. We will suppose that each player has $m$ pure strategies and that
$S_{i}=\\{e_{1},\ldots,e_{m}\\}$, the canonical basis of the vector space
$\mathbb{R}^{m}$, for all $i\in[n]$, and therefore
$S=\\{e_{1},\ldots,e_{m}\\}^{n}$. For simplicity, instead of $e_{j}$ we often
say strategy $j$.

A mixed strategy for player $i$ is a probability distribution over $S_{i}$
that we identify with a vector $x_{i}=(x_{i}^{1},\ldots x_{i}^{m})$ such that
$x_{i}^{j}\geq 0,$ for all $j\in[m]$, and $\sum_{j\in[m]}x_{i}^{j}=1$. We
denote by $\Delta_{i}$ the set of mixed strategies for $i$, and we call
$\Delta=\Delta_{1}\times\cdots\times\Delta_{r}$ the set of mixed strategy
profiles. For a mixed strategy profile $x=(x_{1},\ldots,x_{n})$ and pure
strategy profile $s\in S$, the product $x^{s}=x_{1}^{s_{1}}x_{2}^{s_{2}}\cdots
x_{n}^{s_{n}}$ is the probability of $s$ in $x$. We will consider the
multilinear extension of the payoff functions from $S$ to $\Delta$ defined by
$u_{i}(x)=\sum_{s\in S}x^{s}u_{i}(s)$. The set $\Delta_{-i}$, the partial
mixed strategy profile $x_{-i}$, for $x\in\Delta$ and $i\in[n]$, and the
combined mixed strategy profile $(x^{\prime},x_{i})$ for
$x^{\prime}\in\Delta_{-i}$ and $x_{i}\in\Delta_{i}$ are defined analogously to
the pure case.

The pure strategy $s_{i}$ is a best response for player $i$ against the
partial mixed strategy profile $x^{\prime}\in\Delta_{-i}$ if it maximizes
$u_{i}(x^{\prime},\cdot).$ For $x\in\Delta$ and $i\in[n]$, we will denote by
$\mathrm{br}(x_{-i})$ the set of best responses of player $i$ against
$x_{-i}$. A Nash equilibrium is a mixed strategy profile
$x=(x_{1},\ldots,x_{n})$ such that $\sup(x_{i})\subseteq\mathrm{br}(x_{-i})$,
for all $i\in[n]$.

######  Definition 40 ($n$-party stingy quantum race).

Let $n\geq 2$ be a positive integer. An $n$-party stingy quantum race is
defined by a sequence of increasing probabilities
$0<P_{1}<P_{2}<\ldots<P_{K}\leq 1$, for some positive integer $K$. The set of
pure strategies of all players is $[K]$. For every $i$, the utility function
of the $i^{th}$ player is defined as

$u_{i}(s_{1},\ldots,s_{n})=P_{s_{i}}\prod_{k\neq i,s_{k}\leq
s_{i}}\bar{P}_{s_{k}}.$

Consider an $n$-party stingy quantum race given by the probabilities
$0<P_{1}<\ldots<P_{K}\leq 1$, and let $x_{-i}\in\Delta_{-i}$ for some
$i\in[n]$. If player $i$ plays the pure strategy $s$ against $x_{-i}$, her
payoff is

$u_{i}(x_{-i},s)=P_{s}\prod_{k\neq i}\left(\sum_{s_{k}\in\sup_{\leq
s}(x_{k})}x_{k}^{s_{k}}\bar{P}_{s_{k}}+\sum_{s_{k}\in\sup_{>s}(x_{k})}x_{k}^{s_{k}}\right).$
(42)

The following is the multiparty analog of 14.

######  Claim 41.

Let $x=(x_{1},\ldots x_{n})$ be a Nash equilibrium of an $n$-party stingy
quantum race defined by probabilities $P_{1}<\ldots<P_{K}$. If
$s_{1}\in\sup(x_{i})$, for some $i\in[n]$, then for all $s_{2}>s_{1}$ there
exists $k\neq i$ such that $\sup_{\leq s_{1}}(x_{k})\neq\sup_{\leq
s_{2}}(x_{k})$.

###### Proof.

If $\sup_{\leq s_{1}}(x_{k})=\sup_{\leq s_{2}}(x_{k})$, for all $k\neq i$ then

$u_{i}(x_{-i},s_{2})=\frac{P_{s_{2}}}{P_{s_{1}}}u_{i}(x_{-i},s_{1}).$

As $p_{s_{1}}<p_{s_{2}}$, the payoff for playing $s_{2}$ is strictly larger
than that for playing $s_{1}$. Therefore $s_{1}$ is not a best response for
$x_{-i}$, in contradiction with the definition of a Nash equilibrium. ∎

This claim implies the following properties for the supports of Nash
equilibria in a multiplayer stingy quantum race.

######  Corollary 42.

Let $x$ be a Nash equilibrium of an $n$-party stingy quantum race defined by
probabilities $0<P_{1}<P_{2}<\ldots<P_{K}\leq 1$. Then we have:

  * •

$\bigcup_{i=1}^{n}\sup(x_{i})$ is an interval containing $K$,

  * •

for every $i\in[n],$ for every $s_{1},s_{2}\in\sup(x_{i})$ there exists
$s\in\bigcup_{k\neq i}\sup(x_{k})$ with $s_{1}<s\leq s_{2}$.

Let $x$ be a Nash equilibrium of an $n$-party stingy quantum race. We say that
$x$ is coinciding if $\sup(x_{i})=\sup(x_{k})$, for all $i,k\in[n].$ We call
this common support in a coinciding Nash equilibrium the support of the
equilibrium. In the multiparty case we will only study coinciding Nash
equilibria.

###  5.2 Coinciding Nash equilibria of stingy multiplayer races

By Corollary 42 we know that in a coinciding Nash equilibrium of an $n$-party
stingy quantum race the support of the equilibrium is of the form
$\\{T,T+1,\ldots,K\\}$, for some $1\leq T\leq K$. We would like to
characterize these coinciding equilibria.

######  Lemma 43.

Let $x=(x_{1},\ldots,x_{n})$, where $x_{i}$ is a $K$-dimensional real vector
for every $i\in[n]$, and let $1\leq T\leq K$. Then $x$ is a Nash equilibrium
of support $\\{T,T+1,\ldots,K\\}$ in an $n$-party stingy quantum race defined
by $0<P_{1}<\ldots<P_{K}\leq 1$ if and only $x$ satisfies the following
system, for all $i\in[n]$:

$\displaystyle u_{i}(x_{-i},t)$ $\displaystyle=u_{i}(x_{-i},T)~{}$
$\displaystyle\text{for}~{}~{}T<t\leq K~{},$ (43) $\displaystyle
u_{i}(x_{-i},T-1)$ $\displaystyle\leq u_{i}(x_{-i},T)~{},$ (44) $\displaystyle
x_{i}^{t}$ $\displaystyle=0$ $\displaystyle\text{for}~{}~{}0<t<T~{},$ (45)
$\displaystyle x_{i}^{t}$ $\displaystyle>0$
$\displaystyle\text{for}~{}~{}T\leq t\leq K~{},$ (46)
$\displaystyle\sum_{t=T}^{K}x_{i}^{t}$ $\displaystyle=1~{}.$ (47)

###### Proof.

For every $i\in[n]$, Eq. 45–(47) express that $x_{i}$ is a probability
distribution of support $\\{T,T+1,\ldots,K\\}$. For $T\geq 2$, when playing a
strategy $t<T$ against the partial mixed strategy profile $x_{-i}$, the $i$th
player’s payoff is maximized if she plays $T-1$. Therefore Eq. 43 and (44)
express that the strategies in her support are all best responses against
$x_{-i}$. ∎

######  Definition 44.

For an $n$-party stingy quantum race defined by $0<P_{1}<\ldots<P_{K}\leq 1$
we define its reduced game as the 2-party stingy quantum race defined by the
two sequences of probabilities $p_{1}<\ldots<p_{K}$, and $P_{1}<\ldots<P_{K}$
where $p_{j}=P_{j}^{1/(n-1)}$, for $1\leq j\leq K$.

We denote by $A$ the payoff matrix of the first player in the reduced game

######  Lemma 45.

Let an $n$-party stingy quantum race be defined by $0<P_{1}<\ldots<P_{K}\leq
1$, let $x=(x_{1},\ldots,x_{n})$, where $x_{i}$ is a $K$-dimensional vector,
and let $1\leq T\leq K$. Then Eq. 43–(47) are satisfied by $x$, for every
$i\in[n]$ if and only if Eq. 6–(10) for the reduced game are satisfied by
$x_{i}$, for every $i\in[n]$.

###### Proof.

First we do the “if” direction. By Lemma 19, there is a unique solution to Eq.
6, (8) and (10), thus if these are satisfied by each $x_{i}$ then we must have
$x_{1}=\cdots=x_{n}$. Let $y$ be this common vector. Then for every
$t\in[T-1,K]$,

$\displaystyle u_{i}(x_{-i},t)$ $\displaystyle=P_{t}\prod_{k\neq
i}\left(\sum_{s_{k}\in\sup_{\leq
t}(x_{k})}x_{k}^{s_{k}}\bar{P}_{s_{k}}+\sum_{s_{k}\in\sup_{>t}(x_{k})}x_{k}^{s_{k}}\right)$
$\displaystyle=P_{t}\left(\frac{e_{t}^{\mathrm{T}}Ay}{p_{t}}\right)^{n-1}$
$\displaystyle=\left(e_{t}^{\mathrm{T}}Ay\right)^{n-1}\enspace.$

We now prove the “only if” direction. Let us suppose that $x$ satisfies Eq.
43–(47). Eq. 8–(10) are respectively identical to Eq. 45–(47), and therefore
are satisfied. Let us consider Eq. 6. We fix some $T<t\leq K$. From Eq. 42 we
have, for every $i\in[n]$,

$u_{i}(x_{-i},t)=P_{t}\prod_{k\neq i}\left(\sum_{j\leq
t}x_{k}^{j}\bar{P}_{j}+\sum_{j>t}x_{k}^{j}\right),$ (48)

and

$u_{i}(x_{-i},T)=P_{T}\prod_{k\neq
i}\left(x_{k}^{T}\bar{P}_{T}+\sum_{j>T}x_{k}^{j}\right).$ (49)

Therefore

$\displaystyle\left(e_{t}^{\mathrm{T}}Ax_{i}\right)^{n-1}$
$\displaystyle=p_{t}^{n-1}\left(\sum_{j\leq
t}x_{i}^{j}\bar{P}_{j}+\sum_{j>t}x_{i}^{j}\right)^{n-1}$
$\displaystyle=\frac{p_{t}^{n-1}P_{t}^{n-1}}{P_{t}^{n}}\frac{1}{u_{i}(x_{-i},t)^{n-1}}\prod_{\ell=1}^{n}u_{\ell}(x_{-\ell},t)$
$\displaystyle=\frac{1}{u_{i}(x_{-i},t)^{n-1}}\prod_{\ell=1}^{n}u_{\ell}(x_{-\ell},t)$
$\displaystyle=\frac{1}{u_{i}(x_{-i},T)^{n-1}}\prod_{\ell=1}^{n}u_{\ell}(x_{-\ell},T)$
$\displaystyle=\left(e_{T}^{\mathrm{T}}Ax_{i}\right)^{n-1}\enspace.$

The second equality follows from the fact that

$\prod_{\ell=1}^{n}u_{\ell}(x_{-\ell},t)=P_{t}^{n}\prod_{k=1}^{n}\left(\sum_{j\leq
t}x_{k}^{j}\bar{P}_{j}+\sum_{j>t}x_{k}^{j}\right)^{n-1},$

for the third equality we used $p_{t-1}^{n-1}=P_{t-1}$, and for the fourth
equality we used Eq. 43. As
$e_{t}^{\mathrm{T}}Ax_{i},e_{T}^{\mathrm{T}}Ax_{i}$ are real and nonnegative,
it follows that $e_{t}^{\mathrm{T}}Ax_{i}=e_{T}^{\mathrm{T}}Ax_{i}$ for all
$T<t\leq K$, establishing that Eq. 6 holds.

Now we turn to Eq. 7. Since for every $i\in[n]$, Eq. 6, (8) and (10) are
satisfied by $x_{i}$, from Lemma 19 we know that $x_{1}=\dots=x_{n}$. Thus for
every $i\in[n]$, we have

$\displaystyle\left(e_{T-1}^{\mathrm{T}}Ax_{i}\right)^{n-1}$
$\displaystyle=p_{T-1}^{n-1}\prod_{k\neq
i}\left(\sum_{j=T}^{K}x_{k}^{j}\right)$ $\displaystyle=u_{i}(x_{-i},T-1)$
$\displaystyle\leq u_{i}(x_{-i},T)$ $\displaystyle=P_{T}\prod_{k\neq
i}\left(x_{k}^{T}\bar{P}_{T}+\sum_{j>T}x_{k}^{j}\right)$
$\displaystyle=\left(e_{T}^{\mathrm{T}}Ax_{i}\right)^{n-1}\enspace,$

where for the first equality we used $x_{1}=\dots=x_{n}$, for the second
equality we used $p_{t-1}^{n-1}=P_{T-1}$, and for the inequality we used Eq.
44. The statement of the Lemma therefore follows. ∎

######  Theorem 46.

An $n$-party stingy quantum race always has a unique coinciding Nash
equilibrium $x=(x_{1},\ldots,x_{n})$, where $x_{1}=\cdots=x_{n}$. If the game
is defined by the probabilities $0<P_{1}<P_{2}<\cdots<P_{K}$ then the
coinciding equilibrium has support $\\{T^{*},T^{*}+1,\ldots,K\\}$, where
$T^{*}=T_{B}^{*}$ of the reduced game, and for all $i\in[n]$, the distribution
$x_{i}$ is defined on its support as

$x_{i}^{t}=\begin{cases}{r_{T^{*}}^{B}}/{z_{T^{*}}^{B}}&\text{if}~{}~{}~{}t=T^{*},\\\
{q_{t}^{B}}/{z_{T^{*}}^{B}}&\text{if}~{}~{}~{}T^{*}<t\leq K.\end{cases}$

###### Proof.

Combining Lemma 43 and Lemma 45, we get that $x$ is a coinciding Nash
equilibrium of support $\\{T,T+1,\ldots,K\\}$ if and only if $x_{i}$ satisfies
Eq. 6–(10) for the reduced game, for all $i\in[n]$. By Lemma 21 this happens
if and only if $T=T^{*}_{B}$ of the reduced game, and the unique solution for
$x_{i}$, for $i\in[n]$, is the one stated by the Theorem. ∎

###  5.3 Collision probability of the stingy coinciding equilibrium

Our main objective in this section is to upper bound the collision
probability—the probability that two or more players succeed at the same
time—in the coinciding equilibrium found in the last section for an
$\ell$-dense stingy $n$-player quantum race. To help with this, we make the
following definition.

######  Definition 47.

For a joint probability distribution $y=(y_{1},\ldots,y_{n})\in\Delta$, let
$\mathrm{cp}_{i}^{m}(y)$ denote the probability that player $i$ succeeds first
and that exactly $m$ players (including $i$) succeed at the same time under
the joint strategy $y$. Let
$\mathrm{cp}_{i}(y)=\sum_{m=2}^{n}\mathrm{cp}_{i}^{m}(y)$ denote the
probability that player $i$ succeeds first and at least one other player
succeeds at the same time.

Let us also set up notation to describe the coinciding equilibrium in a stingy
multiplayer race. Define

$\displaystyle q_{i}$
$\displaystyle=\frac{1}{P_{i}}\left(\frac{1}{P_{i-1}^{1/(n-1)}}-\frac{1}{P_{i}^{1/(n-1)}}\right)$
$\displaystyle r_{T}$
$\displaystyle=\frac{1}{\bar{P}_{T}}\left(\frac{1}{P_{K}^{1/(n-1)}}-\sum_{i=T+1}^{K}\bar{P}_{i}q_{i}\right)$
$\displaystyle z_{T}$ $\displaystyle=r_{T}+\sum_{i=T+1}^{K}q_{i}\enspace.$

Let $T^{*}$ be the starting point of the support of the coinciding
equilibrium. Then by Theorem 46, the strategy of player $i$ in the coinciding
equilibrium is given by

$x_{i}^{t}=\begin{cases}{r_{T^{*}}}/{z_{T^{*}}}&\text{if}~{}~{}~{}t=T^{*},\\\
{q_{t}}/{z_{T^{*}}}&\text{if}~{}~{}~{}T^{*}<t\leq K,\\\
0&\text{if}~{}~{}~{}t<T^{*}\enspace.\end{cases}$ (50)

To obtain concrete bounds on the collision probability, we will need bounds on
$z_{T^{*}}$ and $P_{T^{*}-1}$.

######  Lemma 48.

In any stingy multiplayer quantum race with $n$ players
$(1/z_{T^{*}})^{n-1}<1/n$.

###### Proof.

The probability that any given player wins the race is $(1/z_{T}^{*})^{n-1}$.
As in a stingy race no two players can win at the same time, the probability
that the race has a winner is exactly $n/z_{T^{*}}^{n-1}$. The probability
that no one wins the race, which occurs if two or more players succeed at the
same time, or if no one succeeds, is positive, thus $(1/z_{T^{*}})^{n-1}<1/n$.
∎

######  Theorem 49.

Let $P_{1},\ldots,P_{K}$ define a stingy $n$-player quantum race with $n\geq
2$. Then $P_{T^{*}-1}<\frac{1}{n}$. If in addition $P_{1},....,P_{K}$ form an
$\ell$-dense sequence and $4\mathrm{e}\ell n\leq K$ then
$P_{T^{*}-1}\geq\tfrac{1}{2\mathrm{e}n}$, where $\mathrm{e}$ is Euler’s
number.

###### Proof.

As $T^{*}-1$ is not in the support of the coinciding Nash equilibrium, it must
be the case that
$P_{T^{*}-1}\leq\left(\frac{1}{z_{T^{*}}}\right)^{n-1}<\frac{1}{n}$, by Lemma
48.

Now we turn to the lower bound. If $P_{T^{*}+1}>\tfrac{1}{n}$ then as
$P_{1},\ldots,P_{K}$ is $\ell$-dense we must have
$P_{T^{*}-1}\geq\tfrac{1}{n}-\tfrac{2\ell}{K}\geq\tfrac{1}{2\mathrm{e}n}$ and
the proof is done. Otherwise, define
$S=\max_{i>T^{*}}\\{i:P_{i}\leq\tfrac{1}{n}\\}$. Note that by definition and
$\ell$-density we have $\frac{1}{n}\geq p_{S}\geq\frac{1}{n}-\frac{\ell}{K}$.
Now we know from the positivity condition of $r_{T*}$ that

$\displaystyle 1$ $\displaystyle>\sum_{T^{*}+1}^{K}\bar{P}_{i}q_{i}$
$\displaystyle\geq\sum_{T^{*}+1}^{S}\frac{1-P_{i}}{P_{i}}\left(P_{i-1}^{-\frac{1}{n-1}}-P_{i}^{-\frac{1}{n-1}}\right)$
$\displaystyle\geq\frac{1-P_{S}}{P_{S}}\left(P_{T^{*}}^{-\frac{1}{n-1}}-P_{S}^{-\frac{1}{n-1}}\right)$
$\displaystyle\geq(n-1)\left(P_{T^{*}}^{-\frac{1}{n-1}}-\left(\frac{Kn}{K-\ell
n}\right)^{\frac{1}{n-1}}\right)$
$\displaystyle\geq(n-1)\left(P_{T^{*}}^{-\frac{1}{n-1}}-\left(\frac{4\mathrm{e}n}{4\mathrm{e}-1}\right)^{\frac{1}{n-1}}\right)\enspace.$

For the last inequality we have used that $\ell n\leq\frac{K}{4\mathrm{e}}$.
Rearranging the last inequality we have

$P_{T*}\geq\left(\frac{n-1}{1+(n-1)\left(1+\frac{4\mathrm{e}n}{4\mathrm{e}-1}\right)^{\frac{1}{n-1}}}\right)^{n-1}\enspace.$

This means

$\displaystyle\ln(P_{T}^{*})$
$\displaystyle\geq(n-1)\left(\ln(n-1)-\ln\left(1+(n-1)\left(\frac{4\mathrm{e}n}{4\mathrm{e}-1}\right)^{1/(n-1)}\right)\right)$
$\displaystyle=-\ln\left(\frac{4\mathrm{e}n}{4\mathrm{e}-1}\right)-(n-1)\ln\left(1+(n-1)^{-1}\left(\frac{4\mathrm{e}n}{4\mathrm{e}-1}\right)^{-1/(n-1)}\right)\enspace.$

It now remains to upper bound

$(n-1)\ln\left(1+(n-1)^{-1}\left(\frac{4\mathrm{e}n}{4\mathrm{e}-1}\right)^{-1/(n-1)}\right)\leq\left(\frac{4\mathrm{e}n}{4\mathrm{e}-1}\right)^{-1/(n-1)}\leq
1\enspace,$

for $n\geq 2$, where we have used $\ln(1+x)\leq x$ to obtain the first
inequality. Putting it together we have
$\ln(P_{T^{*}})\geq-\ln(\frac{4en}{4\mathrm{e}-1})-1$, which implies
$P_{T^{*}-1}\geq P_{T^{*}}-\frac{\ell}{K}\geq\frac{1}{2\mathrm{e}n}$. ∎

The next lemma bounds the collision probability for player $i$ when all
players but player $i$ play according to the coinciding equilibrium, and
player $i$ plays an arbitrary strategy $v$. We will use this lemma to bound
the total collision probability and also in Section 5.4 to show that the
stingy coinciding equilibrium is an approximate equilibrium in a multiparty
race.

######  Lemma 50.

Let $P_{1},....,P_{K}$ define an $\ell$-dense stingy $n$-player quantum race,
$n\geq 2$, with $4\mathrm{e}n\ell\leq K$, and let $x$ be the unique coinciding
equilibrium given by Eq. 50. Then
$\mathrm{cp}_{i}(x_{-i},v)\leq\frac{8\mathrm{e}\ell}{K}$ for any $i\in[n]$ and
$v\in\Delta_{i}$.

###### Proof.

We use the notation from the definition of the coinciding equilibrium in Eq.
50. Note that since $p_{T^{*}}\geq\frac{1}{2\mathrm{e}n}$ by Lemma 50, and we
assume that $\frac{\ell}{K}\leq\frac{1}{4\mathrm{e}n}$, it must be the case
that $T^{*}\geq 2$, and therefore it makes sense to talk about $T^{*}-1$.
Further, note that $z_{T^{*}}\geq 1$ by Lemma 48.

We upper bound $\mathrm{cp}_{i}(x_{-i},v)$ by multiplying the probability that
player $i$ and player $j$ succeed at the same time (not necessarily first) by
$n-1$.

$\displaystyle\mathrm{cp}_{i}(x_{-i},v)$
$\displaystyle\leq\frac{n-1}{z_{T}^{*}}\left(P_{T^{*}}^{2}v_{T^{*}}r_{T^{*}}+\sum_{t=T^{*}+1}^{K}P_{t}^{2}v_{t}q_{t}\right)$
$\displaystyle\leq\frac{n-1}{z_{T}^{*}}\sum_{t=T^{*}}^{K}P_{t}^{2}v_{t}q_{t}$
$\displaystyle=\frac{n-1}{z_{T}^{*}}\sum_{t=T^{*}}^{K}P_{t}v_{t}\left(\frac{1}{P_{t-1}^{\frac{1}{n-1}}}-\frac{1}{P_{t}^{\frac{1}{n-1}}}\right)$
$\displaystyle=\frac{n-1}{z_{T}^{*}}\sum_{t=T^{*}}^{K}P_{t}v_{t}\frac{P_{t}^{\frac{1}{n-1}}-P_{t-1}^{\frac{1}{n-1}}}{(P_{t-1}P_{t})^{\frac{1}{n-1}}}$

For notational convenience, let $f(x)=x^{\frac{1}{n-1}}$. By the concavity of
$f$ on $[0,\infty)$ we can upper bound $f(P_{t})-f(P_{t-1})$ by

$f(P_{i})-f(P_{i-1})\leq(P_{i}-P_{i-1})f^{\prime}(P_{i-1})\leq\frac{\ell
P_{i-1}^{\frac{2-n}{n-1}}}{K(n-1)}\enspace.$ (51)

Using this upper bound, we can continue:

$\displaystyle\mathrm{cp}_{i}(x_{-i},v)$
$\displaystyle\leq\frac{\ell}{Kz_{T^{*}}}\sum_{t=T^{*}}^{K}P_{t}v_{t}\frac{P_{t-1}^{\frac{2-n}{n-1}}}{(P_{t-1}P_{t})^{\frac{1}{n-1}}}$
$\displaystyle=\frac{\ell}{Kz_{T^{*}}}\sum_{t=T^{*}}^{K}v_{t}\frac{1}{P_{t-1}^{\frac{1}{n-1}}}\left(\frac{P_{t}}{P_{t-1}}\right)^{\frac{n-2}{n-1}}$
$\displaystyle\leq\frac{4\mathrm{e}\ell}{Kz_{T^{*}}}\sum_{t=T^{*}}^{K}v_{t}\left(\frac{P_{t}}{P_{t-1}}\right)^{\frac{n-2}{n-1}}\enspace,$

as $(2\mathrm{e}n)^{1/(n-1)}\leq 4\mathrm{e}$ for all $n\geq 2$. Continuing,
we have

$\displaystyle\mathrm{cp}_{i}(x_{-i},v)$
$\displaystyle\leq\frac{4\mathrm{e}\ell}{Kz_{T^{*}}}\sum_{t=T^{*}}^{K}v_{t}\left(1+\frac{\ell}{KP_{t-1}}\right)^{\frac{n-2}{n-1}}$
$\displaystyle\leq\frac{4\mathrm{e}\ell}{Kz_{T^{*}}}\left(1+\frac{2\mathrm{e}n\ell}{K}\right)^{\frac{n-2}{n-1}}$
$\displaystyle\leq\frac{8\mathrm{e}\ell}{K}\enspace.$

∎

See 8

###### Proof.

The probability that two or more players succeed at the same time is at most

$\sum_{i=1}^{n}\mathrm{cp}_{i}(x)\leq\frac{8\mathrm{e}n\ell}{K}\enspace,$

by Lemma 50. ∎

###  5.4 Multiplayer quantum races

In this section we use our results about the stingy multiplayer quantum race
to analyse the multiplayer quantum race. Namely, we show that the coinciding
equilibrium in a stingy multiplayer quantum race is an approximate equilibrium
in a multiplayer race. The difference between a stingy multiplayer race and a
multiplayer race is that in a multiplayer race, the payoff is equally divided
amongst all players who succeed first at the same time.

######  Definition 51 (Multiplayer quantum race).

Let $u_{i}$ be the payoff function for player $i\in[n]$ in the $n$-player
stingy race defined by $P_{1}<\cdots<P_{k}$, as given by Eq. 42. The payoff
function $u_{i}^{\prime}$ in the $n$-player quantum race defined by
$P_{1},\ldots,P_{k}$ is

$u_{i}^{\prime}(x)=u_{i}(x)+\sum_{m=2}^{n}\frac{\mathrm{cp}_{i}^{m}(x)}{m}\enspace.$

While the tie-splitting payoff in Definition 51 is quite natural, one could
imagine other definitions in-between stingy multiplayer races and the
definition of multiplayer races we have given. Our results in this section
depend very weakly on the exact definition of how ties are split in a
multiplayer race. In fact, the only property we use is

$u_{i}^{\prime}(x)\leq u_{i}(x)+\mathrm{cp}_{i}(x)\enspace.$ (52)

This property holds under any reasonable definition of tie-splitting.

Now we show Theorem 9 from the introduction that the coinciding Nash
equilibrium in a multiplayer stingy quantum race is an approximate Nash
equilibrium in a multiplayer quantum race.

See 9

###### Proof.

Since $x$ is a Nash equilibrium in the stingy race, for any $i\in[n]$ and
probability vector $v\in\Delta_{i}$ we have

$u_{i}(x)\geq u_{i}(x_{-i},v)\enspace.$ (53)

By Definition 51 and Eq. 52 we have

$\displaystyle u_{i}^{\prime}(x)\geq u_{i}(x)$ $\displaystyle\geq
u_{i}^{\prime}(x_{-i},v)-\mathrm{cp}_{i}(x_{-i},v)$ $\displaystyle\geq
u_{i}^{\prime}(x_{-i},v)-\frac{8\mathrm{e}\ell}{K}\enspace,$

by Lemma 50. ∎

##  6 Conclusion

We conclude with some open problems.

  * •

Can we characterize all Nash equilibria in the multiparty stingy quantum race?
We have given a coinciding Nash equilibrium and shown that it is unique,
however, it would be interesting to classify the Nash equilibria where players
play strategies with different supports.

  * •

Can we show that the approximate Nash equilibrium we have given for a
multiparty quantum race is nearly optimal in terms of payoff among all
symmetric Nash equilibria? We were able to do this in the two-party case,
however, this proof used tools like quadratic programming that are not
available in the multiparty case.

  * •

Our model of quantum races assumes that if a player measures and is
unsuccessful then she simply stops playing. A more realistic scenario is that,
if a player measures and fails, she immediately restarts and tries again. Do
the Nash equilibria in this version of the game change substantially? The
large number of available strategies in this version of the game make it much
more difficult to analyze.

## Acknowledgments

We would like to thank Gavin Brennen, Hartmut Klauck, and Marco Tomamichel for
very useful discussions about game theory and quantum Bitcoin mining. We would
also like to thank Or Sattath for sharing an early version of his work [Sat18]
and discussions about its implications.

Part of this work was done while Troy Lee was at the School of Physical and
Mathematical Sciences, Nanyang Technological University and the Centre for
Quantum Technologies, Singapore. Troy Lee and Maharshi Ray were supported in
part by the Singapore National Research Fellowship under NRF RF Award No. NRF-
NRFF2013-13. This research was further partially funded by the Singapore
Ministry of Education and the National Research Foundation under grant
R-710-000-012-135, and in part by the QuantERA ERA-NET Cofund project
QuantAlgo.

## References

  * [ABL+17] Divesh Aggarwal, Gavin Brennen, Troy Lee, Miklos Santha, and Marco Tomamichel.  Quantum attacks on Bitcoin and how to prevent against them.  Technical Report arXiv:1710.10377, arXiv, 2017.
  * [Bac02] Adam Back.  Hashcash—a denial of service counter-measure, 2002.  Available at: http://www.hashcash.org/papers/hashcash.pdf.
  * [Bit18] Bitmain.  Bitmain Antminer S9.  https://shop.bitmain.com/antminer_s9_asic_bitcoin_miner.html, 2018\.  Accessed 2018-02-16.
  * [BK17] Alex Biryukov and Dmitry Khovratovich.  Equihash: Asymmetric proof-of-work based on the generalized birthday problem.  Ledger, 2:1–30, 2017.
  * [But13] Vitalik Buterin.  Bitcoin is not quantum safe, and how we can fix it when needed.  https://bitcoinmagazine.com/articles/bitcoin-is-not-quantum-safe-and-how-we-can-fix-1375242150/, 2013\.
  * [CL99] Miguel Castro and Barbara Liskov.  Practical byzantine fault tolerance.  In Third Symposium on Operating Systems Design and Implementation, 1999.
  * [DH08] Catalin Dohotaru and Peter Høyer.  Exact quantum lower bound for grover’s problem.  Technical Report arXiv:0810.3647, arXiv, 2008.
  * [Dor60] William S. Dorn.  Duality in quadratic programming.  Quarterly of applied mathematics, 18(2):155–162, 1960.
  * [EGS14] Ittay Eyal and Emin Gün Sirer.  Majority is not enough: Bitcoin mining is vulnerable.  In 18th International Conference on Financial Cryptography and Data Security, 2014.
  * [GKW+16] Arthur Gervais, Ghassan Karame, Karl Wüst, Vasileios Glykantzis, Hubert Ritzdorf, and Srdjan Capkun.  On the security and performance of proof of work blockchains.  In Proceedings of the 2016 ACM SIGSAC Conference on Compute and Communications Security (CCS’16), pages 3–16, 2016.
  * [Gro96] Lov K. Grover.  A fast quantum mechanical algorithm for database search.  In Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, STOC ’96, pages 212–219, New York, NY, USA, 1996. ACM.
  * [IKL+11] Nicole Immorlica, Adam Tauman Kalai, Brendan Lucier, Ankur Moitra, Andrew Postlewaite, and Moshe Tennenholtz.  Dueling algorithms.  In Proceedings of the forty-third annual ACM symposium on theory of computing (STOC’11), pages 215–224, 2011.
  * [KRDO17] Aggelos Kiayias, Alexander Russell, Bernardo David, and Roman Oliynykov.  Ouroboros: A provably secure proof-of-stake blockchain protocol.  In CRYPTO, pages 357–388, 2017.
  * [MS64] Olvi L. Mangasarian and H. Stone.  Two-person nonzero-sum games and quadratic programming.  Journal of mathematical analysis and applications, 9:348–355, 1964\.
  * [Nak09] Satoshi Nakamoto.  Bitcoin: A peer-to-peer electronic cash system, 2009.  Available at: http://www.bitcoin.org/pdf.
  * [Nas51] John F. Nash.  Non-cooperative games.  Annals of Mathematics, 54(2):286–295, 1951.
  * [Sat18] Or Sattath.  On the insecurity of quantum Bitcoin mining.  Technical Report arXiv:1804.08118, arXiv, 2018.  Appeared in QCRYPT 2018.

##  Appendix A Symmetric 2-player stingy quantum races

In this appendix we finish the characterization of all Nash equilibria in a
symmetric 2-player stingy quantum race. We have seen in Corollary 16 that a
Nash equilibrium in a symmetric stingy quantum race is either coinciding,
alternating, or alternating-coinciding, and in Theorem 22 we have given the
unique coinciding equilibrium. In this section, we characterize when
alternating and alternating-coinciding equilibria exist. We begin by looking
at alternating equilibria.

For the rest of this section, fix a stingy symmetric quantum race defined by
probabilities $0<p_{1}<p_{2}<\ldots<p_{K}\leq 1$, for some integer $K>0$.

###  A.1 Alternating equilibrium

####  A.1.1 At most one equilibrium

We first consider the case of when an alternating equilibrium can exist. To do
this, it will be handy to introduce some notation. For natural numbers $T<K$,
we let $[T,K]=\\{T,T+1,T+2,\ldots K\\}$, and further let
$D(T,K)=\\{T,T+2,T+4,\ldots,K\\}$ in the case $T,K$ have the same parity and
$D(T,K)=\\{T,T+2,T+4,\ldots,K-1\\}$ in case $T,K$ have opposite parity. We may
assume, up to renaming of the players, that Alice plays at the smallest time.
Thus by Corollary 16 we know that in an alternating equilibrium Alice’s
support is $D(T,K)=\\{T,T+2,T+4,\ldots,K-1\\}$ and that Bob’s support is
$D(T+1,K)=\\{T+1,T+3,\ldots,K\\}$, for some number $1\leq T\leq K$, such that
$K-T$ is odd.

We define the values $\tilde{q}_{T}$, for $T=2,\ldots,K-1$, and the values
$\tilde{r}_{T},\tilde{R}_{T},\tilde{z}_{T}$ and $\tilde{Z}_{T}$, such that
$1\leq T<K$ and $K-T$ is odd, as follows:

$\displaystyle\tilde{q}_{T}$
$\displaystyle=\frac{1}{p_{T}}\cdot\left(\frac{1}{p_{T-1}}-\frac{1}{p_{T+1}}\right),$
$\displaystyle\tilde{r}_{T}$
$\displaystyle=\frac{1}{\bar{p}_{T}}\cdot\left(\frac{1}{p_{K}}-\sum_{i\in
D(T+2,K)}\bar{p}_{i}\tilde{q}_{i}\right),$ $\displaystyle\tilde{R}_{T}$
$\displaystyle=\frac{1}{p_{K-1}}-\sum_{i\in
D(T+1,K-2)}\bar{p}_{i}\tilde{q}_{i},$ $\displaystyle\tilde{z}_{T}$
$\displaystyle=\tilde{r}_{T}+\sum_{i\in D(T+2,K)}\tilde{q}_{i},$
$\displaystyle\tilde{Z}_{T}$ $\displaystyle=\tilde{R}_{T}+\sum_{j\in
D(T+1,K-2)}\tilde{q}_{j}.$

######  Definition 52.

Define $\tilde{T}^{*}$ as the smallest integer $1\leq T<K$ such that
$\tilde{r}_{T}>0$ and $K-T$ is odd.

This is a valid definition since $\tilde{r}_{K-1}=1/(\bar{p}_{K-1}p_{K})>0$.
The following theorem states that there is at most one alternating Nash
equilibrium in a symmetric stingy quantum race.

######  Theorem 53.

Every $2$-party symmetric stingy quantum race has exactly one alternating Nash
equilibrium if $\tilde{R}_{\tilde{T}^{*}}>0$ and
$p_{K}\left(\tfrac{1}{p_{K-1}}-p_{K}R_{\tilde{T}^{*}}\right)\leq 1,$ and no
alternating Nash equilibrium otherwise. The supports of the equilibrium
$(x,y)$ are $\sup(x)=D(\tilde{T}^{*},K)$ and $\sup(y)=D(\tilde{T}^{*}+1,K)$,
and the distributions are defined as:

$\displaystyle x_{i}$
$\displaystyle=\begin{cases}{\tilde{r}_{\tilde{T}^{*}}}/{\tilde{z}_{\tilde{T}^{*}}}&\text{if}~{}~{}~{}i=\tilde{T}^{*},\\\
{\tilde{q}_{i}}/{\tilde{z}_{\tilde{T}^{*}}}&\text{if}~{}~{}~{}i\in
D(T+2,K),\end{cases}$ $\displaystyle y_{j}$
$\displaystyle=\begin{cases}{\tilde{R}_{\tilde{T}^{*}}}/{\tilde{Z}_{\tilde{T}^{*}}}&\text{if}~{}~{}~{}j=K,\\\
{\tilde{q}_{j}}/{\tilde{Z}_{\tilde{T}^{*}}}&\text{if}~{}~{}~{}j\in
D(T+1,K-2).\end{cases}$

###### Proof.

As in the proof of Lemma 19, instead of probability distributions we will
normalize the strategies such that the payoff is 1. We claim that the
conditions of Nash equilibrium for such a distribution can be expressed by the
following system:

$\displaystyle e_{i}^{\mathrm{T}}Ay$ $\displaystyle=1$
$\displaystyle\text{for}~{}~{}i\in D(T,K)~{},$ (54) $\displaystyle
e_{i}^{\mathrm{T}}Ay$ $\displaystyle\leq 1$
$\displaystyle\text{for}~{}~{}1\leq i\leq K~{},$ (55) $\displaystyle
e_{j}^{\mathrm{T}}Ax$ $\displaystyle=1$ $\displaystyle\text{for}~{}~{}j\in
D(T+1,K)~{},$ (56) $\displaystyle e_{j}^{\mathrm{T}}Ax$ $\displaystyle\leq 1$
$\displaystyle\text{for}~{}~{}1\leq j\leq K~{},$ (57) $\displaystyle 0<$
$\displaystyle~{}~{}x_{i}$ $\displaystyle\text{for}~{}~{}i\in D(T,K)~{},$ (58)
$\displaystyle 0<$ $\displaystyle~{}~{}y_{j}$
$\displaystyle\text{for}~{}~{}j\in D(T+1,K)~{}.$ (59) $\displaystyle x_{i}$
$\displaystyle=0$ $\displaystyle\text{ for }i\in[T-1]\cup D(T+1,K)$ (60)
$\displaystyle y_{j}$ $\displaystyle=0$ $\displaystyle\text{ for
}j\in[T-1]\cup D(T,K).\enspace$ (61)

In matrix form Eq. 54 can be expressed as:

$\begin{bmatrix}1&1&1&\cdots&1\\\ \bar{p}_{T+1}&1&1&\cdots&1\\\
\bar{p}_{T+1}&\bar{p}_{T+3}&1&\cdots&1\\\
\bar{p}_{T+1}&\bar{p}_{T+3}&\bar{p}_{T+5}&\cdots&1\\\
\vdots&&&\ddots&\vdots\\\
\bar{p}_{T+1}&\bar{p}_{T+3}&\bar{p}_{T+5}&\cdots&1\\\
\end{bmatrix}\begin{bmatrix}y_{T+1}\\\ y_{T+3}\\\ y_{T+5}\\\ \vdots\\\
y_{K}\end{bmatrix}=\begin{bmatrix}1/p_{T}\\\ 1/p_{T+2}\\\ 1/p_{T+4}\\\
1/p_{T+6}\\\ \vdots\\\ 1/p_{K-1}\end{bmatrix}.$ (62)

Simplifying the system gives

$\begin{bmatrix}p_{T+1}&0&0&\cdots&0\\\ 0&p_{T+3}&0&\cdots&0\\\
0&0&p_{T+5}&\cdots&0\\\ 0&0&0&\cdots&0\\\ \vdots&&&\ddots&\vdots\\\
\bar{p}_{T+1}&\bar{p}_{T+3}&\bar{p}_{T+5}&\cdots&1\\\
\end{bmatrix}\begin{bmatrix}y_{T+1}\\\ y_{T+3}\\\ y_{T+5}\\\ \vdots\\\
y_{K}\end{bmatrix}=\begin{bmatrix}1/p_{T}-1/p_{T+2}\\\ 1/p_{T+2}-1/p_{T+4}\\\
1/p_{T+4}-1/p_{T+6}\\\ 1/p_{T+6}-1/p_{T+8}\\\ \vdots\\\
1/p_{K-1}\end{bmatrix}.$

The unique solution is

$\displaystyle y_{j}$ $\displaystyle=\tilde{q}_{j},\qquad\mbox{for }j\in
D(T+1,K-2),$ $\displaystyle y_{K}$ $\displaystyle=\tilde{R}_{T}\enspace.$

Eq. 56 in matrix form gives a very similar system:

$\begin{bmatrix}\bar{p}_{T}&1&1&\cdots&1\\\
\bar{p}_{T}&\bar{p}_{T+2}&1&\cdots&1\\\
\bar{p}_{T}&\bar{p}_{T+2}&\bar{p}_{T+4}&\cdots&1\\\ \vdots&&&\ddots&\vdots\\\
\bar{p}_{T}&\bar{p}_{T+2}&\bar{p}_{T+4}&\cdots&\bar{p}_{K-1}\\\
\end{bmatrix}\begin{bmatrix}x_{T}\\\ x_{T+2}\\\ x_{T+4}\\\ \vdots\\\
x_{K-1}\end{bmatrix}=\begin{bmatrix}1/p_{T+1}\\\ 1/p_{T+3}\\\ 1/p_{T+5}\\\
\vdots\\\ 1/p_{K}\end{bmatrix}.$ (63)

Similarly simplifying this system we have

$\begin{bmatrix}0&p_{T+2}&0&\cdots&0\\\ 0&0&p_{T+4}&\cdots&0\\\
0&0&0&\cdots&0\\\ \vdots&&&\ddots&\vdots\\\
\bar{p}_{T}&\bar{p}_{T+2}&\bar{p}_{T+4}&\cdots&\bar{p}_{K-1}\\\
\end{bmatrix}\begin{bmatrix}x_{T}\\\ x_{T+2}\\\ x_{T+4}\\\ \vdots\\\
x_{K-1}\end{bmatrix}=\begin{bmatrix}1/p_{T+1}-1/p_{T+3}\\\
1/p_{T+3}-1/p_{T+5}\\\ 1/p_{T+5}-1/p_{T+7}\\\ \vdots\\\ 1/p_{K}\end{bmatrix}.$

The unique solution is

$\displaystyle x_{i}$ $\displaystyle=\tilde{q}_{i},\qquad\mbox{for }i\in
D(T+2,K),$ $\displaystyle x_{T}$ $\displaystyle=\tilde{r}_{T}\enspace.$

Since $\tilde{q}_{t}$ is positive for every $2\leq t\leq K-1$, Eq. 58–(59) are
equivalent to

$\displaystyle\tilde{r}_{T}$ $\displaystyle>0,$ (64)
$\displaystyle\tilde{R}_{T}$ $\displaystyle>0.$ (65)

We now check Eq. 55. As Alice’s payoff for playing a time $i<T$ is maximized
when $i=T-1$, we may assume that $i\in D(T-1,K)$. Consider first the case
where Alice plays in $D(T-1,K-2)$; we will treat the case Alice plays time $K$
later. When Alice plays $i\in D(T-1,K-2)$ then $i+1$ is in $\sup(x)$. Moreover
$D(T+1,K)_{\leq i}=D(T+1,K)_{\leq i+1}$. This means that the payoff for Alice
playing $i+1\in\sup(x)$ is strictly larger than that for playing $i$,
specifically

$e_{i}^{\mathrm{T}}Ay=\tfrac{p_{i}}{p_{i+1}}e_{i+1}^{\mathrm{T}}Ay<1.$ (66)

Thus Alice has no advantage in switching to the strategy $i$.

We have now reduced Eq. 55 to the condition $e_{K}^{\mathrm{T}}Ay\leq 1$. We
cannot use the preceeding argument to get rid of this condition as
$K+1\not\in\sup(x)$. Let us now simplify this condition. Substituting in $y$
gives the condition

$p_{K}\left(\sum_{j\in
E(T)\setminus\\{K\\}}\bar{p}_{j}\tilde{q}_{j}+\bar{p}_{K}\tilde{R}_{T}\right)\leq
1\enspace.$ (67)

Now observe that by Eq. 66 with $i=K-2$,

$p_{K-2}\left(\sum_{j\in
E(T)\setminus\\{K\\}}\bar{p}_{j}\tilde{q}_{j}+\tilde{R}_{T}\right)=\frac{p_{K-2}}{p_{K-1}}\enspace.$

Using this equality shows that Eq. 67 is equivalent to

$p_{K}\left(\tfrac{1}{p_{K-1}}-p_{K}R_{\tilde{T}^{*}}\right)\leq 1\enspace.$
(68)

Now consider Eq. 57. First say Bob plays a time $j\in D(T,K-1)$. In this case
$j+1\in D(T+1,K)$. Similarly to Alice’s case Eq. 66, $D(T,K-1)_{\leq
j}=D(T,K-1)_{\leq j+1}$ and therefore
$e_{j}^{\mathrm{T}}Ax=\tfrac{p_{j}}{p_{j+1}}e_{j+1}^{\mathrm{T}}Ax<1.$ Thus
Bob has no advantage in playing time $j$. Finally, consider the case where Bob
plays a time $j<T$. In such a case, Bob’s success probability is maximized by
playing time $j=T-1$. This gives the condition

$e_{T-1}^{\mathrm{T}}Ax=p_{T-1}\left(\tilde{r}_{T}+\sum_{i\in
D(T+2,K)}\tilde{q}_{i}\right)\leq 1\enspace.$ (69)

To summarize the current situation, Eq. 54–(61) are equivalent to Eq. 64–(65),
(68)–(69). By the definition of $\tilde{T}^{*}$, Eq. 64 is satisfied if and
only if $T\geq\tilde{T}^{*}$.

We claim now that Eq. 69 is satisfied if and only if $T\leq\tilde{T}^{*}$. To
prove this, first note that

${\bar{p}_{T-2}}\tilde{r}_{T-2}={\bar{p}_{T}}(\tilde{r}_{T}-\tilde{q}_{T})\enspace.$
(70)

Using that, from Eq. 63, applied to the case where the interval begins at
$T-2$, we derive

$p_{T-1}\left(\bar{p}_{T}\tilde{r}_{T}+p_{T}\tilde{q}_{T}+\sum_{i\in
D(T+2,K)}\tilde{q}_{i}\right)=1.$ (71)

Therefore Eq. 69 holds if and only if $\tilde{r}_{T}\leq\tilde{q}_{T}$. From
Eq. 70 this is equivalent to $\tilde{r}_{T-2}\leq 0$, and the claim then
follows from the definition of $\tilde{T}^{*}$.

To conclude, we have seen that there can not be more than one alternating Nash
equilibrium, and there is one for $T=T^{*}$ if Eq. 65 and (68) are satisfied,
which is exactly the statement of the Theorem. ∎

####  A.1.2 Starting value

For this subsection we will impose a further natural restriction on the
probabilities defining a quantum race that also holds for the Grover race. We
define a _convex_ quantum race.

######  Definition 54 (Convex race).

Let $K$ be a positive integer. We say that the sequence
$(n_{1},\ldots,n_{K})\in\mathbb{R}^{K}$ is convex if for all $1<i<K$, we have
$2n_{i}\leq n_{i-1}+n_{i+1}$. A symmetric (stingy) quantum race specified by
the probabilities $0<p_{1}<\ldots<p_{K}\leq 1$ is called convex if
$(1/p_{1},\ldots,1/p_{K})$ is a convex sequence.

If $f:[1,K]\rightarrow\mathbb{R}$ is a convex real function on the interval
$[1,K]$, and by definition $n_{i}=f(i)$, for $1\leq i\leq K$, then clearly the
sequence $(n_{1},\ldots,n_{K})$ is convex, which motivates the above
definition. The (stingy) Grover race is convex as
$\csc^{2}(2(t+1/2)\arcsin(\frac{1}{\sqrt{N}}))$ is a convex function.

For 2-player convex symmetric stingy quantum races we can show that the
starting point of the support of the symmetric Nash equilibrium and the
starting point of the support of the alternating Nash equilibrium (if it
exists) are the same, modulo a correction in parity.

######  Theorem 55.

Let $p_{1},\ldots,p_{K}$ define a convex a 2-player symmetric stingy quantum
race.

  1. 1.

If $K-T^{*}$ is odd then $\tilde{T}^{*}=T^{*}$,

  2. 2.

If $K-T^{*}$ is even then $\tilde{T}^{*}\in\\{T^{*}-1,T^{*}+1\\}.$

###### Proof.

Lemma 56 below shows that $T^{*}\leq\tilde{T}^{*}+1$. This direction does not
make use of the convexity assumption. Lemma 58 below shows $\tilde{T}^{*}\leq
T^{*}+1$ and does make use of the convexity assumption. From these two
statements the Theorem follows. ∎

######  Lemma 56.

In every 2-player symmetric stingy quantum race we have
$T^{*}\leq\tilde{T}^{*}+1$.

###### Proof.

We first claim that for every odd $i$ such that $3\leq i\leq K-1$, we have

$\bar{p}_{i}\tilde{q}_{i}>\bar{p}_{i}q_{i}+\bar{p}_{i+1}q_{i+1}\enspace.$ (72)

For this first note that $p_{i}\tilde{q}_{i}=p_{i}q_{i}+p_{i+1}q_{i+1}$. Thus
the claim is equivalent to showing $\tilde{q}_{i}>q_{i}+q_{i+1}$, which is is
true since $\tilde{q}_{i}-q_{i}=\frac{p_{i+1}}{p_{i}}q_{i+1}>q_{i+1}.$

We now claim that for every $T$ such that $1\leq T\leq K-1$ and $K-T$ is odd,
we have

$\tilde{r}_{T}>0\Longrightarrow r_{T+1}>0\enspace,$ (73)

from which the statement of the Lemma clearly follows. This claim is clearly
true for $T=K-1$, therefore we suppose that $T\leq K-3$ and $K-T$ is odd.
Summing up Eq. 72 over $D(T+2,K)$ we get

$\sum_{i\in
D(T+2,K)}\bar{p}_{i}\tilde{q}_{i}>\sum_{i=T+2}^{K}\bar{p}_{i}q_{i}\enspace,$

from which Eq. 73 immediately follows. ∎

######  Claim 57.

In a 2-player convex symmetric stingy quantum race, for every $4\leq i\leq
K-2$, we have

$\bar{p}_{i}q_{i}+\bar{p}_{i+1}q_{i+1}>\bar{p}_{i+1}\tilde{q}_{i+1}\enspace.$
(74)

###### Proof.

Recall that $q_{i+1}-\tilde{q}_{i+1}=-\tfrac{p_{i+2}}{p_{i+1}}q_{i+2}$. Thus

$\displaystyle\bar{p}_{i}q_{i}+\bar{p}_{i+1}q_{i+1}-\bar{p}_{i+1}\tilde{q}_{i+1}$
$\displaystyle=\frac{\bar{p}_{i}}{p_{i}}p_{i}q_{i}-\frac{\bar{p}_{i+1}}{p_{i+1}}{p_{i+2}}q_{i+2}$
$\displaystyle=\left(\frac{1}{p_{i}}-1\right)\left(\frac{1}{p_{i-1}}-\frac{1}{p_{i}}\right)-\left(\frac{1}{p_{i+1}}-1\right)\left(\frac{1}{p_{i+1}}-\frac{1}{p_{i+2}}\right)$
$\displaystyle>\left(\frac{1}{p_{i+1}}-1\right)\left(\frac{1}{p_{i-1}}-\frac{1}{p_{i}}-\frac{1}{p_{i+1}}+\frac{1}{p_{i+2}}\right)$
$\displaystyle>\frac{1}{p_{i-1}}-\frac{1}{p_{i}}-\frac{1}{p_{i+1}}+\frac{1}{p_{i+2}}$
$\displaystyle=\left(\frac{1}{p_{i-1}}-\frac{2}{p_{i}}+\frac{1}{p_{i+1}}\right)+\left(\frac{1}{p_{i}}-\frac{2}{p_{i+1}}+\frac{1}{p_{i+2}}\right)$
$\displaystyle\geq 0\enspace,$

where the last inequality holds by convexity of $(1/p_{1},\ldots,1/p_{K})$. ∎

######  Lemma 58.

In a 2-player convex symmetric stingy quantum race we have $\tilde{T}^{*}\leq
T^{*}+1$.

###### Proof.

The proof of the Lemma will follow from the following statement. For every
$1\leq T\leq K-1$, we have:

$\displaystyle K-T\text{~{}is odd and
}r_{T}>0~{}\Longrightarrow~{}\tilde{r}_{T}>0,$ (75) $\displaystyle
K-T\text{~{}is even and }r_{T}>0~{}\Longrightarrow~{}\tilde{r}_{T+1}>0.$ (76)

Eq. 75 follows since $\tilde{r}_{T}>r_{T}$ by summing over Eq. 74. Similarly,
we can see that $\tilde{r}_{T+1}>r_{T}$ by summing over Eq. 74 from $T+2$
until $K-1$:

$\sum_{i\in
D(T+3,K)}\bar{p}_{i}\tilde{q}_{i}<\sum_{i=T+2}^{K-1}\bar{p}_{i}q_{i},$

from which Eq. 76 follows. ∎

###  A.2 Alternating-coinciding Nash equilibria

In this section, we turn to the third possible strategy structure for a Nash
equilibrium, alternating-coinciding. In this case, Alice and Bob play at
alternating times from time $T$ until time $c-1$, at which point they play the
same times in the interval $[c,K]$. In other words, Alice’s strategy is
supported on a set $\mathcal{A}=\\{T,T+2,\ldots,c-2,c,c+1,\ldots,K\\}$ and
Bob’s strategy is supported on
$\mathcal{B}=\\{T+1,T+3,\ldots,c-1,c,c+1,\ldots,K\\}$. We call this a
$(T,c,K)$-alternating-coinciding strategy, and refer to $c$ as the _change
point_. As we have already treated the coinciding and purely alternating
cases, we will assume in this section that $T<c\leq k$.

To study alternating-coinciding Nash equilibria, we need to define the
following quantities.

$\displaystyle q_{t}$
$\displaystyle=\frac{1}{p_{t}}\left(\frac{1}{p_{t-1}}-\frac{1}{p_{t}}\right),\mbox{
for }1<t\leq K$ $\displaystyle\tilde{q}_{t}$
$\displaystyle=\frac{1}{p_{t}}\left(\frac{1}{p_{t-1}}-\frac{1}{p_{t+1}}\right),\mbox{
for }1<t<K$ $\displaystyle r_{t,c}$
$\displaystyle=\frac{1}{\bar{p}_{t}}\left(\frac{1}{p_{K}}-\sum_{i\in
D(t+2,c-2)}\bar{p}_{i}\tilde{q}_{i}-\sum_{i=c}^{K}\bar{p}_{i}q_{i}\right),\mbox{
for }1\leq t<c\leq K$ $\displaystyle R_{t,c}$
$\displaystyle=\frac{1}{p_{K}}-\sum_{i\in
D(t+1,c-3)}\bar{p}_{i}\tilde{q}_{i}-\sum_{i=c+1}^{K}\bar{p}_{i}q_{i},\mbox{
for }1\leq t<c\leq K$ $\displaystyle w_{i,t,c}$
$\displaystyle=\bar{p}_{i}p_{c-1}\tilde{q}_{c-1}-p_{i}R_{t,c},\mbox{ for
}1\leq t<i\leq c\leq K$ $\displaystyle z_{t,c}$
$\displaystyle=r_{t,c}+\sum_{i\in
D(t+2,c-2)}\tilde{q}_{i}+\sum_{i=c}^{K}q_{i}$ $\displaystyle Z_{t,c}$
$\displaystyle=\sum_{i\in
D(t+1,c-3)}\tilde{q}_{i}-\frac{w_{c,T,c}}{p_{c}-p_{c-1}}+\frac{w_{c-1,T,c}}{p_{c}-p_{c-1}}+\sum_{i=c}^{K}q_{i}$

######  Theorem 59.

Let $p_{1}<p_{2}<\cdots<p_{K}$ define a symmetric stingy quantum race. Let
$1\leq T<c\leq K$ be such that $T,c$ are odd. There is a
$(T,c,K)$-alternating-coinciding Nash equilibrium $(x,y)$ if and only if the
following conditions are satisfied:

$\displaystyle\frac{1}{p_{T-1}}$ $\displaystyle\geq r_{t,c}+\sum_{i\in
D(T+2,c-2)}\tilde{q}_{i}+\sum_{i=c}^{K}q_{i}\enspace,$ (77)
$\displaystyle\frac{1}{p_{c-1}}$ $\displaystyle\geq\sum_{i\in
D(T+1,c-3)}\bar{p}_{i}\tilde{q}_{i}-\bar{p}_{c-1}\frac{w_{c,T,c}}{p_{c}-p_{c-1}}+\frac{w_{c-1,T,c}}{p_{c}-p_{c-1}}+\sum_{i=c+1}^{K}q_{i}\enspace,$
(78) $\displaystyle\frac{1}{p_{K}}$ $\displaystyle>\sum_{i\in
D(T+2,c-2)}\bar{p}_{i}\tilde{q}_{i}+\sum_{i=c}^{K}\bar{p}_{i}q_{i}\enspace,$
(79) $\displaystyle\bar{p}_{c-1}\tilde{q}_{c-1}$
$\displaystyle>R_{T,c}\enspace.$ (80)

If these constraints are satisfied then the Nash equilibrium is given by

$\displaystyle x_{i}=\begin{cases}r_{T,c}/z_{T,c}&\mbox{ if }i=T\\\
\tilde{q}_{i}/z_{T,c}&\mbox{ if }i\in D(T+2,c-2)\\\ q_{i}/z_{T,c}&\mbox{ if
}i\in[c,K]\\\ 0&\mbox{ otherwise}\end{cases},\qquad
y_{j}=\begin{cases}\tilde{q}_{j}/Z_{T,c}&\mbox{ if }j\in D(T+1,c-3)\\\
-\frac{w_{c,T,c}}{Z_{T,c}(p_{c}-p_{c-1})}&\mbox{ if }j=c-1\\\
\frac{w_{c-1,T,c}}{Z_{T,c}(p_{c}-p_{c-1})}&\mbox{ if }j=c\\\
q_{j}/Z_{T,c}&\mbox{ if }j\in[c,K]\\\ 0&\mbox{ otherwise.}\end{cases}$

###### Proof.

Let $\mathcal{A}=D(T,c-2)\cup\\{c,c+1,\ldots,K\\}$ be Alice’s support set and
$\mathcal{B}=D(T+1,c-1)\cup\\{c,c+1,\ldots,K\\}$ be Bob’s support set. A Nash
equilibrium $(x,y)$ with $x$ supported on $\mathcal{A}$ and $y$ supported on
$\mathcal{B}$ must satisfy the equations

$\displaystyle e_{i}^{T}Ay=e_{j}^{T}Ay\mbox{ for all }i,j\in\mathcal{A}$
$\displaystyle e_{i}^{T}Ax=e_{j}^{T}Ax\mbox{ for all }i,j\in\mathcal{B}$

By multiplying $x$ and $y$ by appropriate constants, we can obtain
$x^{\prime},y^{\prime}$ (now unnormalized) that satisfy

$\displaystyle e_{i}^{T}Ay^{\prime}=1\mbox{ for all }i\in\mathcal{A}$
$\displaystyle e_{i}^{T}Ax^{\prime}=1\mbox{ for all }i\in\mathcal{B}$

These sytems of linear equations can be solved similarly to the systems in the
symmetric and alternating cases, and always have a unique solution given by

$\displaystyle x_{i}^{\prime}=\begin{cases}r_{T,c}&\mbox{ if }i=T\\\
\tilde{q}_{i}&\mbox{ if }i\in D(T+2,c-2)\\\ q_{i}&\mbox{ if }i\in[c,K]\\\
0&\mbox{ otherwise}\end{cases},\qquad
y_{j}^{\prime}=\begin{cases}\tilde{q}_{j}&\mbox{ if }j\in D(T+1,c-3)\\\
-\frac{w_{c,T,c}}{p_{c}-p_{c-1}}&\mbox{ if }j=c-1\\\
\frac{w_{c-1,T,c}}{p_{c}-p_{c-1}}&\mbox{ if }j=c\\\ q_{j}&\mbox{ if
}j\in[c,K]\\\ 0&\mbox{ otherwise.}\end{cases}$

For (the normalized versions of) $x^{\prime},y^{\prime}$ to actually be a Nash
equlibrium, $x^{\prime},y^{\prime}$ also need to satisfy the following
additional inequalities.

$\displaystyle e_{j}^{\mathrm{T}}Ax^{\prime}$ $\displaystyle\leq 1\mbox{ for
}1\leq j\leq K\enspace,$ (81) $\displaystyle e_{i}^{\mathrm{T}}Ay^{\prime}$
$\displaystyle\leq 1\mbox{ for }1\leq i\leq K\enspace,$ (82) $\displaystyle
0<x_{i}^{\prime}$ $\displaystyle\mbox{ for }i\in\mathcal{A}\enspace,$ (83)
$\displaystyle 0<y_{j}^{\prime}$ $\displaystyle\mbox{ for
}j\in\mathcal{B}\enspace,$ (84)

We now simplify these conditions given the values of $x^{\prime},y^{\prime}$,
beginning with Eq. 81. With $x^{\prime}$ defined as above,
$e_{j}^{\mathrm{T}}Ax^{\prime}=p_{j}/p_{j+1}$ for $j\geq
T,j\not\in\mathcal{B}$. This is always at most one. Thus for Eq. 81 what
remains to be checked is that $e_{T-1}^{\mathrm{T}}Ax^{\prime}\leq 1$.

Similarly for Eq. 82 with $y^{\prime}$ as defined above we see that
$e_{i}^{T}Ay^{\prime}=p_{i}/p_{i+1}$ for $T-1\leq i<c-1,i\not\in\mathcal{A}$.
As playing a time $i<T-1$ will result in a strictly smaller payoff than
playing time $T-1$, the only constraint that is not immediate is
$e_{c-1}^{T}Ay^{\prime}\leq 1$.

Now for the positivity conditions, Eq. 83 and (84). It is clear that
$\tilde{q}_{i},q_{i}>0$ for $T<i\leq K$ as the probabilities $p_{j}$ form an
increasing sequence. The remaining positivity conditions that must be checked
are $r_{T,c},w_{c-1,T,c},-w_{c,T,c}>0$. The condition $w_{c-1,T,c}>0$ is
equivalent to $R_{T,c}<\bar{p}_{c-1}\tilde{q}_{c-1}$, and the condition
$-w_{c,T,c}>0$ is equivalent to

$\displaystyle R_{T,c}$
$\displaystyle>\bar{p}_{c}p_{c-1}\tilde{q}_{c-1}/p_{c}$
$\displaystyle=\bar{p}_{c-1}\tilde{q}_{c-1}-\frac{p_{c}-p_{c-1}}{p_{c}}\tilde{q}_{c-1}\enspace.$

This gives us the following simplified set of constraints.

$\displaystyle e_{T-1}^{\mathrm{T}}Ax^{\prime}\leq 1$
$\displaystyle\iff\frac{1}{p_{T-1}}\geq r_{t,c}+\sum_{i\in
D(T+2,c-2)}\tilde{q}_{i}+\sum_{i=c}^{K}q_{i}\enspace,$ (85) $\displaystyle
e_{c-1}^{T}Ay^{\prime}\leq 1$
$\displaystyle\iff\frac{1}{p_{c-1}}\geq\sum_{i\in
D(T+1,c-3)}\bar{p}_{i}\tilde{q}_{i}-\bar{p}_{c-1}\frac{w_{c,T,c}}{p_{c}-p_{c-1}}+\frac{w_{c-1,T,c}}{p_{c}-p_{c-1}}+\sum_{i=c+1}^{K}q_{i}\enspace,$
(86) $\displaystyle r_{T,c}>0$ $\displaystyle\iff\frac{1}{p_{K}}>\sum_{i\in
D(T+2,c-2)}\bar{p}_{i}\tilde{q}_{i}+\sum_{i=c}^{K}\bar{p}_{i}q_{i}\enspace,$
(87) $\displaystyle w_{c-1,T,c},-w_{c,T,c}>0,$
$\displaystyle\iff\bar{p}_{c-1}\tilde{q}_{c-1}>R_{T,c}>\bar{p}_{c-1}\tilde{q}_{c-1}-\frac{p_{c}-p_{c-1}}{p_{c}}\tilde{q}_{c-1}\enspace.$
(88)

We can further simplify the constraint in Eq. 88. As
$e_{c}^{\mathrm{T}}Ay^{\prime}=1$, we have

$\frac{1}{p_{c}}=\sum_{i\in
E(T+1,c-3)}\bar{p}_{i}\tilde{q}_{i}-\bar{p}_{c-1}\frac{w_{c,T,c}}{p_{c}-p_{c-1}}+\bar{p}_{c}\frac{w_{c-1,T,c}}{p_{c}-p_{c-1}}+\sum_{i=c+1}^{K}q_{i}\enspace.$

This means that Eq. 86 is equivalent to

$\frac{1}{p_{c-1}}-\frac{1}{p_{c}}\geq
p_{c}\frac{w_{c-1,T,c}}{p_{c}-p_{c-1}}\iff q_{c}\geq x_{c}^{\prime}\enspace.$

Rewriting this inequality in terms of $R_{T,c}$ gives

$R_{T,c}\geq\bar{p}_{c-1}\tilde{q}_{c-1}-q_{c}\left(\frac{p_{c}-p_{c-1}}{p_{c-1}}\right)\enspace.$
(89)

This constraint actually implies the lower bound of Eq. 88. To see this, note
that

$\displaystyle\frac{p_{c}-p_{c-1}}{p_{c-1}}q_{c}$
$\displaystyle=\frac{p_{c}-p_{c-1}}{p_{c-1}p_{c}}\left(\frac{1}{p_{c-1}}-\frac{1}{p_{c}}\right)$
$\displaystyle<\frac{p_{c}-p_{c-1}}{p_{c-1}p_{c}}\left(\frac{1}{p_{c-2}}-\frac{1}{p_{c}}\right)$
$\displaystyle=\frac{p_{c}-p_{c-1}}{p_{c}}\tilde{q}_{c-1}\enspace.$

Thus the lower bound in Eq. 88 is a redundant constraint and can be removed.
This finishes the proof of the theorem. ∎

Next we examine which values of $T$ can be the starting point of an
alternating-coinciding equilibrium.

######  Definition 60.

Let $T^{*}$ be as in Definition 20. For $c>T^{*}$ define
$\hat{T}_{c}^{*}=\min\\{T:r_{T,c}>0\\}$.

The condition $c>T^{*}$ is taken so that $\hat{T}_{c}^{*}$ is always well
defined. The next claim shows that the starting point of an alternating-
coinciding equilibrium with change point $c$ must be $\hat{T}_{c}^{*}$.

######  Claim 61.

Let $p_{1}<p_{2}<\cdots<p_{K}$ define a symmetric stingy quantum race. For any
$1<c<K$, the starting support of an alternating-coinciding Nash equilibrium
with change point $c$ (if it exists) must be
$\hat{T}_{c}^{*}=\min\\{T:r_{T,c}>0\\}$.

###### Proof.

Note that $r_{T,c}$ is an increasing function of $T$. This means that the
condition $r_{T,c}>0$ (Eq. 79) will only be satisfied for $\hat{T}_{c}^{*}\leq
T\leq c$.

We now see that to satisfy Eq. 77 we must have $T\leq\hat{T}_{c}^{*}$. From
the definition of $r_{t,c}$ we have

$\frac{\bar{p}_{t-2}}{\bar{p}_{t}}r_{t-2,c}=r_{t,c}-\tilde{q}_{t}\enspace.$

As $r_{\hat{T}_{c}^{*}-2,c}\leq 0$ and $r_{\hat{T}_{c}^{*},c}>0$, this means
that $r_{\hat{T}_{c}^{*},c}\leq\tilde{q}_{\hat{T}^{*}}$ and
$r_{T,c}>\tilde{q}_{T}$ for $T>\hat{T}_{c}^{*}$.

Considering when Bob plays strategy $T-1$ when the starting point of the
interval is $T-2$, we see that

$\displaystyle\frac{1}{p_{T-1}}$
$\displaystyle=\bar{p}_{T-2}r_{T-2,c}+\sum_{i\in
D(T,c-2)}\tilde{q}_{i}+\sum_{i=c}^{K}q_{i}$
$\displaystyle=\bar{p}_{T}(r_{T,c}-\tilde{q}_{T})+\sum_{i\in
D(T,c-2)}\tilde{q}_{i}+\sum_{i=c}^{K}q_{i}$
$\displaystyle=\bar{p}_{t}r_{T,c}+p_{T}\tilde{q}_{T}+\sum_{i\in
D(T+2,c-2)}\tilde{q}_{i}+\sum_{i=c}^{K}q_{i}$

From this equality we see that if $r_{T,c}>\tilde{q}_{T}$ then

$\frac{1}{p_{T-1}}<r_{T,c}+\sum_{i\in
O(T+2,c)}\tilde{q}_{i}+\sum_{i=c}^{K}q_{i}$

and so will violate Eq. 85. Thus the starting point of a alternating-
coinciding Nash equilibrium with change point $c$ must satisfy
$T\leq\hat{T}_{c}^{*}$. Putting this together with $T\geq T_{c}^{*}$ means
that the only possible starting point of a alternating-coinciding Nash
equilibrium with change point $c$ is $\hat{T}_{c}^{*}$. ∎

######  Claim 62.

Let $p_{1}<p_{2}<\cdots<p_{K}$ define a symmetric stingy quantum race. Let
$T^{*},\tilde{T}^{*}$ be as in Definition 20, 52, respectively. For any
$c>T^{*}$ we have $T^{*}-1\leq\hat{T}^{*}_{c}\leq\tilde{T}^{*}+1$. If $c$ and
$K$ have the same parity then the tighter upper bound
$\hat{T}^{*}_{c}\leq\tilde{T}^{*}$ holds.

###### Proof.

Fix $c>T^{*}$. For $T<c$ of the same parity as $c$, we show that if
$r_{T,c}>0$ then $r_{T+1}>0$. This implies $\hat{T}_{c}^{*}\geq T^{*}-1$.

We have $r_{T,c}>0$ if and only if

$\displaystyle\frac{1}{p_{K}}$ $\displaystyle>\sum_{i\in
D(T+2,c-2)}\bar{p}_{i}\tilde{q}+\sum_{i=c}^{K}$
$\displaystyle\geq\sum_{i=T+2}^{K}\bar{p}_{i}q_{i}$

This inequality follows from the fact that
$\bar{p}_{i}\tilde{q}_{i}\geq\bar{p}_{i}q_{i}+\bar{p}_{i+1}q_{i+1}$. Thus we
have $1/p_{K}>\sum_{i=T+2}^{K}\bar{p}_{i}q_{i}$, which implies $r_{T+1}>0$.

Now let $T,K$, and $c$ all have the same parity and suppose that
$\tilde{r}_{T}>0$. This happens if and only if

$\displaystyle\frac{1}{p_{K}}$ $\displaystyle>\sum_{i\in
D(T+2,K)}\bar{p}_{i}\tilde{q}_{i}$ $\displaystyle\geq\sum_{i\in
D(T+2,c-2)}\bar{p}_{i}\tilde{q}_{i}+\sum_{i=c}^{K}\bar{p}_{i}q_{i}$

This means that $r_{T,c}>0$. This shows that if $c,K$ have the same parity
then $\hat{T}^{*}\leq\tilde{T}^{*}$. If $c,K$ have opposite parity, then we
can repeat the same argument to see that $\tilde{r}_{T}>0\implies
r_{T+1,c}>0$. Thus in the case we have $\hat{T}^{*}_{c}\leq\tilde{T}^{*}+1$. ∎

We can analogously show that for every time $T$ there can be at most one
change point $c$ such that there is an $(T,c,K)$-alternating-coinciding Nash
equilibrium. For this we first need the following claim.

######  Claim 63.

$\bar{p}_{t-1}\tilde{q}_{t-1}-q_{t}\left(\frac{p_{t}-p_{t-1}}{p_{t-1}}\right)=\bar{p}_{t-1}q_{t-1}+\bar{p}_{t}q_{t}\enspace.$

###### Proof.

First we expand the right hand side

$\displaystyle\bar{p}_{t-1}q_{t-1}+\bar{p}_{t}q_{t}$
$\displaystyle=q_{t-1}-\frac{1}{p_{t-2}}+\frac{1}{p_{t-1}}+q_{t}-\frac{1}{p_{t-1}}+\frac{1}{p_{t}}$
$\displaystyle=q_{t-1}+q_{t}+\frac{1}{p_{t}}-\frac{1}{p_{t-2}}\enspace.$

Next we expand the left hand side

$\displaystyle\bar{p}_{t-1}\tilde{q}_{t-1}-q_{t}\frac{p_{t}-p_{t-1}}{p_{t-1}}=\tilde{q}_{t-1}-\frac{1}{p_{t-2}}+\frac{1}{p_{t}}-\frac{1}{p_{t-1}}\left(\frac{1}{p_{t-1}}-\frac{1}{p_{t}}\right)+q_{t}\enspace.$

Canceling like terms and rearranging, it suffices to show

$\displaystyle\tilde{q}_{t-1}-q_{t-1}=\frac{1}{p_{t-1}}\left(\frac{1}{p_{t-1}}-\frac{1}{p_{t}}\right),$

which can be easily verified. ∎

######  Lemma 64.

For any time $T$ there is at most one $c$ such that there is a
$(T,c,K)$-alternating-coinciding Nash equilibrium (up to switching the roles
of Alice and Bob).

###### Proof.

We show that for any $T$ there is at most one possible change point $c$ for an
alternating-coinciding Nash equilibrium starting at $T$. For this we look at
Eq. 88 and Eq. 89, which imply that the change point $c$ for an alternating-
coinciding Nash equilibrium beginning at $T$ must satisfy

$\bar{p}_{c-1}\tilde{q}_{c-1}>R_{T,c}>\bar{p}_{c-1}\tilde{q}_{c-1}-q_{c}\left(\frac{p_{c}-p_{c-1}}{p_{c-1}}\right)\enspace.$
(90)

Using 63 we can rewrite Eq. 90 as

$\bar{p}_{c-1}\tilde{q}_{c-1}>R_{T,c}>\bar{p}_{c-1}q_{c-1}+\bar{p}_{c}q_{c}\enspace.$
(91)

From the definitions, it can be verified that

$R_{T,t+2}-R_{T,t}=-\bar{p}_{t-1}\tilde{q}_{t-1}+\bar{p}_{t+1}q_{t+1}+\bar{p}_{t+2}q_{t+2}\enspace.$

Now suppose that

$\bar{p}_{t-1}\tilde{q}_{t-1}>R_{T,t}>\bar{p}_{t-1}q_{t-1}+\bar{p}_{t}q_{t}\enspace.$
(92)

Then

$\displaystyle R_{\hat{T}^{*},t+2}$
$\displaystyle=R_{\hat{T}^{*},t}-\bar{p}_{t-1}\tilde{q}_{t-1}+\bar{p}_{t+1}q_{t+1}+\bar{p}_{t+2}q_{t+2}$
$\displaystyle<\bar{p}_{t+1}q_{t+1}+\bar{p}_{t+2}q_{t+2}\enspace.$

This means that if $R_{T,c}$ satisfies Eq. 91, then no $R_{T,t}$ can satisfy
this constraint for $t\geq c+2$, as it will be smaller than corresponding
lower bound in Eq. 90. This means that for each $T$, there is at most $c$ such
that Eq. 91 is satisfied. ∎

Finally, in the case of a convex quantum race we can more precisely pin down
the exact form of an alternating-coinciding equilibrium. If $T^{*}$ is the
starting point of the coinciding Nash equilibrium, then the support of any
alternating-coinciding Nash equilibrium must begin in the interval
$[T^{*}-1,T^{*}+2]$.

######  Theorem 65.

Let $p_{1}<p_{2}<\cdots<p_{K}$ define a 2-player convex symmetric stingy
quantum race. Let $T^{*}$ be the starting point of the symmetric Nash
equilibrium. Any alternating-coinciding equilibrium must begin at either
$T^{*}-1,T^{*},T^{*}+1$, or $T^{*}+2$. In particular, there are at most four
alternating-coinciding equilibria (up to switching the roles of Alice and
Bob).

###### Proof.

We first we show the statement about the starting point of the interval. Let
$\hat{T}^{*}_{c}=\min\\{T:r_{T,c}>0\\}$. 61 established that the starting
point of a mixed Nash equilibrium with change point $c$ (if it exists) must be
at $\hat{T}^{*}_{c}$. By 62, we have that
$T^{*}-1\leq\hat{T}^{*}_{c}\leq\tilde{T}^{*}+1$ for any possible value of $c$.
This part of the theorem now follows as Theorem 55 shows that for concave
probabilities $\tilde{T}^{*}\in\\{T^{*}-1,T^{*},T^{*}+1\\}$.

The “in particular” line of the theorem now follows by Lemma 64. For each
$T\in[T^{*}-1,T^{*}+2]$ there can be at most one $c$ such that there is a
$(T,c,K)$-alternating-coinciding Nash equilibrium. Thus there can be at most
four alternating-coinciding Nash equilibria (up to switching the roles of