# The road to solving the Gribov problem of the
center vortex model in quantum chromo dynamics ††thanks: Presented at Excited
QCD 2019 by Rudolf Golubich

Rudolf Golubich and Manfried Faber  Atominstitut, Technische Universität Wien

###### Abstract

The center vortex model of the QCD vacuum is very successful in explaining the
non-perturbative properties of QCD, especially confinement, chiral symmetry
breaking and the topological charge of vacuum configurations. On the other
hand, the center vortex model still suffers from a Gribov problem: Direct
maximal center gauge and center projection can lead to an underestimation of
the string tension in smooth configurations or after persistent simulated
annealing. We discuss methods to identify center regions, whose boundaries
evaluate to center elements, and want to improve the vortex detection: these
regions might help to recognize vortices in configurations where maximal
center gauge lost the vortex finding property.

11.15.Ha, 12.38.Gc

##  1 Introduction

The center vortex model [1, 2, 3] is based upon the center symmetry of the
action in lattice quantum chromo dynamics. It describes the properties of the
vacuum by percolating vortices, which are closed and quantized magnetic flux
lines of finite thickness, condensing in the vacuum. It is capable of
explaining:

  * •

Confinement: behaviour of Wilson and Polyakov loops, see [3]

  * •

Casimir scaling of the potential due to thick vortices, see [4]

  * •

Broken scale invariance, see [5]

  * •

Chiral symmetry breaking can be linked to vortices in sufficiently smooth
configurations [6, 7].

But for some configurations it underestimates the string tension. As this
might be due to failing vortex detection procedures, we intend to improve the
methods of P-vortex detection, also striving towards a direct identification
of thick vortices.

##  2 The center vortex model

Thick vortices are presently localized by P-vortices, which in turn are
identified by maximal center gauge and center projection, see Fig. 1.

Figure 1: Vortex finding property: P-vortices localize thick vortices.

Gauge fixing is done by maximizing the gauge fixing functional

$R=\sum_{x}\sum_{\mu}\mid\text{Tr}[U_{\mu}(x)]\mid^{2},$ (1)

with $U_{\mu}(x)$ being the SU(2) link at position $x$ in direction $\mu$.
Numerical methods like simulated annealing can only find local maxima. Some of
the configurations corresponding to these maxima suffer from a loss of the
vortex finding property. Projecting the single links to center elements

$U_{\mu}(x)\rightarrow Z_{\mu}(x)=\text{sign }\text{Tr}[U_{\mu}(x)].$ (2)

leads to P-vortices. They arise in the projected lattice as plaquettes
evaluating to a non-trivial center element, see figure 2.

Non-trivial links build up the Dirac volume, whose surface is the vortex
(transparent). They are detected by non-trivial plaquettes.

Figure 2: Relationship between center vortices, non-trivial links and the
Dirac volume.

Assuming independent piercings of Wilson loop $W(R,T)$ of size $R\times T$ in
the projected lattice, see figure 3, follows an area law of the expectation
value of Wilson loops,

$\langle{\color[rgb]{0.,0.376,0.}W(R,T)}\rangle=[{\color[rgb]{0.9,0.4,0.}(-1)}\varrho+{\color[rgb]{0.,0.,1.}(+1)}(1-\varrho)]^{\overbrace{{\color[rgb]{0.,0.376,0.}R}\times{\color[rgb]{0.,0.376,0.}T}}^{A}}=e^{-\ln(1-2\varrho)A}=e^{-\sigma
A}.$ (3)

Via the Non-trivial links of the Dirac volume, each P-vortex plaquette
contributes a factor $-1$ to an enclosing Wilson loop. A loop enclosing an
even number of P-plaquettes evaluates to the trivial center element while a
loop enclosing an odd number of P-plaquettes evaluates to a non-trivial center
element.

Figure 3: P-Vortices and Wilson loops.

This estimate relates the vortex density $\varrho$, the percentage of P-vortex
plaquettes, to the string tension $\sigma$

$\sigma=\ln(1-2\varrho).$ (4)

Due to the short range Coulomb field, the Creutz ratios

$\chi(R,T)=\frac{\langle W(R+1,T+1)\rangle\;\langle W(R,T)\rangle}{\langle
W(R,T+1)\rangle\;\langle W(R+1,T)\rangle},\qquad\sigma\approx-\log\chi(R,R),$
(5)

of full configurations decrease with $R$ and approach an asymptotic value
$\sigma_{\infty}$.

Figure 4: String tension $\sigma$ calculated with different methods for
$\beta=2.2$ and lattice size $18^{4}$ with 460 SU(2) Wilson configurations.
Left: Without cooling all calculations are compatible to the literature value.
Right: With cooling (strength $0.05$) calculations based upon vortices
underestimate the literature value.

The corresponding asymptotic string tension is usually well reproduced by the
center projected string tension, even for small $R$. For smooth configurations
the center vortex model tends to underestimate $\sigma_{\infty}$, see Fig. 4.
This might be due to a loss of the vortex finding property in some of the
configurations of the ensemble. We suspected that this loss results in center
regions having opposite sign in the projected $Z_{2}$ configurations [8], see
figure 5, than in the full SU(2) configurations.

$\;=\;{\color[rgb]{0.8125,0.,0.}(-1)^{22}}\;\times$

$\;\underbrace{\qquad\qquad\qquad\qquad}_{\text{\large center
regions}}\;\underbrace{\quad\quad\quad\;}_{\text{\large Area
law}}\quad\;\underbrace{\qquad\qquad\qquad}_{\text{ \large Perimeter law}}$

Regions, whose boundaries evaluate to center elements can be used to factorize
a Wilson loop into two parts: an area factor collecting the fully enclosed
non-trivial regions, correlating to vortices, and a factor from non-center
contributions, a perimeter factor.

Figure 5: Factorization of a Wilson loop using center regions.

##  3 Identifying center regions

The algorithm works down a stack of plaquettes sorted by rising trace. For
each plaquette not already selected it tries to find a bigger region by adding
a before unselected neighbouring plaquette whenever the combination of them
results in a region with a more negative trace, see figure 6.

Figure 6: P-Vortices and Wilson loops.

Figure 7 shows the enlargement procedure: A plaquette is stored as connected
list of its links (1), an evaluation with one link missing is stored (2), by
complementing this open region around the neighbouring plaquette the trace of
a possible enlargement and the respective direction of enlargement are stored
(3), by two multiplications the opening is moved along the perimeter of the
region (4) and another possible complementation is calculated (6). If this
complementation is better than the previously done, it overwrites the stored
variables. This steps are repeated until the best direction of enlargement is
identified and the connected list can be complemented around the respective
neighbouring plaquette (13).

1)  2)  3)  4)  5)

6)  … 10)  11)  12)  13)

Figure 7: Algorithm for enlarging regions.

This procedure only considers plaquettes that do not belong to already
identified regions, hence it runs in linear time with respect to the number of
plaquettes.

##  4 Results

In figure 8 the traces of the identified regions are depicted.

Figure 8: Data taken from SU(2) Wilson configurations at $\beta=2.2$ and
lattice size $14^{3}\times 8$ with cooling strength $0.005$. Left: The first
20000 regions sorted by rising trace, taken from one configuration. Right:
Tracefactor-Histogram of the identified regions for different number of
cooling steps taken from 5 configurations.

After 10 cooling steps the algorithm still detects about 5000 non-trivial
regions for $\beta=2.2$ and about 3000 for $\beta=2.4$. The correct
reproduction of the string tension in the non-cooled configuration was based
on $16874\pm 401$ vortex plaquettes for $\beta=2.2$ and $7338\pm 301$ for
$\beta=2.4$. After 10 cooling steps the maximal center gauge and center
projection identify $4540\pm 249$ vortex plaquettes at $\beta=2.2$, but only
$1534\pm 165$ at $\beta=2.4$. Already with our preliminary algorithm for
center region detection slight improvements of the vortex detection can be
expected.

## References

  * ’t Hooft [1978] G. ’t Hooft.  On the phase transition towards permanent quark confinement.  _Nuclear Physics B_ , 138(1):1 – 25, 1978.  ISSN 0550-3213.  https://doi.org/10.1016/0550-3213(78)90153-0.  URL http://www.sciencedirect.com/science/article/pii/0550321378901530.
  * Cornwall [1979] John M. Cornwall.  Quark confinement and vortices in massive gauge-invariant qcd.  _Nuclear Physics B_ , 157(3):392 – 412, 1979\.  ISSN 0550-3213.  https://doi.org/10.1016/0550-3213(79)90111-1.  URL http://www.sciencedirect.com/science/article/pii/0550321379901111.
  * Del Debbio et al. [1998] L. Del Debbio, Manfried Faber, J. Giedt, J. Greensite, and S. Olejnik.  Detection of center vortices in the lattice Yang-Mills vacuum.  _Phys. Rev._ , D58:094501, 1998.  10.1103/PhysRevD.58.094501.
  * Faber et al. [1998] Manfried Faber, J. Greensite, and S. Olejnik.  Casimir scaling from center vortices: Towards an understanding of the adjoint string tension.  _Phys. Rev._ , D57:2603–2609, 1998.  10.1103/PhysRevD.57.2603.
  * Langfeld et al. [1998] Kurt Langfeld, Hugo Reinhardt, and Oliver Tennert.  Confinement and scaling of the vortex vacuum of SU(2) lattice gauge theory.  _Phys. Lett._ , B419:317–321, 1998.  10.1016/S0370-2693(97)01435-4.
  * Höllwieser et al. [2013] Roman Höllwieser, Thomas Schweigler, Manfried Faber, and Urs M. Heller.  Center Vortices and Chiral Symmetry Breaking in SU(2) Lattice Gauge Theory.  _Phys. Rev._ , D88:114505, 2013.  10.1103/PhysRevD.88.114505.
  * Faber and Höllwieser [2017] Manfried Faber and Roman Höllwieser.  Chiral symmetry breaking on the lattice.  _Prog. Part. Nucl. Phys._ , 97:312–355, 2017.  10.1016/j.ppnp.2017.08.001.
  * Golubich and Faber [2018] Rudolf Golubich and Manfried Faber.  Vortex Model of the QCD-vacuum — Successes and Problems.  _Acta Physica Polonica B Proceedings Supplement_ , 11:583–588, 2018.  DOI:10.5506/APhysPolBSupp.11.583.


# Approximate Nash Equilibrium Learning for n-Player Markov Games in Dynamic
Pricing

Larkin Liu1,2
1Technical University of Munich
2Munich Data Science Institute
<EMAIL_ADDRESS>
###### Abstract

We investigate Nash equilibrium learning in a competitive Markov Game (MG)
environment, where multiple agents compete, and multiple Nash equilibria can
exist. In particular, for an oligopolistic dynamic pricing environment, exact
Nash equilibria are difficult to obtain due to the curse-of-dimensionality. We
develop a new model-free method to find approximate Nash equilibria. Gradient-
free black box optimization is then applied to estimate $\epsilon$, the
maximum reward advantage of an agent unilaterally deviating from any joint
policy, and to also estimate the $\epsilon$-minimizing policy for any given
state. The policy-$\epsilon$ correspondence and the state to
$\epsilon$-minimizing policy are represented by neural networks, the latter
being the Nash Policy Net. During batch update, we perform Nash Q learning on
the system, by adjusting the action probabilities using the Nash Policy Net.
We demonstrate that an approximate Nash equilibrium can be learned,
particularly in the dynamic pricing domain where exact solutions are often
intractable.

##  1 Introduction

The application of deep reinforcement learning to solve single player Markov
Decision Processes are relatively well-researched in today’s machine learning
literature, however, the application of novel deep reinforcement learning
methods to solve multi-agent competitive MDP’s are relatively few.
Particularly, the challenge revolves around competing objectives and solving
for, often computationally intractable, Nash equilibria [Nash, 1950] in a
competitive setting, where agents cannot merely maximize only their respective
Q functions. Nash equilibria in Markov Games are particularly useful in the
area of dynamic pricing, a well-known problem in today’s online eCommerce
marketplaces. In a dynamic pricing game, multiple firms compete for market
share of their product on the same online platform. To model this market, we
adopt a modified version of Bertrand oligopoly [Bertrand, 1889], where the
marginal cost of production is 0, and where purchasing behaviour is
probabilistic.

###  1.1 Market Oligopoly

Especially in today’s online commerce industries, dynamic pricing provides
platform firms with an adversarial advantage and increases profit margins in a
competitive economy. In an ideal case, a firm’s pricing strategy should
consider the actions of other firms, providing the justification for Nash
equilibrium policies over unilateral reward maximization policies. In previous
approaches, [Liu et al., 2019] modelled the dynamic pricing problem using deep
reinforcement learning, however, focused primarily on single agent revenue
maximization and not solving for multi-agent Nash equilibria. [Schlosser and
Boissier, 2018] apply stochastic dynamic programming in a simulated
environment to estimate consumer demand and maximize expected profit, however,
do not consider the equilibrium solution of the market. [van de Geer et al.,
2018] model market demand using parametric functions, with unknown parameters,
yet they do not consider a Nash equilibrium nor the actions of previous
pricing on demand. Thus, in almost all recent research on the dynamic pricing
problem under uncertainty, there exists a desideratum to compute and promote
Nash equilibria for market pricing strategies. Such strategies can be applied
to eCommerce platforms such as Amazon auto pricing, allowing firms to opt for
an automated pricing algorithm.

A large body of literature on dynamic pricing has assumed an unknown demand
function and tried to learn the intrinsic relationship between price and
demand. [Harrison et al., 2012] showed that a myopic Bayesian policy may lead
to incomplete learning and poor profit performance. [Liu et al., 2020] studied
a joint pricing and inventory problem while learning the price-sensitive
demand using a Bayesian dynamic program. Many recent studies have revolved
around non-parametric methods. [Besbes and Zeevi, 2009] developed a pricing
strategy that balances the trade-off between exploration and exploitation.
Furthermore, in [Liu et al., 2019] the demand function was a black box system
where the demand was approximated from experience replay and live online
testing in a reinforcement learning framework.

Dynamic pricing in oligopolies presents multiple problems. One aspect is the
optimization problem, where we learn a Nash equilibrium policy when presented
with the parameters of the market demand function, and second is the learning
of the demand parameters itself. For example, [den Boer and Zwart, 2014] and
[Keskin and Zeevi, 2014] studied parametric approaches, using maximum
likelihood to estimate unknown parameters of the demand function. Recent
research has been conducted in demand learning, for example in cases where
multiple products exist, and firms can learn to price on an assortment of
items [Ferreira and Mower, 2022] using multinomial logit regression, or when
multiple products exist in a demand learning scenario, and a limited inventory
exists, Multi-Armed Bandit approaches have shown to be effective at devising
profitable policies [Ferreira et al., 2018]. However, these approaches do not
consider past pricing actions influencing the future market demand parameters.
Furthermore, they do not consider competing firms aiming for a Nash
equilibrium.

We propose a demand market where past pricing affects the future market demand
in a market competition. To search for a Nash equilibrium, we apply a multi-
agent Markov Decision Process, where the state transition is driven by the
joint pricing actions of all players (or firms). To simplify the problem, we
assume that each firm has unlimited inventory, and there is only a single
product with no substitutes.

###  1.2 Multi-agent Markov Decision Processes

Multi-agent Markov Decision Processes, or Markov Games (MG’s), constitute an
important area of research, especially when multiple agents are self-
interested, and an exact or approximate Nash equilibrium for the system is
desired. The computation of Nash equilibria additionaly presents great
difficulty when searching over the enormous joint state action space of the
problem, and approximations to this search problem do exist [Porter et al.,
2008]. Moreover, the existence of multiple Nash equilibria can further
complicate the solution, as some solutions may be more desirable than others.

Yet approximate search algorithms require prior knowledge of the joint reward
function and are often limited to two players, modelled by a best response
function. We treat our payoff function as an oracle [Vorobeychik and Wellman,
2008], meaning we have knowledge regarding the parametric form of the payoff
function, however, there is no knowledge to the agents in the MG regarding how
the reward function generates rewards for the players. The state of the game
is visible to the agents, yet the agents have no knowledge regarding the state
transition function. Nevertheless, the market demand parameters and Nash
equilibria are known for purposes of experimentation. This eliminates the need
for pre-period model fitting to pre-estimate market demand parameters
[Ferreira et al., 2016] allowing us to compare our solution to the theoretical
solution, as opposed to an empirical estimate.

Model-based approaches furthermore exist to provably find the existence of a
Nash equilibrium [Zhang et al., 2020a]. However, we aim for a Nash equilibrium
solver which is model-free, where no knowledge regarding the reward or
transition function is known to the agents. In recent literature, [Ramponi et
al., 2021] present a model-free algorithm to solve competitive MDP’s when the
environment parameters can be altered by an external party - but this is not
always the case in market economics. Furthermore, [Sayin et al., 2021] propose
a model-free decentralized deep learning framework, where the agent is blind
to the other agents actions, and convergence to a Nash equilibrium is proven.
[Zhang et al., 2020b] propose a convergent solution for zero-sum MG’s via
entropy-regularization. However, both [Zhang et al., 2020b] and [Sayin et al.,
2021] impose a number of theoretical restrictions on the MG in order for this
convergence to occur. Moreover, [Kozuno et al., 2021] present a provably
convergent MG solver for imperfect information restricted to two agents.
Nevertheless, we are concerned with an approximate solution to a full
information MG for N agents.

Contributions: This work outlines a methodology for Deep Q Learning, as
introduced in [Mnih et al., 2015], by extending the framework to multi-agent
reinforcement learning (MARL) with a Nash equilibrium objective based on the
methods in [Hu and Wellman, 2003] and [Wang and Sandholm, 2003]. Although the
framework presented in [Hu and Wellman, 2003] is theoretically sound, the
solution to the Nash equilibrium function is often intractable. We therefore
apply approximation methods to compute a Nash equilibrium. Black box
optimization is applied to estimate an $\epsilon$-Nash Equilibrium policy, and
this approximation is learned as a series of neural networks. This MARL model
is then applied to the domain of dynamic pricing.

##  2 Dynamic Pricing Game

An oligopoly across $N$ firms is modelled as a multi-agent Markov Decision
Process with a fully observable state action space. The state space is
represented by the fully-observable demand-influencing reference price
$\bar{p_{t}}$ being the state of the game $s^{t}$. In discrete intervals at
time $t$, each agent issues a price for the item to be sold to the general
market, $x^{t}_{n}$. The reference price, of the market at time $t$ is
determined by a stochastic function of all the agents actions at time $t-1$.
To focus the problem strictly on dynamic pricing, for each firm we assume a
sufficiently large inventory, with no marginal costs of production, no
possibility for inventory stockouts, no holding costs, and the capacity to
always meet any realization of market demand.

###  2.1 Markov Game Parameters

The joint action space $\\{x_{1}^{t}\ ...\ x_{n}^{t}\\}\in\mathbf{X}$
constitutes the current actions of all agents at time $t$, which drive the
state transition by setting prices at time $t$ and represent the set price of
the item from agent $n$ at time $t$. The state-action-reward space is defined
as a tuple $(s^{t},x_{1}^{t},...,x_{N}^{t},r_{1}^{t},...,r_{N}^{t},s^{t+1})$
where $r_{n}^{t}$ is the reward for agent $n$ at time $t$. The joint reward
can be written as $\bar{r}_{t}=(r_{1}^{t},...,r_{N}^{t})$, and the joint
action can be written as $\bar{x}_{t}=(x_{1}^{t},...,x_{N}^{t})$. $N$ denotes
the number of agents. The exact transition probabilities are not known to the
agents. Each agent must learn the demand function and optimal strategy as the
MG progresses. A state $s^{t}$ is determined by the reference price of the
market observable to all agents, $s\in\mathbb{R}$. We discretize the action
space into even segments representing a firm’s price. Where each segment
represents an action $x_{n}\in X_{n}$, and $X_{n}$ is the action space for any
agent $n\in N$.

###  2.2 Reference Pricing

The first pillar of any market dynamic is constituted by the demand function,
dictated by both the historical and contemporary prices, of the firms in the
market. Demand processes can be ideally linear and continuous, however may not
be guaranteed to be stationary or continuous [Den Boer and Keskin, 2020], and
can be subject to various exogenous factors such as environmental carryover
effects [Rao, 1993].

We create an idealization of a market based on [Taudes and Rudloff, 2012],
where a dynamic pricing problem, with reference price effects and a linear
demand function, is imposed. The expected current demand of a product is a
function of the average price set by all firms, denoted as $\tilde{x}$, and a
historical reference price, $\bar{p}$. The reference price $\bar{p}$ is given,
and cannot be modified during the current time $t$, moreover, it is a function
of the immediate past, $t-1$. Although [Taudes and Rudloff, 2012] is not
necessarily the only model that incorporates reference pricing [Mazumdar et
al., 2005], [Fibich et al., 2003], [Popescu and Wu, 2007], [Heidhues and
Kőszegi, 2014], we adopt it due to its simplicity and the existence of
provable Nash equilibria in an oligopolistic framework.

$\displaystyle
f(\tilde{x})=\beta_{0}+\beta_{1}\tilde{x}+\beta_{2}(\tilde{x}-\bar{p}),\quad\beta_{0}$
$\displaystyle\geq 0,\ \beta_{1}<0,\ \beta_{2}\leq 0,\ f(\tilde{x})\geq
0,\tilde{x}\geq 0$ (1)

$\epsilon_{D}$ is defined as the noise from a Poisson process. Such a Poisson
process has the arrival rate $\lambda_{t}(\tilde{x})=f(\tilde{x})$ from Eq.
(1), and standard deviation $\sigma=\sqrt{\lambda_{t}(\tilde{x})}$.
Furthermore, [Taudes and Rudloff, 2012] make the stipulation of decreasing
demand with respect to increasing price, as illustrated in Condition (1).

This demand-influencing reference price can be affected by a variety of
factors, such as inflation, unemployment, psychological perception [Raman et
al., 2002]. Moreover, in many proposed oligopoly models, as in [Janiszewski
and Lichtenstein, 1999] and [Briesch et al., 1997], the reference price is
dictated by a historical joint market price of multiple firms. However,
modelling a competitive market oligopoly with an autocorrelated reference
price in a MG setting is not heavily investigated until now. In our model, we
focus on designing a market whose reference price is driven by the historical
$t-1$ joint market price, and additional factors which also affect the
reference price are represented as noise $\epsilon_{D}$. Thus the transition
of the reference price is determined by the average of the previous joint
prices plus some Guassian randomness, $\epsilon_{D}$.

In our experiment, the reference price of a product is determined by the
previous actions of the firms. We express the reference price function as
$\bar{p}(t):\ \mathbb{R}^{N}\xrightarrow[]{}\mathbb{R}$, mapping a vector of
historical pricing actions $\mathbf{x}^{t-1}$ to $\mathbb{R}$. In the
beginning of the Markovian process, the reference price is randomly generated
within the action space of the pricing range. The stochastic nature of the
market price transition entail the Markov property of the MG.

$\displaystyle\bar{p}(t)$
$\displaystyle\vcentcolon=\frac{1}{N}\sum^{N}_{n=1}x^{t-1}_{n}+\epsilon_{D},\quad\text{where}\quad\bar{p}(t=0)=\frac{1}{N}\sum^{\mathbf{x^{0}}}_{n=1}x^{0}_{n}+\epsilon_{D}$
(2)

###  2.3 Probabilistic Demand Function

The expected profit for player $n$ is $\mathbf{E}[\Pi_{n}(x_{n})]$, which
equals revenue as the marginal cost is of production is assumed to be 0, is
defined as,

$\displaystyle\mathbf{E}[\Pi_{n}(x_{n})]$
$\displaystyle=\Phi_{n}(x_{n},x_{-n})x_{n}f(\tilde{x})$ (3)
$\displaystyle\Phi_{n}(x_{n},x_{-n})$
$\displaystyle=\frac{e^{\phi(x_{n})}}{\sum^{N}_{i=1}e^{\phi(x_{i})}}$ (4)

$\Phi_{n}(x_{n},x_{-n})$ in Eq. (4) represents the probability that a customer
purchases the item sold by firm $n$, where the player $n$ prices their
merchandise with price $x_{n}$. $f(x_{n})$ is the expected demand during the
single stage game for a fixed time period. Following the quantal response
function from [Luce, 1959] and [Goeree et al., 2020], we define a purchase
elasticity function, $\phi_{n}(x_{n},x_{-n})$,

$\displaystyle\phi(x)=$ $\displaystyle\begin{cases}b_{n}-a_{n}x&\text{for
\quad}0<x<b_{n}/a_{n}\\\ 0&\text{for \quad}x>b_{n}/a_{n}\end{cases}$ (5) where
$\displaystyle x\in\mathbb{R},x>0,a\geq 0,b_{n}=1$ (6)

In $\phi(x)$, $b_{n}$ represents the maximum weighted contribution to the
probability of an item being purchased by a customer given a price. When the
price $x$ is 0, this measure is $b_{n}$. For simplification, we assume the
linear marginal decline of this measure of all players $a_{n}$ as equal,
$a_{n}=a$, that is the market has the same elasticity regarding the marginal
decrease of the customer willingness to purchase from any firm as price
increases, with a negative slope $a$. The probability of a customer choosing
to purchase from firm $n$ at price $x_{n}$ among prices set by other firms
$x_{-n}$ is defined by combining a softmax function and purchase elasticity
function, $\phi(x)$. This mechanism will prevent a solution where each firm
undercuts each other to set their prices to 0, as the lowest price need not
guarantee that a consumer will buy their product.

##  3 Nash Equilibrium Conditions

Computation of exact Nash, or approximate $\epsilon$-Nash, equilibria is an
NP-hard problem and notoriously difficult to compute [Daskalakis et al.,
2006]. This involves a search over the entire joint state action space,
computing the value of each state under a candidate policy. Furthermore, it
involves knowledge of the joint Q function and the transition probability of
the system. In our scenario, we have the condition that all agents are
identical, therefore the solution of one agent can apply to the solution of
another.

###  3.1 Theoretical $\epsilon$-Nash Equilibria

Under the market outlined in Section 2, given the market inputs $\bar{p}$ and
$\tilde{x}$, in any pricing strategy, there exists an optimal deviation
$d^{*}\in\mathbf{R}$, such that $\mathbf{E}[\Pi_{n}(x_{n}-d^{*})]$ will yield
the maximum profit advantage $\epsilon$.

$\displaystyle\epsilon$
$\displaystyle=\underset{d^{*}\in\mathbf{R}}{\mathrm{max}}\
\Bigg{(}\mathbf{E}[\Pi_{n}(x_{n}-d^{*})]-\mathbf{E}[\Pi_{n}(x_{n})]\Bigg{)}$
(7)

An increase in the individual profit of an agent $n$ from unilaterally
deviating is denoted as $\epsilon$. Given this optimal deviation, $d^{*}$, a
maximum theoretical upper bound on the profit advantage $\epsilon$ that can be
obtained. Eq. (8) provides the theoretical value of $d^{*}$ which is a
function of both reference price $\bar{p}$ and market price $\tilde{x}$, as
well as the fixed market parameters $\beta_{0},\beta_{1},\beta_{2}$. A
derivation of $d^{*}$ can be found in Appendix B.

$\displaystyle d^{*}$
$\displaystyle=\frac{\sqrt{c_{1}^{2}-c_{1}+4(c_{2}-1)c_{2}-2c_{2}}}{2c_{2}}$
(8) $\displaystyle\text{where}\quad c_{1}$
$\displaystyle=\frac{-(\beta_{1}+\beta_{2})}{f(\tilde{x})}-\frac{1}{\tilde{x}},\quad
c_{2}=\frac{-(\beta_{1}+\beta_{2})}{f(\tilde{x})\tilde{x}}$

Market Scenario 1:
$\beta_{0}=15,\beta_{1}=-1.05,\beta_{2}=-3.1,a=0.1$

Market Scenario 2:
$\beta_{0}=25,\beta_{1}=-0.6,\beta_{2}=-6.1,a=0.1$

Figure 3.1: Surface plot of potential advantage from deviation
($\epsilon$-deviation) from Nash equilibrium with respect to market price
$\tilde{x}$, and reference price $\bar{p}$, with their respective market
parameters $\beta_{0},\beta_{1},\beta_{2},a$ for arrival of a single sales
event.

Using the Eq. (8), as visualized in Fig. 3.1, multiple Nash equilibria can
exist when $\epsilon=0$, or when $\epsilon$ is sufficiently small (see Section
5). Such behaviour occurs when one agent unilaterally deviates from
$\tilde{x}$, under reference price $\bar{p}$. Thus, the lower plateau from
Fig. 3.1 represents the region where a theoretical Nash Equilibrium exists.
Bounds on the state space and action space are limited to $|S|=|X_{n}|=10$,
that is there are 10 discrete intervals for each state $s^{t}$ and action
$x_{n}^{t}$, representing price values.

###  3.2 Nash Equilibrium in Markov Games ($\delta$)

The value of a policy, at each state, can be represented by a joint action
which maximizes the joint Q function [Watkins and Dayan, 1992] under policy
$\pi(s)$. The probability of agent $n$ taking action $x_{n}$ is defined as
$\pi_{n}(s,x_{n})$.

$\displaystyle
v(s,\pi_{n},\pi_{-n})=\underset{\bar{x}\in\mathbf{X}}{\mathrm{max}}\
\prod_{n=1}^{N}\pi_{n}(s,x_{n})Q_{n}(s,x_{n},x_{-n})$ (9)

An $\epsilon$-Nash equilibrium is defined as a joint policy such that the
reward of a single stage game will not result in a greater payoff to the agent
$n$ by more than $\epsilon$, when any agent unilaterally deviates from said
joint policy. Provided $\epsilon$, we consider a bound on the corresponding
MG, $\delta$, which defines a bound on the gain of the value of a policy,
$v(s,{\pi_{n}}^{*},\pi^{*}_{-n})$, should agent $n$ unilaterally deviate with
an alternative policy. The solution to Eq. (9) can be computed by searching
over the joint action space $\\{x_{n},x_{-n}\\}$.

$\displaystyle\underset{\bar{x}\in\mathbf{X}}{\mathrm{argmax}}\prod_{n=1}^{N}\pi_{n}(s,x_{n})Q_{n}(s,x_{n},x_{-n}^{*})$
$\displaystyle\leq\underset{\bar{x}\in\mathbf{X}}{\mathrm{argmax}}\prod_{n=1}^{N}\pi_{n}(s,x_{n})Q_{n}(s,x_{n}^{*},x_{-n}^{*})+\delta$
(10) $\displaystyle v(s,\pi_{n},\pi_{-n}^{*})$ $\displaystyle\leq
v(s,\pi_{n}^{*},\pi_{-n}^{*})+\delta,\quad\forall s\in\mathbf{S}$ (11)

$\delta$ serves as an upper bound on $\epsilon$, therefore the minimization of
$\delta$ will also minimize any possible existence of $\epsilon$ for each
single stage game in the MG. In fact, the existence of $\epsilon$ implies the
existence of upper bound $\delta$, we provide a proof of this existence in
Appendix B.3.

##  4 Multi-Agent Nash Q Learning

In our model, the game provides full information, where information regarding
the state and the actions of all agents are visible to any agent. This allows
for experience replay for Q learning [Mnih et al., 2015] to occur, and the Q
function can be shared for all agents as they are assumed to be identical. The
joint action space $\bar{x}=(x_{1},...,x_{N})$ is defined as the combined
actions of all agents at time $t$. Normally, in Q learning, the update
mechanism searches for the action that maximizes the Q function, however, in
Nash Q learning, we must update the Q function with the solution to the Nash
equilibrium. In our model, we represent the tabular Q function via a function
approximator, which is denoted simply as $Q(s,\bar{x})$. As new experiences
are obtained when the MG is played, the Nash Q value is updated. We utilize
the Q update mechanism defined in [Hu and Wellman, 2003] as the update
mechanism for the Nash Q estimator for Q learning. Given a Q function and a
Nash policy, we search over the joint action that maximizes the scaled Q
function [Laumônier and Chaib-draa, 2005], as in Eq. (13). In our
representation, the Q function is a vector, returning the respective Q value
for each agent, based on the joint probability input for the joint policy.

$\displaystyle Q^{\prime}(s,\bar{x})$
$\displaystyle\xleftarrow[]{}(1-\alpha)Q(s,\bar{x})+\alpha[r+\gamma\mathcal{N}(s^{\prime})]$
(12) $\displaystyle\bar{x}^{*}$
$\displaystyle=\underset{\bar{x}}{\mathrm{argmax}}\
Q(s^{\prime},\bar{x})\prod_{i=1}^{N}\pi_{n}^{*}(s^{\prime},x_{n})$ (13)
$\displaystyle\mathcal{N}(s^{\prime})$
$\displaystyle=Q(s^{\prime},\bar{x}^{*})\prod_{i=1}^{N}\pi_{n}^{*}(s^{\prime},x^{*}_{n})$
(14)

$\mathcal{N}(s^{\prime})$ represents a Nash Operator, indicating the Q value
of a Nash equilibrium, this is approximated by a scaling factor, according to
the Nash equilibrium policy, $\pi^{*}$, multiplied by the Q value of the joint
action, $Q(s,\bar{x})$. Extending from the work of [Hu and Wellman, 2003], we
introduce a neural network for mapping any state action combination to its
Nash policy, where the Nash scaling factor derives from and is used to compute
$\mathcal{N}(s^{\prime})$ in conjunction with the Q function. The Q-function
used in Eq. (14) and (12) is represented by a deep neural network, simply
referred to as the Nash Q Net $Q(s)$. In a full information game with
homogenous agents, a shared neural network representing $Q(s,\bar{x})$ can be
used for all agents in the Markov Game (if not homogeneous a separate Q
network must be retained and updated separately for each agent). The Q Network
parameters representing $\mathcal{N}(s^{\prime})$ is learned in the same
method as Deep Q learning [Mnih et al., 2015], the key innovation, is that the
scaling factor to compute $\mathcal{N}(s^{\prime})$ is obtained via a Nash
Policy Net, $\Psi(s)$ (defined later in Section 4.2).

###  4.1 Estimating Value Advantage via Black Box Optimization

We apply a deep neural network to represent a mapping of a joint policy to its
respective $\delta$ from Eq. (11), designated as
$\Gamma(\pi)\xrightarrow[]{}\bm{\delta}$, where $\bm{\delta}$ is a vector
containing the $\delta_{s}$ of each state. As the gradient of $\Gamma(\pi)$
cannot be easily evaluated, we apply gradient free black box optimization for
$\delta$ minimization. Trust Region Optimization (TRO) has been shown to be
effective for solving high-dimensional optimization problems [Wang et al.,
2020] [Eriksson et al., 2019] [Diouane et al., 2021] [Regis, 2016],
particularly when the computational resources are available. To compute the
existence of an $\epsilon$-Nash equilibrium in the high-dimensional policy
space efficiently, we apply model-based Bayesian Optimization via Trust Region
optimization (TuRBO) from [Eriksson et al., 2019]. TuRBO combines standard TRO
with a multi-armed bandit system via Thompson Sampling [Thompson, 1933] to
optimize for local multiple trust regions simultaneously, with sufficient
convergence time. However, the candidate generation step in TuRBO is not
constrained to account for the valid joint probabilities of each agent, in
which the sum of probabilities for each agent in its respective action space
must sum to 1. We alter TuRBO by simply normalizing the original candidate
probabilities over each set of probabilities belonging to an agent $n$. The
resulting modified algorithm is denoted TuRBO-p, where any candidate value
generated by TuRBO-p will have joint probabilities that sum to 1 for policies
corresponding to each agent.

$\displaystyle V(s,\pi)$ $\displaystyle=\underset{\bar{x}}{\mathrm{max}}\
Q(s,\bar{x})\prod_{i=1}^{N}\pi_{n}(s,x_{n})$ (15) $\displaystyle\delta$
$\displaystyle=\underset{\pi_{n}^{\prime}}{\mathrm{max}}\
\Bigg{(}V(s,\pi_{n}^{\prime},\pi_{-n})-V(s,\pi_{n},\pi_{-n})\Bigg{)}\quad\forall
s\in\mathbf{S}$ (16)

The maximization problem is formulated in Eq. (16) representing the maximum
gain in value of a policy, where agent $n$ deviates from policy $\pi_{n}$ with
$\pi_{n}^{{}^{\prime}}$.

###  4.2 Nash Policy Learning

The $\epsilon$-Nash policy is defined as a joint policy
$(\pi^{*}_{n},\pi^{*}_{-n})$ that minimizes $\delta$ from Eq. (11). Drawing
inspiration from [Ceppi et al., 2010], where a Nash equilibrium is found by
effectively minimizing for $\epsilon$ via linear programming, we apply a
similar technique of $\delta$-minimization. However, in [Ceppi et al., 2010],
the model parameters are known to the agents, and the Markov game was
constrained to two players. In our MG, the joint reward function must be
learned. Therefore, we perform approximate search over the policy space
instead of using exact methods to discover any possible approximate Nash
equilibrium policies. In principle, each state has maps to a corresponding
probability in accordance with the Nash Policy which minimizes $\delta$ in Eq.
16. However, a table keeping track of such an enormous state policy space is
not feasible. Therefore, we implement a Nash Policy Net
$\Psi(s)\xrightarrow[]{}\pi^{*}$ to learn the state to policy mapping, which
is the joint policy $\pi$ producing an approximate Nash equilibrium as
approximated via TuRBO-p, designated as $\hat{\pi}^{*}(s)$.

$\displaystyle\hat{\pi}^{*}(s)=\underset{\pi}{\mathrm{argmin}}\
\Gamma(\pi)_{s}$ (17)

Algorithm 1 Nash equilibrium learning

1:Initialize state joint policy $\pi$.

2:Initialize random parameters for $\Psi(s_{t})$, $Q(s_{t})$ and
$\Gamma(\pi)$, as $\theta_{Q}$, $\theta_{\Psi}$, and $\theta_{\Gamma}$.

3:Initialize MDP Environment, $\mathcal{M}$.

4:for $e\in episodes$ do:

5: Get initial state $s_{0}$ from $\mathcal{M}$.

6: for $t\in(0,t_{max})$ do: Iterate until end of episode.

7: Get action probabilities $\pi(s_{t},x_{n})$ from Nash Policy Net
$\Psi(s_{t})$.

8: for $n\in(1,N)$ do: Iterate through agents.

9: Sample selected action from Nash policy. $x_{n}\thicksim
Multinomial(s_{t},\pi(\overline{x}))$

10: end for

11: Obtain joint action $\overline{x}\xleftarrow[]{}\\{x_{1},...,x_{N}\\}$

12: Assign
$\delta_{s}\xleftarrow[]{}\underset{\pi_{n}^{\prime}}{\mathrm{max}}\
\Bigg{(}V(s,\pi_{n}^{\prime},\pi_{-n})-V(s,\pi_{n},\pi_{-n})\Bigg{)}$ via
TuRBO-p.

13: Find the Nash policy
$\pi^{*}\xleftarrow[]{}\underset{\pi}{\mathrm{argmin}}\ \Gamma(\pi,s_{t})$ via
TuRBO-p.

14: Execute joint action $\overline{x}$ in $(\mathcal{M},\ s_{t})$ to obtain
$s_{t+1},\overline{r}_{t}$.

15: Append experience
$(s_{t},\overline{x}_{t},\overline{r}_{t},\epsilon_{s},\pi,s_{t+1})$ to
experience replay $\mathcal{D}$.

16: Update State $s_{t}\xleftarrow[]{}s_{t+1}$.

17: if $|\mathcal{D}|>batchsize$ then:

18: Sample minibatch $d$ from $\mathcal{D}$.

19: Set $Q^{\prime}(s_{t},\bar{x})\xleftarrow[]{}\begin{cases}r_{t}&\text{for
\ }s_{t}\ \text{terminal}\\\
(1-\alpha)Q(s,\bar{x})+\alpha[r+\gamma\mathcal{N}(s^{\prime})]&\text{for \
}s_{t}\ \text{not terminal}\end{cases}$

20:
$\mathcal{L}_{Q}\xleftarrow[]{}(Q^{\prime}(S_{t},\bar{x})-Q(S_{t},\bar{x}))^{2}$
Nash Q Update.

21: $\mathcal{L}_{\Psi}\xleftarrow[]{}(\hat{\pi}-\pi^{*})^{2}$ Nash policy
update, where $\hat{\pi}$ is from $\Psi(s)$.

22: $\mathcal{L}_{\Gamma}\xleftarrow[]{}(\hat{\epsilon}-\epsilon)^{2}$ Nash
$\epsilon$ update, where $\hat{\epsilon}$ is from $\Gamma(\pi)$

23: Backpropagate loss functions $\mathcal{L}_{Q}$, $\mathcal{L}_{\Psi}$ and
$\mathcal{L}_{\Gamma}$ on $\mathcal{Q}$, $\Psi$, and $\Gamma$.

24: Update model parameters $\theta_{Q}$, $\theta_{\Psi}$, and
$\theta_{\Gamma}$ via gradient descent.

25: end if

26: Update joint policy $\overline{\pi}\xleftarrow[]{}\overline{\pi}^{*}$.

27: end for

28:end for

##  5 Results

Loss behaviour of Scenario 1 with $n=3$.

Loss behaviour of Scenario 2 with $n=5$.

Figure 5.1: Decreasing loss behaviour of batch update during Deep Q Learning
$Q$ (left y axis) and Nash Net update $\Psi(s)$ (right y axis) demonstrating
that $\Psi(s)$ has learned a representation of the Nash policy (x-axis
represents iterations multiplied by episode).

Stabilization of realized market rewards to Nash equilibrium: Fig. 5.2
represents the convergence of the average market reward of a single agent
(randomly selected as agent 0) towards a Nash equilibrium. We superimpose the
boundaries of the theoretical Nash equilibrium reward over the plot. The
reward is obtained from the boundaries of theoretical Nash equilibria, where
$\epsilon<\epsilon_{l}$ ($\epsilon_{l}=0.0001$). The topology of this function
is illustrated in Fig. 3.1, and for each state, or reference price, there
exists a boundary where the policy deviation of any agent can occur without
significant unilateral reward gain. The expected reward is computed using the
market model parameters per Scenario ($\beta_{0},\beta_{1},\beta_{2},a$). From
the expected reward, we compare it with the positive difference of theoretical
equilibrium reward $\Pi^{\prime}=f(x_{n}^{\prime})\ x_{n}^{\prime}$ where
$x_{n}^{\prime}$. This exists as two boundary points indicating the area where
$\epsilon<\epsilon_{l}$. For each episode the average reward per timestep over
the episode lengths is recorded. From Fig. 5.2, we observe the average reward
per agent of the system per episode (blue dashed line), and the average reward
of a single agent per episode (orange dashed line), to converge within the
boundary of Nash equilibrium (blue shade). However, due to randomization from
black box optimization and/or stochastic behaviour of the Markov Game this
expected reward can sometimes fall outside of the NE region.

Diminishing loss function: We demonstrate empirically, as shown in Fig. 5.1,
that the loss function of $Q(s)$ and $\Psi(s)$ decrease with each RL episode.
This merely indicates that a representation of the function mapping state to
its corresponding Nash policy based on policy-to-$\epsilon$ model
$\Gamma(\pi)$ is being learned, and a stable solution is proposed.
Hyperparameters are presented in Appendix C.

Market rewards per episode Scenario 1, $n=3$.

Market rewards per episode Scenario 2, $n=5$.

Figure 5.2: In a Nash equilibrium, both the market average reward (blue), and
single agent reward (orange) should fall within the Nash equilibria boundary
(blue shade), as the MG progresses.

Comparison with baseline cooperative Q-learning model: We compare our NE
learning model wit a naive cooperative Q learning model to serve as a baseline
measure of model performance. In the naive Q learning model, the objective is
simply to maximize each agent’s respective rewards, and avoid any kind of NE
computation. The Q update function in Eq. (12) is simply a maximization of the
joint Q function, instead of using $\mathcal{N}(s^{\prime})$. From Fig.5.3, we
generally observe lower average reward values from the baseline model compared
to the NE learning model. The NE reward ranges remain very similar. From an
economic perspective, the Nash Q learning agents take into account that other
agents will compete against them, and the solver optimizes accordingly,
whereas, in cooperative Q learning no consideration for the other agents’
strategies are taken, and agents may to over-compete, driving average rewards
lower in an oligopoly.

Scenario 1 - NE Learning vs Q learning, $n=3$.

Scenario 2 - NE Learning vs Q learning, $n=5$.

Figure 5.3: Average revenue per episode from a NE learning model (blue) versus
a baseline Q learning model (green), with NE reward boundaries overlayed in
their respective colours.

##  6 Conclusion

We created a Markov Game that represents an n-firm oligopoly, based on
previously established market models where theoretical $\epsilon$ bounds for a
Nash equilibrium policy exist. A black box algorithm is applied to estimate an
upper bound on the $\epsilon$ value of a joint policy, represented by neural
network $\Gamma(\pi)$. Similarly a Nash Policy Net $\Psi(s)$ is learned to
represent the $\epsilon$-minimizing policy from black box optimization,
constituting an $\epsilon$-Nash policy. Thus $\Psi(s)$ can be used together
with traditional Deep Q learning, to solve for a Nash equilibrium.
Empirically, we show that the average reward of all agents, and the reward of
a respective single agent, converges to an approximate Nash equilibrium. The
limitations of this research are the limited action space of the agents, as
well as the identical nature of the agents. Larger scale experimentation under
this framework is suggested. Furthermore, the proposed market model could be
enhanced by implementing more complex non-linear market oligopoly
environments.

## References

  * Bertrand [1889] Joseph Bertrand.  _Review of Walras’s Théorie mathématique de la richesse sociale and Cournot’s Recherches sur les principes mathématiques de la théorie des richesses_ , page 73–81.  Cambridge University Press, 1889.  doi: 10.1017/CBO9780511528231.006.
  * Besbes and Zeevi [2009] Omar Besbes and Assaf Zeevi.  Dynamic pricing without knowing the demand function: Risk bounds and near-optimal algorithms.  _Operations Research_ , 57(6):1407–1420, 2009\.
  * Briesch et al. [1997] Richard A Briesch, Lakshman Krishnamurthi, Tridib Mazumdar, and Sevilimedu P Raj.  A comparative analysis of reference price models.  _Journal of Consumer Research_ , 24(2):202–214, 1997.
  * Ceppi et al. [2010] Sofia Ceppi, Nicola Gatti, Giorgio Patrini, and Marco Rocco.  Local search methods for finding a nash equilibrium in two-player games.  pages 335–342, 08 2010.  doi: 10.1109/WI-IAT.2010.57.
  * Daskalakis et al. [2006] Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou.  The complexity of computing a nash equilibrium.  In _Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing_ , STOC ’06, page 71–78, New York, NY, USA, 2006. Association for Computing Machinery.  ISBN 1595931341.  doi: 10.1145/1132516.1132527.
  * Den Boer and Keskin [2020] Arnoud V. Den Boer and N. Bora Keskin.  Discontinuous demand functions: Estimation and pricing.  _Management Science_ , 66, 04 2020.  doi: 10.1287/mnsc.2019.3446.
  * den Boer and Zwart [2014] Arnoud V den Boer and Bert Zwart.  Simultaneously learning and optimizing using controlled variance pricing.  _Management Science_ , 60(3):770–783, 2014.
  * Diouane et al. [2021] Youssef Diouane, Victor Picheny, Rodolphe Le Riche, and Alexandre Scotto Di Perrotolo.  Trego: a trust-region framework for efficient global optimization, 2021\.  URL https://arxiv.org/abs/2101.06808.
  * Eriksson et al. [2019] David Eriksson, Michael Pearce, Jacob R. Gardner, Ryan Turner, and Matthias Poloczek.  Scalable global optimization via local bayesian optimization.  _CoRR_ , abs/1910.01739, 2019.  URL http://arxiv.org/abs/1910.01739.
  * Ferreira and Mower [2022] Kris Johnson Ferreira and Emily Mower.  Demand learning and pricing for varying assortments.  _Manufacturing & Service Operations Management_, 2022.
  * Ferreira et al. [2016] Kris Johnson Ferreira, Bin Hong Alex Lee, and David Simchi-Levi.  Analytics for an online retailer: Demand forecasting and price optimization.  _Manufacturing & Service Operations Management_, 18(1):69–88, 2016.
  * Ferreira et al. [2018] Kris Johnson Ferreira, David Simchi-Levi, and He Wang.  Online network revenue management using thompson sampling.  _Operations Research_ , 66(6):1586–1602, 2018\.
  * Fibich et al. [2003] Gadi Fibich, Arieh Gavious, and Oded Lowengart.  Explicit solutions of optimization models and differential games with nonsmooth (asymmetric) reference-price effects.  _Operations Research_ , 51(5):721–734, 2003.
  * Filar and Vrieze [1997] J. Filar and K. Vrieze.  _Competitive Markov Decision Processes_.  Springer, 1997.
  * Goeree et al. [2020] Jacob K. Goeree, Charles A. Holt, and Thomas R. Palfrey.  _Stochastic game theory for social science: a primer on quantal response equilibrium_.  Edward Elgar Publishing, Cheltenham, UK, 2020.  ISBN 9781785363320.  URL https://www.elgaronline.com/view/edcoll/9781785363320/9781785363320.xml.
  * Harrison et al. [2012] J Michael Harrison, N Bora Keskin, and Assaf Zeevi.  Bayesian dynamic pricing policies: Learning and earning under a binary prior distribution.  _Management Science_ , 58(3):570–586, 2012.
  * Heidhues and Kőszegi [2014] Paul Heidhues and Botond Kőszegi.  Regular prices and sales.  _Theoretical Economics_ , 9(1):217–251, 2014\.
  * Hu and Wellman [2003] Junling Hu and Michael P. Wellman.  Nash q-learning for general-sum stochastic games.  _Journal of Machine Learning Research_ , 4:1039–1069, December 2003.  ISSN 1532-4435.
  * Janiszewski and Lichtenstein [1999] Chris Janiszewski and Donald R Lichtenstein.  A range theory account of price perception.  _Journal of Consumer Research_ , 25(4):353–368, 1999.
  * Keskin and Zeevi [2014] N Bora Keskin and Assaf Zeevi.  Dynamic pricing with an unknown demand model: Asymptotically optimal semi-myopic policies.  _Operations Research_ , 62(5):1142–1167, 2014\.
  * Kozuno et al. [2021] Tadashi Kozuno, Pierre Ménard, Rémi Munos, and Michal Valko.  Model-free learning for two-player zero-sum partially observable markov games with perfect recall, 2021.  URL https://arxiv.org/abs/2106.06279.
  * Laumônier and Chaib-draa [2005] Julien Laumônier and Brahim Chaib-draa.  Multiagent q-learning: Preliminary study on dominance between the nash and stackelberg equilibriums.  In _Proceedings of AAAI-2005 Workshop on Multiagent Learning, Pittsburgh, USA_ , 2005.
  * Liu et al. [2019] Jiaxi Liu, Yidong Zhang, Xiaoqing Wang, Yuming Deng, and Xingyu Wu.  Dynamic pricing on e-commerce platform with deep reinforcement learning.  _CoRR_ , abs/1912.02572, 2019.  URL http://arxiv.org/abs/1912.02572.
  * Liu et al. [2020] Jue Liu, Zhan Pang, and Linggang Qi.  Dynamic pricing and inventory management with demand learning: A bayesian approach.  _Computers & Operations Research_, 124:105078, 2020.  doi: 10.1016/j.cor.2020.105078.
  * Luce [1959] R. Duncan Luce.  _Individual Choice Behavior: A Theoretical Analysis_.  Wiley, New York, NY, USA, 1959.
  * Mazumdar et al. [2005] Tridib Mazumdar, Sevilimedu P Raj, and Indrajit Sinha.  Reference price research: Review and propositions.  _Journal of Marketing_ , 69(4):84–102, 2005.
  * Mnih et al. [2015] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis.  Human-level control through deep reinforcement learning.  _Nature_ , 518(7540):529–533, February 2015.  ISSN 00280836.
  * Nash [1950] John F. Nash.  Equilibrium points in n-person games.  _Proceedings of the National Academy of Sciences_ , 36(1):48–49, 1950.  ISSN 0027-8424.  doi: 10.1073/pnas.36.1.48.  URL https://www.pnas.org/content/36/1/48.
  * Popescu and Wu [2007] Ioana Popescu and Yaozhong Wu.  Dynamic pricing strategies with reference effects.  _Operations Research_ , 55(3):413–429, 2007.
  * Porter et al. [2008] Ryan Porter, Eugene Nudelman, and Yoav Shoham.  Simple search methods for finding a nash equilibrium.  _Games and Economic Behavior_ , 63(2):642–662, 2008.  Second World Congress of the Game Theory Society.
  * Raman et al. [2002] Kalyan Raman, Frank M Bass, et al.  A general test of reference price theory in the presence of threshold effects.  _Tijdschrift voor Economie en management_ , 47(2):205–226, 2002.
  * Ramponi et al. [2021] Giorgia Ramponi, Alberto Maria Metelli, Alessandro Concetti, and Marcello Restelli.  Learning in non-cooperative configurable markov decision processes.  In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, _Advances in Neural Information Processing Systems_ , 2021.  URL https://openreview.net/forum?id=t-0eCf8L4-a.
  * Rao [1993] Vithala R Rao.  Pricing models in marketing.  _Handbooks in Operations Research and Management Science_ , 5:517–552, 1993.
  * Regis [2016] Rommel G. Regis.  Trust regions in kriging-based optimization with expected improvement.  _Engineering Optimization_ , 48(6):1037–1059, 2016.  URL https://doi.org/10.1080/0305215X.2015.1082350.
  * Sayin et al. [2021] Muhammed O. Sayin, Kaiqing Zhang, David S. Leslie, Tamer Basar, and Asuman E. Ozdaglar.  Decentralized q-learning in zero-sum markov games.  _CoRR_ , abs/2106.02748, 2021.  URL https://arxiv.org/abs/2106.02748.
  * Schlosser and Boissier [2018] Rainer Schlosser and Martin Boissier.  Dynamic pricing under competition on online marketplaces: A data-driven approach.  In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , KDD ’18, page 705–714, New York, NY, USA, 2018. Association for Computing Machinery.  doi: 10.1145/3219819.3219833.
  * Taudes and Rudloff [2012] Alfred Taudes and Christian Rudloff.  Integrating inventory control and a price change in the presence of reference price effects: a two-period model.  _Mathematical Methods of Operations Research_ , 75(1):29–65, 2012.
  * Thompson [1933] William R Thompson.  On the likelihood that one unknown probability exceeds another in view of evidence of two samples.  _Biometrika_ , 25(3-4):285–294, 12 1933.  doi: 10.1093/biomet/25.3-4.285.
  * van de Geer et al. [2018] Ruben van de Geer, Arnoud V. den Boer, Christopher Bayliss, Christine S. M. Currie, Andria Ellina, Malte Esders, Alwin Haensel, Xiao Lei, Kyle D. S. Maclean, Antonio Martinez-Sykora, and et al.  Dynamic pricing and learning with competition: insights from the dynamic pricing challenge at the 2017 informs rm & pricing conference.  _Journal of Revenue and Pricing Management_ , 18(3):185–203, Oct 2018.  ISSN 1477-657X.  doi: 10.1057/s41272-018-00164-4.  URL http://dx.doi.org/10.1057/s41272-018-00164-4.
  * Vorobeychik and Wellman [2008] Yevgeniy Vorobeychik and Michael Wellman.  Stochastic search methods for nash equilibrium approximation in simulation-based games.  pages 1055–1062, 01 2008.  doi: 10.1145/1402298.1402368.
  * Wang et al. [2020] Linnan Wang, Rodrigo Fonseca, and Yuandong Tian.  Learning search space partition for black-box optimization using monte carlo tree search.  _CoRR_ , abs/2007.00708, 2020.  URL https://arxiv.org/abs/2007.00708.
  * Wang and Sandholm [2003] Xiaofeng Wang and Tuomas Sandholm.  Reinforcement learning to play an optimal nash equilibrium in team markov games.  In S. Becker, S. Thrun, and K. Obermayer, editors, _Advances in Neural Information Processing Systems_ , volume 15. MIT Press, 2003.  URL https://proceedings.neurips.cc/paper/2002/file/f8e59f4b2fe7c5705bf878bbd494ccdf-Paper.pdf.
  * Watkins and Dayan [1992] Christopher J. C. H. Watkins and Peter Dayan.  Q-learning.  _Machine Learning_ , 8(3):279–292, May 1992.  doi: 10.1007/BF00992698.
  * Zhang et al. [2020a] Kaiqing Zhang, Sham M. Kakade, Tamer Basar, and Lin F. Yang.  Model-based multi-agent RL in zero-sum markov games with near-optimal sample complexity.  _CoRR_ , abs/2007.07461, 2020a.  URL https://arxiv.org/abs/2007.07461.
  * Zhang et al. [2020b] Qifan Zhang, Yue Guan, and Panagiotis Tsiotras.  Learning nash equilibria in zero-sum stochastic games via entropy-regularized policy approximation.  _CoRR_ , abs/2009.00162, 2020b.  URL https://arxiv.org/abs/2009.00162.

## Supplemental Material

##  Appendix A Softmax Win Probability

Proposition: In an N-player game when deviating from the equilibrium market
price by an amount of $d$, given the softmax win probability $\Phi(x_{n})$ in
Eq. (4), the probability of winning a customer changes by a factor of
$\Phi_{d}$ as defined in Eq. (19).

Proof: Suppose N-1 players set an equal price of $\tilde{x}$ and one player
deviates with price $x_{n}$, where $x_{n}=\tilde{x}-d$.

The players who do not deviate from the equilibrium price, will have a win
probability of $\Phi(\tilde{x})$

$\displaystyle\Phi(\tilde{x})$
$\displaystyle=\frac{e^{1-a\tilde{x}}}{\sum^{N}_{i=1}e^{1-ax_{i}}}$ (18)

The player that deviates from the market price will have a win probability of
$\Phi(x_{n})$,

$\displaystyle\Phi(x_{n})$
$\displaystyle=\frac{e^{1-ax_{n}}}{\sum^{N}_{i=1}e^{1-ax_{i}}}=\frac{e^{1-a(\tilde{x}-d)}}{\sum^{N}_{i=1}e^{1-ax_{i}}-e^{\tilde{x}}+e^{1-a(\tilde{x}-d)}}$
$\displaystyle=\frac{e^{1-a(\tilde{x}-d)}}{N_{\Phi}+e^{1-a(\tilde{x}-d)}},\quad\text{where}\
N_{\Phi}=\sum^{N}_{i=1}e^{1-ax_{i}}-e^{\tilde{x}}$ (19)

The increase in win probability by deviating from the equilibrium price
$\tilde{x}$ by an increment of $d$ is denoted by $\Phi_{d}$,

$\displaystyle\Phi_{d}$
$\displaystyle=\frac{\Phi(x_{n})}{\Phi(\tilde{x})}=\frac{e^{1-a(\tilde{x}-d)}}{N_{\Phi}+e^{\tilde{x}-d}}\frac{N_{\Phi}+e^{\tilde{x}}}{e^{1-a\tilde{x}}}=e^{ad}\frac{N_{\Phi}+e^{\tilde{x}}}{N_{\Phi}+e^{\tilde{x}-d}}$
(20)

As follows from Eq. (20) the probability of winning a customer’s purchase by
changing price with deviation $d$ with respect to the equilibrium price
effectively changes the win probability by a factor $\Phi_{d}$.

###  A.1 Admissible Values of Profit Function

Proposition: In an N-player game when deviating from the market price by an
amount of $d\in\mathbb{R}$, there always exists a boundary $(d^{-},d^{+})$
such that the expected profit from deviating $\mathbf{E}[\Pi_{n}]^{\prime}>0$
exists. We define this as the admissible range.

$\displaystyle\frac{\mathbf{E}[\Pi_{n}]^{\prime}}{\mathbf{E}[\Pi_{n}]^{0}}>0,\quad\forall
d\in(d^{-},d^{+})$ (21)

Proof: We define the gain function $\Omega(d)$ as,

$\displaystyle\Omega(d)$
$\displaystyle=\frac{\mathbf{E}[\Pi_{n}]^{\prime}}{\mathbf{E}[\Pi_{n}]^{0}}=\frac{\Phi(x_{n})f(x_{n})x_{n}}{\Phi(\tilde{x})f(\tilde{x})\tilde{x}}=\frac{\Phi(\tilde{x})\Phi_{d}[f(\tilde{x})+\gamma
d](\tilde{x}-d)}{\Phi(\tilde{x})f(\tilde{x})\tilde{x}}$
$\displaystyle=\Phi_{d}\frac{[f(\tilde{x})+\gamma
d](\tilde{x}-d)}{f(\tilde{x})\tilde{x}}=\Phi_{d}(1+\frac{\gamma}{f(\tilde{x})}d)(1-\frac{1}{\tilde{x}}d)$
$\displaystyle\Omega(d)$
$\displaystyle=\Phi_{d}(1+\frac{\gamma}{f(\tilde{x})}d)(1-\frac{1}{\tilde{x}}d)$
(22)

Given the deviation condition $\Omega(d)>0$ and Condition (1), the admissible
range is more precisely defined as a range for $d$ where a solution for
Inequality (23) exists,

$\displaystyle\Omega(d)\implies(1+\frac{\gamma}{f(\tilde{x})}d)(1-\frac{1}{\tilde{x}}d)>0$
$\displaystyle\implies-\frac{f(\tilde{x})}{\gamma}<d<\tilde{x}$ (23)

We see from Inequality (23) that there is a bound on admissible values of
$d\in(-f(\tilde{x})/\gamma,\tilde{x})$ which results in admissible $\Omega(d)$
values.

##  Appendix B Equilibrium Study

The Nash equilibrium of a pricing strategy can be either a pure or mixed
strategy. We prove that for a pure strategy, in the support of a mixed
strategy, an $\epsilon$-Nash equilibrium exists. Consequently, multiple Nash
equilibria can exist in this pricing game. Suppose a hypothetical equilibrium
where a market price $\tilde{x}$ exists. We examine the hypothetical situation
if one agent were to deviate from the $\tilde{x}$ of with a price of $x_{n}$.
Particularly, we study the case when a player undercuts or prices above a set
market price, where $x_{n}=\tilde{x}-d$ and $d$ is the value which the player
deviates from the equilibrium price. From the equilibrium setting, as follows
from Eq. (24),

$\displaystyle f(\tilde{x})$
$\displaystyle=\beta_{0}+\beta_{1}\tilde{x}+\beta_{2}(\tilde{x}-\bar{p})$
$\displaystyle=\beta_{0}+\beta_{1}\tilde{x}+\beta_{2}\tilde{x}+c_{N}$ (24)
$\displaystyle\text{where}\quad c_{N}$ $\displaystyle=-\beta_{2}\bar{p}$

We derive Eq. (25) from Eq. (24). From Eq. (25) we see that the expected
demand is simply the demand function at equal pricing $f(\tilde{x})$ corrected
by a factor of $\gamma d$ as defined in the Eq. (26), where $d$ is the amount
the player $n$ deviates from the equilibrium price.

$\displaystyle f(x_{n})$
$\displaystyle=\beta_{0}+\beta_{1}(x_{n}-d)+\beta_{2}(x_{n}-d-\bar{p})$
$\displaystyle=\beta_{0}+\beta_{1}x_{n}+\beta_{2}x_{n}+c_{N}-(\beta_{1}+\beta_{2})d$
$\displaystyle=\beta_{0}+\beta_{1}x_{n}+\beta_{2}x_{n}+c_{N}+\gamma d$
$\displaystyle f(x_{n})$ $\displaystyle=f(\tilde{x})+\gamma d$ (25)
$\displaystyle\text{where}\quad x_{n}$
$\displaystyle\in\mathbb{R},\gamma=-(\beta_{1}+\beta_{2}),x>0,d\in\mathbb{R}$
(26)

###  B.1 Proof of a Best Response Function (Market Undercutting Scenario)

Proposition: In an N-player game, under specific market conditions dictated by
the reference price $\bar{p}$ and equilibrium price $\tilde{x}$, under certain
proven conditions, stipulated later in Condition 33, there can exist a
boundary $(0,d^{\prime})$ such that the expected profit from deviating is
greater than not deviating $\mathbf{E}[\Pi_{n}]^{-}>\mathbf{E}[\Pi_{n}]^{0}$,
when deviating from the market price by undercutting with an amount of $d>0$,
as illustrated by Inequality (27).

$\displaystyle\frac{\mathbf{E}[\Pi_{n}]^{\prime}}{\mathbf{E}[\Pi_{n}]^{0}}>1,\quad\forall
d\in(0,d^{\prime})$ (27)

Given the deviation constraint $d>0$, therefore $\Phi_{d}>1$, refer to
Supplemental A, we find the solution for the polynomial section of the gain
function, defined by Eq. (28).

$\displaystyle\Omega(d)_{p}$
$\displaystyle=(1+\frac{\gamma}{f(\tilde{x})}d)(1-\frac{1}{\tilde{x}}d)$ (28)
$\displaystyle\Omega(d)_{p}$ $\displaystyle>1$ (29)

With the constraint $d>0$, a solution to Inequality (29) is restricted by
Condition (30). And such a solution only exists when
$\tilde{x}>f(\tilde{x})/\gamma$.

$\displaystyle 0<d$
$\displaystyle<\frac{\frac{\gamma}{f(\tilde{x})}-\frac{1}{\tilde{x}}}{\frac{\gamma}{f(\tilde{x})\tilde{x}}}$
(30) $\displaystyle d$
$\displaystyle\in(0,\tilde{x}-f(\tilde{x})/\gamma)\quad\text{when}\quad\tilde{x}>f(\tilde{x})/\gamma$
(31)

Making substitutions from, Eq. (24) into Eq. (31),

$\displaystyle f(\tilde{x})/\gamma$ $\displaystyle<\tilde{x}$
$\displaystyle\frac{\beta_{0}+\beta_{1}\tilde{x}+\beta_{2}\tilde{x}+c_{N}}{-(\beta_{1}+\beta_{2})}$
$\displaystyle<\tilde{x}$
$\displaystyle\frac{\beta_{0}+c_{N}}{-(\beta_{1}+\beta_{2})}+\tilde{x}\frac{\beta_{1}+\beta_{2}}{-(\beta_{1}+\beta_{2})}$
$\displaystyle<\tilde{x}$
$\displaystyle\frac{\beta_{0}+c_{N}}{-(\beta_{1}+\beta_{2})}$
$\displaystyle<\tilde{x}\Bigg{(}1+\frac{\beta_{1}+\beta_{2}}{\beta_{1}+\beta_{2}}\Bigg{)}$
$\displaystyle-\frac{\beta_{0}+c_{N}}{2(\beta_{1}+\beta_{2})}$
$\displaystyle<\tilde{x}$
$\displaystyle\frac{\beta_{2}\bar{p}-\beta_{0}}{2(\beta_{1}+\beta_{2})}$
$\displaystyle<\tilde{x}$ (32)

We see from Inequality (32) that if the equilibrium price of the other agents
$\tilde{x}$ is priced below a function of the reference price $\bar{p}$ there
will be no value of $d$ that satisfies Inequality (31). Therefore, the agent
will not gain profit from undercutting if $\tilde{x}$, the current market
price, is under a certain limit with respect a monotonic function the
reference price $\bar{p}$. The exact conditions on which undercutting the
$\tilde{x}$ will yield profit gain for any agent $n$ is outlined in Inequality
(33).

$\displaystyle\frac{\beta_{2}\bar{p}-\beta_{0}}{2(\beta_{1}+\beta_{2})}<\tilde{x}\And
d$
$\displaystyle\in(0,\tilde{x}-f(\tilde{x})/\gamma)\implies\mathbf{E}[\Pi_{n}]^{-}>\mathbf{E}[\Pi_{n}]^{0}\qed$
(33)

###  B.2 Proof the Existence of Multiple $\epsilon$-Nash Equilibria Single
Stage Game

Proposition: Suppose the market is in an equilibrium state where all agents
price their items at a fixed price, and one player elects to undercut the
market. We demonstrate that there is a theoretical maximum expected reward in
this oligopoly for a single stage game for undercutting the market.

$\displaystyle\mathbf{E}[\Pi_{n}]^{-}\leq\mathbf{E}[\Pi_{n}]^{0}+\epsilon$
(34)

Inequality (34) expresses the conditions of an $\epsilon$-Nash equilibrium,
that is no player can obtain a higher reward than a margin of $\epsilon$ by
deviating from the equilibrium price of the market $\mathbf{E}[\Pi_{n}]^{0}$.
In effect we acknowledge that the upper bound of $\Phi_{d}$ in Eq. (20) as,

$\displaystyle
e^{ad}\frac{N_{\Phi}+e^{1-a\tilde{x}}}{N_{\Phi}+e^{1-a\tilde{x}+d}}$
$\displaystyle\leq e^{N_{\phi}ad}$ (35) $\displaystyle\Phi_{d}$
$\displaystyle\leq e^{N_{\phi}ad}$ (36)

We take the partial derivative with respect the deviation amount $d$ to obtain
theoretical maximum of $\Omega$.

$\displaystyle\frac{\partial\mathbf{E}[\Pi_{n}]^{-}}{\partial d}$
$\displaystyle=\frac{\partial}{\partial
d}\Bigg{[}e^{N_{\phi}ad}(1+\frac{\gamma}{f(\tilde{x})}d)(1-\frac{1}{\tilde{x}}d)\Bigg{]}$
$\displaystyle\frac{\partial\mathbf{E}[\Pi_{n}]^{-}}{\partial d}$
$\displaystyle=e^{N_{\phi}a}\frac{\partial}{\partial
d}\Bigg{[}e^{d}(1+\frac{\gamma}{f(\tilde{x})}d)(1-\frac{1}{\tilde{x}}d)\Bigg{]}$
(37)

Solve the derivative,

$\displaystyle\frac{\partial\mathbf{E}[\Pi_{n}]^{-}}{\partial d}$
$\displaystyle=0$ $\displaystyle e^{N_{\phi}a}\frac{\partial}{\partial
d}\Bigg{[}e^{d}(1+\frac{\gamma}{f(\tilde{x})}d)(1-\frac{1}{\tilde{x}}d)\Bigg{]}$
$\displaystyle=0$ $\displaystyle\frac{\partial}{\partial
d}\Bigg{[}e^{d}+\frac{\gamma}{f(\tilde{x})}de^{d}-\frac{1}{\tilde{x}}de^{d}-\frac{\gamma}{f(\tilde{x})\tilde{x}}d^{2}e^{d}\Bigg{]}$
$\displaystyle=0$ $\displaystyle\frac{\partial}{\partial
d}\Bigg{[}e^{d}+\Bigg{(}\frac{\gamma}{f(\tilde{x})}-\frac{1}{\tilde{x}}\Bigg{)}de^{d}-\frac{\gamma}{f(\tilde{x})\tilde{x}}d^{2}e^{d}\Bigg{]}$
$\displaystyle=0$ $\displaystyle
e^{d}\Bigg{[}\Bigg{(}\frac{\gamma}{f(\tilde{x})}-\frac{1}{\tilde{x}}\Bigg{)}(d+1)-\frac{\gamma}{f(\tilde{x})\tilde{x}}d(d+2)+1\Bigg{]}$
$\displaystyle=0$
$\displaystyle\Bigg{(}\frac{\gamma}{f(\tilde{x})}-\frac{1}{\tilde{x}}\Bigg{)}(d+1)-\frac{\gamma}{f(\tilde{x})\tilde{x}}d(d+2)+1$
$\displaystyle=0$ (38)

The solution to Eq. (38)

$\displaystyle d^{*}$
$\displaystyle=\frac{\sqrt{c_{1}^{2}-c_{1}+4(c_{2}-1)c_{2}-2c_{2}}}{2c_{2}}$
(39) $\displaystyle\text{where}\quad c_{1}$
$\displaystyle=\frac{\gamma}{f(\tilde{x})}-\frac{1}{\tilde{x}},\quad
c_{2}=\frac{\gamma}{f(\tilde{x})\tilde{x}}$ (40)

We proved that when a player deviates from the market price by a margin of
$d$, there exists an optimal deviation amount $d^{*}$, outlined in Eq. (39)
such that the expected profit gain $\Omega$ is maximized. $\epsilon$ is
therefore,

$\displaystyle\epsilon$
$\displaystyle=\mathbf{E}[\Pi_{n}]^{-}-\mathbf{E}[\Pi]^{0}$
$\displaystyle=\Omega(d^{*})\mathbf{E}[\Pi_{n}]^{0}-\mathbf{E}[\Pi_{n}]^{0}$
$\displaystyle=\mathbf{E}[\Pi_{n}]^{0}[\Omega(d^{*})-1)]$ (41)

Multiple solutions can exist where $d^{*}=0$, to give a perfect Nash
equilibria solution, as $c_{1}$ and $c_{2}$ are functions of $\tilde{x}$. The
Nash equilibrium condition is,

$\displaystyle
c_{1}^{2}+4(c_{2}-1)c_{2}=c_{1}+2c_{2}\quad\xrightarrow[]{}\quad\epsilon=0$
(42)

Therefore, by undercutting the market with any price $d>0$, a player can
theoretically yield no higher expected profits than $\epsilon$ greater than
its competitors as defined in Eq. (39) and Eq. (41). Suppose a policy of pure
strategy exists, $\pi^{p}_{n}$, where,

$\displaystyle\pi^{p}_{n}=$ $\displaystyle\begin{cases}1&\text{for
\quad}x=\tilde{x}\\\ 0&\text{for \quad}else\end{cases}$ (43)

Thus, $\pi^{p}_{n}$ constitutes an $\epsilon$-Nash equilibrium resulting from
a pure strategy, with $\epsilon$ denoted in Eq. (41), from which varying the
parameters of $c_{1}$ and $c_{2}$ in Eq. (39), multiple $\epsilon$-Nash or
Nash equilibria exist. ∎

###  B.3 Existence of Nash equilibrium for Markov Game

Proposition: The existence of an $\epsilon$-Nash equilibrium in single stage
game ensures that there exists an $\delta$-Nash equilibrium in the Markov
Game, as defined in Eq. (11), for the value of a joint policy regardless of
the state transition behaviour of the Markov Game.

Proof: From [Filar and Vrieze, 1997], the value of a policy can be defined,

$\displaystyle\mathbf{v}(\pi)=\sum_{t=0}^{\infty}\gamma\mathbf{P}^{t}(\pi)\mathbf{R}(\pi)$
(44)

With a specific policy, the transition matrix of the Markov Game is known, and
therefore the value of a policy can be expressed in Eq. (44), with defined
transition $\mathbf{P}^{t}(\pi)$ and reward $\mathbf{R}(\pi)$ matrices.
Provided the Nash equilibrium condition from Eq. (11) we must demonstrate
that,

$\displaystyle\mathbf{R}(\pi^{\prime})\leq\mathbf{R}(\pi^{*})+\mathbf{\epsilon}\xrightarrow[]{}\mathbf{V}(\pi^{\prime})\leq\mathbf{V}(\pi^{*})+\delta$
(45)

Where $\pi^{\prime}$ denotes any joint policy, and $\pi^{*}$ denotes a Nash
equilibrium policy. We know that the Markov transition probability holds such
that,

$\displaystyle\sum_{i=1}^{|S|}\mathbf{P}^{t}(\pi)_{si}=1,\quad\forall s$ (46)

$\mathbf{P}^{t}(\pi)_{si}$ represents the probability of transition from state
$s$ to state $i$. Eq. (46) simply indicates the sum of transition
probabilities from state $s$ to any other state must equal 1 (Markov
property). Furthermore, suppose,

$\displaystyle R_{s}$ $\displaystyle=\max_{1\leq
s<|S|}\\{\mathbf{R}(\pi^{*})_{s}+\epsilon\\}$ (47) $\displaystyle\delta_{s}$
$\displaystyle=R_{s}-\mathbf{P}(\pi^{*})_{s}\times\mathbf{R}(\pi^{*})$ (48)

$R_{s}$ represents the maximum reward obtainable from state $s$ under policy
$\pi^{*}$, as illustrated in Eq. (47). Provided the Markov property on the
transition matrix $\mathbf{P}^{t}(\pi)$ outlined in Eq. (46), this implies
that

$\displaystyle\mathbf{P}(\pi^{\prime})_{s}\ \times\
\mathbf{R}(\pi^{\prime})\leq\mathbf{P}(\pi^{*})_{s}\ \times\
\mathbf{R}(\pi^{*})+\delta_{s}\quad\forall s\in S$ (49)

Where $\delta$ is a maximum fixed value added to the value of the
$\epsilon$-Nash equilibrium policy $\mathbf{V}(\pi^{*})$ effectively bounding
the value of any other policy deviating from $\pi^{*}$. ∎

##  Appendix C Hardware Configurations and Model Hyperparameters

All experiments were run on a computer with an Intel Core i5-10600K CPU
processor at 4.10GHz, 32 GB DDR3 RAM, with an NVIDIA GeForce GTX 1080 8GB
GDDR5X graphics card. The hyperparameters used for all experiments are listed
in Table 1.

Parameter | Value
---|---
No. Hidden Layers $\Gamma(\pi)$ | 3
No. Hidden Layers $\Psi(s)$ | 3
No. Hidden Layers $Q(s)$ | 3
Hidden Layer Size $\Gamma(\pi)$ | 1500
Hidden Layer Size $\Psi(s)$ | 1500
Hidden Layer Size $Q(s)$ | 75
No. Episodes | 40
Batch Update Frequency | 20
Batch Size | 10
RL Exploration Constant | 0.05
Max. Steps per Episode | 30
Discount Factor ($\gamma$) | 0.9
Learning Rate ($\alpha$) | 0.001
MDP Action Dimensions | 10
TuRBO-p Max. Evaluations | 10
TuRBO-p Batch Size | 4
Table 1: Hyperparameters used for deep reinforcement learning.

##  Appendix D Plots and Figures

Market Scenario 1:
$\beta_{0}=25,\beta_{1}=-0.6,\beta_{2}=-6.1,a=0.1$

Market Scenario 2:
$\beta_{0}=15,\beta_{1}=-1.05,\beta_{2}=-3.1,a=0.1$

Market Scenario 3:
$\beta_{0}=27,\beta_{1}=-1.1,\beta_{2}=-1.0,a=0.1$

Market Scenario 4:
$\beta_{0}=27,\beta_{1}=-3.05,\beta_{2}=-1.1,a=0.2$

Figure D.1: Surface plot of maximum theoretical advantage from deviation
($\epsilon$-deviation) from Nash equilibrium with respect to market price
$\tilde{x}$, and reference price $\bar{p}$, with their respective market
parameters $\beta_{0},\beta_{1},\beta_{2},a$ for arrival of a single sales
event. The lower plateau area, illustrated in dark-blue, constitutes a state
where the combination of joint action market price $\tilde{x}$, and reference
price $\bar{p}$ do not result in significant difference when the player
chooses to undercut the market. For each reference, there is a range of
actions that result in $\epsilon$-Nash equilibrium, where $\epsilon<0.0001$.

Market rewards per episode Scenario 1 with $n=3$.

Market rewards per episode Scenario 2 with $n=3$.

Market rewards per episode Scenario 3 with $n=3$.

Market rewards per episode Scenario 4 with $n=3$.

Market rewards per episode Scenario 2 with $n=5$.

Market rewards per episode Scenario 3 with $n=5$.

Figure D.2: Average market rewards per episode overlaid on top of theoretical
Nash equilibrium bounds (blue shade). Market average is in blue, and average
reward of single agent in orange. In a Nash equilibrium, both the market
average reward, and single agent reward should fall within the Nash equilibria
boundary, as the MG progresses.

Loss behaviour of Scenario 1 with $n=3$.

Loss behaviour of Scenario 2 with $n=3$.

Loss behaviour of Scenario 3 with $n=3$.

Loss behaviour of Scenario 4 with $n=3$.

Loss behaviour of Scenario 2 with $n=5$.

Loss behaviour of Scenario 4 with $n=5$.

Figure D.3: Loss behviour of batch update during Deep Q Learning (left y axis)
and Nash Net update $\Psi(s)$ (right y axis).