# Gradient Dynamics in Linear Quadratic Network Games with Time-Varying
Connectivity and Population Fluctuation

Feras Al Taha, Kiran Rokade, Francesca Parise This work was supported in part
by the Natural Sciences and Engineering Research Council of Canada.The authors
are with the School of Electrical and Computer Engineering, Cornell
University, Ithaca, NY, 14853, USA (e-mail<EMAIL_ADDRESS>
###### Abstract

In this paper, we consider a learning problem among non-cooperative agents
interacting in a time-varying system. Specifically, we focus on repeated
linear quadratic network games, in which the network of interactions changes
with time and agents may not be present at each iteration. To get
tractability, we assume that at each iteration, the network of interactions is
sampled from an underlying random network model and agents participate at
random with a given probability. Under these assumptions, we consider a
gradient-based learning algorithm and establish almost sure convergence of the
agents’ strategies to the Nash equilibrium of the game played over the
expected network. Additionally, we prove, in the large population regime, that
the learned strategy is an $\epsilon$-Nash equilibrium for each stage game
with high probability. We validate our results over an online market
application.

##  I INTRODUCTION

The prominence of big data analytics, Internet-of-Things, and machine learning
has transformed large societal and technological systems. Of special interest
are systems in which a large number of independent agents interacting over a
network structure make strategic decisions, while affected by the actions of
other agents. Examples include pricing in demand-side electricity markets,
supply chain management, wireless networks, public goods provision, financial
exchanges, and international trades, among others. In many settings, agents
lack information or computational capabilities to determine a priori the best
strategy to guide their decisions. Instead, agents need to learn their best
action over time based on observations of their rewards and other agents
actions, while adapting to changes in their environment.

Standard models of learning dynamics assume that the population of agents and
their underlying network of interactions are static. However, in systems with
large populations and high-volume interactions, this assumption is not
realistic since individuals may enter and leave the system, leading to
fluctuations in the population size, and participating agents might change
their interconnections with other agents over time. It then becomes unclear
whether players can reach a stable outcome in this nonstationary environment.

Accordingly, there is a need for a theory of multi-agent learning in dynamic
network settings in which the composition of the agents and their interactions
can change over time. In this paper, we start addressing these issues by
focusing on gradient play dynamics in linear quadratic network games with
time-varying connectivity and dynamic population.

###  I-A Main contributions

To obtain a tractable framework, we model the time-varying network of
interactions and population of agents as stochastic network realizations from
an underlying known distribution. Using stochastic approximation methods [1],
we demonstrate that for linear quadratic network games, when all agents follow
a projected gradient descent scheme, they almost surely converge to a Nash
equilibrium of the game played over the expected network. Moreover, by using
concentration inequalities, we show that with high probability, the learned
strategy profile is an $\epsilon$-Nash equilibrium of the game played over any
realized network, where $\epsilon$ decreases as the population size increases.

###  I-B Related works

Learning in time-varying settings with dynamic populations has been previously
studied for games with a special structure such as congestion games, bandwidth
allocation, markets, first-price auctions or public good games [2, 3, 4, 5].
The efficiency of outcomes in such games was investigated for low-adaptive-
regret learning [2] and later generalized to low-approximate-regret learning
[6], under the assumption that the population size is fixed. The setting with
a changing number of agents was studied for congestion games in [7].
Similarly, the effect of changing populations has been studied in the context
of truthful mechanism design [8, 9, 4]. None of these works cover the setting
of network games considered in this paper.

In terms of learning dynamics to reach Nash equilibria in static
noncooperative games or multi-agent settings, many schemes have been studied.
These include fictitious play [10], parallel and distributed computation [11],
projection-based algorithms (e.g., projected gradient dynamics) [12], and
regret minimization (e.g., no-regret dynamics) [13]. Among these, a growing
literature considered learning dynamics for static aggregative and network
games focusing, for example, on best response dynamics [14, 15], projection-
based algorithms [16, 17], forward–backward operator splitting [18, 19],
passivity-based schemes [20, 21], distributed asynchronous schemes [22, 23],
and state-dependent costs [24], among others.

When considering non-stationary environments, the setting of agents
communicating according to a time-varying network is not novel in the control
literature. Specifically, a large literature focused on cooperative problems
such as consensus/gossip algorithms [25, 26] as well as distributed
optimization [27] over time-varying networks, mainly based on an assumption of
uniform connectivity over contiguous intervals of time. Similar results have
been derived for distributed Nash equilibrium seeking in noncooperative games
[19, 28, 29, 30] and for averaging algorithms over randomized networks with
gossip communication [31, 32]. One common property of these works is that
despite the changing communication network, the underlying problem to solve
(achieving consensus, optimizing some objective in a decentralized fashion, or
reaching a Nash equilibrium) is time-invariant. In contrast, in this paper,
agents take part in a different network game at every iteration. Thus, the
Nash equilibrium that the players are trying to learn is itself time-varying
since their payoff function depends on the time-varying network. The question
at hand is then not solely about the convergence of agents’ strategies, but
also about the nature of the learned strategy and its relation to the time-
varying stage games. We show that, in our setting, strategies converge to the
equilibrium of the game played over the expected network and that this is
approximately optimal for large populations. Finally, convergence of
optimistic gradient descent in games with time-varying utility functions has
recently been studied in [33]. Our model is different as it applies to network
games in which payoff-variability is due to variability of interconnections.
Moreover, we consider a setting in which the population itself may vary, with
agents joining and leaving the system. Open multi-agent systems with random
arrivals and departures of agents have been recently studied for cooperating
homogeneous agents in consensus dynamics [34] or optimal resource allocation
problems [35]. We instead focus on non-cooperating agents with network
interactions.

###  I-C Paper organization

The rest of the paper is organized as follows. Section II presents the
repeated network game setup and recaps known results on learning dynamics in
static environments. Section III introduces the main results on the
convergence of gradient dynamics and the suboptimality guarantees of the
learned strategy for a time-varying network and fixed population. Section IV
extends these results to dynamic populations. Section V demonstrates the
convergence of the proposed projected gradient dynamics with numerical
simulations and Section VI concludes the paper. Omitted proofs are given in
the Appendix.

###  I-D Notation

We denote by $[v]_{j}$ the $j$th component of a vector $v\in\mathbb{R}^{n}$
and by $A_{ij}$ the $ij$th entry of a matrix $A\in\mathbb{R}^{m\times n}$. We
denote the Frobenius norm of a matrix by $\|\cdot\|_{F}$ and the Euclidean
norm of a vector as well as the matrix norm induced by the Euclidean norm by
$\|\cdot\|_{2}$. The symbol $\mathbb{I}_{n}$ denotes the $n\times n$ identity
matrix. The operator $\Pi_{\mathcal{X}}[\cdot]$ denotes the projection onto
the set $\mathcal{X}$. The symbol $\otimes$ denotes the Kronecker product.
Given $n$ matrices $A_{1},\dots,A_{n}$ of appropriate dimensions, we let
$\textrm{diag}(A_{1},\dots,A_{n})$ denote the matrix formed by stacking
$A_{1},\dots,A_{n}$ block-diagonally. Given vectors $x_{1},\dots,x_{n}$, we
let $[x_{i}]_{i\in\\{1,\dots,n\\}}$ denote the vector formed by stacking
$x_{1},\dots,x_{n}$ vertically. For a given square matrix $A$, $\lambda_{\rm
max}(A)$ and $\lambda_{\rm min}(A)$ denote the maximum and minimum eigenvalues
of $A$, respectively.

##  II RECAP ON LINEAR QUADRATIC GAMES OVER STATIC NETWORKS

We present a recap of known results for static games.

###  II-A One shot game

Consider a linear quadratic (LQ) game played by a population of agents indexed
by $i\in\mathcal{N}:=\\{1,\dots,N\\}$ over a static network with no self-
loops, represented by an adjacency matrix $\tilde{A}\in[0,1]^{N\times N}$.
Each agent $i\in\mathcal{N}$ aims at selecting a strategy
$s_{i}\in\mathcal{S}_{i}\subseteq\mathbb{R}^{n}$ to minimize a cost function

$\displaystyle
J_{i}(s_{i},s_{-i},\tilde{A})=\frac{1}{2}s_{i}^{\top}Q_{i}s_{i}-s_{i}^{\top}\Big{(}\theta_{i}+\frac{\alpha}{N}\sum_{j=1}^{N}\tilde{A}_{ij}s_{j}\Big{)}$
(1)

where
$s_{-i}:=[s_{j}]_{j\in\mathcal{N}\setminus\\{i\\}}\in\mathbb{R}^{(N-1)n}$ is
the strategy profile of all other agents, $\alpha\in\mathbb{R}$ models the
strength of network effects, $Q_{i}\in\mathbb{R}^{n\times n}$ and
$\theta_{i}\in\mathbb{R}^{n}$ are parameters modeling agent specific
heterogeneity, and $Q_{i}=Q_{i}^{\top}\succ 0$. Let
$\mathcal{S}:=\prod_{i\in\mathcal{N}}\mathcal{S}_{i}$ be the set of all
strategy profiles of the game. Given a strategy profile
$s:=[s_{i}]_{i\in\mathcal{N}}\in\mathcal{S}$ and a network $\tilde{A}$, the
term $\frac{1}{N}\sum_{j=1}^{N}\tilde{A}_{ij}s_{j}$ represents the local
aggregate sensed by agent $i$. We denote this LQ game by
$\mathcal{G}(Q,\theta,\alpha,\tilde{A})$ where
$\theta:=[\theta_{i}]_{i\in\mathcal{N}}$ and
$Q:=\textrm{diag}(Q_{1},\dots,Q_{N})$.

######  Definition 1 ($\epsilon$-Nash equilibrium)

Given $\epsilon>0$, a strategy profile $\bar{s}\in\mathbb{R}^{Nn}$ is an
$\epsilon$-Nash equilibrium of the game
$\mathcal{G}(Q,\theta,\alpha,\tilde{A})$ if for all $i\in\mathcal{N}$, we have
$\bar{s}_{i}\in\mathcal{S}_{i}$ and

$\displaystyle J_{i}(\bar{s}_{i},\bar{s}_{-i},\tilde{A})\leq
J_{i}(s_{i},\bar{s}_{-i},\tilde{A})+\epsilon\qquad\textrm{for all
}s_{i}\in\mathcal{S}_{i}.$ (2)

If (2) holds for $\epsilon=0$, then $\bar{s}$ is a Nash equilibrium.

It is well known that the Nash equilibria of convex games can be characterized
by using the game Jacobian

$\displaystyle F(s,\tilde{A})$
$\displaystyle:=[\nabla_{s_{i}}J_{i}(s_{i},s_{-i},\tilde{A})]_{i\in\mathcal{N}}$
(3)

which is a map composed of each player’s cost gradient with respect to their
own strategy. For LQ games, this is

$\displaystyle F(s,\tilde{A})$
$\displaystyle=\Big{[}Q_{i}s_{i}-\theta_{i}-\frac{\alpha}{N}\sum_{j=1}^{N}\tilde{A}_{ij}s_{j}\Big{]}_{i\in\mathcal{N}}$
$\displaystyle=Qs-\theta-\frac{\alpha}{N}(\tilde{A}\otimes\mathbb{I}_{n})s.$

A classic approach to characterizing Nash equilibria is to interpret them as
solutions to variational inequalities (see [12, 36] for general games and [14]
for network games). We summarize this relation in the following lemma, after
introducing an assumption that guarantees existence and uniqueness of the Nash
equilibrium.

######  Assumption 1 (Equilibrium uniqueness)

  1.   2. (i)

For each $i\in\mathcal{N}$, $\mathcal{S}_{i}$ is nonempty, convex and compact.
There exists a compact set $\mathcal{\bar{S}}\subseteq\mathbb{R}^{n}$ such
that $\mathcal{S}_{i}\subseteq\mathcal{\bar{S}}$ for all $i$, and $s_{\rm
max}:=\max_{s\in\mathcal{\bar{S}}}\|s\|_{2}<\infty$.

  3. (ii)

The following relation holds

$\displaystyle\lambda_{\rm min}(Q)-\frac{|\alpha|}{N}\|\tilde{A}\|_{2}>0.$ (4)

###### Lemma 2.1

(Variational inequality equivalence, [12, Proposition 1.4.2], [14, Proposition
1 and Proposition 2]) Suppose that Assumption 1-(i) holds. Then, the strategy
profile $\bar{s}$ is a Nash equilibrium of
$\mathcal{G}(Q,\theta,\alpha,\tilde{A})$ if and only if it solves the
variational inequality $(s-\bar{s})^{\top}F(\bar{s},\tilde{A})\geq
0,\quad\forall s\in\mathcal{S}.$ If, additionally, Assumption 1-(ii) holds,
then, $F$ is strongly monotone and the equilibrium is unique.

###  II-B Learning dynamics in repeated games

Consider now a repetition of the stage LQ game defined in Section II-A, played
over the static network $\tilde{A}$. Suppose that each agent $i$ tries to
learn the equilibrium iteratively by using the projected gradient dynamics

$\displaystyle s^{k+1}=\Pi_{\mathcal{S}}[s^{k}-\tau F(s^{k},\tilde{A})],$ (5)

where $s^{k}$ is the strategy profile at iteration $k\geq 0$,
$s^{0}\in\mathcal{S}$, and $\tau>0$ is a fixed step size.

###### Remark 1

To implement their learning dynamics

$\displaystyle\textstyle
s^{k+1}_{i}=\Pi_{\mathcal{S}_{i}}\left[s_{i}^{k}-\tau\left(Q_{i}s_{i}^{k}-\theta_{i}-\frac{\alpha}{N}\sum_{j=1}^{N}\tilde{A}_{ij}s_{j}^{k}\right)\right],$

player $i\in\mathcal{N}$ only requires knowledge of their current strategy,
their cost function parameters, and their current local aggregate. The player
does not need to observe the network realization $\tilde{A}$.

The dynamics in (5) can be shown to converge under a mild assumption on the
step size.

###### Lemma 2.2

(Gradient play over a static network, [12, Theorem 12.1.2]) Suppose that
Assumption 1 holds. Let $L:=\lambda_{\rm
max}(Q)+\frac{|\alpha|}{N}\|\tilde{A}\|_{2}$ be the Lipschitz constant of $F$
and $\mu:=\lambda_{\rm min}(Q)-\frac{\alpha}{N}\|\tilde{A}\|_{2}$ be the
strong monotonicity constant of $F$. If the step size $\tau$ satisfies
$0<\tau<2\mu/L^{2}$, then for any initial strategy profile
$s^{0}\in\mathcal{S}$, the gradient dynamics described in (5) converge to the
unique Nash equilibrium of the game $\mathcal{G}(Q,\theta,\alpha,\tilde{A})$.

The Lipschitz and strong monotonicity constants used in Lemma 2.2 are
computed, e.g., in [14].

##  III GAMES OVER TIME-VARYING NETWORKS

The well-known results summarized in the previous section hold for a static
network of interactions. In many realistic settings however, interactions
among the agents may change across repetitions of the game and agents may not
always be participating. In this section, we consider learning dynamics in
time-varying networks. These results are then extended in Section IV to the
case of dynamic populations.

More specifically, we here assume that the network of interactions is random,
and at every repetition $k=0,1,2,\dots$ of the stage game, a new independent
network realization $A^{k}\in[0,1]^{N\times N}$ is sampled as follows: for all
$i\in\mathcal{N}$, $A_{ii}^{k}=0$ (no self-loop) and for $i\neq j$,
$A_{ij}^{k}$ is sampled from a distribution with bounded support111Restricting
the support to the unit interval is without loss of generality. One can easily
extend this paper’s results to any bounded convex support. in $[0,1]$ and with
mean $\bar{A}_{ij}\in[0,1]$. In the case where $A_{ij}^{k}$ is a Bernoulli
random variable, $\bar{A}_{ij}$ can be interpreted as the probability that
player $j$ contributes to the local aggregate of player $i$. More generally,
$\bar{A}=\mathrm{E}[A^{k}]$ represents the expected network of interactions,
where we set $\bar{A}_{ii}=0$ for all $i\in\mathcal{N}$.

###  III-A Motivating example

We motivate this time-varying setting by presenting an example in the context
of online markets.

######  Example 1 (Dynamic pricing game)

Consider an online market with $N$ sellers. Each merchant $i\in\mathcal{N}$
sells a product $i$ at a price $s_{i}\in\mathbb{R}_{+}$ determined daily. On
each day $k=0,1,2,\dots$, a new set of $M$ customers arrives. Each customer
$c\in\\{1,\dots,M\\}$ decides which products to purchase. The demand of
customer $c$ on day $k$ for product $i$ can be modeled as an affine demand
function [37]

$\displaystyle
d_{i}^{c,k}=\bar{d}_{i}-\eta\Big{(}s_{i}^{k}+\frac{\alpha}{N}\sum_{j=1}^{N}A_{ij}^{c,k}s_{j}^{k}\Big{)}$
(6)

where $s^{k}_{i}$ is the price of product $i$ on day $k$, $\bar{d}_{i}$ is the
maximum demand that a customer can have for product $i$, $\eta>0$ is the price
sensitivity, $\alpha\geq 0$ models the degree of influence that the price of
other products has on the demand of product $i$, and
$A_{ij}^{c,k}\sim\textrm{Ber}(\bar{A}_{ij})$ is a Bernoulli random variable
that indicates whether customer $c$ is interested in co-purchasing product $i$
with product $j$ on day $k$. The mean $\bar{A}_{ij}\in[0,1]$ can be
interpreted as the likelihood of this event.

The total demand for product $i$ can be obtained by aggregating the demands of
all customers:

$\displaystyle d_{i}^{k}$
$\displaystyle=\sum_{c=1}^{M}d_{i}^{c,k}=\sum_{c=1}^{M}\Big{(}\bar{d}_{i}-\eta\Big{(}s_{i}^{k}+\frac{\alpha}{N}\sum_{j=1}^{N}A_{ij}^{c,k}s_{j}^{k}\Big{)}\Big{)}$
$\displaystyle=M\bar{d}_{i}-\eta\Big{(}Ms_{i}^{k}+\frac{\alpha}{N}\sum_{j=1}^{N}\sum_{c=1}^{M}A_{ij}^{c,k}s_{j}^{k}\Big{)}$
$\displaystyle=M\Big{(}\bar{d}_{i}-\eta\Big{(}s_{i}^{k}+\frac{\alpha}{N}\sum_{j=1}^{N}A^{k}_{ij}s_{j}^{k}\Big{)}\Big{)}$

where $A^{k}_{ij}:=(1/M)\sum_{c=1}^{M}A_{ij}^{c,k}$ is a random variable
representing the average complementarity of products $i$ and $j$, with mean
$\mathrm{E}[A^{k}_{ij}]=\bar{A}_{ij}$. Given this demand, each merchant tries
to maximize their profit, i.e., minimize the cost

$\displaystyle J_{i}(s_{i}^{k},s_{-i}^{k},$ $\displaystyle
A^{k})=-s_{i}^{k}d_{i}^{k}$
$\displaystyle=-s_{i}^{k}M\Big{(}\bar{d}_{i}-\eta\Big{(}s_{i}^{k}+\frac{\alpha}{N}\sum_{j=1}^{N}A^{k}_{ij}s_{j}^{k}\Big{)}\Big{)}$
$\displaystyle=M\Big{(}\eta(s_{i}^{k})^{2}-s_{i}^{k}\Big{(}\bar{d}_{i}-\eta\frac{\alpha}{N}\sum_{j=1}^{N}A^{k}_{ij}s_{j}^{k}\Big{)}\Big{)}.$
(7)

This online market competition can be interpreted as a repeated LQ game on a
dynamic network $A^{k}$ that changes daily to capture different daily customer
preferences. Sellers may learn how to price their products using a gradient
descent scheme. Note that the gradient in this case is

$\displaystyle\nabla_{s_{i}}J_{i}(s_{i}^{k},s_{-i}^{k},A^{k})=-d_{i}^{k}+\eta
Ms_{i}^{k},$ (8)

hence, the only information seller $i$ requires to compute their current
gradient update is the total number of customers and the quantity of product
$i$ sold on the previous day.

In the next section, we characterize the asymptotic behavior produced by
gradient updates in time-varying settings, as motivated by the previous
example, for general LQ games.

###  III-B Learning dynamics

In this nonstationary environment, the Nash equilibrium is time-varying.
Despite this, we show that agents learn to play a suitable fixed strategy,
provided that they use a time-varying, diminishing step size $\tau^{k}$ to
ensure convergence of their gradient-based learning dynamics

$\displaystyle s^{k+1}=\Pi_{\mathcal{S}}[s^{k}-\tau^{k}F(s^{k},A^{k})]$ (9)

where $k\geq 0$, and $s^{0}\in\mathcal{S}$. The diminishing step size is
needed to compensate for the network variability.

######  Assumption 2 (Step size)

For all $k$, the step size $\tau^{k}$ satisfies $\tau^{k}>0$, $\tau^{k}\to 0$,
$\sum_{k=1}^{\infty}\tau^{k}=\infty$ and
$\sum_{k=1}^{\infty}(\tau^{k})^{2}<\infty$.

In the following, we show that the gradient dynamics (9) converge almost
surely to the Nash equilibrium of the LQ game played over the expected network
$\bar{A}=\mathrm{E}[A^{k}]$. This result follows from rewriting the dynamics
as a stochastic gradient descent scheme and utilizing stochastic approximation
theory [1] to show convergence.

###### Proposition 1

Suppose that Assumptions 1 (for $\tilde{A}=\bar{A}$) and 2 hold. Then, the
gradient dynamics in (9) converge to the unique Nash equilibrium of the game
played over the expected network $\bar{A}$ almost surely, for any
$s^{0}\in\mathcal{S}$.

If agents compute their gradient updates with noisy local aggregate data,
convergence can still be achieved provided that the noise is additive, zero-
mean, and with bounded variance (as it can be absorbed in the perturbation
vector $w^{k}$).

The following corollary justifies why the Nash equilibrium of the game played
over the expected network is a reasonable policy to learn, by showing that
with high probability, it results in an approximate equilibrium for any
iteration.

###### Corollary 1

Suppose that Assumption 1 (for $\tilde{A}=\bar{A}$) holds. Fix any $k\geq 0$
and any $\delta>0$. Then, with probability at least $1-\delta$, the Nash
equilibrium of the LQ game $\mathcal{G}(Q,\theta,\alpha,\bar{A})$ played over
the expected network $\bar{A}$ is an $\epsilon_{N,\delta}$-Nash equilibrium to
the stage game $\mathcal{G}(Q,\theta,\alpha,A^{k})$ played over the network
$A^{k}$ with

$\displaystyle\epsilon_{N,\delta}:=2|\alpha|s_{\rm
max}^{2}\sqrt{\frac{n\ln\left(2nN/\delta\right)}{2N}}.$

We note that $\epsilon_{N,\delta}$ does not depend on the cost parameters
$Q_{i}$ and $\theta_{i}$. Also, for any confidence $\delta>0$,
$\epsilon_{N,\delta}$ decreases as the population size $N$ grows. This
corollary can be proven by using matrix concentration inequalities, similarly
to the approach in [38, Lemma 14].

##  IV GAMES OVER DYNAMIC POPULATION

In this section, we generalize the previous setting by considering a dynamic
population, where players randomly enter and leave the game from one
repetition to the other. For example, in the online market setting introduced
in Example 1, sellers might lack supply for their products or decide to not
sell their items on certain days. This can be modeled in the following way. If
a player does not participate in a particular iteration, then their strategy
does not update in that iteration, resulting in dynamics where a subset of
components are updated at a time, similarly to random coordinate descent
dynamics.

Let $P^{k}\in\\{0,1\\}^{N\times N}$ be a diagonal matrix such that the random
variable $P_{ii}^{k}\sim\textrm{Ber}(\bar{P}_{ii})$ represents whether player
$i$ is participating ($P_{ii}^{k}=1$) in the game at iteration $k$ or not
($P^{k}_{ii}=0$), with $\bar{P}_{ii}>0$ for all $i\in\mathcal{N}$. Then, the
network realization over which the game is played at time $k$ is $A^{k}P^{k}$
(when $P_{ii}^{k}=0$, the corresponding column in the adjacency matrix is set
to zero such that player $i$ does not affect any other players participating
in the game).

Consider the following gradient dynamics for each player $i$

$\displaystyle s^{k+1}_{i}\\!$
$\displaystyle=\\!\begin{cases}\Pi_{\mathcal{S}_{i}}\Big{[}s^{k}_{i}-\dfrac{\tau^{k}}{\bar{P}_{ii}}\nabla_{s_{i}}J_{i}(s_{i}^{k},s^{k}_{-i},A^{k}P^{k})\Big{]}&\text{if}\,P_{ii}^{k}=1,\\\
s_{i}^{k}&\text{if}\,P_{ii}^{k}=0,\end{cases}$ (10)

where $k\geq 0$, and $s_{i}^{0}\in\mathcal{S}_{i}$. Note that in (10), each
player $i$ scales their gradient step by $1/\bar{P}_{ii}$ to compensate for
missing updates when $P_{ii}^{k}=0$.

Despite these random interruptions to the sequence of strategy updates, we
show that the players learn to play the Nash equilibrium of the game
$\mathcal{G}(Q,\theta,\alpha,\bar{A}\bar{P})$ played over the expected network
$\bar{A}\bar{P}$. Similar to Proposition 1, the key step to prove this result
is to rewrite the dynamics (10) as stochastic gradient dynamics converging to
the aforementioned Nash equilibrium.

###### Proposition 2

Suppose that Assumptions 1 (with $\tilde{A}=\bar{A}\bar{P}$) and 2 hold. If
$\|\theta_{i}\|\leq\theta_{\rm max}$ for all $i\in\mathcal{N}$, then, the
gradient dynamics described in (10) converge to the unique Nash equilibrium of
the LQ game played over the expected network $\bar{A}\bar{P}$ almost surely,
for any $s^{0}\in\mathcal{S}$.

Similar to Corollary 1, the Nash equilibrium of the expected network can be
shown to be an approximate Nash equilibrium to the stage game with high
probability.

###### Corollary 2

Suppose that Assumption 1 (for $\tilde{A}=\bar{A}$) holds. Fix any $k\geq 0$
and $\delta>0$. Then, with probability at least $1-\delta$, the Nash
equilibrium of the LQ game played over the network $\bar{A}\bar{P}$ is an
$\epsilon_{N,\delta}$-Nash equilibrium to the stage game played over the
network $A^{k}P^{k}$, with

$\displaystyle\epsilon_{N,\delta}:=2|\alpha|s_{\rm
max}^{2}\sqrt{\frac{n\ln\left(2nN/\delta\right)}{2N}}.$

##  V NUMERICAL EXPERIMENTS

In this section, we present numerical experiments demonstrating the
convergence of gradient dynamics for the dynamic pricing game presented in
Example 1 for both the static and the dynamic population settings presented in
Sections III and IV, respectively.

Consider a market with $N$ sellers, where each seller is endowed with a
product whose demand has price sensitivity $\eta=1$. Let $\alpha=0.8$ be the
strength of network effects on the demand of every product. We consider two
categories of products, namely category $1$ and category $2$. The probability
that a customer is interested in co-purchasing products from categories $m$
and $l$ is denoted by $\bar{a}_{ml}$, where $m,l\in\\{1,2\\}$. Thus, in the
notation of Example 1, $\bar{A}_{ij}=\bar{a}_{ml}$ if product $i$ is in
category $m$ and product $j$ is in category $l$. For the numerical simulations
in this section, we set these probabilities to be
$\bar{a}_{11}=\bar{a}_{22}=0.8$ and $\bar{a}_{12}=\bar{a}_{21}=0.3$. Moreover,
let $\bar{d}_{1}=2$, $\bar{d}_{2}=10$ be the maximum demands a customer can
have for products in categories $1$ and $2$, respectively.

We first consider the case of static population, in which all sellers
participate in the market every day. Each seller starts with an arbitrary
initial price for their product (set to zero in our simulations). On each day
$k$, a new set of $M=100$ customers arrives. The total demand $d_{i}^{k}$ for
product $i$ on day $k$ is determined by the realization of the co-purchasing
preference matrix $A^{k}$ sampled according to the matrix $\bar{A}$. With the
gradient of their cost function computed as in (8), seller $i$ updates the
price of their product following the projected gradient dynamics in (9) with
step size $\tau_{k}=1/(Lk)$. For various values of $N$, we illustrate in Fig.
1 (top) the deviation of the resulting sequence of price profiles
$\\{s^{k}\\}_{k\geq 0}$ from the Nash equilibrium $\bar{s}$ of the game played
over the expected co-purchasing matrix $\bar{A}$, averaged over $100$ trials.
It can be observed that the prices converge to the price profile $\bar{s}$ for
each $N$, as predicted in Proposition 1.

Figure 1: For dynamic network $A^{k}$ and fixed population size $N$. Top:
Convergence of product prices $s^{k}$ (averaged over 100 trials) to the Nash
equilibrium price profile $\bar{s}$ of the game played over the expected
network $\bar{A}$. Bottom: Maximum suboptimality gap (averaged over 100
trials) across sellers per iteration as defined in (11).

Figure 2: For dynamic network $A^{k}P^{k}$ and dynamic population. Top:
Convergence of product prices $s^{k}$ (averaged over 100 trials) to the Nash
equilibrium price profile $\bar{s}$ of the game played over the expected
network $\bar{A}\bar{P}$. Bottom: Maximum suboptimality gap (averaged over 100
trials) across sellers per iteration as defined in (11).

For each day $k$, we compute the largest normalized suboptimality gap incurred
across sellers defined as

$\displaystyle\bar{\epsilon}_{k}:=\max_{i\in\mathcal{N}}\left|\frac{J_{i}(s_{i}^{k},s_{-i}^{k},A^{k})-J_{i}^{\star}(A^{k})}{J_{i}^{\star}(A^{k})}\right|$
(11)

where
$J_{i}^{\star}(A^{k}):=\inf_{s\in\mathcal{S}_{i}}J_{i}(s,s^{k}_{-i},A^{k})$ is
the cost incurred by seller $i$ by best-responding to other sellers’ prices.
Fig. 1 (bottom) depicts the decrease in the gap $\bar{\epsilon}_{k}$ for
different population sizes as a function of $k$. The oscillations that can be
observed in Fig. 1 (bottom) are due to the variability of the network, and are
smaller for larger population sizes.

Next, we consider the dynamic population case, where some sellers may not
participate in the market every single day. Let $\bar{p}=0.9$ be the
probability that any seller $i\in\mathcal{N}$ participates in the market on a
given day. Thus, $\bar{P}=\bar{p}\ \mathbb{I}_{N}$. In this setting, the
sellers use the gradient dynamics in (10) with a step size of
$\tau_{k}=1/(Lk)$. The deviation between the obtained sequence of prices
$\\{s^{k}\\}_{k\geq 0}$ from the Nash equilibrium $\bar{s}$ of the game played
over the expected co-purchasing matrix $\bar{A}\bar{P}$ is shown in Fig. 2
(top) for various values of $N$, averaged over 100 trials. The slower
convergence of the price profile relative to the static population case is
expected since sellers randomly skip updating their prices on certain days.
Similar to the static population case, Fig. 2 (bottom) presents the largest
suboptimality gap across sellers for each iteration $k$, averaged across 100
trials. A similar trend to Fig. 1 (bottom) can be observed with the decrease
of $\bar{\epsilon}_{k}$ as a function of $N$, but with larger oscillations.
The latter is also to be expected given that the network $A^{k}P^{k}$ has more
variability than the network $A^{k}$.

##  VI CONCLUSIONS

In this work, we have introduced a tractable framework for learning in network
games with time-varying connectivity and dynamic populations. Several
extensions and future research directions can be considered. For example, in
this paper, we have restricted our attention to myopic learning dynamics.
However, one could define a discounted cumulative/averaged payoff over all
iterations and examine the outcome of forward-looking dynamics. Other
interesting directions would be to extend the model to generic cost functions
and evolving graphs that densify with time [39].

## References

  * [1] H. Jiang and H. Xu, “Stochastic approximation approaches to the stochastic variational inequality problem,” IEEE Transactions on Automatic Control, vol. 53, no. 6, pp. 1462–1475, 2008.
  * [2] T. Lykouris, V. Syrgkanis, and É. Tardos, “Learning and efficiency in games with dynamic population,” in Proc. of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 120–129, SIAM, 2016.
  * [3] D. Bergemann and M. Said, “Dynamic auctions: A survey,” 2010.
  * [4] R. Cavallo, D. C. Parkes, and S. Singh, “Efficient mechanisms with dynamic populations and dynamic types,” Unpublished manuscript, Harvard University, 2009.
  * [5] M. Cavaliere, S. Sedwards, C. E. Tarnita, M. A. Nowak, and A. Csikász-Nagy, “Prosperity is associated with instability in dynamical networks,” J. of theoretical biology, vol. 299, pp. 126–138, 2012.
  * [6] D. J. Foster, Z. Li, T. Lykouris, K. Sridharan, and E. Tardos, “Learning in games: Robustness of fast convergence,” Advances in Neural Information Processing Systems, vol. 29, 2016.
  * [7] D. Shah and J. Shin, “Dynamics in congestion games,” ACM SIGMETRICS Performance Evaluation Review, vol. 38, no. 1, pp. 107–118, 2010.
  * [8] R. J. Dolan, “Incentive mechanisms for priority queuing problems,” The Bell Journal of Economics, pp. 421–436, 1978.
  * [9] D. C. Parkes and S. Singh, “An MDP-based approach to online mechanism design,” Advances in neural information processing systems, vol. 16, 2003\.
  * [10] D. Fudenberg, F. Drew, D. K. Levine, and D. K. Levine, The theory of learning in games, vol. 2.  MIT press, 1998.
  * [11] D. Bertsekas and J. Tsitsiklis, Parallel and distributed computation: Numerical methods.  Athena Scientific, 2015.
  * [12] F. Facchinei and J.-S. Pang, Finite-dimensional variational inequalities and complementarity problems.  Springer, 2003.
  * [13] N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani, Algorithmic game theory.  Cambridge university press, 2007.
  * [14] F. Parise and A. Ozdaglar, “A variational inequality framework for network games: Existence, uniqueness, convergence and sensitivity analysis,” Games and Economic Behavior, vol. 114, pp. 47–82, 2019.
  * [15] F. Parise, S. Grammatico, B. Gentile, and J. Lygeros, “Distributed convergence to Nash equilibria in network and average aggregative games,” Automatica, vol. 117, p. 108959, 2020.
  * [16] D. Paccagnan, M. Kamgarpour, and J. Lygeros, “On aggregative and mean field games with applications to electricity markets,” in 2016 European Control Conference (ECC), pp. 196–201, IEEE, 2016.
  * [17] F. Salehisadaghiani and L. Pavel, “Distributed Nash equilibrium seeking in networked graphical games,” Automatica, vol. 87, pp. 17–24, 2018.
  * [18] D. Gadjov and L. Pavel, “Single-timescale distributed GNE seeking for aggregative games over networks via forward–backward operator splitting,” IEEE Transactions on Automatic Control, vol. 66, no. 7, pp. 3259–3266, 2020\.
  * [19] S. Grammatico, “Proximal dynamics in multiagent network games,” IEEE Transactions on Control of Network Systems, vol. 5, no. 4, pp. 1707–1716, 2017\.
  * [20] D. Gadjov and L. Pavel, “A passivity-based approach to Nash equilibrium seeking over networks,” IEEE Transactions on Automatic Control, vol. 64, no. 3, pp. 1077–1092, 2018.
  * [21] C. De Persis and S. Grammatico, “Distributed averaging integral Nash equilibrium seeking on networks,” Automatica, vol. 110, p. 108548, 2019\.
  * [22] J. Koshal, A. Nedić, and U. V. Shanbhag, “Distributed algorithms for aggregative games on graphs,” Operations Research, vol. 64, no. 3, pp. 680–704, 2016.
  * [23] R. Zhu, J. Zhang, K. You, and T. Başar, “Asynchronous networked aggregative games,” Automatica, vol. 136, p. 110054, 2022.
  * [24] M. Shokri and H. Kebriaei, “Network aggregative game in unknown dynamic environment with myopic agents and delay,” IEEE Transactions on Automatic Control, vol. 67, no. 4, pp. 2033–2038, 2021.
  * [25] L. Moreau, “Stability of multiagent systems with time-dependent communication links,” IEEE Transactions on automatic control, vol. 50, no. 2, pp. 169–182, 2005.
  * [26] J. M. Hendrickx and J. N. Tsitsiklis, “Convergence of type-symmetric and cut-balanced consensus seeking systems,” IEEE Transactions on Automatic Control, vol. 58, no. 1, pp. 214–218, 2012.
  * [27] A. Nedić and A. Olshevsky, “Distributed optimization over time-varying directed graphs,” IEEE Transactions on Automatic Control, vol. 60, no. 3, pp. 601–615, 2014.
  * [28] G. Belgioioso, A. Nedić, and S. Grammatico, “Distributed generalized Nash equilibrium seeking in aggregative games on time-varying networks,” IEEE Transactions on Automatic Control, vol. 66, no. 5, pp. 2061–2075, 2020\.
  * [29] C. Cenedese, G. Belgioioso, Y. Kawano, S. Grammatico, and M. Cao, “Asynchronous and time-varying proximal type dynamics in multiagent network games,” IEEE Transactions on Automatic Control, vol. 66, no. 6, pp. 2861–2867, 2020.
  * [30] F. Salehisadaghiani and L. Pavel, “Distributed Nash equilibrium seeking: A gossip-based algorithm,” Automatica, vol. 72, pp. 209–216, 2016.
  * [31] F. Fagnani and S. Zampieri, “Randomized consensus algorithms over large scale networks,” IEEE Journal on Selected Areas in Communications, vol. 26, no. 4, pp. 634–649, 2008.
  * [32] S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah, “Randomized gossip algorithms,” IEEE Transactions on Information Theory, vol. 52, no. 6, pp. 2508–2530, 2006.
  * [33] I. Anagnostides, I. Panageas, G. Farina, and T. Sandholm, “On the convergence of no-regret learning dynamics in time-varying games,” arXiv preprint arXiv:2301.11241, 2023.
  * [34] J. M. Hendrickx and S. Martin, “Open multi-agent systems: Gossiping with random arrivals and departures,” in 2017 IEEE 56th Annual Conference on Decision and Control (CDC), pp. 763–768, IEEE, 2017.
  * [35] C. M. de Galland, R. Vizuete, J. M. Hendrickx, E. Panteley, and P. Frasca, “Random coordinate descent for resource allocation in open multi-agent systems,” arXiv preprint arXiv:2205.10259, 2022.
  * [36] G. Scutari, D. P. Palomar, F. Facchinei, and J.-S. Pang, “Convex optimization, game theory, and variational inequality theory,” IEEE Signal Processing Magazine, vol. 27, no. 3, pp. 35–49, 2010.
  * [37] X. Yue, S. K. Mukhopadhyay, and X. Zhu, “A Bertrand model of pricing of complementary goods under information asymmetry,” J. of Business Research, vol. 59, no. 10-11, pp. 1182–1192, 2006.
  * [38] F. Parise and A. Ozdaglar, “Graphon games: A statistical framework for network games and interventions,” Econometrica, vol. 91, no. 1, pp. 191–225, 2023\.
  * [39] J. Leskovec, J. Kleinberg, and C. Faloutsos, “Graphs over time: densification laws, shrinking diameters and possible explanations,” in Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, pp. 177–187, 2005.

##  VII APPENDIX

###  VII-A Proof of Proposition 1

The gradient dynamics in (9) can be interpreted as stochastic gradient play
for the LQ game played over the expected network $\bar{A}$. This can be seen
by rewriting the dynamics as

$\displaystyle s^{k+1}$
$\displaystyle=\Pi_{\mathcal{S}}[s^{k}-\tau^{k}F(s^{k},A^{k})]$
$\displaystyle=\Pi_{\mathcal{S}}[s^{k}-\tau^{k}(F(s^{k},\bar{A})+\underbrace{F(s^{k},A^{k})-F(s^{k},\bar{A})}_{=:w^{k}})]$

where $w^{k}$ can be interpreted as a stochastic perturbation vector.

Let $\\{\mathcal{F}_{k}\\}_{k\geq 0}$ denote an increasing sequence of
$\sigma$-algebras such that $s^{k}$ is $\mathcal{F}_{k}$-measurable. Consider
the following conditions on the perturbation vector $w^{k}$ and the operator
$F$:

  1. (i)

The perturbation has zero mean $\mathrm{E}[w^{k}\mid\mathcal{F}_{k}]=0$;

  2. (ii)

The variance of $w^{k}$ is such that
$\sum_{k=1}^{\infty}(\tau^{k})^{2}\mathrm{E}[\|w^{k}\|^{2}_{2}\mid\mathcal{F}_{k}]<\infty$
almost surely;

  3. (iii)

The operator $F(\cdot,\bar{A})$ is $L$-Lipschitz;

  4. (iv)

The operator $F(\cdot,\bar{A})$ is $\mu$-strongly monotone.

By Assumption 2 and [1, Theorem 3.2], it suffices to show that the conditions
(i)-(iv) hold to guarantee that the stochastic projected gradient dynamics
presented above converge to the solution of the variational inequality in
Lemma 2.1 with network $\bar{A}$. Then, by Lemma 2.1, this solution is a Nash
equilibrium of the game with network $\bar{A}$.

Conditions (iii) and (iv) are satisfied with constants defined in Lemma 2.2.
To show conditions (i) and (ii), we first compute a simpler expression for the
perturbation vector $w^{k}$

$\displaystyle w^{k}$ $\displaystyle=F(s^{k},A^{k})-F(s^{k},\bar{A})$
$\displaystyle=\left(Qs^{k}-\theta-\frac{\alpha}{N}(A^{k}\otimes\mathbb{I}_{n})s^{k}\right)$
$\displaystyle\qquad-\left(Qs^{k}-\theta-\frac{\alpha}{N}(\bar{A}\otimes\mathbb{I}_{n})s^{k}\right)$
$\displaystyle=-\frac{\alpha}{N}((A^{k}-\bar{A})\otimes\mathbb{I}_{n})s^{k}.$

Condition (i) holds since

$\displaystyle\mathrm{E}[w^{k}\mid\mathcal{F}_{k}]$
$\displaystyle=\mathrm{E}\left[-\frac{\alpha}{N}((A^{k}-\bar{A})\otimes\mathbb{I}_{n})s^{k}\mid\mathcal{F}_{k}\right]$
$\displaystyle=-\frac{\alpha}{N}((\mathrm{E}[A^{k}]-\bar{A})\otimes\mathbb{I}_{n})s^{k}=0.$

Condition (ii) also holds since

$\displaystyle\mathrm{E}$
$\displaystyle[\|w^{k}\|_{2}^{2}\mid\mathcal{F}_{k}]=\mathrm{E}\Big{[}\left\|-\frac{\alpha}{N}((A^{k}-\bar{A})\otimes\mathbb{I})s^{k}\right\|_{2}^{2}\
\Big{|}\ \mathcal{F}_{k}\Big{]}$
$\displaystyle\leq\mathrm{E}\Big{[}\frac{\alpha^{2}}{N^{2}}\|(A^{k}-\bar{A})\otimes\mathbb{I}\|_{2}^{2}\|s^{k}\|_{2}^{2}\
\Big{|}\ \mathcal{F}_{k}\Big{]}$
$\displaystyle\overset{(a)}{\leq}\mathrm{E}\Big{[}\frac{\alpha^{2}}{N^{2}}\|A^{k}-\bar{A}\|_{F}^{2}Ns_{\rm
max}^{2}\Big{]}$
$\displaystyle\overset{(b)}{\leq}\frac{\alpha^{2}}{N^{2}}N^{3}s_{\rm
max}^{2}=N\alpha^{2}s_{\rm max}^{2}<\infty$

where (a) follows from the fact that the 2-norm is upper bounded by the
Frobenius norm and (b) follows from $|A_{ij}^{k}-\bar{A}_{ij}|\leq 1$ since
both terms take value in $[0,1]$. By Assumption 2,
$\mathrm{E}[\,\|w^{k}\|^{2}_{2}\,|\,\mathcal{F}_{k}]\leq N\alpha^{2}s_{\rm
max}^{2}<\infty$ implies that
$\sum_{k=1}^{\infty}(\tau^{k})^{2}\mathrm{E}[\,\|w^{k}\|^{2}_{2}\,|\,\mathcal{F}_{k}]$
is upper bounded by the convergent series $N\alpha^{2}s_{\rm
max}^{2}\sum_{k=1}^{\infty}(\tau^{k})^{2}$ and is thus convergent.

Therefore, by [1, Theorem 3.2], the stochastic gradient dynamics converge to
the unique solution of the variational inequality
$(s-\bar{s})^{\top}F(\bar{s},\bar{A})\geq 0,\quad\forall s\in\mathcal{S}$
almost surely and the desired result follows from Lemma 2.1.

###  VII-B Proof of Corollary 1

The proof follows the method of [38, Lemma 14]. Let $\bar{s}$ be the Nash
equilibrium of the game played over the network $\bar{A}$. For any player
$i\in\mathcal{N}$,

$\displaystyle
J_{i}(\bar{s}_{i},\bar{s}_{-i},A^{k})-\inf_{s_{i}\in\mathcal{S}_{i}}J_{i}(s_{i},\bar{s}_{-i},A^{k})$
$\displaystyle\quad=\frac{1}{2}\bar{s}_{i}^{\top}Q_{i}\bar{s}_{i}-\bar{s}_{i}^{\top}\Big{(}\theta_{i}+\frac{\alpha}{N}\sum_{j=1}^{N}A^{k}_{ij}\bar{s}_{j}\Big{)}-\inf_{s_{i}\in\mathcal{S}_{i}}\Big{\\{}\frac{1}{2}s_{i}^{\top}Q_{i}s_{i}$
$\displaystyle\qquad-
s_{i}^{\top}\Big{(}\theta_{i}+\frac{\alpha}{N}\sum_{j=1}^{N}(A^{k}_{ij}+\bar{A}_{ij}-\bar{A}_{ij})\bar{s}_{j}\Big{)}\Big{\\}}$
$\displaystyle\quad\leq\frac{1}{2}\bar{s}_{i}^{\top}Q_{i}\bar{s}_{i}-\bar{s}_{i}^{\top}\Big{(}\theta_{i}+\frac{\alpha}{N}\sum_{j=1}^{N}A^{k}_{ij}\bar{s}_{j}\Big{)}$
$\displaystyle\qquad-\inf_{s_{i}\in\mathcal{S}_{i}}\Big{\\{}\frac{1}{2}s_{i}^{\top}Q_{i}s_{i}-s_{i}^{\top}\Big{(}\theta_{i}+\frac{\alpha}{N}\sum_{j=1}^{N}\bar{A}_{ij}\bar{s}_{j}\Big{)}\Big{\\}}$
$\displaystyle\qquad-\inf_{s_{i}\in\mathcal{S}_{i}}-\frac{\alpha}{N}s_{i}^{\top}\sum_{j=1}^{N}(A^{k}_{ij}-\bar{A}_{ij})\bar{s}_{j}$
$\displaystyle\quad\overset{(a)}{=}\frac{\alpha}{N}\bar{s}_{i}^{\top}\sum_{j=1}^{N}(\bar{A}_{ij}-A^{k}_{ij})\bar{s}_{j}+\sup_{s_{i}\in\mathcal{S}_{i}}\frac{\alpha}{N}s_{i}^{\top}\sum_{j=1}^{N}(A^{k}_{ij}-\bar{A}_{ij})\bar{s}_{j}$
$\displaystyle\quad\overset{(b)}{\leq}2\frac{|\alpha|}{N}s_{\rm
max}\Big{\|}\sum_{j=1}^{N}(\bar{A}_{ij}-A^{k}_{ij})\bar{s}_{j}\Big{\|}_{2}$
(12)

where (a) holds since $\bar{s}_{i}$ is the minimizer of the first infimum
term, and (b) follows from the Cauchy-Schwarz inequality.

Next, we derive a high-probability bound on
$\left\|\sum_{j=1}^{N}(\bar{A}_{ij}-A^{k}_{ij})\bar{s}_{j}\right\|_{2}$. For
all $j\in\mathcal{N}$, for all $l\in\\{1,\dots,n\\}$, let
$(\bar{A}_{ij}-A^{k}_{ij})[\bar{s}_{j}]_{l}=:X^{j}_{l}$ and
$\sum_{j=1}^{N}X^{j}_{l}=:X_{l}$ (the $j=i$ term is simply zero). Then,

$\displaystyle\Big{\|}\sum_{j=1}^{N}(\bar{A}_{ij}-A^{k}_{ij})\bar{s}_{j}\Big{\|}^{2}_{2}$
$\displaystyle=\sum_{l=1}^{n}\Big{(}\sum_{j=1}^{N}(\bar{A}_{ij}-A^{k}_{ij})[\bar{s}_{j}]_{l}\Big{)}^{2}$
$\displaystyle=\sum_{l=1}^{n}(X_{l})^{2}.$

Note that for each $l$, the random variables
$\\{X_{l}^{j}\\}_{j\in\mathcal{N}}$ are independent since
$\\{A^{k}_{ij}\\}_{j\in\mathcal{N}}$ are independent;
$\mathrm{E}[X^{j}_{l}]=\mathrm{E}\left[(\bar{A}_{ij}-A^{k}_{ij})[\bar{s}_{j}]_{l}\right]=0$
since $\mathrm{E}[A^{k}_{ij}]=\bar{A}_{ij}$; and
$|X^{j}_{l}|=|(\bar{A}_{ij}-A^{k}_{ij})[\bar{s}_{j}]_{l}|=|\bar{A}_{ij}-A^{k}_{ij}|\cdot|[\bar{s}_{j}]_{l}|\leq
s_{\rm max}$ since $|\bar{A}_{ij}-A^{k}_{ij}|\leq 1$ due to the fact that
$A_{ij}^{k},\bar{A}_{ij}\in[0,1]$. Hence, by Hoeffding’s inequality, for all
$t>0$,

$\displaystyle\mathbb{P}\left(|X_{l}|\geq t\right)\leq
2\exp\left(\frac{-2t^{2}}{Ns_{\rm max}^{2}}\right).$

To upper bound $\mathbb{P}\left(|X_{l}|\geq t\right)$ by $\delta/nN$, we fix
$t$ such that

$\displaystyle 2\exp\left(\frac{-2t^{2}}{Ns_{\rm
max}^{2}}\right)=\frac{\delta}{nN}$ $\displaystyle\iff$ $\displaystyle
t^{2}=\frac{Ns_{\rm max}^{2}}{2}\ln\left(\frac{2nN}{\delta}\right).$

By the union bound, $\mathbb{P}\left(|X_{l}|\leq t,\,\forall
l=1,\dots,n\right)\geq 1-\delta/N$. Hence, with probability at least
$1-\delta/N$, $\sum_{l=1}^{n}X_{l}^{2}\leq nt^{2}$ and thus

$\displaystyle\Big{\|}\sum_{j=1}^{N}(\bar{A}_{ij}-A^{k}_{ij})\bar{s}_{j}\Big{\|}_{2}\leq\sqrt{n}t$
$\displaystyle\leq\sqrt{\frac{nNs_{\rm
max}^{2}\ln\left(2nN/\delta\right)}{2}}.$

Substituting the bound obtained above into (12), we obtain that for any
arbitrary player $i\in\mathcal{N}$, with probability at least $1-\delta/N$,

$\displaystyle
J_{i}(\bar{s}_{i},\bar{s}_{-i},A^{k})-\inf_{s_{i}\in\mathcal{S}_{i}}J_{i}(s_{i},\bar{s}_{-i},A^{k})$
$\displaystyle\leq 2|\alpha|s_{\rm
max}^{2}\sqrt{\frac{n\ln\left(2nN/\delta\right)}{2N}}$
$\displaystyle=:\epsilon_{N,\delta}.$

By the union bound, we obtain that, with probability at least $1-\delta$,

$\displaystyle
J_{i}(\bar{s}_{i},\bar{s}_{-i},A^{k})-\inf_{s_{i}\in\mathcal{S}_{i}}J_{i}(s_{i},\bar{s}_{-i},A^{k})\leq\epsilon_{N,\delta}$

for all players $i\in\mathcal{N}$. Thus, with probability at least $1-\delta$,
$\bar{s}$ is an $\epsilon_{N,\delta}$-Nash equilibrium of the game
$\mathcal{G}(Q,\theta,\alpha,A^{k})$ played over $A^{k}$.

###  VII-C Proof of Proposition 2

We first rewrite the gradient dynamics in (10) to interpret them as stochastic
gradient play. Consider the strategy update of player $i$

$\displaystyle
s^{k+1}_{i}=\Pi_{\mathcal{S}_{i}}\Big{[}s^{k}_{i}-\frac{\tau^{k}}{\bar{P}_{ii}}P^{k}_{ii}\nabla_{s_{i}}J_{i}(s^{k}_{i},s^{k}_{-i},A^{k}P^{k})\Big{]}$
$\displaystyle=\Pi_{\mathcal{S}_{i}}\Big{[}s^{k}_{i}-\frac{\tau^{k}}{\bar{P}_{ii}}P^{k}_{ii}\Big{(}Q_{i}s_{i}^{k}-\theta_{i}-\frac{\alpha}{N}\sum_{j=1}^{N}A_{ij}^{k}P_{jj}^{k}s_{j}^{k}\Big{)}\Big{]}$
$\displaystyle=\Pi_{\mathcal{S}_{i}}\Big{[}s^{k}_{i}-\frac{\tau^{k}}{\bar{P}_{ii}}\Big{(}P^{k}_{ii}Q_{i}s_{i}^{k}+\bar{P}_{ii}Q_{i}s_{i}^{k}-\bar{P}_{ii}Q_{i}s_{i}^{k}-P^{k}_{ii}\theta_{i}$
$\displaystyle\qquad\qquad+\bar{P}_{ii}\theta_{i}-\bar{P}_{ii}\theta_{i}-\frac{\alpha}{N}\sum_{j=1}^{N}P^{k}_{ii}A_{ij}^{k}P_{jj}^{k}s_{j}^{k}\Big{)}\Big{]}$
$\displaystyle=\Pi_{\mathcal{S}_{i}}\Big{[}s^{k}_{i}-\frac{\tau^{k}}{\bar{P}_{ii}}\Big{(}\bar{P}_{ii}Q_{i}s_{i}^{k}-\bar{P}_{ii}\theta_{i}-\frac{\alpha}{N}\sum_{j=1}^{N}P^{k}_{ii}A_{ij}^{k}P_{jj}^{k}s_{j}^{k}$
$\displaystyle\qquad\qquad+(P_{ii}^{k}-\bar{P}_{ii})(Q_{i}s_{i}^{k}-\theta_{i})\Big{)}\Big{]}$
$\displaystyle=\Pi_{\mathcal{S}_{i}}\Big{[}s^{k}_{i}-\tau^{k}\Big{(}Q_{i}s_{i}^{k}-\theta_{i}-\frac{\alpha}{N}\sum_{j=1}^{N}\mathrm{E}[\tilde{A}_{ij}^{k}]s_{j}^{k}+w_{i}^{k}\Big{)}\Big{]}$

where
$w_{i}^{k}:=\frac{\alpha}{N}\sum_{j=1}^{N}(\mathrm{E}[\tilde{A}_{ij}^{k}]-\tilde{A}_{ij}^{k})s_{j}^{k}+\frac{1}{\bar{P}_{ii}}(P_{ii}^{k}-\bar{P}_{ii})(Q_{i}s_{i}^{k}-\theta_{i})$
and
$\tilde{A}_{ij}^{k}:=\frac{1}{\bar{P}_{ii}}P^{k}_{ii}A_{ij}^{k}P_{jj}^{k}$.
Note that

$\mathrm{E}[\tilde{A}^{k}]=\mathrm{E}[\bar{P}^{-1}P^{k}A^{k}P^{k}]=\bar{A}\bar{P}.$

This is because
$\mathrm{E}[\tilde{A}^{k}_{ij}]=\frac{1}{\bar{P}_{ii}}\mathrm{E}[P^{k}_{ii}A^{k}_{ij}P^{k}_{jj}]=\frac{1}{\bar{P}_{ii}}\bar{P}_{ii}\bar{A}_{ij}\bar{P}_{jj}$
if $i\neq j$ since the random variables are independent, and
$\mathrm{E}[\tilde{A}^{k}_{ii}]=\frac{1}{\bar{P}_{ii}}\mathrm{E}[P^{k}_{ii}A^{k}_{ii}P^{k}_{ii}]=0$
since $A^{k}_{ii}=0$. Hence, we obtain the following stochastic gradient
dynamics for all agents

$\displaystyle s^{k+1}$
$\displaystyle=\Pi_{\mathcal{S}}[s^{k}-\tau^{k}(F(s^{k},\bar{A}\bar{P})+w^{k})]$

where $w^{k}=[w_{i}^{k}]_{i\in\mathcal{N}}$ is the perturbation vector. The
dynamics of this game can be interpreted as a stochastic approximation to the
gradient play over the game with expected network $\bar{A}\bar{P}$.

As in Proposition 1’s proof, we can verify conditions (i)-(iv) to show
convergence of these stochastic projected gradient dynamics. One can show that
conditions (i)-(ii) hold with the same approach used in Proposition 1 by
showing that $\mathrm{E}[\,w^{k}\,|\,\mathcal{F}_{k}]=0$ and that
$\mathrm{E}[\,\|w^{k}\|_{2}^{2}\,|\,\mathcal{F}_{k}]<\infty$. Conditions
(iii)-(iv) also hold, by Lipschitzness and strong monotonicity of
$F(\cdot,\bar{A}\bar{P})$.

Therefore, by [1, Theorem 3.2], the stochastic gradient dynamics will converge
almost surely to the unique solution of the variational inequality
$(s-\bar{s})^{\top}F(\bar{s},\bar{A}\bar{P})\geq 0$, for all $s\in\mathcal{S}$
and the desired result follows from Lemma 2.1.

###  VII-D Proof of Corollary 2

The proof is similar to that of Corollary 1 and the same arguments hold. Note
that for a fixed $i$, the random variables
$\\{A^{k}_{ij}P^{k}_{jj}\\}_{j\in\mathcal{N}}$ have the same properties as
their counterparts $\\{A^{k}_{ij}\\}_{j\in\mathcal{N}}$ in Corollary 1. In
particular, the random variables
$\\{\bar{A}_{ij}\bar{P}_{jj}-A^{k}_{ij}P^{k}_{jj}\\}_{j\in\mathcal{N}}$ are
independent, zero-mean and satisfy
$|\bar{A}_{ij}\bar{P}_{jj}-A^{k}_{ij}P^{k}_{jj}|\leq 1$, and
$A^{k}_{ii}P^{k}_{ii}=0$ since $A^{k}_{ii}=0$.


The _canonical lifting $A$-bundle gerbe_ is $[EBA/EA]$; here, the central
extension is $A\to EA\to BA$, and the principal $BA$-bundle is $EBA\to
B^{2}A$. As a four term sequence it looks as follows:

$A\longrightarrow EA\circlearrowright EBA\longrightarrow B^{2}A.$

  2. (2)

The _trivial lifting $A$-gerbe_ is $[\ast/A]$, i.e., $N=A$ and $E=\ast$.

The Lifting bundle gerbes appearing in this work are ones with $N$ abelian,
which we then call abelian lifting $A$-gerbes. In most of the cases it is the
degree 0 group $C^{0}$ of a complex, and the group $A$ is the zeroth
cohomology group $H^{0}\subset C^{0}$. The space $E$ consists of pairs of
points on a fixed space together with elements in the degree 1 group $C^{1}$
of the complex. The action of $N$ on $E$ is simply obtained by adding the
image of the differential $d:C^{0}\to C^{1}$.

###  8.2. Morphisms

Take two lifting bundle $A$-gerbes $[E/N]$ and $[D/M]$. A strict morphism is a
continuous functor $\psi:[E/N]\to[D/M]$ that is $A$-equivariant at the level
of morphisms.

More explicitly, the functor $\psi$ is at the level of morphisms given by a
continuous map $\psi_{1}:E\times N\to D\times M$, and $A$ acts on both sides
by multiplication on $N$ and $M$, respectively. The requirement is that
$\psi_{1}$ is equivariant for these actions. Denoting for one moment the
1-category of lifting $A$-gerbes by $A$-${\mathfrak{LftGrbs}}$ we have then:

$\mathrm{Hom}_{A\text{-}{\mathfrak{LftGrbs}}}([E/N],[D/M])\\\
=\\{\psi\in\mathrm{Hom}_{{\mathfrak{TopGpds}}}([E/N],[D/M])\mid\psi_{1}\
\mbox{is}\ A\mbox{-equivariant}\\}.$

It is important to notice that not all continuous functors are morphisms of
lifting$A$-gerbes. The most simple case on which this could be seen is the
trivial gerbe $[*/A]$. On the one hand
$\mathrm{Hom}_{{\mathfrak{TopGpds}}}([*/A],[*/A])=\mathrm{Hom}(A,A)$ consists
off all endomorphism of groups of $A$. On the other hand
$\mathrm{Hom}_{A\text{-}{\mathfrak{LftGrbs}}}([*/A],[*/A])$ consists of only
the identity map. Notice also that the natural transformations from the
identity functor on $[A/*]$ to itself are parameterized by elements in $A$.

A special example of strict morphisms comes from principal bundle morphisms.
Let $E$ be a principal $N/A$-bundle, and let $D$ be a principal $M/A$-bundle,
let $\phi:N\to M$ be an $A$-equivariant group homomorphism, and let
$\psi_{0}:E\to D$ be a $\phi$-equivariant map, i.e.,
$\psi_{0}(e[n])=\psi(e)[\phi(n)]$. Then, $\psi_{0}$ and
$\psi_{1}:=\psi_{0}\times\phi$ from a strict morphism $\psi:[E/N]\to[D/M]$.
Note that this works, in particular, when $M=N$ and $\phi={\text{id}}_{N}$.

###  8.3. 2-Morphisms

Continuous natural transformations provide the 2-morphisms that turn the
1-category of lifting bundle $A$-gerbes into a 2-category, which from now will
be denoted by $A$-${\mathfrak{LftGrbs}}$.

###  8.4. Monoidal structure

The 2-category $A$-${\mathfrak{LftGrbs}}$ of lifting bundle $A$-gerbes can be
moreover be endowed with a monoidal structure. Take two lifting bundle
$A$-gerbes $[E/N]$ and $[D/M]$ and define their product

$[E/N]\otimes[D/M]:=[((E\times D)/(N\otimes M)]$

where the group $N\otimes M$ is the quotient of $N\times M$ by its diagonal
subgroup $\Delta:=\\{(a,a^{-1})\mid a\in A\\}$. The trivial lifting $A$-gerbe
$[\ast/A]$ is neutral with respect to this tensor product.

We remark that the underlying groupoid of $[E/N]\otimes[D/M]$ is not the
direct product of the groupoids $[E/N]$ and $[D/M]$, but that there is a
continuous functor $[E/N]\times[D/M]\to[E/N]\otimes[D/M]$ that is the identity
on the level of objects. A continuous functor
$\psi:[E/N]\times[E^{\prime}/N^{\prime}]\to[D/M]$ induces a strict morphism
$[E/N]\otimes[E^{\prime}/N^{\prime}]\to[D/M]$ of lifting bundle $A$-gerbes if
and only if its restriction to isotropy groups is the product of the group
$A$. In terms of the trivial gerbe $[*/A]$, the only functor
$[*/A]\times[*/A]\to[*/A]$ that induces a morphism of $A$-gerbes
$[*/A]\otimes[*/A]\to[*/A]$ is the one induced by the product structure on
$A$.

###  8.5. Strict group objects

A _strictly multiplicative lifting bundle $A$-gerbe_ is a strict group object
in lifting bundle $A$-gerbes [2]. Thus, it is a lifting bundle $A$-gerbe
$[E/N]$ together with strict morphisms $[E/N]\otimes[E/N]\to[E/N]$
(multiplication), $[E/N]\to[E/N]$ (inversion), and $[\ast/A]\to[E/N]$ (unit),
satisfying strictly the axioms of a group. Note that a strictly multiplicative
lifting bundle $A$-gerbe is in particular a group in the category of
topological groupoids, i.e., a strict topological 2-group. In fact, these two
conditions are equivalent:

######  Lemma 8.1.

A lifting bundle $A$-gerbe is strictly multiplicative if and only if the
underlying groupoid is a strict topological 2-group.

###### Proof.

The reason for this phenomenon is the fact that for a groupoid $[*/A]$ to
become a 2-group it is necessary that $A$ is abelian and that the product
structure $[*/A]\times[*/A]\to[*/A]$ coincides with the product structure of
$A$. Hence, the structural properties of groups in groupoids impose the
conditions necessary for the product to induce one on lifting bundle
$A$-gerbes. ∎

We remark that for a strictly multiplicative lifting bundle $A$-gerbe, the
spaces $E$ and $E/N$ are in fact topological groups, and that there is a group
homomorphism $N\to E$. Hence we obtain an exact four term sequence

$A\longrightarrow N\longrightarrow E\longrightarrow E/N\text{.}$

Under the correspondence between strict 2-groups and crossed modules, the
above 4-term sequence is precisely the one associated to a crossed module, see
§7.1.

The trivial lifting bundle $A$-gerbe $[\ast/A]$ is strictly multiplicative in
a unique way, and the canonical lifting bundle $A$-gerbe $[EBA/EA]$ is
strictly multiplicative for the given group structure on $EBA$. Also, the
2-groups of endomorphisms $\operatorname{End}_{\langle
G,\alpha\rangle^{op}}(G,\overline{\alpha})$, $\operatorname{End}_{\langle
G,\alpha\rangle}(K,\beta)$ and

$\operatorname{End}_{\operatorname{End}_{\langle
G,\alpha\rangle^{op}}(K,\beta)}\left(\mathrm{Hom}_{\langle
G,\alpha\rangle^{op}}((G,\overline{\alpha}),(K,\beta))\right)$

defined in Example 4.3, Theorem 5.1 and Theorem 6.2 respectively are strictly
multiplicative lifting bundle $U(1)$-gerbes.

###  8.6. Representations of strictly multiplicative lifting bundle gerbes

Strict group objects may act on objects. In our case, the lifting bundle
$A$-gerbes representations of a group object in lifting bundle $A$-gerbes form
a 2-category. This 2-category is constructed in the usual way [2]. Objects are
lifting bundle $A$-gerbes representations of the specific group object in
lifting bundle $A$-gerbes, morphisms are morphisms of lifting bundle
$A$-gerbes compatible with the action, and 2-morphisms are the natural
transformations.

An example of a representation of a group in lifting bundle $U(1)$-gerbes is
the lifting bundle $U(1)$-gerbe $\mathrm{Hom}_{\langle
G,\alpha\rangle^{op}}((G,\overline{\alpha}),(K,\beta))$ of Proposition 6.1. It
is a right representation of the group lifting bundle $U(1)$-gerbe
$\operatorname{End}_{\langle G,\alpha\rangle^{op}}(G,\overline{\alpha})$ and a
left representation of the group lifting bundle $U(1)$-gerbe
$\operatorname{End}_{\langle G,\alpha\rangle^{op}}(K,\beta)$.

###  8.7. Weak morphisms

Strict morphisms as defined above are not enough to capture the essence of the
bicategory of lifting bundle $A$-gerbes (though, for the purpose of this
article they suffice to discuss group objects). There is a well established
notion of weak morphisms between topological groupoids that correctly reflects
the equivalence between topological stacks, known as anafunctors, bibundles,
or Hilsum-Skandalis morphisms, see, e.g., [10, 15, 26]. An $A$-equivariant
(smooth) version has been introduced in [22, App. A]. Adapted to our setting,
we obtain the following. A weak morphism between lifting bundle $A$-gerbes
$[E/N]$ and $[D/M]$ consists of the following structure:

  * •

a space $F$ together with maps $\mu:F\to E$ and $\nu:F\to D$,

  * •

an action of $N$ on $F$ making $\mu$ $N$-equivariant,

  * •

an action of $M$ on $F$ making $\nu$ $M$-equivariant and $\mu$ a principal
$M$-bundle,

such that the actions of $A\subset N$ and $A\subset M$ agree on $F$. Weak
morphisms will be pictured as diagrams

$\textstyle{F\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mu}$$\scriptstyle{\nu}$$\textstyle{E}$$\textstyle{D.}$

Whenever the map $\mu:F\to D$ is also an $N$-principal bundle, the weak
morphism becomes a weak isomorphism, whose inverse is obtained by flipping the
sides. In this case we obtain homeomorphisms

$F/D\cong E,\ \ F/M\cong D,\ \ E/N\cong D/M$

and the following diagram induce equivalence of topological groupoids

$\textstyle{[F/(M\times
N)]\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mu}$$\scriptstyle{\simeq}$$\scriptstyle{\nu}$$\scriptstyle{\simeq}$$\textstyle{[E/N]}$$\textstyle{[D/M].}$

We shall see now that a strict morphism induces a weak one. Indeed, suppose
$\Psi:[E/N]\to[D/M]$ is a strict morphism. We obtain a map $\psi:E/N\to D/M$
of the underlying spaces and we may consider the space
$\Delta^{*}(E\times\psi^{*}D)$ where $\Delta:E/N\to E/N\times E/N$ is the
diagonal map. There is a canonical action of $N\times M$ on
$\Delta^{*}(E\times\psi^{*}D)$ and canonical projection maps

$\Delta^{*}(E\times\psi^{*}D)\to E\ \ \mbox{and}\ \
\Delta^{*}(E\times\psi^{*}D)\to D$

where the first one is an $M$-principal bundle. The space
$\Delta^{*}(E\times\psi^{*}D)$ together with the action and the maps is the
weak morphism induced by $\Psi$.

Weak morphisms are related through weak 2-morphisms, which are maps $F\to
F^{\prime}$ that exchange the maps to $E$ and $D$, and are equivariant with
respect to the actions of $M$ and $N$. We refer the reader to the references
above for a detailed study of the 2-categorical structure. Now we are ready to
show the following result.

######  Theorem 8.2.

Let us consider the 2-category of Segal-Mitchison gerbes with structure group
$A$ and the 2-category lifting bundle $A$-gerbes with weak morphisms and weak
2-morphisms. Then, the functor

$\displaystyle A\text{-}\mathfrak{SM}\text{-}\mathfrak{Grbs}\to$
$\displaystyle A\text{-}{\mathfrak{LftGrbs}}$ $\displaystyle(M,\alpha)\mapsto$
$\displaystyle[(\alpha^{*}EBA)/EA],$

is an equivalence of 2-categories.

###### Proof.

The functor is defined in section §2.1 at the level of objects, in section
§2.2 at the level of morphisms and in section §2.3 at the level of
2-morphisms.

Let us now show that the functor is essentially surjective. That is, for a
lifting bundle $A$-gerbe $[E/N]$ we need to find a Segal-Mitchison $A$-gerbe
$\alpha:E/N\to B^{2}A$ and a weak isomorphism between $[E/N]$ and
$[\alpha^{*}EBA/EA]$. For this we need some preparation.

Since the principal bundle $N/A\to E\to E/N$ is obtained by pullback from the
universal one $N/A\to E(N/A)\to B(N/A)$, we will focus our attention in
finding a canonical Segal-Mitchison $A$-gerbe

$\alpha:B(N/A)\longrightarrow B^{2}A$

and a weak isomorphism from $[E(N/A)/N]$ to $[\alpha^{*}EBA/EA]$.

Consider the diagonal action of $A$ on $N\times EA$ and denote $N\times_{A}EA$
the quotient group. Consider the diagram of topological groups

$\textstyle{N\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{EA\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{N\times_{A}EA\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\pi_{1}}$$\scriptstyle{\pi_{2}}$$\textstyle{N/A}$$\textstyle{BA}$

where the diagonals are central extensions of groups, and $\pi_{1}$ and
$\pi_{2}$ are the homomorphisms induced by projections on the first and second
coordinates, respectively. Applying the classifying space functor $B$, we
obtain the diagram

$\textstyle{BN\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{BEA\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{B(N\times_{A}EA)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{B\pi_{1}}$$\scriptstyle{B\pi_{2}}$$\textstyle{B(N/A)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\sigma}$$\textstyle{B^{2}A}$

and note that there exists a section $\sigma:B(N/A)\to B(N\times_{A}EA)$ of
the fiber map $B\pi_{1}$ since the fiber $BEA$ is contractible. Take

$\alpha:=B\pi_{2}\circ\sigma:B(N/A)\to B^{2}A$

and let us show that the lifting bundle $A$-gerbes $[E(N/A)/N]$ and
$[\alpha^{*}EBA/EA]$ are weakly isomorphic.

The diagram of principal bundles

$\textstyle{E(N/A)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{p_{1}}$$\textstyle{E(N\times_{A}EA)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{E\pi_{1}}$$\scriptstyle{E\pi_{2}}$$\scriptstyle{p}$$\textstyle{EA\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{p_{2}}$$\textstyle{B(N/A)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\sigma}$$\textstyle{B(N\times_{A}EA)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{B\pi_{1}}$$\scriptstyle{B\pi_{2}}$$\textstyle{B^{2}A}$

induces the diagram of principal bundles over the same base $B(N/A)$

$\textstyle{E(N/A)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{p_{1}}$$\textstyle{\sigma^{*}E(N\times_{A}EA)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{E\pi_{1}}$$\scriptstyle{E\pi_{2}}$$\scriptstyle{p}$$\textstyle{\alpha^{*}EA\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{p_{2}}$$\textstyle{B(N/A)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{B(N/A)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{B(N/A).}$

The space $\sigma^{*}E(N\times_{A}EA)$ has free commuting actions of both $N$
and $EA$ and their actions agree on $A$. The bundle
$E\pi_{2}:\sigma^{*}E(N\times_{A}EA)\to\alpha^{*}EA$ is an $N$-principal
bundle and the bundle $E\pi_{1}:\sigma^{*}E(N\times_{A}EA)\to E(N/A)$ is an
$EA$-principal bundle. Hence, we have a weak isomorphism.

Note that whenever $N=EA$ we may take $\sigma:B^{2}A\to B(EA\times_{A}EA)$ as
$\sigma:=B\Delta$ where $\Delta:BA\to EA\times_{A}EA$,
$\Delta[\lambda]=[(\lambda,\lambda)]$. The composition becomes

$\alpha=B\pi_{2}\circ B\Delta=B(\pi_{2}\circ\Delta)=B(id)=id$

and therefore the map $\alpha:B^{2}A\to B^{2}A$ is the identity.

Let us now show that the functor is fully faithful. Consider two Segal-
Mitchison gerbes $(M,\alpha)$ and $(N,\beta)$, and let $F$ be a weak morphism
between $[\alpha^{*}EBA/EA]$ and $[\beta^{*}EBA/EA]$. We have then maps

$\textstyle{F\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mu}$$\scriptstyle{\nu}$$\textstyle{\alpha^{*}EBA}$$\textstyle{\beta^{*}EBA}$

where $F$ is endowed with an action of $EA\times EA$ and $\mu$ is a principal
$EA$-bundle. The maps $\mu$ and $\nu$ induce maps at the level of quotient
spaces

$\textstyle{F/(EA\times
EA)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\widetilde{\mu}}$$\scriptstyle{\cong}$$\scriptstyle{\widetilde{\nu}}$$\textstyle{M=\alpha^{*}EBA/EA}$$\textstyle{\beta^{*}EBA/EA=N}$

where $\widetilde{\mu}$ is a homeomorphism and $\widetilde{\mu}^{-1}$ is its
inverse. It is now straightforward to check that the maps $\alpha$ and
$\beta\circ\widetilde{\nu}\circ\widetilde{\mu}^{-1}$ are homotopic, where
$\widetilde{\nu}\circ\widetilde{\mu}^{-1}:M\to N$. This implies that the
functor

$\mathrm{Hom}_{A\text{-}\mathfrak{SM}\text{-}\mathfrak{Grbs}}((M,\alpha),(N,\beta))\to\mathrm{Hom}^{\text{weak}}_{A\text{-}{\mathfrak{LftGrbs}}}([\alpha^{*}EBA/EA],[\beta^{*}EBA/EA])$

is essentially surjective. In order to see that it is fully faithful, we
recall that morphisms of Segal-Mitchison gerbes are mapped to _strict_
morphisms of lifting bundle $A$-gerbes. It is well known from above references
about weak morphisms, that the functor

$\mathrm{Hom}^{\text{strict}}_{A\text{-}{\mathfrak{LftGrbs}}}([E/N],[D/M])\to\mathrm{Hom}^{\text{weak}}_{A\text{-}{\mathfrak{LftGrbs}}}([E/N],[D/M])$

is fully faithful. Thus, it suffices to show that the 2-morphisms between
Segal-Mitchison gerbes correspond one-to-one with 2-morphisms between strict
morphisms of the corresponding lifting gerbes. This follows directly from the
definitions. ∎

## References

  * AN [09] Ettore Aldrovandi and Behrang Noohi.  Butterflies. I. Morphisms of 2-group stacks.  Adv. Math., 221(3):687–773, 2009.
  * BL [04] John C. Baez and Aaron D. Lauda.  Higher-dimensional algebra. V. 2-groups.  Theory Appl. Categ., 12:423–491, 2004.
  * BM [94] Jean-Luc Brylinski and D. A. McLaughlin.  The geometry of degree four characteristic classes and of line bundles on loop spaces I.  Duke Math. J., 75(3):603–638, 1994.
  * Bre [92] Lawrence Breen.  Théorie de Schreier supérieure.  Ann. Sci. École Norm. Sup. (4), 25(5):465–514, 1992.
  * Bry [93] Jean-Luc Brylinski.  Loop spaces, characteristic classes and geometric quantization.  Modern Birkhäuser Classics. Birkhäuser Boston, Inc., Boston, MA, 1993.  Reprint of the 1993 edition.
  * CJM+ [05] Alan L. Carey, Stuart Johnson, Michael K. Murray, Danny Stevenson, and Bai-Ling Wang.  Bundle gerbes for Chern-Simons and Wess-Zumino-Witten theories.  Comm. Math. Phys., 259(3):577–613, 2005.
  * ENO [05] Pavel Etingof, Dmitri Nikshych, and Viktor Ostrik.  On fusion categories.  Ann. of Math. (2), 162(2):581–642, 2005.
  * GR [03] Krzysztof Gawȩdzki and Nuno Reis.  Basic gerbe over non simply connected compact groups.  J. Geom. Phys., 50(1–4):28–55, 2003.
  * GW [09] Krzysztof Gawȩdzki and Konrad Waldorf.  Polyakov-Wiegmann formula and multiplicative gerbes.  J. High Energy Phys., (9):073, 31, 2009.
  * Hae [84] André Haefliger.  Groupoïdes d’holonomie et classifiants.  Astérisque, 116:70–97, 1984.
  * LGSX [09] Camille Laurent-Gengoux, Mathieu Stiénon, and Ping Xu.  Non-abelian differentiable gerbes.  Adv. Math., 220(5):1357–1427, 2009.
  * Mei [03] Eckhard Meinrenken.  The basic gerbe over a compact simple Lie group.  Enseign. Math. (2), 49(3-4):307–333, 2003.
  * MMU [18] Kevin Maya, Adriana Mejía, and Bernardo Uribe.  Classification of pointed fusion categories of dimension $p^{3}$ up to weak morita equivalence.  To appear in J. of Alg. and its Appl., 2018.
  * MnU [18] Álvaro Muñoz and Bernardo Uribe.  Classification of Pointed Fusion Categories of dimension 8 up to weak Morita equivalence.  Comm. Algebra, 46(9):3873–3888, 2018.
  * Moe [91] I. Moerdijk.  Classifying toposes and foliations.  Ann. Inst. Fourier (Grenoble), 41(1):189–209, 1991.
  * Mor [79] Sidney A. Morris.  Duality and structure of locally compact abelian groups$\ldots$for the layman.  Math. Chronicle, 8:39–56, 1979.
  * MS [17] Michaël Mignard and Peter Schauenburg.  Morita equivalence of pointed fusion categories of small rank.  arXiv:1708.06538, 2017.
  * [18] Michael Müger.  From subfactors to categories and topology. I. Frobenius algebras in and Morita equivalence of tensor categories.  J. Pure Appl. Algebra, 180(1-2):81–157, 2003.
  * [19] Michael Müger.  From subfactors to categories and topology. II. The quantum double of tensor categories and subfactors.  J. Pure Appl. Algebra, 180(1-2):159–219, 2003.
  * Mur [96] M. K. Murray.  Bundle gerbes.  J. London Math. Soc. (2), 54(2):403–416, 1996.
  * Nai [07] Deepak Naidu.  Categorical Morita equivalence for group-theoretical categories.  Comm. Algebra, 35(11):3544–3565, 2007.
  * NW [13] Thomas Nikolaus and Konrad Waldorf.  Four equivalent versions of nonabelian gerbes.  Pacific J. Math., 264(2):355–419, 2013.
  * [23] Victor Ostrik.  Module categories, weak Hopf algebras and modular invariants.  Transform. Groups, 8(2):177–206, 2003.
  * [24] Viktor Ostrik.  Module categories over the Drinfeld double of a finite group.  Int. Math. Res. Not., (27):1507–1520, 2003.
  * Pon [34] L. Pontrjagin.  The theory of topological commutative groups.  Ann. of Math. (2), 35(2):361–388, 1934.
  * Pro [96] Dorette A. Pronk.  Entendues and stacks as bicategories of fractions.  Compos. Math., 102:243–303, 1996.
  * Rou [03] Alain Rousseau.  Bicatégories monoïdales et extensions de gr-catégories.  Homology Homotopy Appl., 5(1):437–547, 2003.
  * Row [08] Louis Halle Rowen.  Graduate algebra: noncommutative view, volume 91 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, RI, 2008.
  * Seg [70] Graeme Segal.  Cohomology of topological groups.  In Symposia Mathematica, Vol. IV (INDAM, Rome, 1968/69), pages 377–387. Academic Press, London, 1970.
  * SP [11] Christopher J. Schommer-Pries.  Central extensions of smooth 2-groups and a finite-dimensional string 2-group.  Geom. Topol., 15(2):609–676, 2011.
  * Uri [17] Bernardo Uribe.  On the classification of pointed fusion categories up to weak Morita equivalence.  Pacific J. Math., 290(2):437–466, 2017.
  * Wal [10] Konrad Waldorf.  Multiplicative bundle gerbes with connection.  Differential Geom. Appl., 28(3):313–340, 2010.