# Learning Equilibrium with Estimated Payoffs in Population Games

Shinkyu Park
This work was supported by funding from King Abdullah University of Science
and Technology (KAUST).The author is with Electrical and Computer Engineering,
King Abdullah University of Science and Technology (KAUST), Thuwal,
23955-6900, Kingdom of Saudi Arabia<EMAIL_ADDRESS>
###### Abstract

We study a multi-agent decision problem in population games, where agents
select from multiple available strategies and continually revise their
selections based on the payoffs associated with these strategies. Unlike
conventional population game formulations, we consider a scenario where agents
must estimate the payoffs through local measurements and communication with
their neighbors. By employing task allocation games – dynamic extensions of
conventional population games – we examine how errors in payoff estimation by
individual agents affect the convergence of the strategy revision process. Our
main contribution is an analysis of how estimation errors impact the
convergence of the agents’ strategy profile to equilibrium. Based on the
analytical results, we propose a design for a time-varying strategy revision
rate to guarantee convergence. Simulation studies illustrate how the proposed
method for updating the revision rate facilitates convergence to equilibrium.

##  I Introduction

Large-population game frameworks provide a systematic approach to studying the
decision-making processes of multiple agents engaged in repeated strategic
interactions. These frameworks find applications across a wide range of
fields, including road congestion [1, 2], communication systems [3, 4],
distributed control systems [5], and multi-robot task allocation [6, 7, 8],
among others. In this work, we investigate a decision-making model within the
population game framework [9], where agents utilize the model to select a
strategy among a finite set of available options. This model consists of a
learning rule (also referred to as a revision protocol) and stochastic alarm
clock, defining how individual agents repeatedly revise their strategy
selections, with the primary goal of learning the best strategies. Under this
model, the agent strategy selection is influenced by information about payoffs
of available strategies. Within the standard framework, it is generally
assumed that all agents have perfect knowledge of these payoffs.

However, in many engineering applications, such as decentralized control
systems [10], where sensing and decision-making are decentralized, this
assumption requires well-established communication channels to ensure that all
agents have complete knowledge of the payoffs. Otherwise, agents must estimate
the payoffs based on local observations and communication with neighbors, and
then make decisions on strategy selection based on their own payoff estimates.
In this context, limited communication between agents leads to non-negligible
estimation errors. This paradigm challenges one of the key assumptions of the
standard population game formalism, which is critical for establishing
convergence results [9].

In this paper, we adopt task allocation games [6, 11] and analyze the effect
of errors in payoff estimation on the convergence of the agent strategy
revision process. These games can be viewed as dynamic extensions of
conventional population games, with potential applications in multi-robot
systems research as demonstrated in [6]. In task allocation games, agents
choose strategies to complete a set of predefined tasks, where the payoff for
each strategy is determined by the amount of jobs remaining in its associated
task. Unlike their conventional counterparts, the game has its own state,
governed by a dynamical system model, to represent the remaining jobs for each
task. In such dynamic game settings, if agents have limited capabilities for
observing the game’s state, they must estimate it and use this estimate to
infer expected payoffs and select one of available strategies.

Relevant to our present work where agents are communicating with their
neighbors defined by a graph for payoff estimation, the literature on games
over graphs, as exemplified by [12], studies the long-term strategic
interactions of multiple agents when social networks, represented by graphs,
restrict the interactions between them. The study by [13] proposes a new
population dynamics framework designed to model distributed information
structures in population games. In this framework, the strategic decision-
making of multiple agents is represented by a dynamical system model,
concisely expressed as an ordinary differential equation (ODE) on a graph.
Using this ODE model, the authors examine convergence of population dynamics.

As part of the series of works, the author of [14] proposes a framework to
rigorously formulate the agent decision-making process in scenarios where each
agent has limited access to information about the underlying game. This
limitation results in noisy evaluations of payoffs for available strategies
and limited knowledge of other agents’ strategy selections. The work also
evaluates equilibrium states of the process to predict the long-term behavior
of the agents’ decision-making. The work of [15] discusses analytical methods
for assessing the long-term behavior of agents’ noisy decision-making
processes, described by stochastic dynamical system models. Notably, the main
results illustrate how a stochastically stable equilibrium emerges as the
noise level in the agent decision-making process approaches zero.

In our work, we analyze how payoff estimation errors affect the convergence of
the agent decision-making process in task allocation games. Unlike previous
studies that primarily focus on analyzing the impact of errors on the
decision-making process, we propose a method to eliminate this influence in
our problem setting. Specifically, we rigorously prove that with a decreasing
strategy revision rate, agents’ decision-making process effectively mitigates
the effects of estimation errors, allowing them to asymptotically learn and
attain the equilibrium corresponding to the optimal strategy selection. Based
on this analysis, we propose a design for a stochastic alarm clock to ensure
convergence. Our technical contributions are summarized as follows:

  * •

Leveraging passivity-based analytical tools [16, 17] developed for population
games, we analyze the impact of payoff estimation errors on the convergence of
the agent decision-making process to its equilibrium state in task allocation
games. In particular, we discuss how the influence of the estimation error can
be mitigated by decreasing the rate of agents’ strategy revision.

  * •

Based on the analysis, we propose the design of a stochastic alarm clock using
a non-homogeneous Poisson process to guarantee the convergence. Through
simulations with a large number of agents, we illustrate our analytical
results and evaluate the effectiveness of the proposed clock design.

The paper is organized as follows: In Section II, we formally introduce task
allocation games and an agent decision-making model, specifying when and how
each agent revises its strategy selection and how it estimates the payoffs for
available strategies. In Section III, we present an analysis of how errors in
payoff estimation affect convergence of the agent decision-making process in
task allocation games, and propose a design for a non-homogeneous Poisson
alarm clock that guarantees convergence. In Section IV, we present simulation
results that illustrate both our analytical findings and the effectiveness of
the proposed clock design.

##  II Preliminaries and Problem Description

In task allocation games [6], there is a finite number $n$ of tasks for a
population of agents to carry out. Each agent can select one of available
strategies to address the tasks. In this paper, for a concise presentation, we
assume that the number of strategies and tasks is the same. We denote the
amount of jobs to be completed associated with each task
$i\in\\{1,\cdots,n\\}$ by a non-negative, time-dependent variable
$q_{i}(t)\in[0,q_{\text{max}}]$. We refer to $q(t)=(q_{1}(t),\cdots,q_{n}(t))$
as the game state. When $q_{i}(t)$ is below its maximum, $q_{\text{max}}$, the
variable increases at a constant rate as more jobs are assigned to the agents
and decreases as the agents complete the jobs. This decrease is based on the
agents’ strategy selections, represented by the population state
$x(t)=(x_{1}(t),\cdots,x_{n}(t))$, where each entry $x_{i}(t)$ denotes the
fraction of the population selecting strategy $i$. Let $\mathbb{X}$ be the
space of all viable population states, defined as
$\mathbb{X}=\left\\{x\in\mathbb{R}_{+}^{n}\,\big{|}\,\textstyle\sum_{i=1}^{n}x_{i}=1\right\\}$,
where $\mathbb{R}_{+}^{n}$ is the set of (element-wise) non-negative
$n$-dimensional vectors.

###  II-A Task Allocation Game Model

We adopt the following dynamical system representation from [6] to specify how
$q_{i}(t)$ varies over time: If $q_{i}(t)<q_{\text{max}}$, then

$\displaystyle\dot{q}_{i}(t)=-\underbrace{\mathcal{F}_{i}(q_{i}(t),x_{i}(t))}_{\text{decrease
rate}}+\underbrace{w_{i}}_{\text{increase rate}},~{}q_{i}(0)\geq 0,$ (1)

and $\dot{q}_{i}(t)=\min\\{0,-\mathcal{F}_{i}(q_{i}(t),x_{i}(t))+w_{i}\\}$ if
$q_{i}(t)=q_{\text{max}}$, where the latter condition ensures that $q_{i}(t)$
does not exceed its maximum $q_{\text{max}}$. The function
$\mathcal{F}_{i}:[0,q_{\text{max}}]\times\mathbb{R}_{+}\to\mathbb{R}_{+}$ is
non-negative111Note that even if the $i$-th portion $x_{i}(t)$ of the
population state is within $[0,1]$, we define the domain of $\mathcal{F}_{i}$
corresponding to $x_{i}(t)$ as the entire set $\mathbb{R}_{+}$ of non-negative
real numbers., and $w_{i}$ is a positive constant. Also, to ensure that
$q_{i}(t)$ is non-negative for all $t\geq 0$, the function
$\mathcal{F}_{i}(q_{i},x_{i})$ is zero whenever $q_{i}=0$.

According to (1), each agent can carry out one task at a time. The output of
the game model is the payoff vector $p(t)=(p_{1}(t),\cdots,p_{n}(t))$, where
we define each $p_{i}(t)$ as $p_{i}(t)=q_{i}(t)$ to associate $p_{i}(t)$ with
the amount of remaining jobs in the $i$-th task. Consequently, under this
definition of the payoff vector, agents can be incentivized to carry out the
tasks with more remaining jobs. The following are assumptions we impose on
(1).

###### Assumption 1

The function
$\mathcal{F}_{i}:[0,q_{\text{max}}]\times\mathbb{R}_{+}\to\mathbb{R}_{+}$ is
continuously differentiable and satisfies

$\displaystyle\lim_{x_{i}\to\infty}\mathcal{F}_{i}(q_{i},x_{i})=\infty~{}\text{for
any positive $q_{i}$}$ (2a)
$\displaystyle\frac{\partial\mathcal{F}_{i}}{\partial
x_{i}}(q_{i},x_{i})>0~{}\text{for any positive $q_{i},x_{i}$}$ (2b)
$\displaystyle\frac{\partial\mathcal{F}_{i}}{\partial
q_{i}}(q_{i},x_{i})>0~{}\text{for any positive $q_{i},x_{i}$}.$ (2c)

In other words, the strategies are designed such that (2a) and (2b) imply that
the more agents there are taking on the same task, the faster it can be
completed. Additionally, (2c) suggests that the larger the amount of remaining
jobs, the easier it is for the agents to locate and coordinate to complete
them.

Note that, as we have proved in Lemma 1 in Appendix -A1, under Assumption 1,
the game model (1) is $\delta$-antipassive, as defined in the appendix.

###### Assumption 2

The game model (1) has a unique equilibrium $(q^{\ast},x^{\ast})$ in
$[0,q_{\text{max}})^{n}\times\mathbb{X}$ that satisfies
$x_{i}^{\ast}(q_{j}^{\ast}-q_{i}^{\ast})\leq 0,\,\forall
i,j\in\\{1,\cdots,n\\}$.

As detailed in Section II-B, this implies the uniqueness of the equilibrium of
(1) under the agent decision-making model considered in this work.

###### Example 1

As demonstrated in [6], the game model (1) can be applied to a multi-robot
trash collection application. In this application, there are $n$ spatially
separated patches, with the variable $q_{i}(t)$ representing the volume of
trash in the $i$-th patch. The function $\mathcal{F}_{i}$ is defined as

$\displaystyle\mathcal{F}_{i}(q_{i},x_{i})=R_{i}\frac{e^{\alpha_{i}q_{i}}-1}{e^{\alpha_{i}q_{i}}+1}x_{i}^{\beta_{i}},$
(3)

where $R_{i}$, $\alpha_{i}$, and $\beta_{i}$ are positive parameters.

###### Remark 1

For brevity, we consider the scenario where the number of tasks and strategies
is the same, and the payoff vector is defined as $p(t)=q(t)$. Also, as
specified in (1), every agent can undertake only one task at a time. However,
this scenario can be extended to more general cases where the set of available
strategies exceeds the number of tasks, and some strategies enable an agent to
carry out multiple tasks simultaneously. In such scenarios, the payoff vector
needs to be redefined as a non-trivial function of $q(t)$, e.g., $p(t)=Gq(t)$.
Primary investigations of such extensions have been conducted in [11], and we
consider adopting the analysis from this reference as a future research
direction.

###  II-B Learning Rule, Stochastic Alarm Clock, and Evolutionary Dynamics
Model

Two central components of the agent decision-making model are the learning
rule (also referred to as the revision protocol) and the stochastic alarm
clock. The learning rule describes how each agent changes its strategy
selection when given an opportunity and is typically defined as a function

$\displaystyle\rho_{ji}(p,x)=\mathbb{P}\left(\text{agent switching strategy
from $j$ to $i$}\right).$ (4)

We consider the class of learning rules that depend only on $p$, i.e.,
$\rho_{ji}(p,x)=\rho_{ji}(p)$, and are Lipschitz continuous. That is, there
exists a positive constant $c$ for which the following inequality holds:

$\displaystyle\left|\rho_{ji}(p)-\rho_{ji}(\bar{p})\right|\leq
c\left\|p-\bar{p}\right\|_{2},~{}\forall p,\bar{p}\in\mathbb{R}^{n}.$ (5)

Below is an example of an existing model that belongs to this class.

###### Example 2

Suppose $\rho_{ji}$ is the Smith learning rule, i.e.,
$\rho_{ji}(p)=\varrho[p_{i}-p_{j}]_{+}=\varrho\max(0,p_{i}-p_{j})$ for $i\neq
j$, originally investigated in transportation research [18]. Given that the
range of each $p_{i}$ is bounded, we select a constant $\varrho$ to ensure
that $\sum_{i=1}^{n}\varrho[p_{i}-p_{j}]_{+}\leq 1$ holds for all $j$ in
$\\{1,\cdots,n\\}$. We can derive the following inequality and verify the
Lipschitz continuity of the Smith learning rule:

$\displaystyle\left|\rho_{ji}(p)-\rho_{ji}(\bar{p})\right|\leq\sqrt{2}\varrho\left\|p-\bar{p}\right\|_{2}.$
(6)

While the learning rule defines how each agent revises its strategy, the
stochastic alarm clock determines when the agent can make strategy revision
using the learning rule. Typically, a homogeneous Poisson process $N(t)$ is
utilized to define the clock [9, Chapter 10]. Specifically, at each ring of
the clock, defined as any time $t$ satisfying $N(t)-N(t-\delta)\geq
1,~{}\forall\delta>0$, the agent retains the opportunity to revise its
strategy. As the Poisson processes assigned to the agents are independent, if
they can assess the payoff vector $p$, the agents’ strategy revision can be
conducted in a decentralized manner.

Suppose these Poisson processes are identically distributed, and let $\lambda$
define the rate of the processes. Consider the following ordinary differential
equation:

$\displaystyle\dot{x}_{i}(t)\\!=\\!\textstyle\lambda\\!\sum_{j=1}^{n}\\!x_{j}(t)\rho_{ji}(p(t))\\!-\\!\lambda
x_{i}(t)\\!\sum_{j=1}^{n}\\!\rho_{ij}(p(t)).$ (7)

We refer to (7) as the evolutionary dynamics model (EDM). It has been well-
documented in [9, Chapters 5 and 10] that when the Poisson processes are
independent and identically distributed and there is a sufficiently large
number of agents, the solution of (7) serves as a good predictor of the
population state with arbitrarily high accuracy. Throughout this work, we
assume that (7) is $\delta$-passive, as defined in Appendix -A2. We make the
following assumptions regarding (7), which is widely known as Nash
stationarity [17].

###### Assumption 3

With $p=q$, the following two conditions are equivalent.

  1. 1.

$\sum_{j=1}^{n}x_{j}\rho_{ji}(p)\\!-\\!x_{i}\sum_{j=1}^{n}\rho_{ij}(p)\\!=\\!0,\forall
i\in\\{1,\cdots,n\\}$

  2. 2.

$x_{i}(q_{j}-q_{i})\leq 0,\,\forall i,j\in\\{1,\cdots,n\\}$

Note that when $\rho_{ji}$ is defined as the Smith learning rule, (7)
satisfies Assumption 3. Furthermore, in conjunction with Assumption 2,
Assumption 3 implies that the feedback interconnection of (1) and (7), has a
unique equilibrium.

In addition, according to Assumptions 2 and 3, the equilibrium state
$(q^{\ast},x^{\ast})$ satisfies
$\mathcal{F}_{i}(q_{i}^{\ast},x_{i}^{\ast})=w_{i},~{}\forall
i\in\\{1,\cdots,n\\}$ and $q_{i}^{\ast}=q_{j}^{\ast},~{}\forall
i,j\in\\{1,\cdots,n\\}$. Consequently, we can infer that $(q^{\ast},x^{\ast})$
is the optimal state at which the infinity norm $\|q(t)\|_{\infty}$ of the
game state is minimized over the set $\mathbb{O}$ of stationary points of (1),
defined by
$\mathbb{O}=\\{(q,x)\in[0,q_{\text{max}}]^{n}\times\mathbb{X}\,|\,\mathcal{F}_{i}(q_{i},x_{i})=w_{i},~{}\forall
i\in\\{1,\cdots,n\\}\\}$. In other words, it holds that
$\|q^{\ast}\|_{\infty}=\min_{(q,x)\in\mathbb{O}}\|q\|_{\infty}$.

###  II-C Payoff Vector Estimation

In our problem formulation, instead of directly assessing $q(t)$, each agent
$k$ observes a function $y^{(k)}(t)=h^{(k)}(q(t))$ of the game state $q(t)$
and communicates with its neighbors to estimate $q(t)$. For instance, some
agents may observe the full state $q(t)$, others might only take measurements
of $q_{i}(t)$ associated with their strategy selection $i$, or yet others may
not be able to collect any measurements of $q(t)$ at all. Since not every
agent in the population can directly observe the full state $q(t)$, they adopt
an estimation rule to infer the full state using their own observations
$y^{(k)}(\tau),\tau\in[0,t]$ and information from their neighbors.

Motivated by the large literature on distributed state estimation [19], we
consider that each agent $k$ shares its own estimate $\hat{q}^{(k)}(t)$ of
$q(t)$ whenever it can communicate with its neighbors. Let $\mathbb{N}_{k}(t)$
denote the set of neighbors of agent $k$ at time $t$. Given its observation
$y^{(k)}(t)$ of $q(t)$ and estimates
$\\{\hat{q}^{(l)}(t^{-})\\}_{l\in\mathbb{N}_{k}(t)}$ from its neighbors222We
use the notation $\hat{q}^{(l)}(t^{-})$ to denote the estimate of agent $l$
specifically before the agent updates its estimate at time $t$., the agent
updates its estimate $\hat{q}^{(k)}(t)$ from which the estimate
$\hat{p}^{(k)}(t)$ of the payoff vector $p(t)$ can be derived as
$\hat{p}^{(k)}(t)=\hat{q}^{(k)}(t)$. We represent the estimation rule as

$\displaystyle\hat{q}^{(k)}(t)=g\Big{(}\big{\\{}\hat{q}^{(l)}(t^{-})\big{\\}}_{l\in\mathbb{N}_{k}(t)},y^{(k)}(t)\Big{)}.$
(8)

We provide the following example to illustrate this.

###### Example 3

Given $N$ agents in the population, suppose that only $N_{\text{leader}}(<N)$
leader agents can observe the game state $q(t)$, while the others cannot.
Assuming that the agents are not aware of the game model (1), the estimation
rule (8) can be implemented as

$\displaystyle\hat{q}^{(k)}(t)\\!=\\!\begin{cases}q(t)\\!&\text{if $k$ is a
leader}\\\
\frac{1}{|\mathbb{N}_{k}(t)|}\sum_{l\in\mathbb{N}_{k}(t)}\hat{q}^{(l)}(t^{-})\\!&\text{otherwise}.\end{cases}$
(9)

In other words, agent $k$ sets its estimate $\hat{q}^{(k)}(t)$ to $q(t)$ if it
is a leader and directly measures $q(t)$. Otherwise, the agent updates
$\hat{q}^{(k)}(t)$ to the average of its neighbors’ estimates.

The main results of this paper are applicable to any estimation rule $g$,
provided it satisfies the following two assumptions: 1) Given that the game
state $q(t)$ is bounded, the estimation error $\hat{q}^{(k)}(t)-q(t)$ also
remains bounded for all $t\geq 0$, and 2) as the variation in $q(t)$
diminishes, i.e., $\|\dot{q}(t)\|_{2}\to 0$ as $t\to\infty$, all agents in the
population can asymptotically recover the full state of $q(t)$. We formally
state these assumptions as follows:

###### Assumption 4

The estimation rule (8) satisfies the following conditions for every agent
$k$:

$\displaystyle\sup_{t\geq 0}\epsilon^{(k)}(t)<B_{\epsilon}$ (10a)
$\displaystyle\lim_{t\to\infty}\left\|\dot{q}(t)\right\|_{2}=0\implies\lim_{t\to\infty}\epsilon^{(k)}(t)=0,$
(10b)

where $\epsilon^{(k)}(t)=\|\hat{q}^{(k)}(t)-q(t)\|_{2}$ and $B_{\epsilon}$ is
a fixed positive constant.

Note that when the underlying communication graph is fixed and strongly
connected, (9) satisfies Assumption 4.

##  III Convergence Analysis and Revision Rate Update

We discuss how the estimation error $\epsilon^{(k)}(t)$ influences convergence
of the population state and the game state. In a population of $N$ agents,
suppose each agent $k$ adopts the learning rule $\rho_{ji}(\hat{p}^{(k)}(t))$
using its own payoff vector estimate $\hat{p}^{(k)}(t)$ for strategy revision.
Let $\mathbb{M}_{j}^{N}(t)$ denote the set of agents adopting strategy $j$ at
time $t$. According to the definitions of the learning rule and the Poisson
alarm clock, when the clock of an agent rings, the probability of that agent
currently choosing strategy $j$ and switching to strategy $i$ can be specified
as

$\displaystyle
x_{j}^{N}(t)\sum_{k\in\mathbb{M}_{j}^{N}(t)}\frac{\rho_{ji}(\hat{p}^{(k)}(t))}{|\mathbb{M}_{j}^{N}(t)|},$
(11)

where $x_{j}^{N}(t)$ is the fraction of the $N$-agent population adopting
strategy $j$ at time $t$, $\hat{p}^{(k)}(t)=\hat{q}^{(k)}(t)$ is agent $k$’s
estimate of the payoff vector $p(t)$, and $|\mathbb{M}_{j}^{N}(t)|$ denotes
the cardinality of the set $\mathbb{M}_{j}^{N}(t)$. Note that if
$\mathbb{M}_{j}^{N}(t)$ is empty, implying $x_{j}^{N}(t)=0$, the expression in
(11) is considered zero.

When the size of the population becomes arbitrarily large, that is, as $N$
tends to infinity, we can derive

$\lim_{N\to\infty}x_{j}^{N}(t)\\!\sum_{k\in\mathbb{M}_{j}^{N}(t)}\\!\frac{\rho_{ji}(\hat{p}^{(k)}(t))}{|\mathbb{M}_{j}^{N}(t)|}\\\
=x_{j}(t)\lim_{N\to\infty}\sum_{k\in\mathbb{M}_{j}^{N}(t)}\frac{\rho_{ji}(\hat{p}^{(k)}(t))}{|\mathbb{M}_{j}^{N}(t)|},$
(12)

where $x_{j}(t)$ represents the fraction of agents in the infinite population
adopting strategy $j$. The limit
$\lim_{N\to\infty}\sum_{k\in\mathbb{M}_{j}^{N}(t)}\frac{\rho_{ji}(\hat{p}^{(k)}(t))}{|\mathbb{M}_{j}^{N}(t)|}$
in the right-hand side of (12) represents the average strategy revision
probability of all $j$-strategists. Assuming this limit exists and based on
the definition of $\rho_{ji}$ in (4), we can validate that

  1. 1.

$0\leq\lim_{N\to\infty}\sum_{k\in\mathbb{M}_{j}^{N}(t)}\frac{\rho_{ji}(\hat{p}^{(k)}(t))}{|\mathbb{M}_{j}^{N}(t)|}\leq
1$, and

  2. 2.

$\sum_{i=1}^{n}\lim_{N\to\infty}\sum_{k\in\mathbb{M}_{j}^{N}(t)}\frac{\rho_{ji}(\hat{p}^{(k)}(t))}{|\mathbb{M}_{j}^{N}(t)|}=1$.

Consequently, analogous to the derivation of (7), when agents revise their
strategies based on estimates of the payoff vector and using Poisson alarm
clocks with a rate of $\lambda$, the following EDM can be derived:

$\displaystyle\dot{x}_{i}(t)$
$\displaystyle=\lambda\sum_{j=1}^{n}x_{j}(t)\lim_{N\to\infty}\sum_{k\in\mathbb{M}_{j}^{N}(t)}\frac{\rho_{ji}(\hat{p}^{(k)}(t))}{|\mathbb{M}_{j}^{N}(t)|}$
$\displaystyle\quad-\lambda
x_{i}(t)\sum_{j=1}^{n}\lim_{N\to\infty}\sum_{k\in\mathbb{M}_{i}^{N}(t)}\frac{\rho_{ij}(\hat{p}^{(k)}(t))}{|\mathbb{M}_{i}^{N}(t)|}$
$\displaystyle=\lambda\\!\sum_{j=1}^{n}x_{j}(t)\rho_{ji}(p(t))-\lambda
x_{i}(t)\\!\sum_{j=1}^{n}\rho_{ij}(p(t))+\lambda\xi_{i}(t),$ (13)

where $\xi_{i}(t)$ is defined as

$\displaystyle\xi_{i}(t)$
$\displaystyle=\sum_{j=1}^{n}x_{j}(t)\left(\lim_{N\to\infty}\\!\sum_{k\in\mathbb{M}_{j}^{N}(t)}\\!\frac{\rho_{ji}(\hat{p}^{(k)}(t))}{|\mathbb{M}_{j}^{N}(t)|}-\rho_{ji}(p(t))\right)$
$\displaystyle\quad\\!-\\!x_{i}(t)\\!\sum_{j=1}^{n}\\!\left(\\!\lim_{N\to\infty}\\!\sum_{k\in\mathbb{M}_{i}^{N}(t)}\\!\frac{\rho_{ij}(\hat{p}^{(k)}(t))}{|\mathbb{M}_{i}^{N}(t)|}\\!-\\!\rho_{ij}(p(t))\\!\right).$

According to its definition, $\xi_{i}(t)$ can be interpreted as the difference
between the probability of agents’ strategy revision based on the payoff
vector $p(t)$ and the probability based on the estimates $\hat{p}^{(k)}(t)$.

By the Lipschitz continuity of $\rho_{ji}$, we compute the upper bound of
$\xi_{i}(t)$ as

$\displaystyle|\xi_{i}(t)|$ $\displaystyle\leq
c\sum_{j=1}^{n}x_{j}(t)\lim_{N\to\infty}\sum_{k\in\mathbb{M}_{j}^{N}(t)}\frac{\epsilon^{(k)}(t)}{|\mathbb{M}_{j}^{N}(t)|}.$
(14)

Recall that $\epsilon^{(k)}(t)$ is defined as
$\epsilon^{(k)}(t)=\|\hat{q}^{(k)}(t)-q(t)\|_{2}$. According to Assumption 4,
since $\epsilon^{(k)}(t)$ is bounded, so does $\xi_{i}(t)$. Also, we can infer
that $\xi_{i}(t)$ vanishes as does the estimation error $\epsilon^{(k)}(t)$ at
every agent $k$.

###  III-A Convergence to Equilibrium State

Figure 1: Trajectories of the game state derived by the Smith learning rule in
the task allocation game described in Example 1, where the agents are
estimating the payoff vector using (9).

To visualize the effect of the estimation error on the convergence, we conduct
simulations using the scenario explained in Example 1, the Smith learning
rule, explained in Example 2, and the estimation rule (9). As we use the same
simulation setup as described in Section IV, except $\lambda$ is fixed here,
we refer to that section for details of the simulation setup.

The simulations are executed with two different revision rates, $\lambda=0.01$
and $1.0$, and the results are depicted in Fig. 1. When the revision rate is
high, $\|q(t)\|_{\infty}$ experiences a steep decrease early on; however, in
the long run, its value tends to oscillate and be higher compared to the
scenario with a lower revision rate. Conversely, when the revision rate is
low, the agents have fewer opportunities to revise their strategies, resulting
in a larger overshoot in the early stages. Based on these observations, to
ensure rapid convergence in the initial stages, the rate should be set
sufficiently high; however, to achieve a lower value of $\|q(t)\|_{\infty}$ in
the long term, the rate should be reduced.

Therefore, the optimal design of the strategy revision rate would necessitate
a decrease over time. To provide a rigorous justification for our observation,
we present the following theorem. The proof of the theorem is provided in
Appendix -B.

###### Theorem 1

For a given revision rate $\lambda$, let $q_{\lambda}(t)$ and $x_{\lambda}(t)$
be the game and population states, respectively, determined by the feedback
interconnection of the game model (1) and EDM (III). Under Assumptions 1-4, it
holds that

$\displaystyle\limsup_{t\to\infty}\left(\left\|q_{\lambda}(t)-q^{\ast}\right\|_{2}+\left\|x_{\lambda}(t)-x^{\ast}\right\|_{2}\right)\to
0\text{ as }\lambda\to 0,$

where $(q^{\ast},x^{\ast})$ is the unique equilibrium state of the closed loop
system defined by (1) and (7) with $p(t)=q(t)$.

###  III-B Revision Rate Update

As we stated in Theorem 1 and observed from the simulation results depicted in
Fig. 1, starting with a high initial revision rate $\lambda$, followed by its
proper regulation, ensures the convergence of $(q(t),x(t))$ to the equilibrium
state, while particularly achieving steep convergence at the early stages of
the game. The proof of the theorem utilizes the so-called storage functions
$\mathcal{L}(q(t),x(t))$ and $\mathcal{S}(p(t),x(t))$ of the game model (1)
and EDM (7), respectively, which are defined in Appendix -A, to construct a
Lyapunov candidate function. Notably, by decreasing $\lambda$, we establish
that both the storage functions diminish over time, thereby ensuring the
convergence to the equilibrium state. This process requires knowledge of the
game model (1) and its associated storage function $\mathcal{L}(q(t),x(t))$.
However, if the game model (1) is unknown to the agents, this method of
updating $\lambda$ using the game model becomes infeasible.

Instead, we propose updating $\lambda$ when the frequency of the agents
revising to other strategies decreases, despite receiving revision
opportunities. To implement this, we consider a time-varying revision rate
$\lambda(t)$. Let $\\{t_{m}\\}_{m=1}^{\infty}$ and
$\\{\lambda_{m}\\}_{m=1}^{\infty}$ be sequences of time instants and rates,
respectively, where $\lambda(t)$ of each agent’s Poisson alarm clock is
defined as $\lambda(t)=\lambda_{m}$ for $t\in[t_{m},t_{m+1})$. An agent with
the most accurate estimates of $(q(t),x(t))$, such as the leader agents in
Example 3, updates the revision rate to $\lambda_{m+1}=\gamma\lambda_{m}$ with
$\gamma\in(0,1)$ at time $t_{m+1}$ if the following condition is met:

$\displaystyle\nabla_{x}^{T}\mathcal{S}(p(t_{m+1}),x(t_{m+1}))\mathcal{V}(p(t_{m+1}),x(t_{m+1}))\geq-\epsilon,$
(15)

where $\mathcal{V}=(\mathcal{V}_{1},\cdots,\mathcal{V}_{n})$ with
$\mathcal{V}_{i}(p,x)=\sum_{j=1}^{n}x_{j}\rho_{ji}(p)-x_{i}\sum_{j=1}^{n}\rho_{ij}(p)$
and $\epsilon$ is a small positive constant. Then, it informs the other agents
of this update. According to (-A2), when $\epsilon$ is sufficiently small,
(15) implies that the magnitude of $\mathcal{V}(p(t_{m+1}),x(t_{m+1}))$
becomes small. Consequently, the agents change their strategies less
frequently.

Additionally, we require $t_{m+1}-t_{m}\geq\frac{\tau}{\lambda_{m}}$ to ensure
that every agent receives a strategy revision opportunity with a certain
probability dependent on a constant $\tau$ before the revision rate is
updated. To understand this, by definition, $1-e^{-\tau}$ represents the
probability of a revision opportunity occurring within the time interval
$[t_{m},t_{m}+\frac{\tau}{\lambda_{m}})$. Therefore, the inequality
requirement suggests that with a larger $\tau$, it becomes increasingly likely
that every agent will receive a revision opportunity before the revision rate
updates at $t_{m+1}$.

##  IV Simulations

Figure 2: Population state and game state trajectories when the rate of the
Poisson alarm clock is updated according to the method described in Section
III-B. The trajectories are examined using three different parameter choices:
(a) $\gamma=0.8,\tau=0.2$, (b) $\gamma=0.95,\tau=1.0$, and (c)
$\gamma=0.99,\tau=1.4$.

To illustrate our analysis and also to validate the strategy revision rate
update method, we design and carry out simulations based on Example 1 with
$n=3$. The parameters of (3) are set as $R_{1}=R_{2}=R_{3}=3.44$,
$\alpha_{1}=\alpha_{2}=\alpha_{3}=0.036$, and
$\beta_{1}=\beta_{2}=\beta_{3}=0.91$. The increase rate
$w=(w_{1},w_{2},w_{3})$ is specified as $w=(0.5,1,2)$. It can be verified that
$\mathcal{F}_{i}$ satisfies Assumption 1. Additionally, by setting a
sufficiently large value for $q_{\text{max}}$, we can validate that Assumption
2 holds.

In each simulation, there are $3000$ agents in the population and they can
communicate and share their estimates of the payoff vector via a strongly
connected graph, generated by the Erdős-Rényi model with the edge formation
probability $p=0.1$. Among the entire population, we uniformly randomly select
$10\%$ of the total population as the leaders who can directly observe the
game state $q(t)$, and the rest of the population cannot observe the payoff
vector at all, as in the scenario explained in Example 3. Each agent $k$
computes its own estimate $q^{(k)}(t)$ of $q(t)$ according to the estimation
rule described in (9), and revises its strategy based on the Smith learning
rule $\rho_{ji}(p^{(k)}(t))=\varrho[p_{i}^{(k)}(t)-p_{j}^{(k)}(t)]_{+}$ with
$\varrho=1/400$.333The choice $\varrho=1/400$ is made to ensure that
$\varrho\sum_{i=1}^{n}[p_{i}^{(k)}(t)-p_{j}^{(k)}(t)]_{+}\leq 1$ throughout
the simulations.

The communication and observation of the game state by the agents occur at
discrete time instants, specifically at $t=1,2,3,\cdots$. For its strategy
revision, each agent takes samples of time instants based on its Poisson alarm
clock, and at each sampled time, it revises its strategy using the Smith
learning rule and estimated payoff vector.

We iterate the simulation over a range of parameters for the strategy revision
update method, fixing the initial conditions to $x(0)=(1/3,1/3,1/3)$ and
$q(0)=(100,200,300)$, and setting the initial estimates of $q(0)$ by all
agents to $\hat{q}^{(k)}(0)=(0,0,0)$. Fig. 2 illustrates the simulation
results for three cases: (a) $\gamma=0.8,\tau=0.2$, (b)
$\gamma=0.95,\tau=1.0$, and (c) $\gamma=0.99,\tau=1.4$, with the initial
revision rate $\lambda(t_{0})$ set to $1$ in all three cases. We fix
$\epsilon=0.01$ as the left-hand side term in (15) approaches zero over time
in the simulation. In all cases, the revision rates decrease over time, and we
can observe the convergence of the population and game states to the
equilibrium state, as we have discussed in Theorem 1. When the parameters
$\gamma$ and $\tau$ are small, the revision rate decreases fast, resulting in
the substantial overshoot in the game state trajectory, as observed in Fig. 2.
As those parameters increase, the game state tends to have a steeper decrease
in the early stage, as observed in Fig. 2. However, if these parameters are
too large, the reduction of the revision rate becomes slow and convergence to
the equilibrium takes longer, as illustrated in Fig. 2.

##  V Conclusion

We investigated a population game problem in which decision-making agents need
to estimate the payoff vector for their strategy selections. By adopting task
allocation games, we examined the effect of errors in the payoff vector
estimation on the convergence to the equilibrium state. Our analysis showed
how the adaptive rate of the agents’ strategy revisions mitigates the impact
of these errors on the convergence. Leveraging the analytical results, we
proposed a design for time-varying strategy revision rates to ensure
convergence. As a future direction of research, we plan to explore
optimization of the time-varying revision rate design. Also, analyzing how the
topology of the communication graph affects the convergence and investigating
the optimal communication topology design are topics of our interest.

###  -A Passivity of Game Model and EDM

The notions of $\delta$-antipassivity and $\delta$-passivity are adopted from
[17].

####  -A1 $\delta$-Antipassivity of Game Model (1)

We call (1) $\delta$-antipassive if there is a continuously differentiable
non-negative function
$\mathcal{L}:(0,q_{\text{max}})^{n}\times\mathbb{X}\to\mathbb{R}_{+}$
satisfying

$\displaystyle\nabla_{x}\mathcal{L}(q,x)=\mathcal{F}(q,x)-w$ (16a)
$\displaystyle\nabla_{q}^{T}\mathcal{L}(q,x)\left(-\mathcal{F}(q,x)+w\right)\leq
0,$ (16b)

and

$\displaystyle\mathcal{L}(q,x)=0$ $\displaystyle\iff\mathcal{F}(q,x)=w$
$\displaystyle\iff\nabla_{q}^{T}\mathcal{L}(q,x)\left(-\mathcal{F}(q,x)+w\right)=0,$
(17)

where $\mathcal{F}=(\mathcal{F}_{1},\cdots,\mathcal{F}_{n})$ and
$w=(w_{1},\cdots,w_{n})$ are defined in (1). We refer to $\mathcal{L}$ as the
$\delta$-antistorage function.

Adopting the analysis presented in [11], we let

$\displaystyle\mathcal{L}(q,x)=\sum_{i=1}^{n}\int_{x_{i}^{\ast}(q_{i})}^{x_{i}}(\mathcal{F}_{i}(q_{i},s)-w_{i})\,\mathrm{d}s,$
(18)

where $x_{i}^{\ast}:(0,q_{\text{max}})\to\mathbb{R}_{+}$ is a function that
maps the game state $q_{i}$ to an element in $\mathbb{R}_{+}$ satisfying
$\mathcal{F}_{i}(q_{i},x_{i}^{\ast}(q_{i}))=w_{i}$. Note that by Assumption 1,
for a given positive $q_{i}$, there is a unique $x_{i}^{\ast}(q_{i})$, and by
the implicit function theorem, the function $x_{i}^{\ast}$ is continuously
differentiable.

###### Lemma 1

The function $\mathcal{L}$ in (18) satisfies (16) and (-A1).

###### Proof:

Note that $\mathcal{L}$ can be re-written as

$\displaystyle\mathcal{L}(q,x)$
$\displaystyle=\sum_{i=1}^{n}(f_{i}(q_{i},x_{i})-w_{i}x_{i}),$ (19)

where
$f_{i}(q_{i},x_{i})=\int_{x_{i}^{\ast}(q_{i})}^{x_{i}}\mathcal{F}_{i}(q_{i},s)\,\mathrm{d}s+w_{i}x_{i}^{\ast}(q_{i})$,
from which we can infer that $\frac{\partial\mathcal{L}(q,x)}{\partial
x_{i}}=\mathcal{F}_{i}(q_{i},x_{i})-w_{i}$. Since $s\geq x_{i}^{\ast}(q_{i})$
if and only if $\mathcal{F}_{i}(q_{i},s)\geq w_{i}$, and
$\mathcal{F}_{i}(q_{i},s)$ is increasing in $s$, we can establish
$\mathcal{L}(q,x)\geq 0$ where the equality holds if and only if
$\mathcal{F}_{i}(q_{i},x_{i})=w_{i}$ for all $i$ in $\\{1,\cdots,n\\}$.

Notice that

$\displaystyle\frac{\partial\mathcal{L}(q,x)}{\partial q_{i}}=\frac{\partial
f_{i}(q_{i},x_{i})}{\partial
q_{i}}=\int_{x_{i}^{\ast}(q_{i})}^{x_{i}}\frac{\partial\mathcal{F}_{i}(q_{i},s)}{\partial
q_{i}}\,\mathrm{d}s,$ (20)

and since $\mathcal{F}_{i}(q_{i},x_{i})$ is an increasing function of $q_{i}$,
we can derive

$\displaystyle\nabla_{q}^{T}\mathcal{L}(q,x)\left(-\mathcal{F}(q,x)+w\right)$
$\displaystyle=\sum_{i=1}^{n}\frac{\partial\mathcal{L}(q,x)}{\partial
q_{i}}\left(-\mathcal{F}_{i}(q_{i},x_{i})+w_{i}\right)$
$\displaystyle=\sum_{i=1}^{n}\int_{x_{i}^{\ast}(q_{i})}^{x_{i}}\frac{\partial\mathcal{F}_{i}(q_{i},s)}{\partial
q_{i}}\,\mathrm{d}s\,\left(-\mathcal{F}_{i}(q_{i},x_{i})+w_{i}\right).$ (21)

Since $\mathcal{F}_{i}(q_{i},x_{i})$ is increasing in $x_{i}$ and
$\mathcal{F}_{i}(q_{i},x_{i}^{\ast}(q_{i}))=w_{i}$, it holds that
$\nabla_{q}^{T}\mathcal{L}(q,x)\left(-\mathcal{F}(q,x)+w\right)\leq 0$ where
the equality holds if and only if $\mathcal{F}_{i}(q_{i},x_{i})=w_{i}$ for all
$i$ in $\\{1,\cdots,n\\}$. This completes the proof. ∎

####  -A2 $\delta$-Passivity of EDM (7)

Let us define
$\mathcal{V}_{i}(p,x)=\sum_{j=1}^{n}x_{j}\rho_{ji}(p)-x_{i}\sum_{j=1}^{n}\rho_{ij}(p)$.
We refer to EDM (7) $\delta$-passive if there is a continuously differentiable
non-negative function
$\mathcal{S}:\mathbb{R}^{n}\times\mathbb{X}\to\mathbb{R}_{+}$ satisfying

$\displaystyle\nabla_{p}\mathcal{S}(p,x)=\mathcal{V}(p,x)$ (22a)
$\displaystyle\nabla_{x}^{T}\mathcal{S}(p,x)\mathcal{V}(p,x)\leq 0,$ (22b)

and

$\displaystyle\mathcal{S}(p,x)=0$ $\displaystyle\iff\mathcal{V}(p,x)=0$
$\displaystyle\iff\nabla_{x}^{T}\mathcal{S}(p,x)\mathcal{V}(p,x)=0,$ (23)

where $\mathcal{V}=(\mathcal{V}_{1},\cdots,\mathcal{V}_{n})$. We refer to
$\mathcal{S}$ as the $\delta$-storage function. The EDM defined using the
Smith learning rule is $\delta$-passive and has the $\delta$-storage function
given by
$\mathcal{S}(p,x)=\frac{\varrho}{2}\sum_{i,j=1}^{n}x_{j}[p_{i}-p_{j}]_{+}^{2}$.

###  -B Proof of Theorem 1

Recall that the agents are revising their strategy selections using their own
payoff vector estimates. The state equation for the closed-loop system
consisting of (1) and (III) is given as

$\displaystyle\dot{q}_{i}(t)$
$\displaystyle=-\mathcal{F}_{i}(q_{i}(t),x_{i}(t))+w_{i}$ (24a)
$\displaystyle\dot{x}_{i}(t)$
$\displaystyle=\lambda\mathcal{V}_{i}(p(t),x(t))+\lambda\xi_{i}(t),$ (24b)

where
$\mathcal{V}_{i}(p,x)=\sum_{j=1}^{n}x_{j}\rho_{ji}(p)-x_{i}\sum_{j=1}^{n}\rho_{ij}(p)$
and $p(t)=q(t)$. Since (7) is assumed to be $\delta$-passive, when
$\xi_{i}(t)=0,~{}\forall i\in\\{1,\cdots,n\\}$, (24b) is $\delta$-passive and
has the $\delta$-storage function $\mathcal{S}(p,x)$ as explained in Appendix
-A2. Also, according to Lemma 1, (24a) is $\delta$-antipassive with the
$\delta$-antistorage function $\mathcal{L}(q,x)$ as in (19).

We provide a two-part proof: in the first part, we show that
$\mathcal{L}(q(t),x(t))$ becomes arbitrarily small as we select small
$\lambda$, and in the second part, we argue that $\mathcal{S}(p(t),x(t))$ also
becomes arbitrarily small. Then, based on (-A1) and (-A2), we conclude that
$(q(t),x(t))$ converges to the equilibrium $(q^{\ast},x^{\ast})$ as $\lambda$
becomes arbitrarily small.

We first evaluate the time-derivative of
$\lambda\mathcal{S}(p(t),x(t))+\mathcal{L}(q(t),x(t))$.

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}t}\left(\lambda\mathcal{S}(p(t),x(t))+\mathcal{L}(q(t),x(t))\right)$
$\displaystyle=\underbrace{\lambda\nabla_{p}^{T}\mathcal{S}(p(t),x(t))}_{=\dot{x}^{T}(t)-\lambda\xi^{T}(t)}\dot{p}(t)$
$\displaystyle\qquad+\lambda\nabla_{x}^{T}\mathcal{S}(p(t),x(t))\underbrace{\dot{x}(t)}_{=\lambda\mathcal{V}(p(t),x(t))+\lambda\xi(t)}$
$\displaystyle\qquad+\nabla_{q}^{T}\mathcal{L}(q(t),x(t))\dot{q}(t)+\underbrace{\nabla_{x}^{T}\mathcal{L}(q(t),x(t))}_{=-\dot{q}^{T}(t)}\dot{x}(t),$
$\displaystyle=\lambda\xi^{T}(t)\left(\lambda\nabla_{x}\mathcal{S}(p(t),x(t))-\dot{p}(t)\right)$
$\displaystyle\quad+\underbrace{\lambda^{2}\nabla_{x}^{T}\mathcal{S}(p(t),x(t))\mathcal{V}(p(t),x(t))}_{\leq
0}\\!+\\!\underbrace{\nabla_{q}^{T}\mathcal{L}(q(t),x(t))\dot{q}(t)}_{\leq
0},$ (25)

where $\mathcal{V}=(\mathcal{V}_{1},\cdots,\mathcal{V}_{n})$ and
$\xi=(\xi_{1},\cdots,\xi_{n})$. First, we note that since $q(t)$ and $x(t)$
are bounded, by the continuous differentiability of $\mathcal{S}$, we have
that $\nabla_{x}\mathcal{S}(p(t),x(t))$ is bounded. Also, recall that $\xi(t)$
and $\dot{p}(t)$ are bounded. Hence, for any $\delta>0$, we can select
sufficiently small $\lambda$ for which
$\lambda\xi^{T}(t)\left(\lambda\nabla_{x}\mathcal{S}(p(t),x(t))-\dot{p}(t)\right)<\delta$
holds. Consequently, for sufficiently small $\lambda$, we can establish

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}t}\left(\lambda\mathcal{S}(p(t),x(t))+\mathcal{L}(q(t),x(t))\right)$
$\displaystyle<\\!\delta\\!+\\!\lambda^{2}\nabla_{x}^{T}\mathcal{S}(p(t),\\!x(t))\mathcal{V}(p(t),\\!x(t))\\!+\\!\nabla_{q}^{T}\mathcal{L}(q(t),\\!x(t))\dot{q}(t).$

From the above inequality, we can observe that the function
$\lambda\mathcal{S}(p(t),x(t))+\mathcal{L}(q(t),x(t))$ decreases if
$\lambda^{2}\nabla_{x}^{T}\mathcal{S}(p(t),x(t))\mathcal{V}(p(t),x(t))+\nabla_{q}^{T}\mathcal{L}(q(t),x(t))\dot{q}(t)<-2\delta$
holds. Since $\lambda\mathcal{S}(p(t),x(t))+\mathcal{L}(q(t),x(t))$ is a non-
negative function, for some $t>0$, it should hold that

$\lambda^{2}\nabla_{x}^{T}\mathcal{S}(p(t),x(t))\mathcal{V}(p(t),x(t))\\\
+\nabla_{q}^{T}\mathcal{L}(q(t),x(t))\dot{q}(t)\geq-2\delta.$ (26)

Otherwise, $\lambda\mathcal{S}(p(t),x(t))+\mathcal{L}(q(t),x(t))$ eventually
becomes negative. Let $\mathbb{U}_{\delta}$ be a set defined as

$\mathbb{U}_{\delta}=\\{(q,x)\in[0,q_{\text{max}}]^{n}\times\mathbb{X}\,|\,\\\
\nabla_{q}^{T}\mathcal{L}(q,x)(-\mathcal{F}(q,x)+w)\geq-2\delta\\}.$

Also, define a positive constant $\alpha$ using $\mathbb{U}_{\delta}$ as

$\displaystyle\alpha=\sup_{(q,x)\in\mathbb{U}_{\delta}}\left(\lambda\mathcal{S}(p,x)+\mathcal{L}(q,x)\right).$

Notice that, by construction, the set
$\\{(q,x)\in[0,q_{\text{max}}]^{n}\times\mathbb{X}\,|\,\lambda\mathcal{S}(p,x)+\mathcal{L}(q,x)\leq\alpha\\}$
is invariant, and according to (26), the trajectory $(q(t),x(t))$ always
enters the set. Hence, we conclude that for some large $T_{\lambda}>0$, it
holds that $\mathcal{L}(q(t),x(t))\leq\alpha,~{}\forall t\geq T_{\lambda}$.

Since $\alpha$ decreases as does $\lambda$, we can construct a class
$\mathcal{K}$ function444See [20, Chapter 4.4] for its definition.
$\kappa_{1}$ of $\lambda$ for which it holds that

$\displaystyle\mathcal{L}(q(t),x(t))<\kappa_{1}(\lambda),~{}\forall t\geq
T_{\lambda}.$ (27)

Hence, by (-A1) and Assumption 4, we can select small $\lambda$ to make
$\limsup_{t\to\infty}\|\dot{q}(t)\|_{2}$ and
$\limsup_{t\to\infty}\|\xi(t)\|_{2}$ arbitrarily small.

Now suppose, for given $\epsilon>0$, we select $\lambda$ such that
$\|\dot{q}(t)\|_{2}<\epsilon,~{}\forall t\geq T_{\lambda}$ holds. Then, for
each $i$ in $\\{1,\cdots,n\\}$, it holds that

$\displaystyle\left|\mathcal{F}_{i}(q_{i}(t),x_{i}(t))-w_{i}\right|<\epsilon.$
(28)

if $q_{i}(t)<q_{\text{max}}$. Otherwise $q_{i}(t)=q_{\text{max}}$.

By the implicit function theorem and Assumption 1, there exists a continuously
differentiable function $\bar{q}_{i}=g_{i}(x_{i})$ for which
$\mathcal{F}_{i}(\bar{q}_{i},x_{i})=w_{i}$ holds if such
$\bar{q}_{i}\in[0,q_{\text{max}}]$ exists for a given $x_{i}\in[0,1]$. We then
extend the domain of the function $g_{i}$ to the entire $[0,1]$ by setting
$q_{\text{max}}=g_{i}(x_{i})$ if
$\mathcal{F}_{i}(q_{\text{max}},x_{i})<w_{i}$.555Note that the extended
$g_{i}$ is continuously differentiable except at $x_{i}$ for which
$\mathcal{F}_{i}(q_{\text{max}},x_{i})=w_{i}$ holds. Note that $g_{i}$ is a
non-increasing function of $x_{i}$, i.e., $\frac{\partial g_{i}}{\partial
x_{i}}\leq 0$. Consequently, by Assumption 1, if $\epsilon$ is sufficiently
small, $q_{i}(t)$ lies in a small neighborhood of $g_{i}(x_{i}(t))$.

Let us define

$\displaystyle\mathcal{G}(x)=\begin{pmatrix}g_{1}(x_{1})&g_{2}(x_{2})&\cdots&g_{n}(x_{n})\end{pmatrix}^{T},$
(29)

and let $\zeta(t)=q(t)-\mathcal{G}(x(t))$. Eq. (24b) can be re-written as

$\displaystyle\dot{x}_{i}(t)$
$\displaystyle=\lambda\mathcal{V}_{i}(\mathcal{G}(x(t))+\zeta(t),x(t))+\lambda\xi_{i}(t)$
$\displaystyle=\lambda\mathcal{V}_{i}(\mathcal{G}(x(t)),x(t))+\lambda\bar{\xi}_{i}(t),$
(30)

where $\bar{\xi}_{i}(t)$ is defined as

$\displaystyle\bar{\xi}_{i}(t)$
$\displaystyle=\xi_{i}(t)\\!+\\!\sum_{j=1}^{n}x_{j}(t)\big{(}\rho_{ji}(\mathcal{G}(x(t))\\!+\\!\zeta(t))\\!-\\!\rho_{ji}(\mathcal{G}(x(t)))\big{)}$
$\displaystyle\quad-
x_{i}(t)\sum_{j=1}^{n}\big{(}\rho_{ij}(\mathcal{G}(x(t))+\zeta(t))-\rho_{ij}(\mathcal{G}(x(t)))\big{)}.$

By the Lipschitz continuity of $\rho_{ji}$, it holds that

$\displaystyle\Bigg{|}\sum_{j=1}^{n}x_{j}(t)\big{(}\rho_{ji}(\mathcal{G}(x(t))+\zeta(t))-\rho_{ji}(\mathcal{G}(x(t)))\big{)}$
$\displaystyle\quad-
x_{i}(t)\sum_{j=1}^{n}\big{(}\rho_{ij}(\mathcal{G}(x(t))+\zeta(t))-\rho_{ij}(\mathcal{G}(x(t)))\big{)}\Bigg{|}$
$\displaystyle\leq c\left\|\zeta(t)\right\|_{2}.$

Therefore, if $\lambda$ is sufficiently small, both $\|\xi(t)\|_{2}$ and
$\|\zeta(t)\|_{2}$ eventually become arbitrarily small, as does
$|\bar{\xi}_{i}(t)|$.

Now, we evaluate the time derivative of $\mathcal{S}(\mathcal{G}(x(t)),x(t))$
as follows.

$\displaystyle\frac{\mathrm{d}}{\mathrm{d}t}\mathcal{S}(\mathcal{G}(x(t)),x(t))$
$\displaystyle=\\!\nabla_{p}^{T}\\!\mathcal{S}(\mathcal{G}(x(t)),\\!x(t))\nabla\mathcal{G}(x(t))\dot{x}(t)\\!+\\!\nabla_{x}^{T}\\!\mathcal{S}(\mathcal{G}(x(t)),\\!x(t))\dot{x}(t)$
$\displaystyle\leq\\!\lambda\left(\mathcal{V}^{T}(\mathcal{G}(x(t)),x(t))\nabla\mathcal{G}(x(t))\\!+\\!\nabla_{x}^{T}\mathcal{S}(\mathcal{G}(x(t)),x(t))\right)\bar{\xi}(t)$
$\displaystyle\qquad+\lambda\nabla_{x}^{T}\mathcal{S}(\mathcal{G}(x(t)),x(t))\mathcal{V}(\mathcal{G}(x(t)),x(t)),$
(31)

where we used (22) and the fact that $\nabla\mathcal{G}(x)$ is a negative
semi-definite matrix for every $x\in\mathbb{X}$. Since
$\bar{\xi}(t)=(\bar{\xi}_{1}(t),\cdots\bar{\xi}_{n}(t))$ eventually vanishes
as $\lambda$ decreases, using the same arguments as in the first part of the
proof, we can conclude that there is a $\mathcal{K}$ class function
$\kappa_{2}$ of $\lambda$ for which

$\displaystyle\mathcal{S}(\mathcal{G}(x(t)),x(t))<\kappa_{2}(\lambda),~{}\forall
t\geq T_{\lambda}^{\prime}$ (32)

holds for some $T_{\lambda}^{\prime}>0$. Therefore, we conclude that by
decreasing $\lambda$, we can guarantee the convergence of $(q(t),x(t))$ to
$(q^{\ast},x^{\ast})$. This completes the proof.

## References

  * [1] N. Mehr and R. Horowitz, “How will the presence of autonomous vehicles affect the equilibrium state of traffic networks?” _IEEE Transactions on Control of Network Systems_ , vol. 7, no. 1, pp. 96–105, 2020.
  * [2] S. H. Li, Y. Yu, N. I. Miguel, D. Calderone, L. J. Ratliff, and B. Açıkmeşe, “Adaptive constraint satisfaction for markov decision process congestion games: Application to transportation networks,” _Automatica_ , vol. 151, p. 110879, 2023.
  * [3] W. Saad, Z. Han, T. Basar, M. Debbah, and A. Hjorungnes, “Hedonic coalition formation for distributed task allocation among wireless agents,” _IEEE Transactions on Mobile Computing_ , vol. 10, no. 9, pp. 1327–1344, 2011.
  * [4] H. Tembine, E. Altman, R. ElAzouzi, and W. H. Sandholm, “Evolutionary game dynamics with migration for hybrid power control in wireless communications,” in _47th IEEE Conference on Decision and Control (CDC)_ , 2008, pp. 4479–4484.
  * [5] N. Quijano, C. Ocampo-Martinez, J. Barreiro-Gomez, G. Obando, A. Pantoja, and E. Mojica-Nava, “The role of population games and evolutionary dynamics in distributed control systems: The advantages of evolutionary game theory,” _IEEE Control Systems Magazine_ , vol. 37, no. 1, pp. 70–97, 2017.
  * [6] S. Park, Y. D. Zhong, and N. E. Leonard, “Multi-robot task allocation games in dynamically changing environments,” in _2021 IEEE International Conference on Robotics and Automation (ICRA)_ , 2021, pp. 8678–8684.
  * [7] I. Jang, H.-S. Shin, and A. Tsourdos, “Anonymous hedonic game for task allocation in a large-scale multiple agent system,” _IEEE Transactions on Robotics_ , vol. 34, no. 6, pp. 1534–1548, 2018.
  * [8] S. Amaya and A. Mateus, “Tasks allocation for rescue robotics: A replicator dynamics approach,” in _Artificial Intelligence and Soft Computing_ , L. Rutkowski, R. Scherer, M. Korytkowski, W. Pedrycz, R. Tadeusiewicz, and J. M. Zurada, Eds. Cham: Springer International Publishing, 2019, pp. 609–621.
  * [9] W. H. Sandholm, _Population Games and Evolutionary Dynamics_. MIT Press, 2011.
  * [10] A. Mahajan, N. C. Martins, M. C. Rotkowitz, and S. Yüksel, “Information structures in optimal decentralized control,” in _2012 IEEE 51st IEEE Conference on Decision and Control (CDC)_ , 2012, pp. 1291–1306.
  * [11] S. Park and J. Barreiro-Gomez, “Payoff mechanism design for coordination in multi-agent task allocation games,” in _2023 62nd IEEE Conference on Decision and Control (CDC)_ , 2023, pp. 8116–8121.
  * [12] G. Szabó and G. Fáth, “Evolutionary games on graphs,” _Physics Reports_ , vol. 446, no. 4, pp. 97–216, 2007.
  * [13] J. Barreiro-Gomez, G. Obando, and N. Quijano, “Distributed population dynamics: Optimization and control applications,” _IEEE Transactions on Systems, Man, and Cybernetics: Systems_ , vol. 47, no. 2, pp. 304–314, 2017.
  * [14] J. C. Harsanyi, “Games with incomplete information played by ”bayesian” players, i-iii. part ii. bayesian equilibrium points,” _Management Science_ , vol. 14, no. 5, pp. 320–334, 1968.
  * [15] D. Foster and P. Young, “Stochastic evolutionary game dynamics$\ast$,” _Theoretical Population Biology_ , vol. 38, no. 2, pp. 219–232, 1990.
  * [16] M. J. Fox and J. S. Shamma, “Population games, stable games, and passivity,” _Games_ , vol. 4, pp. 561–583, Oct. 2013.
  * [17] S. Park, N. C. Martins, and J. S. Shamma, “From population games to payoff dynamics models: A passivity-based approach,” in _2019 IEEE 58th Conference on Decision and Control (CDC)_ , 2019, pp. 6584–6601.
  * [18] M. J. Smith, “The stability of a dynamic model of traffic assignment—an application of a method of Lyapunov,” _Transportation Science_ , vol. 18, no. 3, pp. 245–252, 1984.
  * [19] F. F. Rego, A. M. Pascoal, A. P. Aguiar, and C. N. Jones, “Distributed state estimation for discrete-time linear time invariant systems: A survey,” _Annual Reviews in Control_ , vol. 48, pp. 36–56, 2019.
  * [20] H. K. Khalil, _Nonlinear Systems; 3rd ed._ Upper Saddle River, NJ: Prentice-Hall, 2002.