# Jumping through Local Minima: Quantization in the Loss Landscape of Vision
Transformers

Natalia Frumkin
The University of Texas at Austin
<EMAIL_ADDRESS>Dibakar Gope
Arm Inc.
<EMAIL_ADDRESS>Diana Marculescu
The University of Texas at Austin
<EMAIL_ADDRESS>
###### Abstract

Quantization scale and bit-width are the most important parameters when
considering how to quantize a neural network. Prior work focuses on optimizing
quantization scales in a global manner through gradient methods (gradient
descent & Hessian analysis). Yet, when applying perturbations to quantization
scales, we observe a very jagged, highly non-smooth test loss landscape. In
fact, small perturbations in quantization scale can greatly affect accuracy,
yielding a $0.5-0.8\%$ accuracy boost in 4-bit quantized vision transformers
(ViTs). In this regime, gradient methods break down, since they cannot
reliably reach local minima. In our work, dubbed Evol-Q, we use evolutionary
search to effectively traverse the non-smooth landscape. Additionally, we
propose using an infoNCE loss, which not only helps combat overfitting on the
small calibration dataset ($1,000$ images) but also makes traversing such a
highly non-smooth surface easier. Evol-Q improves the top-1 accuracy of a
fully quantized ViT-Base by $10.30\%$, $0.78\%$, and $0.15\%$ for $3$-bit,
$4$-bit, and $8$-bit weight quantization levels. Extensive experiments on a
variety of CNN and ViT architectures further demonstrate its robustness in
extreme quantization scenarios. Our code is available at
https://github.com/enyac-group/evol-q .

##  1 Introduction

Quantization is a widespread technique for efficient neural network inference:
reducing data precision from $32$ bits to $\leq$ $8$ bits is an effective
approach to aggressively reduce model footprint and speed up computation.
Network quantization is an extremely important tool for deploying models in
cloud [28] and edge settings [27], where we aim to maximize accuracy while
reducing the computational burden. We consider the post-training quantization
(PTQ) setting, where there is access to a small ($\sim$$1,000$ image)
calibration dataset but no access to the original training dataset. PTQ is an
integral component of model deployment, when a carefully curated full-
precision model is too expensive to retrain. Our work, Evol-Q, is a PTQ method
for vision transformers which leverages four key observations:

(a) ResNet-18 Test Loss

(b) DeiT-Tiny Test Loss

Figure 1: We perturb along two basis vectors of one layer/block’s quantization
scales. The test loss landscape during perturbation is smooth in the CNN case
(a), and highly non-smooth in the ViT case (b).

  1. 1.

Small perturbations in quantization scale can lead to significant improvement
in quantization accuracy. For example, small adjustments in a self-attention
block’s scale can induce a $\pm$ 1% change in accuracy.

  2. 2.

As shown in Fig. 1, quantized vision transformers (ViTs) have an extremely
non-smooth loss landscape, particularly with respect to the perturbation in
quantization scales, making stochastic gradient descent a poor choice for
optimization. We use evolutionary search to favor nearby local minima to
significantly improve accuracy ($\sim$ $0.5-1\%$).

  3. 3.

In comparison to non-contrastive loss functions such as mean squared error,
cosine similarity, and the KL divergence, contrastive losses tend to smooth
the loss landscape, as observed in our experiments and supported by recent
work [10]. This finding inspires the use of contrastive loss to further
facilitate the quantization scale search process. Contrastive losses,
specifically the infoNCE loss in this work, also helps in combating
overfitting on the small calibration dataset by incorporating negative
examples into the loss.

  4. 4.

The Evol-Q framework generalizes to CNN quantization as well, since the
infoNCE loss provides a smoother landscape than other losses.

Combining these observations, we devise a new optimization scheme to adjust
the quantization scales of low bit-width ViTs. Instead of using gradient
descent to optimize all network parameters or estimating a noisy Hessian, we
propose a series of cheap evolutionary search procedures to successively
minimize the quantization error. Evol-Q injects small perturbations into the
quantization scale at one layer and uses a global infoNCE loss to evaluate
them. In the next section, we will show how prior work does not properly
address the non-smooth ViT loss landscape.

(a) A single cycle of block-wise evolutionary search.

(b) Visualization of the infoNCE Loss

Figure 2: An overview of Evol-Q. On the left, we show one cycle completed on a
single block. Each block has $C$ cycles of evolutionary search, and we perform
$P$ passes over all blocks. On the right, we provide intuition for the infoNCE
loss (Step 2), where we encourage similarity between the quantized and
corresponding predictions while simultaneously maximizing dissimilarity
between unlike predictions.

##  2 Related Work

CNN Quantization: When quantizing ViTs, it is natural to borrow techniques
from CNN quantization and apply them to vision transformers. In the case of
general quantization, one can consider either naive methods (such as MinMax
[14] quantization) or complex methods (such as gradient descent) to find the
quantization scale. Naive techniques include MinMax [14], Log2 [3], or
Percentile quantization, where we apply some statistical analysis on the
values of a model tensor. While simple to implement, these methods can result
in unacceptable accuracy degradation, particularly in the $3$-bit and $4$-bit
case. This leads us to employ more advanced strategies to recoup some accuracy
lost by quantization.

Complex methods involve techniques such as gradient descent[24], Hessian
analysis [15], or knowledge distillation [6] to maximize the quantized model’s
accuracy. In particular, many methods employ a layer-wise loss [29, 13, 2]. A
layer-wise loss can serve as a good proxy for a smooth global loss [23], yet a
local loss is unlikely to resemble the ViT’s highly non-smooth global
landscape [1]. While Hessian-based methods [15] can utilize second order
information, the ViT loss landscape resembles an “egg carton” with a high
density of extremal points. This space cannot be traversed well with only
first and second-order gradient information. Moreover, BRECQ [15] assumes the
Hessian is positive semi-definite (PSD) which is a poor assumption for any
non-smooth landscape.

ViT Quantization: Some work has already achieved very good accuracy on vision
transformers. PTQ-for-ViT [22] learns a quantization scale for each layer by
using two loss functions: (1) a ranking loss for each multi-head attention
module; and (2) cosine similarity for the MLP layer. The layer-wise loss may
achieve good accuracy, but with the non-smooth ViT landscape, this approach
may end up at a local maximum and may be very sensitive to initialization.
PTQ4ViT [31] also employs a Hessian-guided metric for guided global
optimization similar to BRECQ [15]. As we mentioned before, the PSD assumption
on the Hessian breaks down for our “egg carton”-shaped loss landscape. In
contrast, PSAQ-ViT-V2 [16] uses a student-teacher MinMax game to minimize the
KL divergence between the full precision and quantized models. The KL
divergence is applied to kernel density estimations which are much more robust
than Hessian-based or gradient-based techniques. We believe this technique can
traverse the non-smooth ViT landscape, and despite being data-free, it has the
best accuracy of all other methods we compare against.

We apply Evol-Q, our quantization scale learning method, on top of the FQ-ViT
[20] which incorporates Log2 quantization and an integer Softmax function for
end-to-end $8$-bit quantization. FQ-ViT [20] is surprisingly effective on
ViTs, likely because Log2 quantization can compensate for the asymmetric
distributions following the Softmax and GeLU layers.

Quantization-Aware Training (QAT) has shown impressive results on vision
transformers [30, 19, 18, 17], yet these methods consider training with the
entire dataset rather than an unlabeled calibration dataset.

Contrastive Loss: In this work, we use a global infoNCE loss as our preferred
loss function for both CNN and ViT quantization. Since we have such a small
calibration dataset, the infoNCE loss helps generalize to the unseen test set.
We are the first work to use a infoNCE loss in this manner. Prior work has
combined quantization and self-supervised learning in a joint training
framework [4, 11] allowing for regularization from both the contrastive loss
and a quantization loss in training. In particular, SSQL [4] uses a joint
SimSiam-$L_{2}$ loss during training to improve quantization for all bit-
widths, whereas our method considers how the infoNCE loss, in conjunction with
an evolutionary search, is used to traverse the highly non-smooth loss
landscape and optimize the quantization scale for a specific bit-width at test
time. Moreover, SSQL [4] uses the loss as regularization and not as a proxy
for the test loss . Another work [26] applies contrastive learning to
binarized ResNet and VGG models. They apply a layer-wise infoNCE loss, showing
that it achieves good results for the 2-bit loss landscape of small CNNs.
While a layer-wise loss is sub-optimal, the ability for the infoNCE loss to
perform well on a binary loss landscape is great motivation for our work.

In summary, prior work has migrated CNN quantization techniques to ViT
quantization without addressing the non-smooth ViT loss landscape. In the
coming section, we present Evol-Q as an effective solution to this problem.

##  3  The Evol-Q Framework

In the non-smooth ViT quantization landscape, first and second-order gradient
methods are not effective and cannot handle the large number of local minima.
In such a regime, small perturbations in quantization scale can lead to a
significant boost in accuracy. We apply evolutionary search using an infoNCE
loss to evaluate these perturbations, enabling Evol-Q to traverse a non-smooth
surface and minimize overfitting on the calibration dataset.

We begin with an overview of uniform quantization and then dive into the core
components of our method: traversing perturbations using evolutionary search
and evaluating them using an infoNCE loss.

###  3.1 Uniform, End-to-End Quantization

We consider uniform quantization, where full precision values are mapped to a
uniform range based on the quantization bit-width (b). Uniform quantization is
formally defined as:

$Q(\textbf{x},\delta,b)=\texttt{clip}(\Big{\lfloor}\frac{\textbf{x}}{\delta}\Big{\rceil},-2^{b-1}+1,2^{b-1}-1)$
(1)

where x is a full-precision vector and $\delta$ is the quantization scale. We
can generalize this idea to a tensor X and a corresponding quantization vector
$\Delta$ (e.g, each element in $\Delta$ corresponds to a channel in channel-
wise quantization). In our framework, we learn these initial quantization
parameters using a fast, layer-wise framework such as FQ-ViT [20], and then
use evolutionary search to adjust the scales of each attention block’s
projection layers.

###  3.2 Where to Perturb?

A ViT model [8] consists of $12$ multi-head self-attention (MHSA) blocks
stacked on top of each other. Each block applies the following transformation
on a given query (Q), key (K), and value (V):

$MHSA(Q,K,V)=\texttt{concat}(H_{0},H_{1},\dots H_{N})W^{O}$ (2)

where each attention head $H_{i}$ is:

$H_{i}(Q,K,V)=\texttt{softmax}(\frac{(W^{Q}Q)(W^{K}K)^{T}}{\sqrt{d_{k}}})\cdot
W^{V}V$ (3)

Our method applies end-to-end quantization meaning that for each attention
block we quantize all $3N+1$ weight tensors and $6N+1$ intermediary
activations where N is number of heads. The quantization scales of all weights
and activations can be concatenated and viewed as the vector $\Delta$. This
stacked vector is very important for understanding our algorithm – we can
perturb the scales for all weights and activations simultaneously by
perturbing $\Delta$. We perturb by sampling from a uniform ball centered
around $\Delta$:

$\boldsymbol{\Delta}_{\texttt{new}}\sim\mathcal{U}(\boldsymbol{\Delta},-\epsilon,\epsilon)$
(4)

where $\epsilon$ controls the size of the uniform ball. Perturbations within a
small $\epsilon$-ball ($\epsilon\approx 10^{-4}$) yields a change in accuracy
of $\pm 1\%$ top-1 accuracy for $4$-bit quantization. This is the same order
of magnitude used to compare a variety of quantization methods, further
illustrating that small perturbations matter considerably for quantization
performance.

We will show in sequel how evolutionary search can quickly evaluate multiple
perturbations and choose which local minima to hop into.

###  3.3 Global Search for Quantization Scales

As previously mentioned, we perturb the quantization scales ($\Delta$) for one
attention block at a time. If we perturb too many scales at once, we end up
traversing a very high dimensional search space and the number of iterations
for evolutionary search convergence increases exponentially. Of course,
gradient descent is often effective for such large search spaces, but first-
order methods will not work well in our non-smooth loss regime. After
partitioning our search space in a block-wise manner, we find evolutionary
search to perform well and achieve acceptable convergence times (on par with
the runtime of other PTQ methods).

We apply a small evolutionary search algorithm for each attention block (shown
in Fig. 2), and repeat this for all blocks in the model. A block’s
evolutionary search algorithm has $C$ cycles, where each cycle spawns a
perturbation. The search population is initially set to $|K|$ copies of the
original scale, and each cycle progressively updates the population of scales.
During one cycle, we choose a parent scale from the population and a
perturbation (child scale) is then spawned from the uniform distribution
parameterized by the parent scale (see Eq. 4). The child scales are then
placed into the population for the next cycle. We evaluate each child scale
using the fitness function defined in Algorithm 2 which applies a global
infoNCE loss. The block-wise search algorithm is shown in Algorithm 1. We
refer the reader to evolutionary computing literature [9] for more details on
parent, child, and fitness function.

In summary, our block-wise evolutionary search consists of $P$ passes over all
attention blocks. For each attention block $b$, we apply a small evolutionary
algorithm for $C$ cycles, meaning that each block’s quantization scale is
adjusted $P\times C$ times. A full enumeration of the search settings are in
Tab. 1.

Algorithm 1 Block-wise Evolutionary Search

Input: Calibration Dataset $D_{C}$
Quantized Model $M_{Q}$, Full Precision Model $M_{F}$
Number of passes $P$, cycles $C$
Population size $K$, Sample size $S$

1:for passes in 0 : $P$ do

2: $\triangleright$ traverse all attention blocks

3: for each attention block $b$ do

4: $\triangleright$ sub-problem illustrated in Fig. 2

5: pop $\leftarrow$ [ ]

6: $\triangleright$ init population with $K$ perturbations

7: while $|$ pop $|$ $<$ $K$ do

8: $\triangleright$ Fitness defined in Algorithm 2

9: fitness $\leftarrow$ Fitness($b$, $M_{Q}$, $M_{F}$, $D_{C}$)

10: pop.insert(($\boldsymbol{\Delta}_{\texttt{b}}$, fitness))

11: $\triangleright$ Iterate to find best child $\Delta$

12: for cycles in 0 : $C$ do

13: $\triangleright$ From population, sample a parent $\Delta$

14: samples $\leftarrow$ [ ]

15: while $|$ samples $|$ $<$ $S$ do

16: samples $\leftarrow$ RandomElement(pop)

17: parent $\leftarrow$ BestFitness(samples)

18:

19: $\triangleright$ Generate child and add to population

20: $\boldsymbol{\Delta}_{\texttt{child}}$ $\leftarrow$
Perturb($\boldsymbol{\Delta}_{\texttt{parent}}$)

21: fitness $\leftarrow$ Fitness($D_{C}$, $M_{Q}$, $M_{F}$ )

22: pop.insert( ($\boldsymbol{\Delta}_{\texttt{child}}$, fitness ) )

23: $\triangleright$ remove candidate with lowest fitness

24: pop.DeleteDead()

25: $\triangleright$ Choose best perturbation as b’s final $\Delta$

26: $\boldsymbol{\Delta}_{\texttt{b}}$ $\leftarrow$ BestFitness(pop)

27:return $M_{Q}$ $\triangleright$ model with updated scales

###  3.4 The infoNCE Loss for Scale Search

If we apply evolutionary search on the test loss landscape, we can quickly
traverse the space of local minima and find the best quantization scale.
Unfortunately, the test loss is not known to us, and the small calibration
dataset may produce a loss landscape that is different from the true loss
landscape. We find that the infoNCE loss can incorporate negative samples to
reduce the model’s tendency to overfit on positive bias.

The infoNCE loss is a common contrastive loss function used in self-supervised
learning to smooth the loss landscape [10], prevent representation collapse
[12] and encourage discrimination between the target representation and a set
of negative examples. We find the infoNCE loss to be very effective to prevent
overfitting of a quantized network’s representation in the same way that it is
used to develop richer representations in a self-supervised setting [10] (see
supplementary materials for details). Inspired by Chen et al. [5], we use the
infoNCE [25] loss:

$\mathcal{L}_{c}=-\log\frac{\exp(p\cdot o^{+}/\tau)}{\exp(p\cdot
o^{+}/\tau)+\sum_{o^{-}}\exp(p\cdot o^{-}/\tau)}$ (5)

where $p$ is the prediction of the quantized model. The infoNCE loss is
sampled within the full-precision model’s batch, where $o^{+}$ is the
corresponding prediction to $p$, and $o^{-}$ is a prediction of other images
in the same batch. In Algorithm 2, we show how the infoNCE is evaluated in the
fitness function for Evol-Q.

Algorithm 2 Fitness Function

Input: calibration dataset $D_{C}$
quantized model $M_{Q}$, full precision model $M_{F}$

1:for batch in $D_{C}$ do

2: p = $M_{Q}$(batch)

3: o = $M_{F}$(batch)

4: score += infoNCE(p, o) $\triangleright$ Eq. 5

5:return score / size($D_{C}$)

##  4 Results

In the following section, we present results on a variety of vision
transformers and show the consistency of our method under standard $8$-bit
quantization and in extreme quantization schemes ($3$-bit and $4$-bit
weights). We present results for end-to-end quantization, where all weights
and activations are quantized.

###  4.1 Setup

In our post-training (PTQ) setup, the calibration dataset is $1,000$ randomly
sampled images from the ImageNet training set. Experiments are conducted on
ImageNet (ILSVRC2012), and we evaluate top-1 accuracy for a variety of ViT
model families. For Evol-Q, the initial quantized model ($M_{Q}$ in Algorithm
1) is generated using FQ-ViT, and our method perturbs its quantization scales
to yield better performance. FQ-ViT is an end-to-end quantization framework
that uses MinMax [14] for weight quantization and Log2 [3] for activation
quantization. We refer to FQ-ViT and our code for other quantization settings.
The Evol-Q search parameters (from Algorithm 1) are in Tab. 1.

passes | $P$ | 10
---|---|---
population size | $K$ | 15
cycles | $C$ | 3
samples | $S$ | 10
mutation range | $\epsilon$ | $10^{-3}/10^{-4}$
Table 1: Block-wise evolutionary search settings. The mutation range is
$10^{-3}$ for 8W8A, and $10^{-4}$ for 4W8A and 3W8A.

###  4.2 8-bit Quantization

We compare our standard 8-bit quantization with state-of-the-art methods in
Tab. 2. Evol-Q improves over existing end-to-end quantization techniques by
$0.1\%$, $1.2\%$, and $0.15\%$ for DeiT-Small, DeiT-Base, and ViT-Base,
respectively.

8-bit weights, 8-bit activations (8W8A)
---
Method | DeiT-T | DeiT-S | DeiT-B | ViT-B
PSAQ-ViT | 71.56 | 76.92 | 79.10 | 37.36
PTQ4ViT | - | 79.47 | 81.48 | 84.25
FQ-ViT | 71.61 | 79.17 | 81.20 | 83.31
PSAQ-ViT-V2† | 72.17 | 79.56 | 81.52 | -
Evol-Q (ours) | 71.63 | 79.57 | 82.67 | 84.40

† Does not quantize Softmax/GeLU layers

Table 2: Top-1 Accuracy on ImageNet using 8W8A quantization. -T, -S, & -B
refer to Tiny, Small, and Base models respectively.

We also compare with PSAQ-ViT-V2 [16] and find that it outperforms our method
by $0.5\%$ for DeiT-Tiny. However, PSAQ-ViT-V2 is not a full end-to-end
quantization method since it does not quantize the activations following the
Softmax and GeLU layers. These activations are typically very sensitive to
quantization and are often maintained at full precision. We applied Evol-Q on
an end-to-end quantized model, so we are forced to quantize the post-
Softmax/GeLU activations. We leave it to future work to apply our technique on
top of PSAQ-ViT-V2, but expect similar improvements to what we achieved with
FQ-ViT.

###  4.3 4-bit Quantization

Moving from $8$-bit to $4$-bit weight quantization, we see an accuracy
degradation of about $2-5\%$ across all models. In Tab. 3, Evol-Q performs
similarly to what is shown for 8-bit quantization. In particular, we still see
improvement for DeiT-Small, DeiT-Base, and ViT-Base, but now the top-1
accuracy improvement is $0.13\%$, $0.16\%$, and $0.77\%$, respectively.

4-bit weights, 8-bit activations (4W8A)
---
Method | DeiT-T | DeiT-S | DeiT-B | ViT-B
PSAQ-ViT | 65.57 | 73.23 | 77.05 | 25.34
PTQ4ViT | - | - | 64.39 | -
FQ-ViT | 66.91 | 76.93 | 79.99 | 78.73
PSAQ-ViT-V2† | 68.61 | 76.36 | 79.49 | -
Evol-Q (ours) | 67.29 | 77.06 | 80.15 | 79.50

† Does not quantize Softmax/GELU layers

Table 3: Top-1 Accuracy on ImageNet using 4W8A quantization.

###  4.4 3-bit Quantization

We report 3-bit quantization results in Tab. 4 to show that Evol-Q extends to
more extreme quantization scenarios. In particular, Evol-Q improves accuracy
over FQ-ViT by $10.3\%$ for ViT-Base and $3.7\%$ for DeiT-Tiny.

3-bit weights, 8-bit activations (3W8A)
---
Method | DeiT-T | DeiT-S | DeiT-B | ViT-B
FQ-ViT | 35.79 | 60.58 | 72.11 | 55.33
Evol-Q (ours) | 39.45 | 61.16 | 72.41 | 65.63
Table 4: Top-1 Accuracy on ImageNet with 3W8A quantization.

By reducing the precision from $32$ to $3$ bits, we achieve a $>$10X reduction
in memory footprint while still maintaining a reasonable accuracy for DeiT-
Base. We refer to supplementary materials for ablations on using OMSE [7] and
bias correction [2] for 3W8A which dramatically improves our method’s
performance.

###  4.5 Extending to Swin & LeViT Models

We run our experiments on additional model families to ensure that our method
is applicable to different types of attention blocks. Swin transformers [21]
have the same macro-architecture as DeiT and ViT models, with the exception
that the Swin transformer block is a windowed attention. We see results for
4-bit Swin transformers in Tab. 5.

Method | Swin-T | Swin-S | Swin-B
---|---|---|---
PSAQ-ViT | 71.79 | 75.14 | -
PSAQ-ViT-V2† | 76.28 | 78.86 | -
FQ-ViT | 80.73 | 82.13 | 82.73
Evol-Q (ours) | 80.43 | 82.63 | 83.07

† Does not quantize Softmax/GELU layers

Table 5: Top-1 Accuracy for 4W8A Swin Models.

Prior quantization techniques do not consider LeViT models, a family of ViTs
that improve the inference speed of existing transformers. Using a longer
convolutional backbone, they can achieve similar results to classic ViTs while
also reducing the complexity of the transformer blocks in favor of ResNet-like
stages. We include the LeViT family in our experiments to illustrate how our
method can be extended beyond the standard block size. We can see 4W8A results
for the LeViT model family in Tab. 6. Across the board, we see a significant
improvement in LeViT quantization as compared to FQ-ViT, our baseline.

| LeViT | LeViT | LeVit | LeViT
---|---|---|---|---
Method | -128S | -192 | -256 | -384
FQ-ViT | 14.90 | 17.00 | 61.33 | 64.60
Evol-Q (ours) | 29.20 | 30.37 | 64.57 | 69.50
Table 6: Top-1 Accuracy for 4W8A LeViT models.

In fairness, we have not applied any other techniques to boost LeViT’s
accuracy (doing so may inflate our method’s improvement), so we leave it to
future work to incorporate other quantization techniques on top of our
framework.

##  5 Analysis

In the following section, we support the three observations set forth in the
introduction. First, we show how the non-smooth ViT loss landscape compares
with the CNN one, and discuss how a variety of loss functions perform in the
Evol-Q framework. Next, we visualize the layer-wise weight distributions to
illustrate how small perturbations can yield a significant jump in accuracy.
Finally, we report runtime and various ablations to contextualize our method
in the broader space of quantization techniques. For more ablations and
analysis, please refer to the supplementary materials.

(a) Resnet-18 loss landscape

(b) DeiT-Tiny loss landscape

Figure 3: A comparison of the test loss landscapes for 4-bit quantized CNNs
and ViTs. In Fig. 3(a), we show how small perturbations in the $4^{th}$
convolutional layer yields a smooth test loss landscape. In Fig. 3(b), we
apply perturbations to attention block #10 and the resultant loss landscape is
highly non-smooth.

###  5.1 The Test Loss Landscape of ViTs

In Fig. 3, we show that perturbing quantization scale yields a smooth test
loss landscape for ResNet-18 and a jagged, non-smooth landscape for DeiT-Tiny.
This loss landscape illustrates how the test loss is related to the
$\Delta_{10}$ scale at block #10. We perturb along two basis vectors for the
$\Delta_{10}$ and observe the effect on the test loss. The DeiT-Tiny loss
landscape is very complex and highly non-linear, whereas the ResNet-18
landscape is comparatively smooth. Intuitively, we hypothesize that the
presence of many GeLUs and Softmax functions induces in the DeiT loss
landscape many more extreme points than in the ResNet loss landscape.

For the smooth landscape in Fig. 3(a), the infoNCE loss is clearly optimal
since it is closest to the global minimum. If we plot the MSE, Cosine
(Cossim), and Fisher loss landscapes, we find that they are not as smooth as
the infoNCE loss in the CNN case (see supplementary materials, Sec A). The
infoNCE loss helps to provide a smoother loss with respect to the calibration
dataset by incorporating negative samples to reduce bias [10].

In the non-smooth landscape, Fig. 3(b), the global minimum is very hard to
find. In fact, proximity to the global loss in this landscape is not a good
indicator of loss function quality, since there are many local maxima in close
proximity (with an $\epsilon$\- ball) of the global minimum. In Sec. 5.3, we
provide an empirical justification that the infoNCE loss prevents overfitting
and is superior to other loss functions.

Figure 4: A zoomed in section of the landscape in Fig. 3(b), where we perform
gradient descent and evolutionary search for three initial points. We show the
solutions of evolutionary search ($\hat{X}_{evol}$ ) and gradient descent
($\hat{X}_{GD}$) after 10 iterations.

(a) Query, Key, Value

(b) Projection Layer

(c) FC Layer #1

(d) FC Layer #2

Figure 5: Loss Landscapes for the 4-bit quantized QKV, Projection, and Fully
Connected (FC) layers in self-attention block #5. We perturb the the
quantization scale along two basis vectors (Perturbation 1 & 2) to visualize
the loss landscape. These landscapes capture a zoomed in region around the
global minimum of the full landscape. The FC layers exhibit relative
smoothness around the global minimum whereas the QKV & Projection layers are
not easily traversible. The Projection layer is particularly difficult for
gradient methods because it has 4 deep minima in close proximity to the global
minimum.

###  5.2 Gradient Descent vs. Evolutionary Search

In Fig. 4, we show how evolutionary search finds candidates close the local
minima, whereas gradient descent breaks down the ViT loss landscape. We show
three initial points, where gradient descent either oscillates (init 3) or
does not converge to a local minima (init 1 and 2). In contrast, evolutionary
search generates a candidate perturbation and steps in the direction of the
best candidate. We find that evolutionary search is very good at finding the
closest local minima, which is sufficient to get an accuracy boost of $\sim
0.4\%$ in this loss landscape.

In Table 7, we show quantitatively that gradient-based optimizers underperform
in comparison to evolutionary search for the same block-wise setting as in
Evol-Q. We believe that non-smoothness at the block level is what makes these
gradient-based techniques ineffective.

Method | DeiT-T | DeiT-S | DeiT-B | ViT-B
---|---|---|---|---
SGD | 71.57 | 79.25 | 81.24 | 83.40
Adam | 71.29 | 79.25 | 81.24 | 83.25
AdamW | 71.37 | 79.00 | 81.30 | 83.36
Evol-Q (ours) | 71.63 | 79.57 | 82.67 | 84.40

Table 7: Comparison with gradient-based optimizers using 8-bit weights, 8-bit
activations (8W8A).

###  5.3 Loss Function Choice

We compare the infoNCE (contrastive) loss with other common loss functions in
Fig. 6. We find mean-squared error (MSE) to be equally (if not more) effective
in the initial iterations of Evol-Q. However, as the number of passes grows,
MSE does not perform as well as the infoNCE loss. Both cosine similarity and
the Kullback–Leibler divergence (KL) fail to improve performance as the number
of iterations increases. We postulate that the poor performance of these
traditional loss functions is due to overfitting to the calibration dataset.
On the other hand, the infoNCE loss is naturally regularized by the negative
samples in the batch, allowing for it to preserve the quantization parameters
that help discriminate between classes.

Figure 6: Comparing four loss functions in the Evol-Q framework on ViT-Base.
The infoNCE (contrastive) loss prevents overfitting to the calibration
dataset, whereas all other loss functions cannot improve accuracy beyond the
initialized quantization scheme.

###  5.4 Which layers contribute to non-smoothness?

In Fig. 5, we visualize which layers of the self-attention mechanism yield the
non-smooth loss curve. We show that learning the quantization scale for query,
key, value (QKV) and projection layers is more difficult because their loss
landscape is filled with local minima. We observe this property across
different self-attention blocks and advocate for using ES to jump through the
field of local minima.

###  5.5 Layer-wise Weight Distributions

In Fig. 7, we compare the weight distributions of the full precision, FQ-ViT,
and Evol-Q quantization schemes. Evol-Q’s quantized values are only a small
adjustment of FQ-ViT’s, yet Evol-Q has a $0.8\%$ improvement. In summary, a
small adjustment in scale yields a significant boost in accuracy.

Figure 7:  The weight distribution of the projection layer for attention block
#1 of ViT-Base. The top plot shows the full precision weight distribution and
the bottom plot shows the 8-bit weights using both FQ-ViT and Evol-Q.

This observation is consistent with results in AdaRound [23], where authors
show how choosing the correct rounding scheme can significantly impact
performance. Unlike AdaRound [23], our method traverses the global loss
landscape (rather than a layer-wise proxy) whereas AdaRound assumes a diagonal
Hessian which does not hold in the ViT landscape.

We refer to Sec. F of the supplementary materials for more discussion on
layer-wise distributions.

###  5.6 Generalization to CNNs

Our method begins with a pre-quantized model, $M_{Q}$, and adjusts the
quantization scales to improve accuracy. We only require that the model can be
abstracted into blocks, which makes our method readily applicable to other
types of models such as CNNs, LSTMs, and Graph Neural Networks. In Tab. 8, we
show how Evol-Q is run on top of BRECQ to achieve state-of-the-art CNN
quantization. In this case, our block is one convolutional layer and $\Delta$
is the stacked vector of quantization scales for the one layer’s weight
matrix. We find Evol-Q’s method to be suitable for CNN quantization, achieving
1-2.5% accuracy boost over BRECQ for 4-bit quantization. We refer to
supplementary material for an explanation of using the infoNCE loss to smooth
out the CNN loss landscape.

| ResNet-18 | ResNet-50 | RegNet-3.2GF
---|---|---|---
BRECQ [16] | 69.60 | 75.05 | 74.21
Evol-Q† | 70.10 | 77.30 | 76.87

† Using BRECQ[16] as pre-quantized model $M_{Q}$

Table 8: Top-1 Accuracy on ImageNet using 4W4A quantization.

###  5.7 Pareto Front for 8-bit Quantized ViTs

Evol-Q improves over existing PTQ techniques for vision transformers. In Fig.
8, Evol-Q is on the Pareto front in terms of both top-1 accuracy and runtime
for 8-bit ViT-Base. Current ViT-specific QAT methods [19, 30] do not report
8-bit accuracy, so we do not include them here. These QAT methods are likely
to reach the Pareto front, but would take much longer than existing PTQ
methods.

All open-source methods are run on a single Nvidia A100 GPU, but some code is
not open-sourced at the time of submission. PSAQ-ViT-V2 does not report
runtime, so we estimate it to be $60$ minutes based on PSAQ-ViT and the
relative cost of additional steps.

Figure 8: The runtime of 8-bit quantization methods for ViTs. We consider PTQ
methods, and show the potential for QAT methods (orange square).

###  5.8 Runtime

We run our method on an Nvidia A100-PCIE-40GB Tensor Core GPU and find that
all experiments take less than one hour to run. The average runtime is shown
in Tab. 9. We use PyTorch 1.9.1, built with the CUDA 11.1 toolkit.

| DeiT-T | DeiT-S | DeiT-B | ViT-B
---|---|---|---|---
Runtime (m) | 41.5 | 46.3 | 41.6 | 43.2
Table 9: Evol-Q Runtime (in minutes) on one Nvidia A100 GPU

In Fig. 8, we compare runtime with other ViT quantization methods and
demonstrate that our method achieves superior accuracy on ViT-Base. Fig. 8
only captures the Top-1 Accuracy of ViT-Base (or, alternatively, DeiT-base if
ViT-Base is unavailable). We refer to the supplementary material for a wider
discussion on how this plot changes with different models.

##  6 Conclusion

Evol-Q achieves state-of-the-art results on ViT’s highly non-smooth loss
landscape with a high density of extremal points. Prior work on ViT
quantization does not address the non-smooth loss landscape, nor how small
perturbations in quantization scale can affect performance. Using evolutionary
search and an infoNCE loss, Evol-Q evaluates small perturbations in
quantization scale, improving accuracy by $\sim 0.5\%$ for 4-bit quantized
vision transformers.

##  7 Acknowledgements

Partial work completed during a summer internship at Arm Ltd. A special thank
you to Jesse Beu for overseeing this internship project, and to Feng Liang for
helpful discussion. This work was sponsored by NSF CCF Grant No. 2107085 and
the UT Cockrell School of Engineering Doctoral Fellowship.

## References

  * [1] Haoli Bai, Wei Zhang, Lu Hou, Lifeng Shang, Jing Jin, Xin Jiang, Qun Liu, Michael Lyu, and Irwin King.  Binarybert: Pushing the limit of bert quantization.  arXiv preprint arXiv:2012.15701, 2020.
  * [2] Ron Banner, Yury Nahshan, and Daniel Soudry.  Post training 4-bit quantization of convolutional networks for rapid-deployment.  Advances in Neural Information Processing Systems, 32, 2019.
  * [3] Jingyong Cai, Masashi Takemoto, and Hironori Nakajo.  A deep look into logarithmic quantization of model parameters in neural networks.  In Proceedings of the 10th International Conference on Advances in Information Technology, pages 1–8, 2018.
  * [4] Yun-Hao Cao, Peiqin Sun, Yechang Huang, Jianxin Wu, and Shuchang Zhou.  Synergistic self-supervised and quantization learning.  In European Conference on Computer Vision, pages 587–604. Springer, 2022.
  * [5] Xinlei Chen, Saining Xie, and Kaiming He.  An empirical study of training self-supervised vision transformers.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 9640–9649, 2021.
  * [6] Yoojin Choi, Jihwan Choi, Mostafa El-Khamy, and Jungwon Lee.  Data-free network quantization with adversarial knowledge distillation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pages 710–711, 2020.
  * [7] Yoni Choukroun, Eli Kravchik, Fan Yang, and Pavel Kisilev.  Low-bit quantization of neural networks for efficient inference.  In 2019 IEEE/CVF International Conference on Computer Vision Workshop (ICCVW), pages 3009–3018. IEEE, 2019.
  * [8] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  arXiv preprint arXiv:2010.11929, 2020.
  * [9] Agoston E Eiben and James E Smith.  Introduction to evolutionary computing.  Springer, 2015.
  * [10] Philip Fradkin, Lazar Atanackovic, and Michael R Zhang.  Robustness to adversarial gradients: A glimpse into the loss landscape of contrastive pre-training.  In First Workshop on Pre-training: Perspectives, Pitfalls, and Paths Forward at ICML 2022.
  * [11] Yonggan Fu, Qixuan Yu, Meng Li, Xu Ouyang, Vikas Chandra, and Yingyan Lin.  Contrastive quant: quantization makes stronger contrastive learning.  In Proceedings of the 59th ACM/IEEE Design Automation Conference, pages 205–210, 2022.
  * [12] Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, et al.  Bootstrap your own latent-a new approach to self-supervised learning.  Advances in neural information processing systems, 33:21271–21284, 2020.
  * [13] Itay Hubara, Yury Nahshan, Yair Hanani, Ron Banner, and Daniel Soudry.  Accurate post training quantization with small calibration sets.  In International Conference on Machine Learning, pages 4466–4475. PMLR, 2021.
  * [14] Benoit Jacob, Skirmantas Kligys, Bo Chen, Menglong Zhu, Matthew Tang, Andrew Howard, Hartwig Adam, and Dmitry Kalenichenko.  Quantization and training of neural networks for efficient integer-arithmetic-only inference.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2704–2713, 2018.
  * [15] Yuhang Li, Ruihao Gong, Xu Tan, Yang Yang, Peng Hu, Qi Zhang, Fengwei Yu, Wei Wang, and Shi Gu.  Brecq: Pushing the limit of post-training quantization by block reconstruction.  arXiv preprint arXiv:2102.05426, 2021.
  * [16] Zhikai Li, Mengjuan Chen, Junrui Xiao, and Qingyi Gu.  Psaq-vit v2: Towards accurate and general data-free quantization for vision transformers.  arXiv preprint arXiv:2209.05687, 2022.
  * [17] Zhikai Li and Qingyi Gu.  I-vit: Integer-only quantization for efficient vision transformer inference.  arXiv preprint arXiv:2207.01405, 2022.
  * [18] Zhengang Li, Mengshu Sun, Alec Lu, Haoyu Ma, Geng Yuan, Yanyue Xie, Hao Tang, Yanyu Li, Miriam Leeser, Zhangyang Wang, et al.  Auto-vit-acc: An fpga-aware automatic acceleration framework for vision transformer with mixed-scheme quantization.  arXiv preprint arXiv:2208.05163, 2022.
  * [19] Zhexin Li, Tong Yang, Peisong Wang, and Jian Cheng.  Q-vit: Fully differentiable quantization for vision transformer.  arXiv preprint arXiv:2201.07703, 2022.
  * [20] Yang Lin, Tianyu Zhang, Peiqin Sun, Zheng Li, and Shuchang Zhou.  Fq-vit: Post-training quantization for fully quantized vision transformer.  In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, pages 1173–1179, 2022.
  * [21] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo.  Swin transformer: Hierarchical vision transformer using shifted windows.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 10012–10022, 2021.
  * [22] Zhenhua Liu, Yunhe Wang, Kai Han, Wei Zhang, Siwei Ma, and Wen Gao.  Post-training quantization for vision transformer.  Advances in Neural Information Processing Systems, 34:28092–28103, 2021.
  * [23] Markus Nagel, Rana Ali Amjad, Mart Van Baalen, Christos Louizos, and Tijmen Blankevoort.  Up or down? adaptive rounding for post-training quantization.  In International Conference on Machine Learning, pages 7197–7206. PMLR, 2020.
  * [24] Yury Nahshan, Brian Chmiel, Chaim Baskin, Evgenii Zheltonozhskii, Ron Banner, Alex M Bronstein, and Avi Mendelson.  Loss aware post-training quantization.  Machine Learning, 110(11):3245–3262, 2021.
  * [25] Aaron van den Oord, Yazhe Li, and Oriol Vinyals.  Representation learning with contrastive predictive coding.  arXiv preprint arXiv:1807.03748, 2018.
  * [26] Yuzhang Shang, Dan Xu, Ziliang Zong, Liqiang Nie, and Yan Yan.  Network binarization via contrastive learning.  In Computer Vision–ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23–27, 2022, Proceedings, Part XI, pages 586–602. Springer, 2022.
  * [27] Sangeetha Siddegowda, Marios Fournarakis, Markus Nagel, Tijmen Blankevoort, Chirag Patel, and Abhijit Khobare.  Neural network quantization with ai model efficiency toolkit (aimet).  arXiv preprint arXiv:2201.08442, 2022.
  * [28] Han Vanholder.  Efficient inference with tensorrt.  In GPU Technology Conference, volume 1, page 2, 2016.
  * [29] Di Wu, Qi Tang, Yongle Zhao, Ming Zhang, Ying Fu, and Debing Zhang.  Easyquant: Post-training quantization via scale optimization.  arXiv preprint arXiv:2006.16669, 2020.
  * [30] Sheng Xu, Yanjing Li, Teli Ma, Bohan Zeng, Baochang Zhang, Peng Gao, and Jinhu Lu.  Tervit: An efficient ternary vision transformer.  arXiv preprint arXiv:2201.08050, 2022.
  * [31] Zhihang Yuan, Chenhao Xue, Yiqi Chen, Qiang Wu, and Guangyu Sun.  Ptq4vit: Post-training quantization for vision transformers with twin uniform quantization.  In Computer Vision–ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23–27, 2022, Proceedings, Part XII, pages 191–207. Springer Nature Switzerland Cham, 2022.


# Equilibria and incentives for illiquid auction markets

Joffrey Derchu111École Polytechnique, CMAP, 91128, Palaiseau, France,
<EMAIL_ADDRESS>Dimitrios Kavvathas222Harmony Advisors Ltd.;
<EMAIL_ADDRESS>Thibaut Mastrolia333Department of
Industrial Engineering and Operations Research, UC Berkeley;
<EMAIL_ADDRESS>
and Mathieu Rosenbaum444École Polytechnique, CMAP;
<EMAIL_ADDRESS>555This work benefits from the financial
support of the Chaires Analytics and Models for Regulation, Deep finance and
statistics, Machine learning and systematic methods.

###### Abstract

We study a toy two-player game for periodic double auction markets to generate
liquidity. The game has imperfect information, which allows us to link market
spreads with signal strength. We characterize Nash equilibria in cases with or
without incentives from the exchange. This enables us to derive new insights
about price formation and incentives design. We show in particular that
without any incentives, the market is inefficient and does not lead to any
trade between market participants. We however prove that quadratic fees
indexed on each players half spread leads to a transaction and we propose a
quantitative value for the optimal fees that the exchange has to propose in
this model to generate liquidity.
Keywords: double auction, Nash equilibrium, game with imperfect information.

##  1 Introduction

Auctions are becoming an increasingly popular trading mechanism. In such
market design, market participants typically send market and limit orders
during some (randomized) period of time. At the end of this period, a clearing
price is set so that it maximises the traded volume. Some exchanges offer
auctions in a periodic way throughout the day, such as BATS-CBOE for European
equities. More generally, many platforms use auctions at the beginning and at
the end of the day, often collecting a very significant part of the daily
traded volume at these specific times. The large interest in auctions in the
recent years is notably due to the role of high frequency trading in the
modification of the financial markets ecosystem. In some influential papers
such as [Budish et al., 2015, Du and Zhu, 2017, Farmer and Skouras, 2012,
Madhavan, 1992, Wah and Wellman, 2013] the authors explore flaws of limit
order books and argue that high frequency traders operating in a continuous
limit order book generate negative externalities for investors due to their
speed advantage. By their very definition, auctions mechanically slow down the
market and therefore are a remedy to some of the supposed inherent flaws of
continuous limit order books associated to ultra fast trading. Inspired by [Du
and Zhu, 2017, Duffie and Zhu, 2017, Antill and Duffie, 2021], [Jusselin et
al., 2021] shows that from a price discovery viewpoint, the optimal auction
duration is between 1 and 10 minutes for typical stocks. In addition they
demonstrate that continuous limit order books are in general a sub-optimal
market mechanism. Combination of auctions and continuous limit order books are
investigated in [Derchu et al., 2020]. Furthermore, for illiquid assets,
offering continuous trading is probably not required to obtain a satisfactory
price formation process. Therefore, auctions appears as a natural and cost
efficient design for an exchange.

In this work, we are interested in understanding the behavior of market
participants during an auction in a illiquid market. We show in particular how
incentives allow the exchange to create new market equilibria and generate
liquidity. By illiquid we mean a market where trading frequency is low,
volumes are small, market data is limited and information is scarce. In this
framework, we use a notion of efficient price, to be understood as a partially
known long term value of the asset, also often called the “fair” price. Since
we consider an illiquid market, at a given time point, it may be significantly
different from the last traded price.

We model this market by a very simplified one period framework with two
participants, one buyer and one seller, taking part to an auction organized by
an exchange. At the time of the auction, we assume that the increment between
the fair price, denoted by $P_{\infty}$ and the last traded price is given by
a centered Gaussian variable with variance $v^{2}$. The parameter $v$ can be
interpreted as the degree of illiquidity of our market. A large $v$ can for
instance translate the fact that auctions are not very frequent, leading to
large fluctuations of the fair price between them. It can also mean that the
asset is simply very volatile, for example because of the uncertainty about
its value due to limited available information.

We assume both participants have access to a proxy of the fair price at the
beginning of the auction, denoted by $P_{\infty|a}$ for the seller and
$P_{\infty|b}$ for the buyer. The standard deviations of the error of this
proxy are drawn from independent random variables, denoted by $\sigma_{a}$ and
$\sigma_{b}$. These standard deviations are specific to each market
participant and represent their degree of sophistication. Using his personal
information, the buyer agent computes a maximal price at which he is willing
to buy and send a limit order, and symmetrically for the seller one. Inspired
by standard quoting mechanisms, we suppose that the agents build their quote
as a deviation from their proxy depending on their uncertainty about the
quality of their proxy. Therefore these quotes take the form
$P_{\infty|i}\pm\delta_{i}(\sigma_{i})$ for $i=a,b$. More precisely, we are
interested in the symmetric case where market participants have the same
pricing rule and consequently the function $\delta_{i}$ does actually not
depend on $i$. If the buy limit order price is larger than the sell limit
order price, a trade happens at the midprice. So, for a given function
$\delta$, each (risk neutral) agent optimizes simultaneously the price of its
limit order by maximizing or minimizing the expected value of the difference
between the obtained midprice and the fair price, taking into account the
probability that no trade happens.

The goal of this paper is to study the situations where such game leads to a
viable market. To do so, we aim at finding Nash equilibria. A Nash equilibrium
in our context simply consists in the existence of a function $\delta$ such
that both market participants can optimize at the same time and have no
interest to deviate from the computed optima. We actually show that in such
framework, Nash equilibria usually do not exist. This is bad news from an
exchange or regulator perspective as it tells us that even in a very
simplified setting, we can expect unstable behaviours from market
participants. To remedy this, we consider that the exchange is able to put in
place a make-take fees system, where he rewards or penalizes market
participants with respect to the quality of their quotes. We first study the
case where the penalty on market participants depends on the price formation
process: participants are penalized if the auction clearing price is far from
the efficient price. Then we consider the situation where the penalty is
computed from the displayed spreads. Interestingly, we establish that one can
recover Nash equilibria with the second mechanism while the first one does not
enable us to do so. We also explain how to design optimally the spread penalty
leading to Nash equilibrium.

The paper is organized as follows. We start by introducing the model and the
assumptions in Section 2. Then we consider the case where an exchange imposes
penalties on the players in Section 3. Section 4 gathers the numerical
results. We study some extensions of our framework in Section 5. Finally, some
proofs are relegated to the appendix.

##  2 The game

We consider two players, Player $a$ and Player $b$ aiming at trade an asset.
Player $a$ sends a sell limit order at a price $P^{a}\in\mathbb{R}$ while
Player $b$ sends a buy limit order at the price $P^{b}\in\mathbb{R}$. Both
players announce their price simultaneously. If $P^{a}\leq P^{b}$, a trade
occurs at the price $\frac{P^{a}+P^{b}}{2}$. In this case, player $a$ sells
one unit at the price $\frac{P^{a}+P^{b}}{2}$ to player $b$. From now on,
Player $a$ is always selling ($a$ stands for ‘ask’) and Player $b$ is always
buying ($b$ stands for ‘bid’). We could easily extend our framework to the
case where our two players send both buy and sell orders.

We assume that there exists on this market an efficient price of the asset
denoted by $P_{\infty}$. At the time of the auction, the increment between
this fair price and the last traded price of the previous auction is normally
distributed with mean 0 and variance $v^{2}$ with $v\in\mathbb{R}$ and
possibly $v\to+\infty$. The parameter $v$ represents the degree of illiquidity
of the market. A large $v$ indicates that auctions are not very frequent
leading to possibly large fluctuation between the efficient price and the
auction price or that the asset is very volatile.

###  2.1 Efficient price estimation and market statistics

Due to the illiquid nature of our market, our players do not have access to
$P_{\infty}$. They can only estimate it based on some private information.
Each player $i=a,b$ compute his own private estimate $P_{\infty|i}$ of
$P_{\infty}$ defined by

$\displaystyle P_{\infty|a}=P_{\infty}+\boldsymbol{\sigma}_{a}\epsilon_{a}$
$\displaystyle P_{\infty|b}=P_{\infty}+\boldsymbol{\sigma}_{b}\epsilon_{b}$

where666From now on, bold letters are used to emphasize certain random
variables.

  * •

$\boldsymbol{\sigma}_{a},\boldsymbol{\sigma}_{b}$ denote player $i$’s
uncertainty in his estimate. We assume that $\boldsymbol{\sigma}_{a}$ and
$\boldsymbol{\sigma}_{b}$ are uniformly distributed on
$[\sigma_{-},\sigma_{+}]$, for some bounds $0<\sigma_{-}<\sigma_{+}$.

  * •

$\epsilon_{a}$ and $\epsilon_{b}$ are normally distributed with zero mean and
unit variance such that
$\text{Corr}(\epsilon_{a},\epsilon_{b})=\rho\in(-1,1)$.

  * •

The variables $P_{\infty},\boldsymbol{\sigma}_{a},\boldsymbol{\sigma}_{b}$ and
the couple $(\epsilon_{a},\epsilon_{b})$ are all independent from one another.

We assume that the only information available to each player $i$ is
$P_{\infty|i}$ and $\boldsymbol{\sigma}_{i}$. In particular the players do not
know the efficient price $P_{\infty}$, the other player’s signal
$P_{\infty|i}$ nor the other player’s confidence in his signal
$\boldsymbol{\sigma}_{i}$. Recalling that bold symbol stands for random
variables and to simplify notations, we set for some
$\sigma_{a},\sigma_{b}\in[\sigma_{-},\sigma_{+}]$

$\Sigma_{\rho}:=\sqrt{\sigma_{a}^{2}+\sigma_{b}^{2}-2\rho\sigma_{a}\sigma_{b}},\quad\boldsymbol{\Sigma}_{\rho}:=\sqrt{\boldsymbol{\sigma}_{a}^{2}+\boldsymbol{\sigma}_{b}^{2}-2\rho\boldsymbol{\sigma}_{a}\boldsymbol{\sigma}_{b}},\quad\boldsymbol{\Sigma}^{b}_{\rho}:=\sqrt{\sigma_{a}^{2}+\boldsymbol{\sigma}_{b}^{2}-2\rho\sigma_{a}\boldsymbol{\sigma}_{b}},$

$Q_{\rho}:=\frac{\frac{1}{\sigma_{b}^{2}}-\frac{\rho}{\sigma_{a}\sigma_{b}}}{\frac{1}{\sigma_{a}^{2}}+\frac{1}{\sigma_{b}^{2}}-2\frac{\rho}{\sigma_{a}\sigma_{b}}}=\frac{\sigma_{a}-\rho\sigma_{b}}{\Sigma_{\rho}^{2}},\quad\boldsymbol{Q}^{b}_{\rho}:=\frac{\frac{1}{\boldsymbol{\sigma}_{b}^{2}}-\frac{\rho}{\sigma_{a}\boldsymbol{\sigma}_{b}}}{\frac{1}{\sigma_{a}^{2}}+\frac{1}{\boldsymbol{\sigma}_{b}^{2}}-2\frac{\rho}{\sigma_{a}\boldsymbol{\sigma}_{b}}}=\frac{\sigma_{a}-\rho\boldsymbol{\sigma}_{b}}{|\boldsymbol{\Sigma}^{b}_{\rho}|^{2}},$

and

$\tilde{Q}_{\rho}:=\frac{\frac{1}{\sigma_{a}^{2}}-\frac{\rho}{\sigma_{a}\sigma_{b}}}{\frac{1}{\sigma_{a}^{2}}+\frac{1}{\sigma_{b}^{2}}-2\frac{\rho}{\sigma_{a}\sigma_{b}}}=\frac{\sigma_{b}-\rho\sigma_{a}}{\Sigma_{\rho}^{2}}.$

As explained in the introduction, we assume that the way market participants
form their prices $P^{a},P^{b}$ is as follows

$P^{a}=P_{\infty|a}+\delta(\boldsymbol{\sigma}_{a})\text{ and
}P^{b}=P_{\infty|b}-\delta(\boldsymbol{\sigma}_{b}),\text{ for some function
}\delta:[\sigma_{-},\sigma_{+}]\longrightarrow\mathbb{R}.$

Given a strategy $\delta$, statistics on the market quality can be easily
derived as stated in the proposition below.

######  Proposition 2.1.

Let $\delta$ be fixed, then we can compute the following quantities

  * •

Spread: $\mathbb{E}[P^{a}-P^{b}]=2\mathbb{E}[\delta(\boldsymbol{\sigma}_{a})]$

  * •

Variance of the spread:
$\mathbb{V}[P^{a}-P^{b}]=2(\mathbb{E}[\boldsymbol{\sigma}_{a}^{2}]-\rho\mathbb{E}[\boldsymbol{\sigma}_{a}]^{2}+\mathbb{V}[\delta(\boldsymbol{\sigma}_{a})])$

  * •

Average mid price-efficient price error:
$\mathbb{E}[\frac{P^{a}+P^{b}}{2}-P_{\infty}]=0$

  * •

Variance of the mid price-efficient price error:
$\mathbb{V}[\frac{P^{a}+P^{b}}{2}-P_{\infty}]=\frac{\mathbb{E}[\boldsymbol{\sigma}_{a}^{2}]+\rho\mathbb{E}[\boldsymbol{\sigma}_{a}]^{2}+\mathbb{V}[\delta(\boldsymbol{\sigma}_{a})]}{2}$

  * •

Trade occurrence: $\mathbb{P}[P^{a}\leq
P^{b}]=1-\mathbb{E}[\Phi(\frac{\delta(\boldsymbol{\sigma}_{a})+\delta(\boldsymbol{\sigma}_{b})}{\boldsymbol{\Sigma}_{\rho}})].$

We note that those results hold when $v$ is finite and at the limit
$v\to+\infty$.

The average error on the efficient price is zero which shows that if there is
an equilibrium a reasonable price formation process takes place. The variance
of the spread and the variance of the error on the efficient price are equal
up to a multiplicative constant. Interestingly, only the variance of
$\delta(\boldsymbol{\sigma}_{a})$ appears in the variance of the error on the
efficient price. In other words the relevance of the mid-price as an estimator
of the efficient price is not impaired if the spreads are uniformly increased
(if we add some constant to $\delta$). The quality of the mid-price proxy
decreases if the spreads are transformed linearly (if we multiply $\delta$ by
some constant larger than $1$). Note also that both variances are lower
bounded (by $2\mathbb{V}[\boldsymbol{\sigma}_{a}^{2}]$ and
$\frac{\mathbb{V}[\boldsymbol{\sigma}_{a}^{2}]}{2}$ respectively): this
implies that the market quality is limited by the quality of its participants,
and no amount of incentives to change $\delta$ could make the market better
than this limit. The number of trades is related in a non-trivial way to
$\delta$, though we still have the obvious result that a smaller $\delta$
leads to more trades. Positive correlation tends to fix the spread but damages
the price formation process.

###  2.2 Optimization and equilibrium

We assume that both players send their orders simultaneously without any
communication between them.

Given $\boldsymbol{\sigma}_{a}$ and $P_{\infty|a}$ and that Player $b$ sets
$P^{b}=P_{\infty|b}-\delta(\boldsymbol{\sigma}_{b}$), Player $a$ wants to
maximize over $x=P^{a}-P_{\infty|a}$ his expected payoff

$\displaystyle\mathbb{E}[(\frac{P_{\infty|a}+x+P_{\infty|b}-\delta(\boldsymbol{\sigma}_{b})}{2}-P_{\infty})\mathbf{1}_{P_{\infty|a}+x\leq
P_{\infty|b}-\delta(\boldsymbol{\sigma}_{b})}|(P_{\infty|a},\boldsymbol{\sigma}_{a})].$

We have the following proposition whose proof is in Appendix A.

######  Proposition 2.2.

Let $\delta$, $\sigma_{a}\in[\sigma_{-},\sigma_{+}]$ and
$p_{\infty|a}\in\mathbb{R}$ be fixed. Then

$\displaystyle
x\in\mathbb{R}\mapsto\mathbb{E}[(\frac{P_{\infty|a}+x+P_{\infty|b}-\delta(\boldsymbol{\sigma}_{b})}{2}-P_{\infty})\mathbf{1}_{P_{\infty|a}+x\leq
P_{\infty|b}-\delta(\boldsymbol{\sigma}_{b})}|(P_{\infty|a}=p_{\infty|a},\boldsymbol{\sigma}_{a}=\sigma_{a})]$

converges uniformly to

$\displaystyle
e^{\sigma_{a}}_{\delta}:x\mapsto\frac{1}{\sigma_{+}-\sigma_{-}}\int_{\sigma_{-}}^{\sigma^{+}}\big{(}$
$\displaystyle\frac{x-\delta(\sigma_{b})}{2}(1-\Phi(\frac{x+\delta(\sigma_{b})}{\Sigma_{\rho}}))+\Sigma_{\rho}(\frac{1}{2}-Q_{\rho})\Phi^{\prime}(\frac{x+\delta(\sigma_{b})}{\Sigma_{\rho}})\big{)}d\sigma_{b}$

as $v\to+\infty$, with $\Phi$ the cumulative distribution function of a
standard Gaussian variable. Note that $e^{\sigma_{a}}_{\delta}$ does not
depend on $p_{\infty|a}$.

Note that in the case where $v$ is finite, $e^{\sigma_{a}}_{\delta}$ could
depend on $P_{\infty|a}$. However, if we take $v\to+\infty$, the expected
payoff converges to a limit which does not depend on $P_{\infty|a}$ as this
limit corresponds to an extremely illiquid market.

######  Remark 2.3.

We can rewrite

$\displaystyle e^{\sigma_{a}}_{\delta}(x)$
$\displaystyle=\frac{1}{\sigma_{+}-\sigma_{-}}\int_{\sigma_{-}}^{\sigma^{+}}\big{(}\frac{x-\delta(\sigma_{b})}{2}(1-\Phi(\frac{x+\delta(\sigma_{b})}{\Sigma_{\rho}}))+\Sigma_{\rho}(\frac{1}{2}-Q_{\rho})\Phi^{\prime}(\frac{x+\delta(\sigma_{b})}{\Sigma_{\rho}})\big{)}d\sigma_{b}$
$\displaystyle=\mathbb{E}[\big{(}\frac{x-\delta(\boldsymbol{\sigma}_{b})}{2}+\tilde{\epsilon}_{\infty}\frac{1}{\sqrt{\frac{1}{\sigma_{a}^{2}}+\frac{1}{\boldsymbol{\sigma}_{b}^{2}}}}+\tilde{\epsilon}_{ab}\boldsymbol{\Sigma}^{b}_{\rho}(\frac{1}{2}-\boldsymbol{Q}_{\rho}^{b})\big{)}\mathbf{1}_{\tilde{\epsilon}_{ab}\geq\frac{x+\delta(\boldsymbol{\sigma}_{b})}{\boldsymbol{\Sigma}_{\rho}^{b}}}],$

where $(\tilde{\epsilon}_{ab},\tilde{\epsilon}_{\infty})$ is a bivariate
normal random variable centered with unit covariance matrix.

We now define a Nash equilibrium in our setting.

######  Definition 2.4 (Nash equilibrium (NE)).

Let $\delta$ be a function from $[\sigma_{-},\sigma_{+}]$ to
$\mathbb{R}_{+}^{*}$. We say that $\delta$ is a Nash equilibrium (NE) in the
case $v\to\infty$ if, for all $\sigma_{a}\in[\sigma_{-},\sigma_{+}]$, we
have777By symmetry we do not repeat this condition for Player $b$. If $\delta$
is an optimizer for Player $a$, it is also optimal for Player $b$.

$\displaystyle\delta(\sigma_{a})\in\arg\sup e^{\sigma_{a}}_{\delta}.$

From Remark 2.3 we deduce the following important lemma which is a first step
toward finding a Nash equilibrium.

######  Lemma 2.5.

Let $\delta$ be some non-negative function on $[\sigma_{-},\sigma_{+}]$,
$\sigma_{a}\in[\sigma_{-},\sigma_{+}]$. Assume that
$\rho\leq\frac{\sigma_{-}}{\sigma_{+}}$. Then $e^{\sigma_{a}}_{\delta}$
attains its maximum on $\mathbb{R}_{+}$.

###  2.3 No incentive, no equilibrium, no liquidity

The main result of this section is that, in our framework with symmetric
players and without any incentives, there is no Nash equilibrium.

######  Proposition 2.6.

There is no Nash equilibrium as defined in Definition 2.4.

###### Proof.

If $\sigma_{+}=\sigma_{-}$, we need
$1-\Phi(\frac{\sqrt{2}\delta(\sigma_{+})}{\sigma_{+}\sqrt{1-\rho^{2}}})=0$
which is impossible with $\delta(\sigma_{+})$ finite.

If $\sigma_{+}>\sigma_{-}$, we must have

$\displaystyle(e^{\sigma_{a}}_{\delta})^{\prime}(\delta(\sigma_{a}))$
$\displaystyle=\frac{1}{\sigma_{+}-\sigma_{-}}\int_{\sigma_{-}}^{\sigma^{+}}\big{(}\frac{1}{2}(1-\Phi(\frac{\delta(\sigma_{a})+\delta(\sigma_{b})}{\Sigma_{\rho}}))+\frac{1}{\Sigma_{\rho}}(-\delta(\sigma_{a})\tilde{Q}_{\rho}+\delta(\sigma_{b})Q_{\rho})\Phi^{\prime}(\frac{\delta(\sigma_{a})+\delta(\sigma_{b})}{\Sigma_{\rho}})\big{)}d\sigma_{b}$
$\displaystyle=0$

for all $\sigma_{a}\in[\sigma_{-},\sigma_{+}]$. Thus

$\displaystyle\int_{\sigma_{-}}^{\sigma^{+}}\int_{\sigma_{-}}^{\sigma^{+}}\big{(}\frac{1}{2}(1-\Phi(\frac{\delta(\sigma_{a})+\delta(\sigma_{b})}{\Sigma_{\rho}}))\big{)}d\sigma_{a}d\sigma_{b}=0$

which is impossible with $\delta$ finite. ∎

To mitigate the fact that there is no equilibrium in our framework, we
introduce some frictions under the form of transaction fees imposed by the
exchange, hoping that it can lead to a more viable market.

##  3 Optimal transaction costs to create liquidity

We introduce penalties in the players payoffs. This translates real-world
liquidity provision programs.

###  3.1 Price discovery penalty: inefficient policy

In this section, we assume that the exchange is able to know $P_{\infty}$. For
example, one can thing of $P_{\infty}$ as the closing price pf the day. We
suppose that both players pay a penalty
$\gamma(\frac{P^{a}+P^{b}}{2}-P_{\infty})^{2}$ with $\gamma>0$. The problem of
Player a is to maximize on $x=P^{a}-P_{\infty|a}$ the penalized payoff

$\displaystyle\mathbb{E}[(\frac{P_{\infty|a}+x+P_{\infty|b}-\delta(\boldsymbol{\sigma}_{b})}{2}-P_{\infty})\mathbf{1}_{P_{\infty|a}+x\leq
P_{\infty|b}-\delta(\boldsymbol{\sigma}_{b})}-\gamma(\frac{P^{a}+P^{b}}{2}-P_{\infty})^{2}|(P_{\infty|a},\boldsymbol{\sigma}_{a})].$

Then we have the following result.

######  Proposition 3.1.

Let $\gamma>0$. Then there is no NE with finite $\delta$.

###### Proof.

Using the same notations as previously we have

$\displaystyle\mathbb{E}[(\frac{P^{a}+P^{b}}{2}-P_{\infty})^{2}|(P_{\infty|a},\sigma_{a})]=\frac{1}{4}(x^{2}-2x\mathbb{E}[\delta(\sigma_{b})]+\mathbb{E}[\delta(\boldsymbol{\sigma}_{b})^{2}]+\sigma_{a}^{2}+\mathbb{E}[\boldsymbol{\sigma}_{b}^{2}]+2\rho\sigma_{a}\mathbb{E}[\boldsymbol{\sigma}_{b}])$

so

$\displaystyle e^{\sigma_{a}}_{\delta}(x)=$
$\displaystyle\frac{1}{\sigma_{+}-\sigma_{-}}\int_{\sigma_{-}}^{\sigma^{+}}\big{(}\frac{x-\delta(\sigma_{b})}{2}(1-\Phi(\frac{x+\delta(\sigma_{b})}{\Sigma_{\rho}}))+\Sigma_{\rho}(\frac{1}{2}-Q_{\rho})\Phi^{\prime}(\frac{x+\delta(\sigma_{b})}{\Sigma_{\rho}})\big{)}d\sigma_{b}$
$\displaystyle-\gamma\frac{1}{\sigma_{+}-\sigma_{-}}\int_{\sigma_{-}}^{\sigma^{+}}(\delta(\sigma_{b})^{2}+\sigma_{b}^{2}+2\rho\sigma_{a}\sigma_{b})d\sigma_{b}-\gamma\sigma_{a}^{2}-\gamma(x^{2}-2x\frac{1}{\sigma_{+}-\sigma_{-}}\int_{\sigma_{-}}^{\sigma^{+}}\delta(\sigma_{b})d\sigma_{b})$

and

$\displaystyle(e^{\sigma_{a}}_{\delta})^{\prime}(x)=$
$\displaystyle\frac{1}{\sigma_{+}-\sigma_{-}}\int_{\sigma_{-}}^{\sigma^{+}}\big{(}\frac{1}{2}(1-\Phi(\frac{x+\delta(\sigma_{b})}{\Sigma_{\rho}}))+\frac{1}{\Sigma_{\rho}}(-x\tilde{Q}_{\rho}+\delta(\sigma_{b})Q_{\rho})\Phi^{\prime}(\frac{x+\delta(\sigma_{b})}{\Sigma_{\rho}})\big{)}d\sigma_{b}$
$\displaystyle-2\gamma(x-\frac{1}{\sigma_{+}-\sigma_{-}}\int_{\sigma_{-}}^{\sigma^{+}}\delta(\sigma_{b})d\sigma_{b}),$

recalling that
$\tilde{Q}_{\rho}:=\frac{\frac{1}{\sigma_{a}^{2}}-\frac{\rho}{\sigma_{a}\sigma_{b}}}{\frac{1}{\sigma_{a}^{2}}+\frac{1}{\sigma_{b}^{2}}-2\frac{\rho}{\sigma_{a}\sigma_{b}}}.$
If $\sigma_{-}=\sigma_{+}$, $\delta$ describes a NE if and only if

$\displaystyle\frac{1}{2}(1-\Phi(\frac{\sqrt{2}\delta(\sigma_{+})}{\sigma_{+}}))=0,$

which cannot be obtained.

If $\sigma_{-}<\sigma_{+}$, we use the same method as with $\gamma=0$. ∎

As a consequence, a transaction fees based on the distance between the market
mid-price and a player’s mid-price does not provide an equilibrium.

###  3.2 Quadratic fees in the players’ half-spread: liquidity generation

Assume now that $P_{\infty|i}$ is known by the exchange. This can be done for
example if the players quote both bid and ask prices (i.e. the game is played
twice).

Suppose both players pay a penalty $\gamma(P^{i}-P_{\infty|i})^{2}$ with
$\gamma>0$. The problem of Player $a$ is to maximize on $x=P^{a}-P_{\infty|a}$
the penalized payoff

$\displaystyle\mathbb{E}[(\frac{P_{\infty|a}+x+P_{\infty|b}-\delta(\boldsymbol{\sigma}_{b})}{2}-P_{\infty})\mathbf{1}_{P_{\infty|a}+x\leq
P_{\infty|b}-\delta(\boldsymbol{\sigma}_{b})}-\gamma(P^{a}-P_{\infty|a})^{2}|(P_{\infty|a},\boldsymbol{\sigma}_{a})].$

Then we have the following result proved in Appendix B.

######  Theorem 1.

Let $\gamma>0$. Assume that $\rho\leq\frac{\sigma_{-}}{\sigma_{+}}$. Then

  * •

if $\sigma_{-}=\sigma_{+}$ there exists a unique NE with finite $\delta$. In
that case $\delta(\sigma_{+})$ is given by the unique positive root of the
function
$x\mapsto\frac{1}{2}(1-\Phi(\frac{\sqrt{2}x}{\sqrt{1-\rho}\sigma_{+}}))-2\gamma
x$

  * •

if $\sigma_{-}<\sigma_{+}$, let
$C=2\frac{1}{2\frac{1-\rho\frac{\sigma_{+}}{\sigma_{-}}}{1-(\frac{\sigma_{-}}{\sigma_{+}})^{2}}+1}\frac{1-\rho\frac{\sigma_{+}}{\sigma_{-}}}{1-(\frac{\sigma_{-}}{\sigma_{+}})^{2}}\sqrt{\frac{1}{2}\frac{(1-\rho^{2})^{2}\sigma_{-}^{4}}{\sigma_{+}^{2}}}$:
if
$\gamma\geq\frac{1}{4C}(1-\Phi(\frac{C}{\sqrt{2}\sigma_{+}}))+\frac{1}{2\sqrt{2}\sigma_{-}}\Phi^{\prime}(\frac{C}{\sqrt{2}\sigma_{+}})$
there exists a NE with $\delta$ bounded by $C$.888This bound is not tight and
we refer to the proof of this result for more details.

######  Remark 3.2.

From the proof of Proposition 3.1 we can also note that combining the two
previously mentioned penalties leads to a NE. Intuitively, and looking at the
derivative of $e_{\delta}^{\sigma_{i}}$, adding a quadratic penalty in the
mid-price error (as in Subsection 3.1) to a quadratic penalty in the spread
(as in the current subsection) would tend to reduce the variance of the
spread, which could be beneficial, as we have seen in Proposition 2.1.

###  3.3 Optimal transaction fees: the exchange’s perspective

We now consider that the exchange receives quadratic fees in the players’
half-spread as presented in Section 3.2. Recall that this case generates trade
between players. For simplicity, we only consider the case
$\sigma_{-}=\sigma_{+}$ in this section. The optimal PnL of the exchange
becomes

$\displaystyle\underset{\gamma>0}{\sup}\,\gamma\mathbb{E}[(P^{a}-P_{\infty|a})^{2}+(P^{b}-P_{\infty|b})^{2}]=2\underset{\gamma>0}{\sup}\,\gamma\delta(\sigma_{+})^{2}$
(3.1)

where $\delta$ is the strategy chosen by the players, with which they reach a
NE in their game with quadratic penalties with parameter $\gamma$. We can
compute the optimal $\gamma$ based on the following theorem.

######  Theorem 2.

Assume $\sigma_{-}=\sigma_{+}$. Then (3.1) has a unique solution $\gamma^{*}$.
It is given by $\gamma^{*}=\frac{\Phi^{\prime}(y^{*})}{2\sqrt{2}\sigma_{+}}$
where $y^{*}$ is the unique solution to
$1-\Phi(y^{*})-y^{*}\Phi^{\prime}(y^{*})=0$. In this case we also have
$\delta(\sigma_{+})=\frac{\sigma y^{*}}{\sqrt{2}}$.

###### Proof.

The optimization problem is

$\displaystyle\underset{\gamma>0}{\sup}\,\gamma\delta^{2}\text{ where
}\delta\text{ solves
}\frac{1}{2}(1-\Phi(\frac{\sqrt{2}\delta}{\sigma_{+}}))-2\gamma\delta=0.$

As $\gamma$ describes $\mathbb{R}^{*}_{+}$, the associated $\delta$ describes
also $\mathbb{R}_{+}^{*}$ so the problem can be rewritten

$\displaystyle\underset{\delta>0}{\sup}\,\frac{1}{4}(1-\Phi(\frac{\sqrt{2}\delta}{\sigma_{+}}))\delta.$

With the ansatz $\delta=\frac{\sigma y}{\sqrt{2}}$, $y>0$ we find from the
first order optimality condition that the optimum $y$ is unique and that it
solves $1-\Phi(y)-y\Phi^{\prime}(y)=0$. ∎

##  4 Numerical results

###  4.1 Suggestions for parameters calibration in practice

In this model, the main parameters to be calibrated are $\sigma_{-}$,
$\sigma_{+}$ and $\rho$.

  * •

The parameter $\sigma_{+}$ is the confidence level of the player suffering
from the highest level of uncertainty on the efficient price. We can choose
$\sigma_{+}$ equals to the volatility between two auctions, while $\sigma_{-}$
can be chosen small enough.

  * •

The ratio $\frac{\sigma_{-}}{\sigma_{+}}$ can be seen as a measure of the
symmetry of the ability of the players to estimate the efficient price. If
$\sigma_{-}=\sigma_{+}$ then no player is particularly accurate compared to
the others. In this case $\rho=1$ describes the situation where the players
have the same forecast. The case $\rho\neq 1$ would then describe a market
with some heterogeneity in the beliefs (trend-follower versus contrarian for
example). If $\sigma_{-}<\sigma_{+}$ then some player might have better
information. The ratio $\frac{\sigma_{-}}{\sigma_{+}}$ is similar to the ratio
$r$ in [Huang et al., 2019]. The second and fourth results of Proposition 2.1
suggest that this ratio should be calibrated on the market using the observed
spreads as well as $\rho$.

In the following we take $\sigma_{-}=0.1$, $\sigma_{+}=1.1$ and $\rho=0$.

###  4.2 Optimal strategies

In Figure 1, we plot the optimal strategies $\delta$ as a function of
$\sigma_{i}$ for different values of $\gamma$.

Figure 1: Optimal strategies $\delta(\sigma_{i})$ in a NE. The colorbar gives
possible values for the parameter $\gamma$.

We first observe that the optimal strategies are increasing in $\sigma_{i}$.
This result is natural: the more uncertain the market, the greater the spread.
Market makers increase their spread when the volatility is high. We also note
that the optimal strategies of the market makers are not linear functions of
the uncertainty. Finally, we see that the greater the fees, the smaller the
spreads. This is a result of the incentive mechanism put in place by the
exchange to reduce the difference between the price sent by the market makers
and their own private estimates.

###  4.3 Optimal incentives

We now turn to the optimal fees propose by the exchange to increase the
liquidity. We compute in Figure 2 $\mathbb{E}[\gamma\delta(\sigma_{i})^{2}]$
for multiple choices of $\gamma$ in NEs.

Figure 2: Penalties paid $\mathbb{E}[\gamma\delta(\sigma_{i})^{2}]$.

With this set of parameters, the condition ensuring the existence of a Nash
equilibrium is $\gamma\geq 1.5$. Therefore, based on Figure 2, the exchange
should pick $\gamma\approx 1.5$. It is larger than the optimal $\gamma\simeq
0.1$ given by Theorem 2 if $\sigma_{-}=\sigma_{+}=1.1$.

##  5 Extension to half-linear controls

We consider a variant of our model to better account for the fact that each
trader can use multiple limit orders. Player $a$ now has a demand function
$p\mapsto K^{a}(p-P^{a})\mathbf{1}_{p\geq P^{a}}$ and controls $P^{a}$ where
$K^{a}$ is constant. Similarly Player $b$ has an offer function $p\mapsto
K^{b}(P^{b}-p)\mathbf{1}_{p\leq P^{b}}$ and controls $P^{b}$, where $K^{b}$ is
constant.

A trade once again happens if $P^{a}\leq P^{b}$, but in this case we now have
the trade price which equals $\frac{K^{a}P^{a}+K^{b}P^{b}}{K^{a}+K^{b}}$ and
the traded volume is $\frac{K^{a}K^{b}}{K^{a}+K^{b}}(P^{b}-P^{a})$. So Player
$a$ maximizes, for any $p_{\infty|a}$ and $\sigma_{a}$, his expected gain

$\displaystyle\mathbb{E}[\frac{K^{a}K^{b}}{K^{a}+K^{b}}(P^{b}-P^{a})(\frac{K^{a}P^{a}+K^{b}P^{b}}{K^{a}+K^{b}}-P_{\infty})\mathbf{1}_{P^{a}\leq
P^{b}}|(P_{\infty|a}=p_{\infty|a},\boldsymbol{\sigma}_{a}=\sigma_{a})].$

We have a first negative result proved in Appendix C.1.

######  Proposition 5.1.

If $K^{a}=K^{b}=\bar{k}>0$ there is no NE.

As previously this result can be mitigated if both players pay a penalty
$\gamma(P^{i}-P_{\infty|i})^{2}$. We have the following result proved in
Appendix C.2.

######  Theorem 3.

Let $\gamma>0$. Assume that $\rho\leq\frac{\sigma_{-}}{\sigma_{+}}$ and that
the slopes are fixed $K^{a}=K^{b}=\bar{k}$. Then

  * •

if $\sigma_{-}=\sigma_{+}$ there exist a unique NE with finite $\delta$. In
that case $\delta(\sigma_{+})$ is given by the unique positive root of the
function
$x\mapsto\frac{\bar{k}}{2}(-x(1-\Phi(\frac{\sqrt{2}x}{\sqrt{1-\rho}\sigma_{+}}))+\frac{\sigma_{+}\sqrt{1-\rho}}{\sqrt{2}}\Phi^{\prime}(\frac{\sqrt{2}x}{\sqrt{1-\rho}\sigma_{+}}))-2\gamma
x$

  * •

if $\sigma_{-}<\sigma_{+}$, let
$\gamma\geq\frac{\bar{k}}{2}\max(-(1-\Phi(z))+z\Phi^{\prime}(z))$ there exists
a NE with $\delta$ bounded by
$C=\frac{\bar{k}}{4\gamma}\frac{1}{\sigma_{+}-\sigma_{-}}\int_{\sigma_{-}}^{\sigma_{+}}\bigg{(}\Sigma_{\rho}Q_{\rho}\Phi^{\prime}(0)\bigg{)}d\sigma_{b}$.

##  Appendix A Proof of Proposition 2.2

In the following, we set

$\epsilon_{ab}=\frac{P_{\infty|b}-P_{\infty|a}}{\boldsymbol{\Sigma}_{\rho}}$

and

$\epsilon_{\infty}=(P_{\infty}-\frac{\frac{1}{\boldsymbol{\sigma}_{a}^{2}}P_{\infty|a}+\frac{1}{\boldsymbol{\sigma}_{b}^{2}}P_{\infty|b}-2\frac{\rho}{\boldsymbol{\sigma}_{a}\boldsymbol{\sigma}_{b}}\frac{P_{\infty|a}+P_{\infty|b}}{2}}{\frac{1}{\boldsymbol{\sigma}_{a}^{2}}+\frac{1}{\boldsymbol{\sigma}_{b}^{2}}-2\frac{\rho}{\boldsymbol{\sigma}_{a}\boldsymbol{\sigma}_{b}}})\sqrt{\frac{1}{\boldsymbol{\sigma}_{a}^{2}}+\frac{1}{\boldsymbol{\sigma}_{b}^{2}}-2\frac{\rho}{\boldsymbol{\sigma}_{a}\boldsymbol{\sigma}_{b}}}/\sqrt{1-\rho^{2}}.$

We have the following lemma.

######  Lemma A.1.

Conditioned by $\boldsymbol{\sigma}_{a}=\sigma_{a}$ and
$\boldsymbol{\sigma}_{b}=\sigma_{b}$, $\epsilon_{ab}$ and $\epsilon_{\infty}$
are independent standard Gaussian variables.

###### Proof.

Given $\boldsymbol{\sigma}_{a}=\sigma_{a}$ and
$\boldsymbol{\sigma}_{b}=\sigma_{b}$, we have

$\displaystyle\epsilon_{ab}=$
$\displaystyle\frac{\sigma_{b}\epsilon_{b}-\sigma_{a}\epsilon_{a}}{\Sigma_{\rho}},$
$\displaystyle\epsilon_{\infty}=$
$\displaystyle-\frac{\frac{1}{\sigma_{a}}\epsilon_{a}+\frac{1}{\sigma_{b}}\epsilon_{b}-2\frac{\rho}{\sigma_{a}\sigma_{b}}\frac{\sigma_{a}\epsilon_{a}+\sigma_{b}\epsilon_{b}}{2}}{\sqrt{1-\rho^{2}}\sqrt{\frac{1}{\sigma_{a}^{2}}+\frac{1}{\sigma_{b}^{2}}-2\frac{\rho}{\sigma_{a}\sigma_{b}}}}$

and the conclusion follows. ∎

Conditional on $P_{\infty|a}$, $\epsilon_{ab}$ and $\epsilon_{\infty}$ are no
longer independent, but they become independent when we take $v\to+\infty$.
The following lemma comes directly from the conditional distribution of random
Gaussian vectors.

######  Lemma A.2.

Conditioned by $P_{\infty|a}=P_{\infty|a}$,
$\boldsymbol{\sigma}_{a}=\sigma_{a}$ and $\boldsymbol{\sigma}_{b}=\sigma_{b}$,
we have

$\displaystyle\begin{pmatrix}\Sigma_{\rho}\epsilon_{ab}\\\
-\sqrt{\frac{1}{\sigma_{a}^{2}}+\frac{1}{\sigma_{b}^{2}}-2\frac{\rho}{\sigma_{a}\sigma_{b}}}\epsilon_{\infty}\end{pmatrix}\sim{\cal
N}\Bigg{(}\begin{pmatrix}P_{\infty|a}\frac{-\sigma_{a}^{2}+\rho\sigma_{a}\sigma_{b}}{v^{2}+\sigma_{a}^{2}}\\\
P_{\infty|a}\frac{\sqrt{1-\rho^{2}}}{v^{2}+\sigma_{a}^{2}}\end{pmatrix},\begin{pmatrix}\Sigma_{\rho}^{2}-\frac{(-\sigma_{a}^{2}+\rho\sigma_{a}\sigma_{b})^{2}}{v^{2}+\sigma_{a}^{2}}&\frac{(\sigma_{a}^{2}-\rho\sigma_{a}\sigma_{b})\sqrt{1-\rho^{2}}}{v^{2}+\sigma_{a}^{2}}\\\
\frac{(\sigma_{a}^{2}-\rho\sigma_{a}\sigma_{b})\sqrt{1-\rho^{2}}}{v^{2}+\sigma_{a}^{2}}&\frac{1}{\sigma_{a}^{2}}+\frac{1}{\sigma_{b}^{2}}-2\frac{\rho}{\sigma_{a}\sigma_{b}}-\frac{1-\rho^{2}}{v^{2}+\sigma_{a}^{2}}\end{pmatrix}\Bigg{)}$

and $(\epsilon_{ab},\epsilon_{\infty})$ converges when $v\to\infty$ towards a
centered Gaussian vector with unit variance.

Notice that the limit distribution does not depend on $P_{\infty|a}$.

###### Proof.

Given $P_{\infty|a}=p_{\infty|a}$, $\boldsymbol{\sigma}_{a}=\sigma_{a}$, we
can write

$\displaystyle\frac{P_{\infty|a}+P_{\infty|b}}{2}-P_{\infty}$
$\displaystyle=(p_{\infty|a}+P_{\infty|b})(\frac{1}{2}-\boldsymbol{Q}^{b}_{\rho})+\epsilon_{\infty}\frac{\sqrt{1-\rho^{2}}}{\sqrt{\frac{1}{\sigma_{a}^{2}}+\frac{1}{\boldsymbol{\sigma}_{b}^{2}}-2\frac{\rho}{\sigma_{a}\boldsymbol{\sigma}_{b}}}}$
$\displaystyle=\epsilon_{\infty}\frac{\sqrt{1-\rho^{2}}}{\sqrt{\frac{1}{\sigma_{a}^{2}}+\frac{1}{\boldsymbol{\sigma}_{b}^{2}}-2\frac{\rho}{\sigma_{a}\boldsymbol{\sigma}_{b}}}}+\epsilon_{ab}\boldsymbol{\Sigma}^{b}_{\rho}(\frac{1}{2}-\boldsymbol{Q}_{\rho}^{b})$

and

$\displaystyle
P_{\infty|a}-P_{\infty|b}=-\epsilon_{ab}\boldsymbol{\Sigma}^{b}_{\rho}.$

Therefore

$\displaystyle\mathbb{E}[(\frac{P_{\infty|a}+x+P_{\infty|b}-\delta(\boldsymbol{\sigma}_{b})}{2}-P_{\infty})\mathbf{1}_{P_{\infty|a}+x\leq
P_{\infty|b}-\delta(\sigma_{b})}|(P_{\infty|a}=p_{\infty|a},\boldsymbol{\sigma}_{a}=\sigma_{a})]$
$\displaystyle=\mathbb{E}[\big{(}\frac{x-\delta(\boldsymbol{\sigma}_{b})}{2}+\epsilon_{\infty}\frac{\sqrt{1-\rho^{2}}}{\sqrt{\frac{1}{\sigma_{a}^{2}}+\frac{1}{\boldsymbol{\sigma}_{b}^{2}}-2\frac{\rho}{\sigma_{a}\boldsymbol{\sigma}_{b}}}}+\epsilon_{ab}\boldsymbol{\Sigma}^{b}_{\rho}(\frac{1}{2}-\boldsymbol{Q}_{\rho}^{b})\big{)}\mathbf{1}_{\epsilon_{ab}\geq\frac{x+\delta(\boldsymbol{\sigma}_{b})}{\boldsymbol{\Sigma}^{b}_{\rho}}}|(P_{\infty|a}=p_{\infty|a},\boldsymbol{\sigma}_{a}=\sigma_{a})]$
$\displaystyle=\mathbb{E}[\big{(}\frac{x-\delta(\boldsymbol{\sigma}_{b})}{2}+P_{\infty|a}\frac{\frac{-(1-\rho^{2})}{v^{2}+\sigma_{a}^{2}}}{\frac{1}{\sigma_{a}^{2}}+\frac{1}{\boldsymbol{\sigma}_{b}^{2}}-2\frac{\rho}{\sigma_{a}\boldsymbol{\sigma}_{b}}}+P_{\infty|a}\frac{\frac{\sqrt{1-\rho^{2}}(-\sigma_{a}^{2}+\rho\sigma_{a}\boldsymbol{\sigma}_{b})}{v^{2}+\sigma_{a}^{2}}}{\frac{1}{\sigma_{a}^{2}}+\frac{1}{\boldsymbol{\sigma}_{b}^{2}}-2\frac{\rho}{\sigma_{a}\boldsymbol{\sigma}_{b}}}\frac{\sqrt{\frac{1}{\sigma_{a}^{2}}+\frac{1}{\boldsymbol{\sigma}_{b}^{2}}-2\frac{\rho}{\sigma_{a}\boldsymbol{\sigma}_{b}}-\frac{1-\rho^{2}}{v^{2}+\sigma_{a}^{2}}}}{\sqrt{|\boldsymbol{\Sigma}^{b}_{\rho}|^{2}-\frac{(-\sigma_{a}^{2}+\rho\sigma_{a}\boldsymbol{\sigma}_{b})^{2}}{v^{2}+\sigma_{a}^{2}}}}$
$\displaystyle\hskip
10.00002pt+\epsilon_{ab}(-\chi(\sigma_{a},\boldsymbol{\sigma}_{b},v)+\boldsymbol{\Sigma}^{b}_{\rho}(\frac{1}{2}-\boldsymbol{Q}^{b}_{\rho}))\big{)}\mathbf{1}_{\epsilon_{ab}\geq\frac{x+\delta(\boldsymbol{\sigma}_{b})}{\boldsymbol{\Sigma}^{b}_{\rho}}}|(P_{\infty|a}=p_{\infty|a},\boldsymbol{\sigma}_{a}=\sigma_{a})]$
$\displaystyle=\frac{1}{\sigma_{+}-\sigma_{-}}\int_{\sigma_{-}}^{\sigma^{+}}\Bigg{[}\Big{(}\frac{x-\delta(\sigma_{b})}{2}+p_{\infty|a}S(\sigma_{a},\sigma_{b},\rho)+p_{\infty|a}\frac{\frac{-\sigma_{a}^{2}+\rho\sigma_{a}\sigma_{b}}{v^{2}+\sigma_{a}^{2}}}{\Sigma_{\rho}}\big{(}-\chi(\sigma_{a},\sigma_{b},v)+\Sigma_{\rho}(\frac{1}{2}-Q_{\rho})\big{)}\Big{)}$
$\displaystyle\hskip
90.00014pt\times\Big{(}1-\Phi\big{(}\frac{x+\delta(\sigma_{b})-p_{\infty|a}\frac{-\sigma_{a}^{2}+\rho\sigma_{a}\sigma_{b}}{v^{2}+\sigma_{a}^{2}}}{\sqrt{\Sigma_{\rho}^{2}-\frac{(-\sigma_{a}^{2}+\rho\sigma_{a}\sigma_{b})^{2}}{v^{2}+\sigma_{a}^{2}}}}\big{)}\Big{)}$
$\displaystyle\vspace{1cm}\hskip
50.00008pt+\frac{\sqrt{\Sigma_{\rho}^{2}-\frac{(-\sigma_{a}^{2}+\rho\sigma_{a}\sigma_{b})^{2}}{v^{2}+\sigma_{a}^{2}}}}{\Sigma_{\rho}}(-\chi(\sigma_{a},\sigma_{b},v)+\Sigma_{\rho}(\frac{1}{2}-Q_{\rho}))\Phi^{\prime}(\frac{x+\delta(\sigma_{b})-p_{\infty|a}\frac{-\sigma_{a}^{2}+\rho\sigma_{a}\sigma_{b}}{v^{2}+\sigma_{a}^{2}}}{\sqrt{\Sigma_{\rho}^{2}-\frac{(-\sigma_{a}^{2}+\rho\sigma_{a}\sigma_{b})^{2}}{v^{2}+\sigma_{a}^{2}}}})\Bigg{]}d\sigma_{b}$

by setting

$S(\sigma_{a},\sigma_{b},\rho):=\frac{\frac{-(1-\rho^{2})}{v^{2}+\sigma_{a}^{2}}}{\frac{1}{\sigma_{a}^{2}}+\frac{1}{\sigma_{b}^{2}}-2\frac{\rho}{\sigma_{a}\sigma_{b}}}+\frac{\frac{\sqrt{1-\rho^{2}}(-\sigma_{a}^{2}+\rho\sigma_{a}\sigma_{b})}{v^{2}+\sigma_{a}^{2}}}{\frac{1}{\sigma_{a}^{2}}+\frac{1}{\sigma_{b}^{2}}-2\frac{\rho}{\sigma_{a}\sigma_{b}}}\frac{\sqrt{\frac{1}{\sigma_{a}^{2}}+\frac{1}{\sigma_{b}^{2}}-2\frac{\rho}{\sigma_{a}\sigma_{b}}-\frac{1-\rho^{2}}{v^{2}+\sigma_{a}^{2}}}}{\sqrt{\Sigma_{\rho}^{2}-\frac{(-\sigma_{a}^{2}+\rho\sigma_{a}\sigma_{b})^{2}}{v^{2}+\sigma_{a}^{2}}}},$

$\chi(\sigma_{a},\sigma_{b},v)=\frac{\Sigma_{\rho}\frac{(\sigma_{a}^{2}-\rho\sigma_{a}\sigma_{b})\sqrt{1-\rho^{2}}}{v^{2}+\sigma_{a}^{2}}}{(\Sigma_{\rho}^{2}-\frac{(-\sigma_{a}^{2}+\rho\sigma_{a}\sigma_{b})^{2}}{v^{2}+\sigma_{a}^{2}})\sqrt{\Sigma_{\rho}^{2}\frac{(-\sigma_{a}^{2}+\rho\sigma_{a}\sigma_{b})^{2}}{v^{2}+\sigma_{a}^{2}}}(\frac{1}{\sigma_{a}^{2}}+\frac{1}{\sigma_{b}^{2}-2\frac{\rho}{\sigma_{a}\sigma_{b}}})},$

and by using Lemma A.2. Now, as
$\chi(\sigma_{a},\sigma_{b},v)\underset{v\to+\infty}{\longrightarrow}0$, we
have

$\displaystyle\mathbb{E}[(\frac{P_{\infty|a}+x+P_{\infty|b}-\delta(\boldsymbol{\sigma}_{b})}{2}-P_{\infty})\mathbf{1}_{P_{\infty|a}+x\leq
P_{\infty|b}-\delta(\boldsymbol{\sigma}_{b})}|(P_{\infty|a}=p_{\infty|a},\boldsymbol{\sigma}_{a}=\sigma_{a})]$
$\displaystyle\underset{v\to+\infty}{\longrightarrow}$
$\displaystyle\frac{1}{\sigma_{+}-\sigma_{-}}\int_{\sigma_{-}}^{\sigma^{+}}\big{(}\frac{x-\delta(\sigma_{b})}{2}(1-\Phi(\frac{x+\delta(\sigma_{b})}{\Sigma_{\rho}}))+\Sigma_{\rho}(\frac{1}{2}-Q_{\rho})\Phi^{\prime}(\frac{x+\delta(\sigma_{b})}{\Sigma_{\rho}})\big{)}d\sigma_{b}.$

Notice that the convergence is uniform in $x$ as $\Phi$ and $\Phi^{\prime}$
are bounded. ∎

##  Appendix B Proof of Theorem 1

Using the same notations as previously we have

$\displaystyle\mathbb{E}[(P^{a}-P_{\infty|a})^{2}|(P_{\infty|a},\sigma_{a})]=x^{2}$

so

$\displaystyle e^{\sigma_{a}}_{\delta}(x)=$
$\displaystyle\frac{1}{\sigma_{+}-\sigma_{-}}\int_{\sigma_{-}}^{\sigma^{+}}\big{(}\frac{x-\delta(\sigma_{b})}{2}(1-\Phi(\frac{x+\delta(\sigma_{b})}{\Sigma_{\rho}}))+\Sigma_{\rho}(\frac{1}{2}-Q_{\rho})\Phi^{\prime}(\frac{x+\delta(\sigma_{b})}{\Sigma_{\rho}})\big{)}d\sigma_{b}-\gamma
x^{2}$

and

$\displaystyle(e^{\sigma_{a}}_{\delta})^{\prime}(x)=$
$\displaystyle\frac{1}{\sigma_{+}-\sigma_{-}}\int_{\sigma_{-}}^{\sigma^{+}}\big{(}\frac{1}{2}(1-\Phi(\frac{x+\delta(\sigma_{b})}{\Sigma_{\rho}}))$
$\displaystyle\hskip
85.35826pt+\frac{1}{\Sigma_{\rho}}(-x\tilde{Q}_{\rho}+\delta(\sigma_{b})Q_{\rho})\Phi^{\prime}(\frac{x+\delta(\sigma_{b})}{\Sigma_{\rho}})\big{)}d\sigma_{b}-2\gamma
x.$

If $\sigma_{-}=\sigma_{+}$, $\delta$ describes a NE equilibrium if and only if

$\displaystyle\frac{1}{2}(1-\Phi(\frac{\sqrt{2}\delta(\sigma_{+})}{\sigma_{+}\sqrt{1-\rho}}))-2\gamma\delta(\sigma_{+})=0,$

which can always be achieved for some unique $\delta(\sigma_{+})>0$ if
$\gamma>0$.

If $\sigma_{-}<\sigma_{+}$, we start by observing that it makes sense to
consider $\delta$ non-negative. Indeed if $0\leq\delta\leq C$ we have
$e^{\sigma_{a}}_{\delta}(x)\underset{x\to+\infty}{\longrightarrow}-\infty$ and
$(e^{\sigma_{a}}_{\delta})^{\prime}(y)>0$ for all $y\leq 0$. By the asymptotic
expansion $1-\Phi(x)\underset{x\to+\infty}{\sim}\frac{\Phi^{\prime}(x)}{x}$ we
also get
$(e^{\sigma_{a}}_{\delta})^{\prime}(x)\underset{x\to+\infty}{\longrightarrow}-\infty$
so by elementary computations $e^{\sigma_{a}}_{\delta}$ attains its maximum on
$\mathbb{R}_{+}^{*}$.

By computing the second derivative we get

$\displaystyle(e^{\sigma_{a}}_{\delta})^{\prime\prime}(x)=$
$\displaystyle\frac{1}{\sigma_{+}-\sigma_{-}}\int_{\sigma_{-}}^{\sigma^{+}}\big{(}-(\frac{1}{2}+\tilde{Q}_{\rho}+\frac{1}{\Sigma_{\rho}^{2}}Q_{\rho}\delta(\sigma_{b})^{2})-\frac{\delta(\sigma_{b})}{\Sigma_{\rho}^{2}}Q_{\rho}x+\frac{1}{\Sigma_{\rho}^{2}}\tilde{Q}_{\rho}x^{2}\big{)}\frac{\Phi^{\prime}(\frac{x+\delta(\sigma_{b})}{\Sigma_{\rho}})}{\Sigma_{\rho}}d\sigma_{b}-2\gamma.$

Each quadratic function in the integral is non-positive on an interval

$\displaystyle[\frac{1}{2}\delta(\sigma_{b})\frac{(\frac{\sigma_{a}}{\sigma_{b}})^{2}-1}{1-\rho\frac{\sigma_{a}}{\sigma_{b}}}$
$\displaystyle\pm\sqrt{(\frac{1}{2}\delta(\sigma_{b})\frac{(\frac{\sigma_{a}}{\sigma_{b}})^{2}-1}{1-\rho\frac{\sigma_{a}}{\sigma_{b}}})^{2}+(\frac{1}{2}+\tilde{Q}_{\rho}+\frac{1}{\sigma_{a}^{2}+\sigma_{b}^{2}-2\rho\sigma_{a}\sigma_{b}}Q_{\rho}\delta(\sigma_{b})^{2})\frac{\Sigma_{\rho}^{2}}{\sigma_{b}^{2}-\rho\sigma_{a}\sigma_{b}}}].$

Take
$C=2\lambda\frac{1-\rho\frac{\sigma_{+}}{\sigma_{-}}}{1-(\frac{\sigma_{-}}{\sigma_{+}})^{2}}\sqrt{\frac{1}{2}\frac{(1-\rho^{2})^{2}\sigma_{-}^{4}}{\sigma_{+}^{2}}}$
for some $\lambda\in(0,1)$. Then the intersection of those intervals contains
the interval
$[0,(1-\lambda)\sqrt{\frac{1}{2}\frac{(1-\rho^{2})^{2}\sigma_{-}^{4}}{\sigma_{+}^{2}}}]$.
In particular if
$\lambda=\frac{1}{2\frac{1-\rho\frac{\sigma_{+}}{\sigma_{-}}}{1-(\frac{\sigma_{-}}{\sigma_{+}})^{2}}+1}$
we have
$C=(1-\lambda)\sqrt{\frac{1}{2}\frac{(1-\rho^{2})^{2}\sigma_{-}^{4}}{\sigma_{+}^{2}}}$
and so $(e^{\sigma_{a}}_{\delta})^{\prime\prime}<0$ on $(0,C)$ for all
$\sigma_{a}$.

Let $c\geq C$. We have for all $\sigma_{a}$

$\displaystyle(e^{\sigma_{a}}_{\delta})^{\prime}(c)\leq$
$\displaystyle\underset{u\in[\sigma_{-},\sigma_{+}]}{\max}\frac{1}{\sigma_{+}-\sigma_{-}}\int_{\sigma_{-}}^{\sigma^{+}}\big{(}\frac{1}{2}(1-\Phi(\frac{c}{\sqrt{u^{2}+\sigma_{b}^{2}-2\rho
u\sigma_{b}}}))$ $\displaystyle+\frac{1}{\sqrt{u^{2}+\sigma_{b}^{2}-2\rho
u\sigma_{b}}}\underset{F\in{[0,C]}}{\max}(-cG(u;\sigma_{b})+F\tilde{G}(u;\sigma_{b}))\Phi^{\prime}(\frac{c+F}{\sqrt{u^{2}+\sigma_{b}^{2}-2\rho
u\sigma_{b}}})\big{)}d\sigma_{b}$ $\displaystyle-2\gamma c$
$\displaystyle\leq\frac{1}{\sigma_{+}-\sigma_{-}}\int_{\sigma_{-}}^{\sigma^{+}}\frac{1}{2}(1-\Phi(\frac{C}{\sqrt{\sigma_{+}^{2}+\sigma_{b}^{2}-2\rho
u\sigma_{b}}}))d\sigma_{b}$
$\displaystyle+C\frac{1}{\sigma_{+}-\sigma_{-}}\int_{\sigma_{-}}^{\sigma^{+}}\frac{1}{\sqrt{u^{2}+\sigma_{b}^{2}}}\tilde{G}(u;\sigma_{b})\Phi^{\prime}(\frac{C}{\sqrt{u^{2}+\sigma_{b}^{2}-2\rho
u\sigma_{b}}})d\sigma_{b}-2\gamma C$
$\displaystyle\leq\frac{1}{2}(1-\Phi(\frac{C}{\sqrt{2}\sigma_{+}}))+C(\frac{1}{\sqrt{2}\sigma_{-}}\Phi^{\prime}(\frac{C}{\sqrt{2}\sigma_{+}})-2\gamma)$

by setting

$G(u;\sigma_{b})=\frac{\frac{1}{u^{2}}-\rho\frac{1}{u}\frac{1}{\sigma_{b}}}{\frac{1}{u^{2}}+\frac{1}{\sigma_{b}^{2}}-2\rho\frac{1}{u}\frac{1}{\sigma_{b}}}$

and

$\tilde{G}(u;\sigma_{b})=\frac{\frac{1}{\sigma_{b}^{2}}-\rho\frac{1}{u}\frac{1}{\sigma_{b}}}{\frac{1}{u^{2}}+\frac{1}{\sigma_{b}^{2}}-2\rho\frac{1}{u}\frac{1}{\sigma_{b}}}.$

So for $\gamma$ large enough we have

$\displaystyle\gamma\geq\frac{1}{4C}(1-\Phi(\frac{C}{\sqrt{2}\sigma_{+}}))+\frac{1}{2\sqrt{2}\sigma_{-}}\Phi^{\prime}(\frac{C}{\sqrt{2}\sigma_{+}})$

so $(e^{\sigma_{a}}_{\delta})^{\prime}(c)\leq 0$ for all $\sigma_{a}$, $c\geq
C$.

In this case, if we let ${\cal C}_{[0,c]}$ be the set of continuous functions
on $[\sigma_{-},\sigma_{+}]$ with values on $[0,C]$, then $\delta\in{\cal
C}_{[0,C]}\mapsto(\sigma_{a}\mapsto\arg\max e^{\sigma_{a}}_{\delta})\in{\cal
C}_{[0,C]}$ is continuous in the $L^{\infty}$ norm. We consider a sequence
$\delta_{n}\in{\cal C}_{[0,c]}$ converge to $\delta\in{\cal C}_{[0,c]}$ in the
$L^{\infty}$ norm. We first show that

$\displaystyle\underset{(\sigma_{a},x)\in[\sigma_{-},\sigma_{+}]\times[0,C]}{\sup}|e_{\delta}^{\sigma_{a}}(x)-e_{\delta_{n}}^{\sigma_{a}}(x)|\underset{n\to+\infty}{\longrightarrow}0.$

To see that, we can observe that, if $\|\delta-\delta_{n}\|_{L^{\infty}}<\nu$,
then, using the intermediate values theorem, we have, for any
$(\sigma_{a},x)\in[\sigma_{-},\sigma_{+}]\times[0,C]$,

$\displaystyle|e_{\delta}^{\sigma_{a}}(x)-e_{\delta_{n}}^{\sigma_{a}}(x)|\leq$
$\displaystyle\frac{1}{\sigma_{+}-\sigma_{-}}\int_{\sigma_{-}}^{\sigma^{+}}\big{(}\frac{\nu}{2}+\underset{g\in[0,C]}{\sup}|\frac{x-g}{2}\frac{\nu}{\Sigma_{\rho}}\Phi^{\prime}(\frac{x+g}{\Sigma_{\rho}})|$
$\displaystyle+|(\frac{1}{2}-Q_{\rho})|\nu\underset{g\in[0,C]}{\sup}|\Phi^{\prime\prime}(\frac{x+\delta(\sigma_{b})}{\Sigma_{\rho}})|\big{)}d\sigma_{b}$
$\displaystyle\leq$
$\displaystyle\frac{1}{\sigma_{+}-\sigma_{-}}\int_{\sigma_{-}}^{\sigma^{+}}\big{(}\frac{\nu}{2}+C\nu\sup|\Phi^{\prime}|\frac{1}{\Sigma_{\rho}}+|(\frac{1}{2}-Q_{\rho})|\nu\sup|\Phi^{\prime\prime}|\big{)}d\sigma_{b}$

so

$\displaystyle\underset{(\sigma_{a},x)\in[\sigma_{-},\sigma_{+}]\times[0,C]}{\sup}|e_{\delta}^{\sigma_{a}}(x)-e_{\delta_{n}}^{\sigma_{a}}(x)|\leq
K\nu$

where $K$ is some constant which depends only on $C,\sigma_{-},\sigma_{+}$.
This proves that

$\displaystyle\underset{(\sigma_{a},x)\in[\sigma_{-},\sigma_{+}]\times[0,C]}{\sup}|e_{\delta}^{\sigma_{a}}(x)-e_{\delta_{n}}^{\sigma_{a}}(x)|\underset{n\to+\infty}{\longrightarrow}0.$

In particular, $e_{\delta_{n}}^{\sigma_{a}}$ converges uniformly to
$e_{\delta}^{\sigma_{a}}$ for all $\sigma_{a}\in[\sigma_{-},\sigma_{+}]$. By
strong concavity on $[0,C]$ and classical results on epi-convergence, we have
that $\arg\max e_{\delta_{n}}^{\sigma_{a}}$ converges to $\arg\max
e_{\delta}^{\sigma_{a}}$. The continuity of $\sigma_{a}\mapsto\arg\max
e_{\delta}^{\sigma_{a}}$ also comes from the same epi-convergence argument.

We now prove that the convergence is uniform. We suppose that it is not. Let
$\eta>0$ and $\sigma_{n}\in[\sigma_{-},\sigma_{+}]$ such that $|\arg\max
e_{\delta}^{\sigma_{n}}-\arg\max e_{\delta_{n}}^{\sigma_{n}}|\geq\eta$ for all
$n\in\mathbb{N}$. We can assume that $\sigma_{n}\longrightarrow\sigma_{a}$.
The function $e_{\delta_{n}}^{\sigma_{n}}$ is twice derivable at $\arg\max
e_{\delta_{n}}^{\sigma_{n}}$ and $e_{\delta_{n}}^{\sigma_{n}}\leq-2\gamma$ so
we have

$\displaystyle e_{\delta_{n}}^{\sigma_{n}}(\arg\max
e_{\delta_{n}}^{\sigma_{n}})-e_{\delta_{n}}^{\sigma_{n}}(\arg\max
e_{\delta}^{\sigma_{n}})\geq\gamma(\arg\max
e_{\delta_{n}}^{\sigma_{n}}-\arg\max
e_{\delta}^{\sigma_{n}})^{2}\geq\gamma\eta^{2}.$

However

$e_{\delta_{n}}^{\sigma_{n}}(\arg\max e_{\delta_{n}}^{\sigma_{n}})=\max
e_{\delta_{n}}^{\sigma_{n}}\longrightarrow\max e_{\delta}^{\sigma_{a}}$

and

$e_{\delta_{n}}^{\sigma_{n}}(\arg\max
e_{\delta}^{\sigma_{n}})=e_{\delta}^{\sigma_{n}}(\arg\max
e_{\delta}^{\sigma_{n}})+(e_{\delta_{n}}^{\sigma_{n}}(\arg\max
e_{\delta}^{\sigma_{n}})-e_{\delta}^{\sigma_{n}}(\arg\max
e_{\delta}^{\sigma_{n}})),$

with

$e_{\delta}^{\sigma_{n}}(\arg\max e_{\delta}^{\sigma_{n}})=\max
e_{\delta}^{\sigma_{n}}\longrightarrow\max e_{\delta}^{\sigma_{a}}$

and

$|e_{\delta_{n}}^{\sigma_{n}}(\arg\max
e_{\delta}^{\sigma_{n}})-e_{\delta}^{\sigma_{n}}(\arg\max
e_{\delta}^{\sigma_{n}})|\longrightarrow 0.$

So $e_{\delta_{n}}^{\sigma_{n}}(\arg\max
e_{\delta_{n}}^{\sigma_{n}})-e_{\delta_{n}}^{\sigma_{n}}(\arg\max
e_{\delta}^{\sigma_{n}})\longrightarrow 0$ and we obtain a contradiction.

Finally we can apply the Schauder fixed-point theorem to show that there
exists a NE.

##  Appendix C Proof of Section 5

###  C.1 Proof of Proposition 5.1

We have

$\displaystyle e^{\delta}_{\sigma_{a}}(x)=$
$\displaystyle\frac{1}{\sigma_{+}-\sigma_{-}}\int_{\sigma_{-}}^{\sigma_{+}}\frac{\bar{k}}{2}\bigg{(}\big{(}\Sigma_{\rho}^{2}(\frac{1}{2}-Q_{\rho})-\frac{x-\delta(\sigma_{b})}{2}(\delta(\sigma_{b})+x)\big{)}(1-\Phi(\frac{x+\delta(\sigma_{b})}{\Sigma_{\rho}}))$
$\displaystyle\hskip
70.0001pt+\Sigma_{\rho}\frac{x-\delta(\sigma_{b})}{2}\Phi^{\prime}(\frac{x+\delta(\sigma_{b})}{\Sigma_{\rho}})\bigg{)}d\sigma_{b}$

so

$\displaystyle(e^{\delta}_{\sigma_{a}})^{\prime}(x)=$
$\displaystyle\frac{1}{\sigma_{+}-\sigma_{-}}\int_{\sigma_{-}}^{\sigma_{+}}\frac{\bar{k}}{2}\bigg{(}-x(1-\Phi(\frac{x+\delta(\sigma_{b})}{\Sigma_{\rho}}))+\Sigma_{\rho}Q_{\rho}\Phi^{\prime}(\frac{x+\delta(\sigma_{b})}{\Sigma_{\rho}})\bigg{)}d\sigma_{b}$

and we have once again that $(e^{\delta}_{\sigma_{a}})^{\prime}(x)>0$ if
$x\leq 0$. If $\delta$ gives a NE we should have

$\displaystyle\frac{1}{\sigma_{+}-\sigma_{-}}\int_{\sigma_{-}}^{\sigma_{+}}(e^{\delta}_{\sigma_{a}})^{\prime}(\delta(\sigma_{a}))d\sigma_{a}=0$

so

$\displaystyle\int_{\sigma_{-}}^{\sigma_{+}}\int_{\sigma_{-}}^{\sigma_{+}}(-\delta(\sigma_{a})(1-\Phi(\frac{\delta(\sigma_{a})+\delta(\sigma_{b})}{\Sigma_{\rho}}))+\Sigma_{\rho}Q_{\rho}\Phi^{\prime}(\frac{\delta(\sigma_{a})+\delta(\sigma_{b})}{\Sigma_{\rho}}))d\sigma_{a}d\sigma_{b}=0.$

Summing this and the symmetric equation we get

$\displaystyle\int_{\sigma_{-}}^{\sigma_{+}}\int_{\sigma_{-}}^{\sigma_{+}}(-(\delta(\sigma_{a})+\delta(\sigma_{b}))(1-\Phi(\frac{\delta(\sigma_{a})+\delta(\sigma_{b})}{\Sigma_{\rho}}))+\Sigma_{\rho}\Phi^{\prime}(\frac{\delta(\sigma_{a})+\delta(\sigma_{b})}{\Sigma_{\rho}}))d\sigma_{a}d\sigma_{b}=0$

which is impossible as $\frac{x(1-\Phi(x))}{\Phi^{\prime}(x)}<1$ for $x>0$.

###  C.2 Proof of Theorem 3

We prove the second point, as the first one is straightforward from the proof
of Proposition 5.1, by analogy with Theorem 1.

We have

$\displaystyle(e^{\delta}_{\sigma_{a}})^{\prime}(x)=$
$\displaystyle\frac{1}{\sigma_{+}-\sigma_{-}}\int_{\sigma_{-}}^{\sigma_{+}}\frac{\bar{k}}{2}\bigg{(}-x(1-\Phi(\frac{x+\delta(\sigma_{b})}{\Sigma_{\rho}}))+\Sigma_{\rho}Q_{\rho}\Phi^{\prime}(\frac{x+\delta(\sigma_{b})}{\Sigma_{\rho}})\bigg{)}d\sigma_{b}-2\gamma
x$

so

$\displaystyle(e^{\delta}_{\sigma_{a}})^{\prime\prime}(x)=$
$\displaystyle\frac{1}{\sigma_{+}-\sigma_{-}}\int_{\sigma_{-}}^{\sigma_{+}}\frac{\bar{k}}{2}\bigg{(}-(1-\Phi(\frac{x+\delta(\sigma_{b})}{\Sigma_{\rho}}))+\frac{1}{\Sigma_{\rho}}(\tilde{Q}_{\rho}x-Q_{\rho}\delta(\sigma_{b}))\Phi^{\prime}(\frac{x+\delta(\sigma_{b})}{\Sigma_{\rho}})\bigg{)}d\sigma_{b}-2\gamma.$

We need to find a constant $C$ and a parameter $\gamma$ such that
$(e^{\delta}_{\sigma_{a}})^{\prime}(x)<0$ and
$(e^{\delta}_{\sigma_{a}})^{\prime\prime}(y)<0$ if $x\geq C\geq y\geq 0$ and
$0\leq\delta\leq C$. We have

$\displaystyle(e^{\delta}_{\sigma_{a}})^{\prime\prime}(y)\leq$
$\displaystyle\frac{1}{\sigma_{+}-\sigma_{-}}\int_{\sigma_{-}}^{\sigma_{+}}\frac{\bar{k}}{2}\bigg{(}-(1-\Phi(\frac{y+\delta(\sigma_{b})}{\Sigma_{\rho}}))+\frac{y+\delta(\sigma_{b})}{\Sigma_{\rho}}\Phi^{\prime}(\frac{y+\delta(\sigma_{b})}{\Sigma_{\rho}})\bigg{)}d\sigma_{b}-2\gamma$
$\displaystyle\leq$
$\displaystyle\frac{\bar{k}}{2}\max(-(1-\Phi(z))+z\Phi^{\prime}(z))-2\gamma\leq
0$

and

$\displaystyle(e^{\delta}_{\sigma_{a}})^{\prime}(x)\leq$
$\displaystyle\frac{1}{\sigma_{+}-\sigma_{-}}\int_{\sigma_{-}}^{\sigma_{+}}\frac{\bar{k}}{2}\bigg{(}\Sigma_{\rho}Q_{\rho}\Phi^{\prime}(\frac{C}{\Sigma_{\rho}})\bigg{)}d\sigma_{b}-2\gamma
C$

and the conclusion follows easily from the assumptions and the arguments of
the proof of Theorem 1.

## References

  * [Antill and Duffie, 2021] Antill, S. and Duffie, D. (2011).  Augmenting markets with mechanisms.  The Review of Economic Studies 88, no. 4: 1665-1719.
  * [Budish et al., 2015] Budish, E., Cramton, P., and Shim, J. (2015).  The high-frequency trading arms race: Frequent batch auctions as a market design response.  The Quarterly Journal of Economics, 130(4):1547–1621.
  * [Derchu et al., 2020] Derchu, J., Guillot, P., Mastrolia, T., and Rosenbaum, M. (2020).  Ahead: Ad hoc electronic auction design.  ArXiv, 2010.02827.
  * [Du and Zhu, 2017] Du, S. and Zhu, H. (2017).  What is the optimal trading frequency in financial markets?  The Review of Economic Studies, 84(4):1606–1651.
  * [Duffie and Zhu, 2017] Duffie, D. and Zhu, H. (2017).  Size discovery.  The Review of Financial Studies 30, no. 4: 1095-1150.
  * [Farmer and Skouras, 2012] Farmer, D. and Skouras, S. (2012).  Review of the benefits of a continuous market vs. randomised stop auctions and of alternative priority rules (policy options 7 and 12).  Manuscript, Foresight. Government Office for Science.
  * [Huang et al., 2019] Huang, W., Rosenbaum, M., and Saliba, P. (2019).  From Glosten-Milgrom to the whole limit order book and applications to financial regulation.  SSRN Electronic Journal.
  * [Jusselin et al., 2021] Jusselin, P., Mastrolia, T., and Rosenbaum, M. (2021).  Optimal auction duration: A price formation viewpoint.  Operations Research 69, no. 6: 1734-1745.
  * [Madhavan, 1992] Madhavan, A. (1992).  Trading mechanisms in securities markets.  the Journal of Finance, 47(2):607–641.
  * [Wah and Wellman, 2013] Wah, E. and Wellman, M. P. (2013).  Latency arbitrage, market fragmentation, and efficiency: A two-market model.  In Proceedings of the fourteenth ACM conference on Electronic commerce, pages 855–872.