∎

11institutetext: Tamer Başar 22institutetext: Coordinated Science Laboratory
and the Department of Electrical and Computer Engineering, University of
Illinois at Urbana-Champaign, 1308 West Main Street, Urbana, IL, 61801, USA.
Tel.: +1 217-333-3607
Fax: +1 217-265-0997
22email<EMAIL_ADDRESS>33institutetext: Quanyan Zhu 44institutetext:
Coordinated Science Laboratory and the Department of Electrical and Computer
Engineering, University of Illinois at Urbana-Champaign, 1308 West Main
Street, Urbana, IL, 61801, USA.
44email<EMAIL_ADDRESS>
# Prices of Anarchy, Information, and Cooperation in Differential
Games††thanks: Research supported in part by grants from AFOSR and DOE.

Tamer Başar  Quanyan Zhu

(Received: date / Accepted: date)

###### Abstract

The price of anarchy (PoA) has been widely used in static games to quantify
the loss of efficiency due to noncooperation. Here, we extend this concept to
a general differential games framework. In addition, we introduce the price of
information (PoI) to characterize comparative game performances under
different information structures, as well as the price of cooperation to
capture the extent of benefit or loss a player accrues as a result of
altruistic behavior. We further characterize PoA and PoI for a class of scalar
linear quadratic differential games under open-loop and closed-loop feedback
information structures. We also obtain some explicit bounds on these indices
in a large population regime.

###### Keywords:

Differential games Nash equilibria efficiency price of anarchy price of
information price of cooperation linear-quadratic games information structures

##  1 Introduction

It is well known that the non-cooperative Nash equilibrium in nonzero-sum
games is generally inefficient DUB86 , which means that it would be possible
for all players to do better in terms of attaining higher utilities or lower
costs (than they would attain under Nash equilibria, even if the equilibrium
is unique) through a cooperative behavior. This is true for static
deterministic games, and naturally also for stochastic games as well as
dynamic and differential games. In these latter of classes of games, one could
bring up additional issues with regard to Nash equilibria beyond efficiency or
lack thereof, such as whether an increase in information to one player (or all
or a subset of the players) would be advantageous to that player (or groups of
players), in terms of attaining higher utilities or lower costs, or whether
acquiring more information would be undesirable for a player. In the special
class of games where all players have the same utility function or cost
function (that is, team problems) and what is sought is the global maximum or
global minimum of these functions, the answer to such a query is clean, which
is that additional information (defined as expansion of sigma fields) can
never hurt. The same is true for the special class of zero-sum games. In
stochastic games, or dynamic and differential games which are not team
problems or zero-sum games, however, the answer is not that clean, and one
could encounter quite surprising and at the outset counter-intuitive results.
Perhaps the first demonstration of this was reported in Basar72  and BasHo74 ,
where two classes of two-player stochastic static games were considered, one a
linear-quadratic-Gaussian (LQG) model and the other one a stochastic Cournot
duopoly model, both of which admit unique Nash equilibria. It was shown that
for the LQG model better information (on some stochastic variables) for only
one player leads to lower average Nash equilibrium costs for both players, but
in the duopoly model only the player whose information is improved benefits
while the other one hurts (in the sense that his average Nash equilibrium cost
increases). Another way of comparison would be in terms of the relative values
of the average Nash equilibrium costs attained by the players, when one player
has informational advantage over the other. It was again shown in Basar72
that, in an otherwise completely symmetric game, the player who has better
information attains higher cost than the other player in the LQG model (the
counter-intuitive result), whereas he attains lower cost in the duopoly model
(the intuitive result). Several manifestations of these conclusions can be
seen also in dynamic and differential games; for example time-consistent open-
loop Nash equilibrium is not necessarily inferior to the strongly time-
consistent closed-loop feedback Nash equilibrium BasOls99 .

Now coming back to inefficiency of Nash equilibrium in a fixed nonzero-sum
game, one question of interest is exploration of the extent of this
inefficiency, that is how far off is a Nash equilibrium from the socially
optimal solution, which is obtained as the maximum of the sum of the utilities
of the players, or some convex combination of the utilities (or minimum in the
case of cost functions). The notion of the price of anarchy (PoA)was
introduced in ROU04  as a quantification of this offset, as a utility ratio
between the worst possible Nash solution (among multiple Nash equilibria) and
the social optimum. In a way, this index serves to quantify the loss of
efficiency due to competition. It has been shown that in routing games and
resource allocation games (see, ROU04  and JMT05 ), PoA is bounded by a
constant, allowing agents to achieve some level of efficiency despite being
suboptimal.

The idea of quantifying the gap between social optimality and game equilibrium
solutions sparked many follow-up work in that same vein. In SS08 , price of
simplicity has been introduced for a pricing game in communication networks as
the ratio between the revenue collected from a flat pricing rule and the
maximum possible revenue. In GJC09 , price of uncertainty has been introduced
to measure the relative payoff of an expert user of a security game under
complete information to the one under incomplete information. In ZHU08b ,
price of leadership has been proposed as a measure of comparison of utilities
in a power control game between Nash equilibria and Stackelberg solutions. In
all of these works, primarily communication networks have been used as a
backdrop application domain, be it routing, resource allocation, power
control, or security. Game-theoretical methods along with Nash equilibrium
have found many applications in communication networks, with some selected
recent references being AB98 ; Basar07 ; MahBas03 ; SAAB02 ; ZHU08e ; JOH03 ;
JMT05 ; ABEJW06

In this paper, we discuss several indices which quantify variations or offsets
in the payoff values or costs attained under Nash equilibria in the context of
differential games (DGs). We first extend the notion of PoA to DGs, which
heretofore has been primarily limited to static continuous kernel games. We
provide a characterization of PoA for a class of scalar linear-quadratic (LQ)
DGs, and quantify the efficiency loss in the long run when the players behave
non-cooperatively under the Nash equilibrium concept. We consider both open-
loop (OL) and closed-loop (CL) information structures (ISs). We show that for
the class of scalar LQ DGs with CL IS using the strongly time-consistent CL
feedback Nash equilibrium, the PoA has some appealing computable upper bounds,
which can further be approximated when the number of players is sufficiently
large (that is, the large population regime), whereas, under the OL IS, it is
possible to obtain an expression for the PoA in closed form.

As mentioned earlier, going from static to dynamic (differential) games brings
in the possibility of various ISs, which add richness to the (Nash
equilibrium) solution of a game. Different ISs (generally) yield different
equilibrium solutions, and hence IS is a crucial factor in the investigation
of PoA in DGs. Motivated by this, we introduce another index, the price of
information (PoI), which is a result of the comparison of the equilibrium
utilities or costs under different ISs. For the class of scalar LQ DGs above,
we show that the PoI between the feedback and open-loop ISs is shown to be
bounded from below by ${\sqrt{2}}/{2}$ and from above by $\sqrt{2}$, again in
the large population regime. Finally, motivated by some recent results
reported in AAE10  on the level of cooperation between players in a routing
game, captured by the degree of willingness of a player to place partial
weight on other players’ utilities in his utility function, we introduce the
price of cooperation (PoC) as a measure of benefit or loss to a player on his
base Nash equilibrium payoff due to cooperation.

The structure of the paper is as follows. In Section 2, we introduce a general
$N$-player DG framework with different ISs, and define in this context the
indices, PoA, PoI, and PoC. In Section 3, we investigate the PoA for a class
of scalar LQ feedback DGs. In Section 4, we study the LQ DGs under open-loop
IS, and in Section 5, we establish bounds on the PoI. We conclude and identify
future directions in Section 6. An earlier version of some of the results in
this paper can be found in the recent conference paper ZhuBas10 .

##  2 General Problem Formulation

In this section we first introduce the general nonzero-sum differential games
framework along with the Nash equilibrium solution, and then introduce the
three indices: prices of anarchy, information, and cooperation.

Let $\mathcal{N}=\\{1,2,\cdots,N\\}$ be the set of players, and
$[0,T\rangle$111The notation “$\rangle$” is introduced to capture two cases:
finite horizon when $T$ is finite (in which case we have $[0,T]$), and
infinite horizon when $T$ is infinite (in which case we have $[0,\infty)$). be
the time interval of interest. At each time instant $t\in[0,T\rangle$, each
player, say Player $i$, chooses an $m_{i}$-dimensional control value (action)
$u_{i}(t)$ from his set of feasible control values
$U_{i}\subset\mathbb{R}^{m_{i}}$, where we also make the standard assumption
that as a function of $t$ the control function $u_{i}(\cdot)$ is piecewise
continuous on $[0,T\rangle$. The state variable $x$ is of dimension $n$, and
takes values in $\mathbb{R}^{n}$; as a function of time, $t$, we assume
$x(\cdot)$ to be piecewise continuously differentiable on $[0,T\rangle$, and
evolving according to the differential equation:

$\dot{x}(t)=f(x(t),u_{1}(t),\cdots,u_{N}(t),t)\,,\;\;x(0)=x_{0}\,,$

where $x_{0}\in\mathbb{R}$ is the initial value of the state and the system
dynamics $f(\cdot):\Omega\rightarrow\mathbb{R}^{n}$ is defined on the set

$\Omega=\\{(x,u_{1},\cdots,u_{N},t)|x\in\mathbb{R}^{n},t\in[0,T\rangle,u_{i}\in
U_{i},i\in\mathcal{N}\\}\,,$

as a jointly piecewise continuous function which is also Lipschitz in $x$, and
also possibly Lipschitz in the $u_{i}$’s, depending on whether the underlying
information structure (IS) is open loop of closed loop feedback.

We will consider two different ISs: Open loop (OL),, where the controls are
just functions of time, $t$ (and also of initial state $x_{0}$, which however
is assumed to be fixed and a known parameter of the game), and closed-loop
state-feedback, where the controls are allowed to be functions of current
value of the state and of time, that is, for Player $i$,
$u_{i}(t)=\gamma_{i}(t;x(t))$. In the latter case,
$\gamma_{i}:[0,T\rangle\times\mathbb{R}^{n}\to U_{i}$ is known as the policy
variable (strategy) of Player $i$, which is a mapping from the set of
information available to the player to his control (action) set.222One can
introduce more general ISs, such as those that involve memory, but here we
will restrict the discussion to only OL and CL state-feedback (SF) structures
so as not to encounter informational non-uniqueness of Nash equilibria
BasOls99 . We require each $\gamma_{i}(t;\cdot)$ to be Lipschitz in $x$, in
addition to being jointly piecewise continuous in its arguments, and denote
the class of all such mappings by $\Gamma_{i}$. We further require that $f$ be
Lipschitz not only in $x$ but also in $\\{u_{1},\ldots,u_{N}\\}$, so that the
differential equation generating the state,

$\dot{x}(t)=f(x(t),\gamma_{1}(t;x(t)),\cdots,\gamma_{N}(t;x(t)),t)\,,\;\;x(0)=x_{0}\,,$

admits a unique piecewise continuously differentiable solution for each
$\gamma_{i}\in\Gamma_{i},\;i\in\mathcal{N}$. Clearly, when a particular
$\gamma_{i}$ does not depend on $x$ (such as the OL IS), then it would be
captured as a special case, and hence to capture this also notationally, we
will write $\gamma_{i}\in\Gamma_{i}$ as
$\gamma_{i}^{\eta}\in\Gamma_{i}^{\eta}$, where $\eta$ stands for the
underlying IS (which for the discussion in this paper is either OL or CL
SF).333Even though in general different players can have different ISs, we
will consider here only the case when the IS in the entire DG is either OL or
CL SF. Otherwise, derivation of Nash equilibrium becomes complicated, and one
has to introduce small noise robustness in order to eliminate informational
non-uniqueness, even in LQ DGs Basar89 , BasOls99 . At the conceptual level,
however, the analysis in this paper, and the indices introduced, equally apply
to the mixed IS case.

Each player $i\in\mathcal{N}$ is a cost-minimizer, with the objective function
for Player $i$, as defined on the state and action spaces, is given by

$L_{i}(u)=\int_{0}^{T}F_{i}(x(t),u_{1}(t),\cdots,u_{N}(t),t)dt+S_{i}(x(T))$

when $T<\infty$, and

$L_{i}(u)=\int_{0}^{\infty}F_{i}(x(t),u_{1}(t),\cdots,u_{N}(t),t)dt$

when $T=\infty$, where $u:=\\{u_{1},\ldots,u_{N}\\}$. In the expressions
above, for each $i\in\mathcal{N}$, the function
$F_{i}:\Omega\rightarrow\mathbb{R}$ is Player $i$’s instantaneous (running)
cost function, and in the first expression
$S_{i}:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is the terminal value function.
Substituting $u_{i}(t)=\gamma_{i}(t;x(t))$ in the above, we arrive at the ėm
normal or strategic form of the DG, where now the dependence in $L_{i}$ is on
$\gamma_{i}$’s instead of $u_{i}$’s. Let us denote this new cost function
representation by $J_{i}$, for Player $i$, which we write more explicitly
(showing its argument) as $J_{i}(\gamma^{\eta})$, where
$\gamma^{\eta}:=\\{\gamma_{1}^{\eta},\ldots,\gamma_{N}^{\eta}\\}\in\Gamma^{\eta}:=\Gamma^{\eta}_{1}\times\cdots\times\Gamma^{\eta}_{N}$,
where again this covers also the OL IS as a special case; we will occasionally
drop the superscript $\eta$ when the IS is clear from context.

Let $\gamma_{-i}^{\eta}$ denote the collection of policies of all players
except Player $i$, i.e.,
$\gamma_{-i}^{\eta}=(\gamma_{1}^{\eta},\ldots,\gamma_{i-1}^{\eta},\gamma_{i+1}^{\eta},\ldots,\gamma_{N}^{\eta})\,,$
in a game with IS $\eta$. If $\gamma_{-i}^{\eta}$ is fixed as
${\gamma_{-i}^{\eta*}}$, Player $i$ is faced with the dynamic optimization
(optimal control) problem: 444We use “$\textrm{OC}(i)$” to denote Player $i$’s
individual optimal control problem.

$\displaystyle(\textrm{OC}(i))\;\;$
$\displaystyle\min_{\gamma_{i}\in{{\Gamma_{i}^{\eta}}}}J_{i}(\gamma_{i},\gamma_{-i}^{\eta*}):=\int_{0}^{T}F_{i}(x,\gamma_{i}(\eta),{\gamma_{-i}^{\eta*}}(\eta),t)dt+S_{i}(x(T))$
(1)
$\displaystyle\textrm{s.t.~{}}\;\;\dot{x}(t)=f(x,\gamma_{i}(\eta),{{\gamma^{\eta*}_{-i}}}(\eta),t)\,,\;\;x(0)=x_{0}\,.$

In the case of infinite horizon, the problem remains the same with
$S_{i}\equiv 0$ and $T=\infty$. If we denote the solution to $\textrm{OC}(i)$
by ${\gamma_{i}^{\eta}}^{*}$, and carry out the optimization for each $i$,
then what we have is a Nash equilibrium compatible with the IS that defines
the DG. This is made precise below.

###### Definition 1

[$\eta$-Nash equilibrium] For a DG with IS $\eta$, the policy $N$-tuple
$\\{{\gamma_{i}^{\eta}}^{*},\;i\in\mathcal{N}\\}=:{\gamma^{\eta}}^{*}$ is an
$\eta-$Nash equilibrium if, for each $i\in\mathcal{N}$, $\gamma_{i}^{\eta*}$
solves the optimal control problem (OC$(i)$). Let $\Gamma^{\eta*}$ be the set
of all $\eta-$Nash equilibria, as a subset of $\Gamma^{\eta}$.

Now, for the CL IS case, one has to further refine the Nash equilibrium, in
order to eliminate informational non-uniqueness. Consider a family of DGs,
structured the same way, but defined over the time interval $[s,T\rangle$,
where $s>0$ is the parameter that identifies different elements of the family.
We say that an $\eta$-Nash equilibrium, when $\eta$ is the CL IS is strongly
time consistent if its restriction to $[s,T\rangle$ is also an $\eta$-Nash
equilibrium, and this being true for each $s$ and all $x(s)$. Such Nash
equilibria could also be called sub-game perfect equilibria, by direct analogy
with a similar concept in finite games. We will henceforth consider only
strongly time consistent Nash equilibria when $\eta$ is CL, but will suppress
that refinement in the development below.

Let $J^{\eta*}_{i},i\in\mathcal{N}$, denote the achieved values of the
objective functions of the players under a particular $\eta-$Nash equilibrium
$\gamma^{\eta*}$, and a corresponding total cost achieved (as a convex
combination of the individual costs) be given by
$J_{\mu}^{\eta*}=\sum_{i\in\mathcal{N}}\mu_{i}J_{i}^{\eta*}$, where $\mu_{i}$
is a positive weighting factor on Player $i$’th cost, satisfying the
normalization condition $\sum_{i\in\mathcal{N}}\mu_{i}=1$. We assume, without
any loss of generality, that $J^{\eta*}_{i}>0$ for all $i\in\mathcal{N}$, and
hence a fortiori $J_{\mu}^{\eta*}>0$.

Now as a benchmark, let us consider the case of full coordination, where the
players agree on minimizing a single objective function, which is a convex
combination of the individual cost functions. We may call this also a socially
optimal solution. The corresponding underlying optimization problem is the
optimal control problem: 555The acronym “COC” stands for “Centralized Optimal
Control”.

$\displaystyle(\textrm{COC})\;\;\;$
$\displaystyle\min_{\gamma\in\Gamma}\sum_{i=1}^{N}\mu_{i}\left\\{\int_{0}^{T}F_{i}(x(t),\gamma(\eta),t)dt+S_{i}(x(T))\right\\}$
s.t. $\displaystyle\dot{x}(t)=f(x,\gamma(\eta),t)\,,\;\;x(0)=x_{0}\,,$

where the optimization could also be carried out with respect to control
values, $u$, that is in an open-loop fashion, since the problem is
deterministic and also is not strategic. Hence, the optimal value of this
optimal control problem is independent of the IS, which we denote by
$J_{\mu}^{\circ}$, and the corresponding (open-loop) optimal control by
$u^{\circ}=[u_{1}^{\circ},\ldots,u_{N}^{\circ}]$. Note that we necessarily
have $0<J_{\mu}^{\circ}\leq J_{\mu}^{\eta*}\,,\;$ where $J_{\mu}^{\eta*}$ is
under any Nash equilibrium solution out of $\Gamma^{\eta*}$.

######  Definition 2 (Price of Anarchy)

Consider an $N$-person DG as above and its associated optimal control problem
(COC) with $J_{\mu}^{\circ}>0$. The price of anarchy for the DG is666If the
maximum below does not exist, then it is replaced by supremum in the
definition of PoA.

$\rho_{N,\mu,T}^{\eta}=\max_{\gamma^{\eta*}\in\Gamma^{\eta*}}\,J_{\mu}^{\eta*}/{J_{\mu}^{\circ}}$
(2)

as the worst-case ratio of the total game cost to the optimum social cost.

In addition to its dependence on the cost functions, PoA depends on the number
of players in the game, the IS, the weights on individual players and the time
horizon. Note that the PoA as defined in (2) is lower-bounded by 1.

######  Definition 3 (Price of Information (PoI))

Let $\eta_{1}$ and $\eta_{2}$ be two ISs. Consider two $N$-person DGs which
differ only in terms of their ISs, with game $1$ having IS $\eta_{1}$, and
game $2$ having $\eta_{2}$. Let the values of a particular $\mu$ convex
combination of the objective functions be ${J^{\eta_{1}}_{\mu}}^{*}$ and
${J^{\eta_{2}}_{\mu}}^{*}$, respectively, achieved under the Nash equilibria
${\gamma^{\eta_{1}}}^{*}$ and ${\gamma^{\eta_{2}}}^{*}$. The price of
information between the two ISs (under cost minimization) is given by

$\chi_{\eta_{1}}^{\eta_{2}}(\mu)=\max_{\gamma^{\eta_{2}^{*}}\in\Gamma^{\eta^{*}_{2}}}J_{\mu}^{\eta^{*}_{2}}\,/\max_{\gamma^{\eta_{1}^{*}}\in\Gamma^{\eta_{1}^{*}}}J_{\mu}^{\eta_{1}^{*}}.$
(3)

The PoI compares the worst-case costs under two different ISs for the same
convex combination, and quantifies the relative loss or gain when the DG is
played under a different IS. Clearly, when
$\chi_{\eta_{1}}^{\eta_{2}}(\mu)<1$, the IS $\eta_{2}$ is superior to its
counterpart $\eta_{1}$ . The connection between PoI and PoA can be captured by
$\;\chi_{\eta_{1}}^{\eta_{2}}(\mu)={\rho_{N,\mu,T}^{\eta_{2}}}\,/{\rho_{N,\mu,T}^{\eta_{1}}}\,.$

Before introducing the third index (price of cooperation), let us define
another class of DGs, which is an intermediate case between full cooperation
and full non-cooperation. Consider the case where Player $i$, even though his
cost function is $J_{i}$, adopts an altruistic mode and minimizes instead a
cost function that places some weight on other players’ costs. Let
$\lambda_{i}:=\\{\lambda_{i}^{j},j\in\mathcal{N}\\}$ be a set of nonnegative
parameters adding up to $1$, $\sum_{j\in\mathcal{N}}\lambda^{j}_{i}=1$. Let
$\tilde{J}_{i}(\gamma^{\eta};\lambda_{i})\,,\;i\in\mathcal{N}$ be defined by

$\tilde{J}_{i}(\gamma^{\eta};\lambda_{i}):=\sum_{j\in\mathcal{N}}\lambda_{i}^{j}J_{j}(\gamma^{\eta})\,,\;\;i\in\mathcal{N}$

Consider the $\eta$ IS DG with cost functions $\tilde{J}$’s, and let
$\tilde{\Gamma}^{\eta}$ be the set of all its $\eta$-Nash equilibria. For
$\tilde{\gamma}^{\eta}\in\tilde{\Gamma}^{\eta}$, Player $i$ achieves an actual
cost of $J_{i}(\tilde{\gamma}^{\eta})$, which may be better (lower) or worse
(higher) than $J^{\eta*}_{i}$ defined earlier. Note that if
$\lambda_{i}^{j}=\mu_{i}$ for all $i,j\in\mathcal{N}$, then all players have
the same cost function, and every $\eta$-Nash equilibrium solution of the
altruistic game is a solution to COC, assuming that person by person optimal
solutions of COC are globally optimal. Hence, in this limiting case we have
full cooperation. This now brings us to the third index, which is keyed to
individual players.

######  Definition 4 (Price of Cooperation (PoC))

Consider an N-player DG with a fixed IS $\eta$, and with a fixed set of
cooperation vectors $\lambda:=\\{\lambda_{i},\;i\in\mathcal{N}\\}$. Let
$\tilde{J}_{i},\;i\in\mathcal{N}$, and ${\tilde{\Gamma}}^{\eta}$ be as defined
above, and $\Gamma^{\eta}$ be the set of all Nash equilibria of the original
game. Then, the price of cooperation for Player $i$ under the cooperation
scheme $\lambda$ is given by

$\nu_{i}^{\eta}(\lambda)=\max_{\gamma\in{\tilde{\Gamma}}^{\eta}}J_{i}(\gamma)/\max_{\gamma\in\Gamma^{\eta}}J_{i}(\gamma)\,.$
(4)

As indicated earlier, if $\lambda_{i}=\mu$ for all $i$, where
$\mu=\\{\mu_{i},\;i\in\mathcal{N}\\}$ as in PoA, then every NE of
$\\{\tilde{J}_{i},\;i\in\mathcal{N}\\}$ is a person-by-person optimal solution
of the COC with cost function $J_{\mu}$, which would also be globally optimal
under some appropriate convexity conditions. If $\gamma^{0}$ is one such
solution, minimizing $J_{\mu}$, then the PoC is given by

$\nu_{i}^{\eta}(\mu)=J_{i}(\gamma)/\max_{\gamma\in\Gamma^{\eta}}J_{i}(\gamma)\,,$

which can be viewed as the reciprocal of individualized PoA, where the latter
is a measure of the loss or gain an individual player incurs on his individual
cost when he (along with other players) plays the worst NE strategy as opposed
to the globally minimizing strategy (again along with other players).

##  3 Scalar LQ Feedback Differential Games

The analysis of the price of anarchy is complex for general DGs as there often
exist more than one Nash equilibrium, which show strong dependence on the
underlying IS. For specific game structures, however, its analysis may be
tractable provided that we avoid informational non-uniqueness. One such class
is scalar linear quadratic DGs with state feedback IS, which is what we focus
on in this section. These games also enjoy wide applications in economics and
communication networks; see, DJLS06 , AB98 . We first state our model and
recall some important relevant results on LQ feedback DGs; for details, see
BasOls99 , Eng05 .

###  3.1 Game Model

As a special case of the class of DGs considered in the previous section,
consider the infinite-horizon scalar $N-$person LQ DGs, with quadratic cost
function

$L_{i}(u)=\int_{0}^{\infty}\left(q_{i}x^{2}(t)+r_{i}u_{i}^{2}(t)\right)dt,\;\;\;i\in\mathcal{N},$
(5) $\dot{x}(t)=ax(t)+\sum_{i=1}^{N}b_{i}u_{i}(t),\;\;\;x(0)=x_{0}\,,$ (6)

where $q_{i}>0$, $r_{i}>0$, $x_{0}\not=0$, $b_{i}\not=0$ are all scalar
quantities. Let $b:=[b_{1},\dots,b_{N}]$. We are interested in strongly time-
consistent state-feedback (SF) Nash equilibrium (NE), where further the NE
policies are required to be stationary (that is time invariant). We will refer
to such equilibria in short as Feedback NE. The following theorem provides
their characterization.

###### Theorem 1

[Feedback NE, BasOls99 , Eng05 ] Let $\\{k_{i},\;i\in\mathcal{N}\\}$ solve the
set of coupled algebraic Riccati equations

$2\left(a-\sum_{j=1}^{N}s_{j}k_{j}\right)k_{i}+q_{i}+s_{i}k_{i}^{2}=0,\;i\in\mathcal{N}$
(7)

satisfying the stability condition $a-\sum_{i=1}^{N}s_{i}k_{i}<0\,,$ where
$s_{i}:=b_{i}^{2}/r_{i}$. Then, the $N$-tuple of policies
$\gamma_{i}^{*}(x)=-\frac{b_{i}}{r_{i}}k_{i}x,\;i\in\mathcal{N},$ constitutes
a feedback NE, with the corresponding cost for Player $i$ being
$J^{*}_{i}=k_{i}x^{2}_{0}$. Furthermore, the positively weighed total cost is
$J_{\mu}^{*}=\bar{k}x^{2}_{0}$, where $\bar{k}=\sum_{i=1}^{N}\mu_{i}k_{i}$.
If the set of coupled algebraic Riccati equations do not admit a solution
which is also stabilizing, then the DG does not have a feedback NE. $\diamond$

The main challenge in computing the feedback NE solution for this DG is that
equation (7) is a nonlinear coupled system of equations. The fact that we have
a scalar problem alleviates the difficulty somewhat, since it is possible to
turn it into a linear problem through a change of variables, as outlined in
Eng00a ,Eng00b . Let $\sigma_{i}=s_{i}q_{i}$,
$\sigma_{\max}=\max_{i}\sigma_{i}$, $p_{i}=s_{i}k_{i},i=1,\ldots,N$, and

$\lambda=\sum_{i=1}^{N}p_{i}-a.$ (8)

Multiplying (7) by $s_{i}$, we rewrite it as

$p_{i}^{2}-2\lambda p_{i}+\sigma_{i}=0,\;i=1,\ldots,N.$ (9)

Let $\Omega\subset\mathcal{N}$ be an index set,
$\Omega_{-i}=\Omega\backslash\\{i\\}$, and $n_{\Omega}=|\Omega|$. For every
$\Omega\neq\emptyset$, we have (after some manipulations)

$\prod_{j\in\Omega}p_{j}\lambda=\frac{1}{2n_{\Omega}-1}\left\\{\sum_{i\in\Omega}\sigma_{i}\prod_{j\in\Omega_{-i}}p_{j}-\sum_{i\notin\Omega}\prod_{j\in\Omega}p_{j}p_{i}+a\prod_{j\in\Omega}p_{j}\right\\}.$
(10)

When $\Omega=\emptyset$, we define

$\prod_{j\in\Omega}p_{j}\lambda:=\lambda=\sum_{j=1}^{N}p_{j}-a.$ (11)

Hence, for every $\Omega$, we have an equation in the form of either (10) or
(11). Let $\mathbf{p}=[1,p_{1},p_{2},$
$\ldots,p_{N},p_{1}p_{2},\ldots,p_{1}p_{N},p_{2}p_{3},\ldots,p_{N-1}p_{N},\ldots,\prod_{i=1}^{N}p_{i}]^{T}$.
We can write (10) and (11) into

$\widetilde{\mathbf{M}}\mathbf{p}=\lambda\mathbf{p}.$ (12)

Let
$\mathbf{p}:=[1,k_{1},k_{2},\ldots,k_{N},k_{1}k_{2},\ldots,k_{1}k_{N},k_{2}k_{3},\ldots,$
$k_{N-1}k_{N},\ldots,\prod_{i=1}^{N}k_{i}]^{T}$ and
$\mathbf{D}=\textrm{diag}\\{1$, $s_{1}$, $s_{2}$, $\ldots$, $s_{N}$,
$s_{1}s_{2},$ $\ldots$, $s_{1}s_{N}$,$s_{2}s_{3},$ …,
$s_{N-1}s_{N},\ldots,\prod_{i=1}^{N}s_{i}\\}\,.$ Hence, we can rewrite
$\mathbf{p}=\mathbf{D}\mathbf{k}$ and (12) into

$\mathbf{M}\mathbf{k}=\lambda\mathbf{k},\,\mbox{ where
}\;\mathbf{M}:=\mathbf{D}^{-1}\widetilde{\mathbf{M}}\mathbf{D}\,.$ (13)

Equation (13) is an eigenvalue problem with each index set $\Omega$
corresponding to a row enumerated starting from the empty set. It has maximum
$2^{N}$ distinct eigenvalues and $2^{N}$ eigenvectors. The vector formed by
the second entry to the $N+1$-st entry of the eigenvectors yields the solution
to (7) when the first entry of the vector is normalized to $1$ and they
satisfy the stability condition of Theorem 1. This leads to:

###### Theorem 2

[Feedback NE Computation, Eng05 ] Suppose $\mathbf{M}$ is a nondefective
matrix with distinct eigenvalues. Let $(\lambda,\mathbf{k})$ be an eigenvalue-
eigenvector pair such that $\lambda\in\mathbb{R}_{+}$ and
$\lambda>\sigma_{\max}$. Then, a feedback NE
$\gamma_{i}^{*}(x)=-\frac{b_{i}}{r_{i}}k_{i}\,x,\;i\in\mathcal{N}\,,$ is
yielded by $k^{*}=\mathbf{1}^{T}\mathbf{k}$ provided that the resulting
solution is stabilizing, where $\mathbf{1}=[0,1,\ldots,1,0,\ldots,0]^{T}$ is a
vector whose $2$nd to $N+1$-st entries are 1’s.

###### Theorem 3

[Uniqueness of Feedback NE] Let
$\bar{p}:=\sum_{j\in\mathcal{N}}p_{j},p_{-i}:=\sum_{j\in\mathcal{N},j\neq
i}p_{j}$. There exists a unique feedback NE for the LQ DG described by (5) and
(6) under either one of the following two conditions:
(i) $N$ is sufficiently large such that $p_{-i}>a,\forall i$, or (ii) $a=0$.
Furthermore, the solutions to the coupled algebraic Riccati equations that
characterize the feedback NE are of the following forms under the
corresponding conditions above:

  1. (s-i)

$p_{i}=(\bar{p}-a)-\sqrt{(\bar{p}-a)^{2}-\sigma_{i}}~{};$

  2. (s-ii)

$p_{i}=\bar{p}-\sqrt{\bar{p}^{2}-\sigma_{i}},\;$ where

$\bar{p}-a=\frac{1}{N-1}\left(\sum_{i=1}^{N}\sqrt{(\bar{p}-a)^{2}-\sigma_{i}}+a\right).$
(14)

Moreover, the stability condition $a-\sum_{i=1}^{N}s_{i}k_{i}<0\,$ is
satisfied, and hence the FB NE is stabilizing.

###### Proof

From (9), we obtain

$p_{i}^{2}+2(p_{-i}-a)p_{i}-\sigma_{i}=0,$ (15)

which admits the solutions:

$p_{i}=(a-p_{-i})\pm\sqrt{(a-p_{-i})^{2}+\sigma_{i}}.$ (16)

Since we need $p_{i}>0$, we retain the one with $``+"$ sign. By rearranging
the positive solution of (16), we arrive at

$(\bar{p}-a)^{2}=(p_{-i}-a)^{2}+\sigma_{i}\,,$ (17)

and, therefore, in terms of $\bar{p}$, we have

$p_{i}=(\bar{p}-a)\pm\sqrt{(\bar{p}-a)^{2}-\sigma_{i}}.$ (18)

Under condition (i), we have $p_{i}-\bar{p}+a<0$, hence we obtain the unique
solution (s-i). Under scenario (ii), (18) reduces to
$p_{i}=\bar{p}\pm\sqrt{\bar{p}^{2}-\sigma_{i}}.$ Since, $p_{i}<\bar{p}$, we
again obtain the unique solution (s-ii).

By summing over (18), we have a fixed point equation (14). Let

$\bar{P}(\bar{p}):=\frac{1}{N-1}\left(\sum_{i=1}^{N}\sqrt{(\bar{p}-a)^{2}-\sigma_{i}}+a\right)-(\bar{p}-a)\,.$

Its derivative is given by

$\frac{d\bar{P}}{d\bar{p}}=-1+\frac{\bar{p}-a}{N-1}\left(\sum_{i=1}^{N}\frac{1}{\sqrt{(a-\bar{p})^{2}-\sigma_{i}}}\right).$

Since $\sigma_{i}\geq 0$ and $\bar{p}-a>0$, it follows that

$\displaystyle\frac{d\bar{P}}{d\bar{p}}$ $\displaystyle\geq$
$\displaystyle-1+\frac{\bar{p}-a}{N-1}\left(\frac{N}{(\bar{p}-a)}\right)$ (19)
$\displaystyle=$ $\displaystyle\frac{1}{N-1}>0,\textrm{~{}for~{}}N\geq 2.$
(20)

This says that $\bar{P}$ is a monotonically increasing function, and hence the
solution to $\bar{P}=0$ is unique. Hence, under (i) or (ii), there exists a
unique feedback NE.

The fact that the solution is stabilizing follows directly from (7), where the
first term has to be negative because the second and third terms are positive.

###  3.2 Team Model

When players form a team to achieve an optimal social objective, a specific
total cost is minimized. Let $\bar{q}_{\mu}=\sum_{i=1}^{N}\mu_{i}q_{i}$,
$\overline{R}_{\mu}=\textrm{diag}\\{\mu_{1}r_{1},\ldots,\mu_{N}r_{N}\\}$, and
consider

$\displaystyle(\textrm{FOC})$
$\displaystyle\;\;\;\;\min_{u(t)}\int_{0}^{\infty}\left(\bar{q}_{\mu}x^{2}(t)+u^{T}(t)\overline{R}_{\mu}u(t)\right)dt$
s.t.
$\displaystyle\;\;\;\dot{x}(t)=ax(t)+\sum_{i=1}^{N}b_{i}u_{i}(t)\,,\;\;x(0)=x_{0}\not=0\,.$

The solution to this optimal control problem is standard, and is given below
for future reference (where we suppress the dependence of $\bar{q}$ and
$\overline{R}$ on $\mu$).

###### Theorem 4

[Centralized Optimization] The optimal control problem (FOC) admits a unique
feedback solution which is further stabilizing. The optimal policies are

$\gamma^{\circ}_{i}(x)=-\frac{b_{i}}{\mu_{i}r_{i}}\hat{k}_{\mu}\,x\,,\quad\hat{k}_{\mu}:=\frac{a+\sqrt{a^{2}+\bar{q}\bar{b}}}{\bar{b}}\,,$
(21)

with $\bar{b}:=\sum_{i=1}^{N}(b_{i}^{2}/\mu_{i}r_{i})$, and minimum cost is
$J^{\circ}_{\mu}=\hat{k}_{\mu}x_{0}^{2}$.
The optimal control can also be expressed in open-loop form, as:

$u^{\circ}_{i}=-\frac{b_{i}}{\mu_{i}r_{i}}\hat{k}_{\mu}\Phi(t,0)x_{0},$

where $\Phi(t,0)$ is the unique solution to

$\dot{\Phi}(t,0)=\left(a-\sum_{i=1}^{N}\frac{b_{i}^{2}}{\mu_{i}r_{i}}\hat{k}_{\mu}\right)\Phi(t,0),~{}~{}\Phi(0,0)=1.$

###  3.3 Price of Anarchy (PoA)

Here, we provide a closed-form expression for the PoA in the feedback LQ DG,
where we make the natural assumption that $x_{0}\not=0$, as otherwise the
costs are all zero.

###### Theorem 5

The PoA of the LQ feedback DG described by (5) and (6) is characterized by the
following:

  1. (i)

Given a weight vector $\mu$, the PoA $\rho_{\mu}$ is equal to

$\rho_{\mu}^{FB}=\max_{\mathbf{k}\in\mathcal{K}}\,\,[\,{\boldsymbol{\mu}^{T}\mathbf{k}}\,]\,/{\hat{k}}\,,$
(22)

where $\boldsymbol{\mu}=[0,\mu^{T},0,\ldots,0]^{T}$ and $\mathcal{K}$ is the
set of all eigenvectors of the matrix $\mathbf{M}$.

  2. (ii)

Suppose
$\mu_{i}=\bar{\mu}_{i}:={s_{i}}\,/{\sum_{j=1}^{N}s_{j}},i\in\mathcal{N}$.
Then,

$\rho^{FB}_{\bar{\mu}}\leq[\,{\varrho({\mathbf{M}})+a}\,]\,/{\sum_{i=1}^{N}s_{i}\hat{k}}\,,$

where $\varrho(\mathbf{M})$ is the spectral radius of $\mathbf{M}$.

  3. (iii)

Let $\mu^{s}_{\max}=\max_{i\in\mathcal{N}}\mu_{i}/s_{i}$. Given a weight
vector $\mu$ that satisfies $\sum_{i=1}^{N}\mu_{i}=1$, the PoA is bounded by

$\rho^{FB}_{\mu}\leq{\mu^{s}_{\max}(\varrho(\mathbf{M})+a)}\,/{\hat{k}}.$ (23)

###### Proof

The proof is a direct application of the results in Theorem 1 and Theorem 4.
PoA is the worst-case ratio of the game cost under feedback NE to the optimum
social cost as defined in (2). Under the feedback IS, an LQ DG has

$\rho^{FB}_{\mu}=\max_{k^{*}}\frac{\sum_{i=1}^{N}\mu_{i}k^{*}_{i}(x_{0})^{2}}{\hat{k}(x^{0})^{2}}=\max_{\mathbf{k}\in\mathcal{K}}\frac{\mu^{T}\mathbf{k}}{\hat{k}}\,.$

This leads to statement (i). The price of anarchy under $\bar{\mu}$ is

$\displaystyle\rho^{FB}_{\bar{\mu}}$ $\displaystyle=$
$\displaystyle\max_{k}\frac{\sum_{i=1}^{N}\bar{\mu}_{i}k_{i}}{\hat{k}}=\max_{k}\frac{s_{i}k_{i}}{\sum_{i=1}^{N}{s_{i}}\hat{k}}$
(24) $\displaystyle=$
$\displaystyle\max_{\lambda}\frac{\lambda+a}{\sum_{i=1}^{N}{s_{i}}\hat{k}}.$

The last equality is due to (8). Hence, by taking the largest eigenvalue, we
obtain (ii). The equality is achieved when $\varrho(\mathbf{M})$ is an
eigenvalue in the eigenvalue-eigenvector pair that yields the equilibrium from
Theorem 2. For an arbitrarily picked $\mu$, (22) yields

$\displaystyle\rho^{FB}_{\bar{\mu}}$ $\displaystyle=$
$\displaystyle\max_{k}\frac{\sum_{i=1}^{N}\frac{\mu_{i}}{s_{i}}s_{i}k_{i}}{\hat{k}}\leq\max_{k}\frac{u^{s}_{\max}\sum_{i=1}^{N}s_{i}k_{i}}{\hat{k}}$
(25) $\displaystyle=$
$\displaystyle\max_{\lambda}\frac{u_{\max}^{s}(\lambda+a)}{\hat{k}}\leq\frac{u_{\max}^{s}(\varrho(\mathbf{M})+a)}{\hat{k}}.$

Using (8) and taking the worst case, we obtain statement (iii). Since

$\max_{i\in\mathcal{N}}\frac{\bar{\mu}_{i}}{s_{i}}=\frac{1}{\sum_{j=1}^{N}{s_{j}}}\,,$

the last inequality is achieved when $\mu=\bar{\mu}$.

The next corollary further characterizes the bound on PoA.

###### Corollary 1

The following follow from Theorem 5:

  1. (i)

Given a $\mu$ and $a\neq 0$, PoA is bounded above by

$\rho^{FB}_{{\mu}}\leq\left(1+\frac{1}{2a}(N+\sigma_{\max}-1)\right)s^{\bullet},$
(26)

where $\sigma_{\max}=\max_{i\in\mathcal{N}}\sigma_{i}$, and

$s^{\bullet}:=\sum_{i=1}^{N}\frac{s_{i}}{\min_{j\in\mathcal{N}}s_{j}}\,.$

The upper-bound is independent of $\mu$.

  2. (ii)

If $a=0$, PoA is bounded above by

$\rho^{FB}_{{\mu}}\leq\frac{\mu^{s}_{\max}}{\sqrt{\bar{q}}\sqrt{\mu^{s}_{\min}}}\sqrt{N}(N+\sigma_{\max}-1),$
(27)

where $\mu^{s}_{\min}=\min_{i\in\mathcal{N}}\mu_{i}/s_{i}$.

###### Proof

The matrices $\mathbf{M}=[m_{ij}]$ and
$\widetilde{\mathbf{M}}=[\tilde{m}_{ij}],i,j=1,\ldots,2^{N},$ share the same
set of eigenvalues. From Gersgorin theorem, we can obtain

$\varrho(\widetilde{\mathbf{M}})\leq\min\left\\{\max_{i}\sum_{j=1}^{2^{N}}|\tilde{m}_{ij}|,\max_{j}\sum_{i=1}^{2^{N}}|\tilde{m}_{ij}|\right\\}\leq\max_{i}\sum_{j=1}^{2^{N}}|\tilde{m}_{ij}|.$

From (10) and (11), the absolute row sum $RS_{k},k=1,\ldots,2^{N}$, can easily
be evaluated by letting $p_{i}=1$:

$\displaystyle
RS_{k}=[{a+\sum_{i\in\Omega}\sigma_{i}+(N-n_{\Omega})}]\,/\,[{2n_{\Omega}-1}],$

where $k$ is the row index corresponding to the set $\Omega$. When
$\Omega=\emptyset$, we let $RS_{1}=N+a$. From (23),

$\rho^{FB}_{\mu}\leq\,\,[\,{\varrho(\mathbf{M})+a}\,]/({\hat{k}/\mu_{\max}^{s}}).$

The numerator is upper-bounded by (skipping some steps):

$\displaystyle\varrho(\mathbf{M})+a$ $\displaystyle\leq$
$\displaystyle\max\left\\{\max_{1\leq n_{\Omega}\leq
N}\frac{(2a+\sigma_{\max}-1)n_{\Omega}+N}{2n_{\Omega}-1},2a+N-1\right\\}$ (28)
$\displaystyle\leq$
$\displaystyle\max\left\\{{2a+N+\sigma_{\max}-1},2a+N-1\right\\}$
$\displaystyle\leq$ $\displaystyle 2a+N+\sigma_{\max}-1.$

The second inequality holds because the quantity

$\frac{(2a+\sigma_{\max}-1)n_{\Omega}+N}{2n_{\Omega}-1}$

increases with $n_{\Omega}$. The denominator has a lower bound:

$\displaystyle\frac{2a}{\bar{b}\mu^{s}_{\max}}$ $\displaystyle\geq$
$\displaystyle\frac{2a}{\sum_{i=1}^{N}\left(\frac{\max_{i\in\mathcal{N}}\mu_{i}/s_{i}}{\mu_{i}}\right)\frac{b_{i}^{2}}{r_{i}}}$
(29) $\displaystyle\geq$
$\displaystyle\frac{2a}{\sum_{i=1}^{N}\frac{s_{i}}{\min_{i\in\mathcal{N}}s_{i}}}=\frac{2a}{s^{\bullet}}\,.$

The last inequality is due to
$\max_{i}\mu_{i}/s_{i}\leq\max_{i}\mu_{i}\max_{i}\frac{1}{s_{i}}$. Combining
(28) and (29), we have, for $a\not=0$,

$\rho^{FB}_{{\mu}}\leq\left(1+\frac{1}{2a}(N+\sigma_{\max}-1)\right)s^{\bullet}$

When $a=0$,

$\hat{k}=\sqrt{\bar{q}/\bar{b}}=\sqrt{\frac{\bar{q}}{\sum_{i=1}^{N}\frac{s_{i}}{\mu_{i}}}}\geq\frac{\sqrt{\bar{q}\mu^{s}_{\min}}}{\sqrt{N}}\,.$

Using this together with (28), we arrive at the inequality (27).

The upper bound on price of anarchy in the preceding corollary provides a
worst case of efficiency loss.

The next result studies the large population game and its proof relies on the
Taylor series expansion of the square-root term in (18).

###### Theorem 6

Suppose the number of players in the LQ DG is sufficiently large so that

$\mbox{(C-i) }p_{-i}>a,\forall i\in\mathcal{N}\,,\;\mbox{(C-ii) }a\ll
N\,,\;\mbox{(C-iii) }\sigma_{\max}\ll\bar{\sigma}\,,$

where $\bar{\sigma}=\sum_{i=1}^{N}\sigma_{i}$. Then, the following quantities
can be approximated as given:

$\mbox{(i) }p_{i}\sim\frac{\sigma_{i}}{\sqrt{2\bar{\sigma}}}\,,\;\;\mbox{(ii)
}u_{i}\sim-\frac{\sigma_{i}}{b_{i}\sqrt{2\bar{\sigma}}}x\,,\;\;$ $\mbox{(iii)
}J^{*}\sim\frac{\bar{q}}{\sqrt{2\bar{\sigma}}}(x_{0})^{2}\,,\;\;\mbox{(iv)
}J^{*}\sim\frac{\bar{q}}{\sqrt{2\bar{\sigma}}}(x_{0})^{2}\,,\;\;$ $\mbox{(v)
}\rho^{FB}_{\mu}\sim\frac{\bar{q}}{\hat{k}\sqrt{2\bar{\sigma}}}\,,\;\mbox{and
for }a=0,\,\rho^{FB}_{\mu}\sim\sqrt{\frac{\bar{q}\bar{b}}{2\bar{\sigma}}}\,.$

###### Proof

By Taylor series expansion, (18) can be written as

$\displaystyle p_{i}$ $\displaystyle=$
$\displaystyle(\bar{p}-a)\left[1-\sqrt{1-\frac{\sigma_{i}}{(\bar{p}-a)^{2}}}\right]$
(30) $\displaystyle=$
$\displaystyle\frac{\sigma_{i}}{2(\bar{p}-a)}\left[1+O\left(\frac{\sigma_{i}}{(\bar{p}-a)^{2}}\right)\right],$

where $O(\cdot)$ is a function such that $\lim_{x\rightarrow 0}O(x)=0$. In a
similar way, (14) can be rewritten as (skipping some steps):

$\displaystyle\bar{p}-a=$
$\displaystyle\frac{\bar{p}-a}{N-1}\left(\sum_{i=1}^{N}\sqrt{1-\frac{\sigma_{i}}{(\bar{p}-a)^{2}}}+a\right)$
$\displaystyle=$
$\displaystyle\frac{\bar{p}-a}{N-1}\left[\frac{N\bar{\sigma}}{2(\bar{p}-a)^{2}}\left(1+O\left(\frac{\sigma_{\max}}{2(\bar{p}-a)^{2}}\right)\right)+a\right].$
(31)

Hence, we obtain for large $N$

$\displaystyle\bar{p}-a$ $\displaystyle=$
$\displaystyle\sqrt{\frac{\bar{\sigma}}{2}}\left[1+O\left(\frac{\sigma_{\max}}{2(\bar{p}-a)^{2}}\right)\right]$
(32)

Note that $\bar{p}-a>0$ due to the stability condition. Let
$\bar{\sigma}=\sum_{i=1}^{N}\sigma_{i}$, as before. Let a solution of (32) be
$\bar{p}=\sqrt{\bar{\sigma}/2}+a$, i.e.,

$\displaystyle\bar{p}-a=\sqrt{\frac{\bar{\sigma}}{2}}\left[1+O\left(\frac{\sigma_{\max}}{\bar{\sigma}}\right)\right].$
(33)

(33) is consistent provided that $\sigma_{\max}\ll\sigma$ and $a\ll N$. Since,
by Theorem 3, the solution is unique under (C-i), $\bar{p}$ can indeed be
approximated by $\bar{p}\sim a+\sqrt{\bar{\sigma}/2}$, which leads to
$p_{i}\sim\frac{\sigma_{i}}{\sqrt{2\bar{\sigma}}}$ from (30). Hence, (ii)-(v)
follow.

##  4 Open-Loop LQ Differential Games

In this section, we go back to the DGs described by (5) and (6), but with
open-loop information. Each player knows only the value of the initial state
of the system. Since the cost runs from zero to infinity, we are interested in
controls that yield finite costs. Accordingly, we restrict the controls of the
players to belong to the set

$\mathcal{U}^{OL}(x_{0})=\\{u\in\mathcal{L}_{2}[0,\infty)\mid
J_{i}(x_{0},u)<\infty,\;\forall i\in\mathcal{N}\\}\,,$

where $\mathcal{L}_{2}[0,\infty)$ is the space of square-integrable functions
on $[0,\infty)$.

###### Theorem 7

[Open-Loop NE, BasOls99 , Eng05 ] Consider the $N-$person LQ DG in (5) and
(6), and assume that there exists a unique solution $\xi^{\star}$ to the set
of equations

$0=2a\xi_{i}+q_{i}-\xi_{i}\left(\sum_{j=1}^{N}s_{j}\xi_{j}\right),$ (34)

such that $a-\sum_{j=1}^{N}s_{j}\xi_{j}^{\star}<0$, where
$s_{i}:=b_{i}^{2}/r_{i}$. Then, the game admits a unique open-loop Nash
equilibrium for every initial state, given by

$u_{i}^{\star}(t)=-\frac{b_{i}}{r_{i}}\xi_{i}^{\star}\exp\left[\left(a-\sum_{j=1}^{N}s_{j}\xi_{j}^{\star}\right)t\right]x_{0}\,.$
(35)

The optimal cost to player $i$ using $u_{i}^{\star}$ is
$\,J_{i}^{\star}=k_{i}^{\star}x_{0},\;$ where $k_{i}^{\star}$ is the unique
solution to

$2\left(a-\sum_{j=1}^{N}s_{j}\xi_{j}^{\star}\right)k_{i}+q_{i}+s_{i}(\xi_{i}^{\star})^{2}=0.$
(36)

The quantities in Theorem 7 can be made more explicit as we discuss below. By
a slight abuse of notation, let $p_{i}:=s_{i}\xi_{i}$ as in the state-feedback
information case. Multiplying (34) and (36) by $s_{i}$, we obtain
$\;0=2ap_{i}+\sigma_{i}-p_{i}\bar{p}\,,\;$ and
$0=2s_{i}k_{i}(a-\bar{p})+\sigma_{i}+p_{i}^{2},$ where
$\bar{p}=\sum_{i=1}^{N}p_{i}$. Hence we can solve for $p_{i},k_{i}$, and
obtain

$p_{i}={\sigma_{i}}\,/\,({\bar{p}-2a})$ (37)
$k_{i}={\sigma_{i}+p_{i}^{2}}\,/\,({2s_{i}(\bar{p}-a)}).$ (38)

To obtain $\bar{p}$, we sum (37) over $i$ and arrive at the quadratic equation
$\bar{p}=\frac{\bar{\sigma}}{\bar{p}-2a}.$ Thus,

$\bar{p}=\sqrt{a^{2}+\bar{\sigma}}+a\,,$ (39)

where we have retained only the positive solution of the quadratic equation
for obvious reasons. It should be pointed out that since the relevant
$\bar{p}$ is unique, we have a unique open-loop NE. Using (39), we can
determine the expression for $\xi_{i}^{\star}$ (and thus the OL NE strategies
of the players 35), as

$\xi_{i}^{\star}=\frac{q_{i}}{\sqrt{a^{2}+\bar{\sigma}}-a}.$ (40)

Note that these are necessarily stabilizing, that is
$a-\sum_{j=1}^{N}s_{j}\xi_{j}^{\star}<0$, in view of (36). Now using (39) and
(37) in (38), we arrive at the closed-form expression for $k_{i}^{\star}$:

$k_{i}^{\star}=\frac{1}{\sqrt{a^{2}+\bar{\sigma}}}\left(\frac{q_{i}}{2}+\frac{\sigma_{i}q_{i}}{2(\sqrt{a^{2}+\bar{\sigma}}-a)^{2}}\right).$
(41)

When $a=0$, $k_{i}^{\star}$ is reduced to

$k^{\star}_{i}=\frac{1}{\sqrt{\bar{\sigma}}}\left(\frac{q_{i}}{2}+\frac{\sigma_{i}q_{i}}{2\bar{\sigma}}\right).$
(42)

Given weighting $\mu$, the open-loop NE yields a total cost of

$J_{\mu}^{\star}=\sum_{i=1}^{N}\mu_{i}J_{i}^{\star}=\sum_{i=1}^{N}\mu_{i}k_{i}^{\star}(x_{0})^{2}=:k_{\mu}^{\star}(x_{0})^{2}\,.$

Since the open-loop NE solution is unique, the PoA under open loop IS can thus
be easily found to be:

$\rho_{\mu}^{OL}={k_{\mu}^{\star}}\,/\,{\hat{k}_{\mu}}\,.$ (43)

We now capture all this in the corollary below.

###### Corollary 2

The OL LQ DG of Theorem 7 admits a unique OL NE given by (35) and (40), which
is also stabilizing. Furthermore, the OL PoA is given by (43).

##  5 Price of Information (PoI)

In the previous sections, we have introduced PoA as a measure of efficiency in
going from cooperative to noncooperative framework, and obtained expressions
for it for FB and OL LQ DGs . Here, we study the price of information (PoI) as
a measure of efficiency with respect to the ISs for again the LQ DG. Following
Definition 3, PoI between open-loop and feedback ISs is defined by

$\chi^{OL}_{FB}={\max_{k^{\star}}J^{OL\star}}\,/\,{\max_{k^{*}}J^{FB*}}\,,$
(44)

which can also be expressed in terms of the PoAs under the two ISs:

$\chi_{FB}^{OL}={\rho_{\mu}^{OL}}\,/\,{\rho_{\mu}^{FB}}\,.$

Using Theorem 5, we can obtain a bound on PoI:

$\chi^{OL}_{FB}\geq\frac{k^{\star}}{\mu_{\max}^{s}(\varrho(\mathbf{M})+a)}\,.$

The following theorem further characterizes the PoI in a special case.

###### Theorem 8

Suppose $a=0$, and the number of players is large so that $N$ satisfies (C-i),
(C-ii), and (C-iii). Then, the PoI is bounded from above and below by two
constants:

${\sqrt{2}}/{2}\leq\chi_{FB}^{OL}\leq\sqrt{2}.$ (45)

###### Proof

Under conditions (C-i), (C-ii), and (C-iii), we have a unique feedback NE that
can be approximated as in statement (iv) of Theorem 6. Hence, from (39) we
obtain

$\displaystyle\chi_{FB}^{OL}$ $\displaystyle=$
$\displaystyle\frac{J^{OL\star}}{J^{FB*}}=\frac{\sqrt{2}}{2}\left(1+\frac{\sum_{i=1}^{N}\mu_{i}q_{i}\sigma_{i}}{\bar{q}\bar{\sigma}}\right)$
$\displaystyle=$
$\displaystyle\frac{\sqrt{2}}{2}\left(1+\frac{\sum_{i=1}^{N}\mu_{i}q_{i}\sigma_{i}}{\sum_{i=1}^{N}\mu_{i}q_{i}\sum_{i=1}^{N}\sigma_{i}}\right)\leq\sqrt{2}\,,$

where the last inequality is obtained by noting that

$\sum_{i=1}^{N}\mu_{i}q_{i}\sigma_{i}\geq\sum_{i=1}^{N}\mu_{i}q_{i}\sum_{i=1}^{N}\sigma_{i}\,.$

The lower bound can be achieved by noting that $\sigma_{i},q_{i},\mu_{i}$ are
all nonnegative.

Theorem 8 is useful in the design of games via access control or pricing
mechanisms. Let $\bar{\chi}\in(\frac{\sqrt{2}}{2},\sqrt{2}]$ be some target
PoI to achieve so that $\chi_{FB}^{OL}\leq\bar{\chi}$. For example, when
$\bar{\chi}=1$, it means the game needs to be designed so that the open-loop
NE yields no larger cost than the feedback NE. Hence, a necessary condition to
meet such a design criterion is:

$\frac{\sum_{i\in\mathcal{N}}\mu_{i}q_{i}\sigma_{i}}{\bar{q}\bar{\sigma}}\leq\sqrt{2}\chi_{FB}^{OL}-1.$
(46)

An access control is to admit a set $\mathcal{N}$ of players so that (46) is
satisfied when all the system and player parameters are given. When set
$\mathcal{N}$ is fixed and not adjustable, we may use “pricing” mechanisms to
control the parameters $r_{i}$ or $q_{i}$, which reflect the unit “price” of
penalty on the control effort and the state, respectively. In the following
corollary, we capture the special case of homogeneous players.

###### Corollary 3

Suppose the LQ DG satisfies the conditions in Theorem 8. In addition, let the
players be symmetric so that $\sigma_{i}=\sigma,p_{i}=p,\forall
i\in\mathcal{N}$. When $N\geq 3$, the open-loop IS yields better total optimal
cost; otherwise the FB information does better. In addition, as
$N\rightarrow\infty$,
$\lim_{N\rightarrow\infty}\chi_{FB}^{OL}=\frac{\sqrt{2}}{2}$ at the rate of
$O\left(\frac{1}{N}\right)$.

###### Proof

The proof directly follows from Theorem 8. The price of information under the
additional assumptions becomes
$\chi_{FB}^{OL}=\frac{1}{\sqrt{2}}\left(1+\frac{1}{N}\right)$. It is
independent of the parameters of the players and approaches
$\frac{\sqrt{2}}{2}$ as $N\rightarrow\infty$. By letting $\chi_{FB}^{OL}\leq
1$, we obtain $\;N\geq\,{1}\,/\,({\sqrt{2}-1})\,.$ Hence, since $N$ is an
integer, the open-loop NE does better than the feedback NE when there are $3$
or more players.

Theorem 8 and Corollary 3 have implications in the design of games via access
control when open loop is the preferred mode of play.

##  6 Applications and Illustrations

In this section, we apply the results obtained heretofore to two classes of
application scenarios in flow control.

###  6.1 Multiuser Rate-Based Flow Control

We adopt here the communication systems model described in AB98 , where the
players are the users or sources, and the action (control) variables are the
flows into the network. If a link receives more total flow than what it can
accommodate (measured by its capacity), then packets queue up. Having long
queues is not desirable, because it leads to delays in transmission. We call
such links which are congested bottleneck links, and formulate the game around
one such link. Let $q_{l}(t)$ denote the queue length at such a bottleneck
link and let $s(t)$ denote the total effective service rate available at that
link. Assume that each user is assigned a fixed proportion of the available
bandwidth; more specifically, the traffic of source $i,i=1,2,\ldots,N$, has an
allotted bandwidth of $w_{i}s(t)$, where $w_{i}$’s are positive parameters
which add up to $1$. We assume that the users have perfect measurement of
$s(t)$, but occasionally exceed or fall short of the bandwidth allotted to
them due to fluctuations. Hence, if $d_{i}(t)$ denotes the rate of source $i$
at time $t$, we can introduce $u_{i}(t):=d_{i}(t)-w_{i}s_{r}(t)$ as the
control (action) variable of the source. Then, queue build-up is governed by
the differential equation

$\dot{q_{l}}(t)=\sum_{i=1}^{N}u_{i}(t)\,,$ (47)

where we assume that queue is relatively tightly controlled so that end effect
constraints (starvation and exceeding an upper limit) do not become active.
The goal is to ensure that the bottleneck queue size stays around some desired
level $\bar{q}_{l}$, and good tracking between input and output rates is
achieved. Toward that end, we consider the shifted variable
$x(t):=q_{l}(t)-\bar{q}_{l}$, which satisfies the following differential
equation which is the shifted version of (47):

$\dot{x}(t)=\sum_{i=1}^{N}u_{i}\,\;\;x(0)=x_{0}\,.$ (48)

We now consider a noncooperative scenario in which each source determines a
linear feedback policy (or an open-loop policy) to minimize its own individual
cost function

$L_{i}(u)=\int_{0}^{\infty}\left(|x(t)|^{2}+|u_{i}(t)|^{2}\right)dt,$ (49)

which is consistent with the overall goal of keeping $x$ and $u_{i}$’s small.
We can also consider a related team problem in which sources minimize
cooperatively a common cost under the same information structure (where as we
know actually the IS does not make a difference in this case):

$L(u)=\int_{0}^{\infty}\left(N|x(t)|^{2}+\sum_{i=1}^{N}|u_{i}(t)|^{2}\right)dt.$
(50)

This is now within the framework of LQ DGs studied earlier, with the
correspondences being $a=0,x_{0}=1,\sigma_{i}=s_{i}=q_{i}=r_{i}=b_{i}=1$ in
(5) and (6). To obtain some numerical results, let us take $x_{0}=1$.

In the case of the 2-person LQ feedback game, the $M$ matrix introduced
earlier becomes

$\mathbf{M}_{2}=\left[\begin{array}[]{cccc}0&1&1&0\\\ 1&0&0&-1\\\ 1&0&0&-1\\\
0&1/3&1/3&0\end{array}\right]$

and if $N=3$, we have

$\mathbf{M}_{3}=\left[\begin{array}[]{cccccccc}0&1&1&1&0&0&0&0\\\
1&0&0&0&-1&-1&0&0\\\ 1&0&0&0&-1&0&-1&0\\\ 1&0&0&0&0&-1&-1&0\\\
0&1/3&1/3&0&0&0&0&-1/3\\\ 0&1/3&0&1/3&0&0&0&-1/3\\\ 0&0&1/3&1/3&0&0&0&-1/3\\\
0&0&0&0&1/5&1/5&1/5&0\end{array}\right].$

The positive eigenvalue of $\mathbf{M}_{2}$ is $\lambda_{2}=1.1547$ and the
corresponding vector is
$\mathbf{p}_{2}=\mathbf{k}_{2}=[1.0000,0.5774,0.5774,0.3333]^{T}$. The sum of
the optimal costs under equal weights is $J^{*}_{2}=0.5774$ while the optimal
common cost is $J^{\circ}_{2}=0.5$, yielding the price of anarchy value
$\rho^{FB}_{\mu,2}=1.1547$. For the case with 3 players, the eigenvector is
found to be
$\mathbf{p}_{3}=\mathbf{k}_{3}=[1.0000,0.4472,0.4472,0.4472,0.2000,0.2000,0.2000,0.0894]^{T}$
corresponding to $\lambda_{3}=1.3416$. Again under equal weights, the total NE
cost is $J^{*}_{3}=0.4472$ and the minimum social cost is
$J^{\circ}_{3}=0.3333$. Hence, the price of anarchy is given by
$\rho^{{FB}}_{\mu,3}=1.3416$. When the number of players becomes large,
$\rho^{FB}_{\mu}\sim\sqrt{\frac{N}{2}}$ from Theorem 6.

In the case of open-loop flow control, we obtain
$k^{\star}_{i}=\frac{1}{\sqrt{N}}\left(\frac{1}{2}+\frac{1}{2N}\right)$ and
total NE cost as $J^{\star}_{N}=k^{\star}$. In the 2-user game,
$J^{\star}_{2}=0.5303$ yielding the price of information
$\chi_{FB}^{OL}=0.9184$. The open-loop NE thus yields $8.16\%$ less cost in
comparison to the closed-loop FB one. In a 3-user game,
$J^{\star}_{3}=0.3849$, leading to a price of information value of
$\chi_{FB}^{OL}=0.8607$, which yields a $13.93\%$ more cost for the FB IS
case. We also note that as the number of players increases, the open-loop IS
yields a cost approaching $0$, i.e.,
$\lim_{N\rightarrow\infty}J_{N}^{\star}=0$, while in the feedback case, even
though it still converges to $0$, the rate is slower:
$J^{*}\sim\frac{1}{\sqrt{2N}}\rightarrow 0$. We observe that $\chi_{FB}^{OL}$
goes to $\frac{\sqrt{2}}{2}$ at a rate of $\frac{1}{N}$ as $N$ gets large,
i.e.,

$\lim_{N\rightarrow\infty}\chi_{FB}^{OL}=\frac{\sqrt{2}}{2}+\frac{1}{2N}\rightarrow\frac{\sqrt{2}}{2}.$

It is also noted that open-loop NEs always yield less equilibrium costs even
though they require less information.

Due to the symmetry of players in the flow control problem, we can obtain
exact closed-form solutions to the equilibrium costs using (18) and (14)
without approximation. It is not hard to show that under equal weights,

$J^{*}_{\mbox{OL}}=k_{i}=\frac{1}{\sqrt{2N-1}}\,,\;\;J^{\star}_{\mbox{FB}}=\frac{1}{\sqrt{N}}\left(\frac{1}{2}+\frac{1}{2N}\right)\,\;\;\mbox{and}\;\;J^{\circ}=\frac{1}{N}\,.$

In Figure 1, we show the price of information under open-loop and feedback
information structures, and in Figure 2, we show the corresponding prices of
anarchy. By exact calculation, we find when $N=4$, the open-loop NE cost to be
$J^{\star}_{4}=\frac{3}{8}=0.3125$, which catches up with and becomes better
than the feedback NE cost: $J^{*}_{4}=\frac{1}{\sqrt{7}}=0.378$.This is
consistent with our earlier observation based on large population
approximation.

We observe in Figure 1 that the NE costs are the same at $N=1$ (as they should
be), and as $N$ increases, both open-loop and feedback NE costs decrease. As
$N$ becomes large, both costs approach $0$. This happens because the queue
length is fixed. When the number of players goes to infinity, the contribution
from each user is negligible. Moreover, the state $x(t)$ can be driven to zero
very fast as the amount of total control effort increases with the number of
players. The cost incurred from the transient behavior of $x(t)$ then goes to
zero. In addition, for $N\geq 2$, open-loop NE yields better costs. The price
of information $\chi_{FB}^{OL}$ is always below $1$ but maintains its level
above $\frac{\sqrt{2}}{2}$. In Figure 2, the price of anarchy starts at $1$
when $N=1$ and increases as the number of players grows. The cost under the
feedback NE grows faster than the one under open-loop NE.

Figure 1: Price of Information Figure 2: Price of Anarchy

###  6.2 Normalized Flow Control Dynamics

In this section, we investigate a general flow control dynamics, which differs
from (48) by inclusion of a population-dependent normalization factor $f(N)$,
where $f(\cdot)$ is an increasing function of $N$:

$\dot{x}(t)=\frac{1}{f(N)}\sum_{i=1}^{N}u_{i}\,,\;\;\;x(0)=1\,.$ (51)

The introduction of a normalization factor is to adjust the queue length
proportionally when the number of users increases.

###### Proposition 1

The prices of anarchy $\rho_{\mu}^{OL},\rho_{\mu}^{FB}$, and the price of
information $\chi_{FB}^{OL}$ are independent of the normalization factor
$f(N)$, as summarized in Table 1.

Table 1: Various indices for normalized flow control game $J^{*}$ (FB) |  $J^{\circ}$ (TP) |  $J^{\star}$ (OL) | $\rho_{\mu}^{FB}$ | $\rho_{\mu}^{OL}$ | $\chi_{FB}^{OL}$
---|---|---|---|---|---
$\frac{f(N)}{\sqrt{2N-1}}$ | $\frac{f(N)}{N}$ | $\frac{f(N)}{\sqrt{N}}\left(\frac{1}{2}+\frac{1}{2N}\right)$ | $\frac{N}{\sqrt{2N-1}}$ | $\sqrt{N}\left(\frac{N+1}{2N}\right)$ | $\sqrt{2-\frac{1}{N}}\left(\frac{1}{2}+\frac{1}{N}\right)$

###### Proof

Using (18) and (14), we obtain $p_{i}$ for a given $N$ as follows:

$\displaystyle\bar{p}$ $\displaystyle=$
$\displaystyle\frac{N}{f(N)}\frac{1}{\sqrt{2N-1}},$ $\displaystyle p_{i}$
$\displaystyle=$ $\displaystyle\frac{1}{f(N)\sqrt{2N-1}},$ $\displaystyle
k_{i}$ $\displaystyle=$
$\displaystyle\frac{p_{i}}{s_{i}}=\frac{f(N)}{\sqrt{2N-1}},$ $\displaystyle
J^{*}$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{N}\frac{1}{N}k_{i}x_{0}^{2}=k_{i}.$

The team problem yields an optimal cost of

$J^{\circ}=\sqrt{\frac{\bar{q}}{\bar{b}}}=\frac{f(N)}{N}.$ (52)

Hence, the price of anarchy $\rho_{\mu}^{FB}$ under the state-feedback
information structure is independent of $f(N)$, and is given by

$\rho_{\mu}^{FB}=\frac{N}{\sqrt{2N-1}}$ (53)

The open-loop price of anarchy is also independent of the factor $f(N)$. Since
$J^{\star}=\frac{f(N)}{\sqrt{N}}\left(\frac{1}{2}+\frac{1}{N}\right)$, it is
given by

$\rho_{\mu}^{OL}=\sqrt{N}\left(\frac{N+1}{2N}\right).$ (54)

The price of information is also independent of $f(N)$, and given by

$\chi_{FB}^{OL}=\sqrt{2-\frac{1}{N}}\left(\frac{1}{2}+\frac{1}{N}\right).$
(55)

As a case study, we let $f(N)=\frac{1}{N}$. Then, $b_{i}=\frac{1}{N}$,
$s_{i}=\sigma_{i}=\frac{1}{N^{2}}$, for all $i\in\mathcal{N}$. When the
population is large, we have $J^{*}\sim\sqrt{\frac{N}{2}}$ and
$J^{\star}=\sqrt{N}\left(\frac{1}{2}+\frac{1}{N}\right)$. The price of anarchy
remains $\rho\sim\sqrt{\frac{N}{2}}$. The price of information remains
$\chi_{FB}^{OL}=\frac{\sqrt{2}}{2}+\frac{\sqrt{2}}{2N}\rightarrow\frac{\sqrt{2}}{2}$
as $N\rightarrow\infty$. It can be shown that $\chi_{FB}^{OL}$ does not change
with the factor $f(N)$. In Figures 3 and 4, we show the prices based on the
exact closed form solution obtained in the same fashion as in the previous
section based on (18) and (14). We observe that the open-loop NE always
outperforms the feedback equilibrium. It should be pointed out that (i) in
Figure 3, the open-loop and feedback costs increase with the number of users.
This is due to the introduction of normalization factor into the system
dynamics. We allocate the queue length as an increasing function of the number
of users; (ii) Figures 4 and 2 are identical due to the above proposition.

If we set $f(N)=\sqrt{N}$, we have the open-loop and feedback optimal costs
approach $\frac{1}{2}$ and $\frac{\sqrt{2}}{2}$ respectively, as
$N\rightarrow\infty$. Figure 5 demonstrates that result.

Figure 3: Price of Information in the Normalized System, $f(N)={N}$ Figure 4:
Price of Anarchy in the Normalized System, $f(N)={N}$ Figure 5: Price of
Information in the Normalized System, $f(N)=\sqrt{N}$

A summary of the results with $f(N)=1$ and $f(N)=\frac{1}{N}$ under large
population approximation is provided in Table 2.

Table 2: Indices under two normalization factors using the large population approximation $f(N)$ |  $J^{*}$ (FB) |  $J^{\circ}$ (TP) |  $J^{\star}$ (OL) | $\rho_{\mu}^{FB}$ | $\rho_{\mu}^{OL}$ | $\chi_{FB}^{OL}$
---|---|---|---|---|---|---
$1$ | $\frac{1}{\sqrt{2N}}$ | $\frac{1}{N}$ | $\frac{1}{\sqrt{N}}\left(\frac{1}{2}+\frac{1}{2N}\right)$ | $\sqrt{\frac{N}{2}}$ | $\sqrt{N}\left(\frac{1}{2}+\frac{1}{2N}\right)$ | $\frac{\sqrt{2}}{2}+\frac{\sqrt{2}}{2N}$
$\frac{1}{N}$ | $\sqrt{\frac{N}{2}}$ | $1$ | $\sqrt{N}\left(\frac{1}{2}+\frac{1}{2N}\right)$ | $\sqrt{\frac{N}{2}}$ | $\sqrt{N}\left(\frac{1}{2}+\frac{1}{2N}\right)$ | $\frac{\sqrt{2}}{2}+\frac{\sqrt{2}}{2N}$

##  7 Conclusion

In this paper, we have introduced the notions of price of anarchy, price of
information, and price of cooperation for nonzero-sum differential games, have
studied the first two extensively for a class of scalar linear-quadratic
differential games, and have obtained bounds and approximations on them, with
computable bounds available in the large population regime. Future promising
work is to extend these results to non-scalar differential games as well as to
obtain their counterparts for the price of cooperation. Also computing these
indices for specific models from communication networks and economics would be
a fruitful area of research.

## References

  * (1) T. Alpcan, T. Başar, R. Srikant, and E. Altman, “CDMA uplink power control as noncooperative game,” Wireless Networks, 8:659-690, 2002.
  * (2) E. Altman and T. Başar, “Multiuser rate-based flow control,” IEEE Trans. Communications, 46(7):940-949, 1998.
  * (3) E. Altman, T. Boulogne, R. El-Azouzi, T. Jimnez, and L. Wynter, “A survey on networking games in telecommunications,” Computers and Operations Research, 33(2):286-311, February 2006.
  * (4) A.P. Azad, E. Altman, and R. El-Azouzi, “Routing games: From egoism to altruism,” Proc. 8th International Symp Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt 2010), Workshop WNC3 2010, pp. 442-451, Avignon, France, May 31-June 4, 2010.
  * (5) T. Başar, “A contradictory property of the Nash solution for two stochastic nonzero-sum games,” Proc. 10th Allerton Conf on Circuit and System Theory, pp. 819-827, October 1972.
  * (6) T. Başar, “Time consistency and robustness of equilibria in noncooperative dynamic games,” in F. Van der Ploeg and A. de Zeeuw, editors, Dynamic Policy Games in Economics, pp. 9–54. North Holland, 1989.
  * (7) T. Başar, “Control and game-theoretic tools for communication networks (Overview),” Appl. Comput. Math. , 6(2):104-125, 2007.
  * (8) T. Başar and Y.C. Ho, “Informational properties of the Nash solutions of two stochastic nonzero-sum games,” J. Economic Theory, 7(4):370-387, April 1974.
  * (9) T. Başar and G. J. Olsder, Dynamic Noncooperative Game Theory, 2nd ed., SIAM Series in Classics in Applied Math., Philadelphia, 1999.
  * (10) E. Dockner, S. Jorgensen, N. V. Long, and G. Sorger, Differential Games in Economics and Management Science, Cambridge University Press, 2006.
  * (11) P. Dubey, “Inefficiency of Nash equilibria,” Math. Operations Research, 11(1), February 1986.
  * (12) J. C. Engwerda, “Feedback Nash equilibria in the scalar infinite horizon LQ-game,” Automatica, 36:135-739, 2000.
  * (13) J. C. Engwerda, “The solution set of the N-player scalar feedback Nash algebraic Riccati equations,” IEEE Trans. Automatic Control, 48:847-853, 2000.
  * (14) J. C. Engwerda, LQ Dynamic Optimization and Differential Games, Wiley, 2005.
  * (15) J. Grossklags, B. Johnson, and N. Christin, “The price of uncertainty in security games,” Proc. Eighth Workshop on the Economics of Information Security (WEIS), 2009.
  * (16) R. Johari, S. Mannor, and J. Tsitsiklis, “Efficiency loss in a network resource allocation game: the case of elastic supply,” IEEE Trans. Automatic Control, 50(11):1712-1724, 2005.
  * (17) R. Johari and J. Tsitsiklis, “Network resource allocation and a congestion game: The single link case,” Proc. 42nd IEEE Conf. Decision and Control (CDC), pp. 2112-2117, December 2004.
  * (18) R.T. Maheswaran and T. Başar, “Nash equilibrium and decentralized negotiation in auctioning divisible resources,” J. Group Decision and Negotiation (GDN) , 13, October 2003.
  * (19) T. Roughgarden and E. Tardos, “Bounding the inefficiency of equilibria in nonatomic congestion games,” Games and Economic Behavior, 47:389-403, 2004.
  * (20) S. Shakkottai, R. Srikant, A. Ozdaglar, and D. Acemoglu, “The price of simplicity,” IEEE J. Selected Areas in Communication: Game Theory in Communication Systems, 26(7), 2008.
  * (21) Q. Zhu and T. Başar, “Price of anarchy and price of information in $N$-person linear-quadratic differential games,” Proc. American Control Conf. (ACC), Baltimore, Maryland, June 2010.
  * (22) Q. Zhu and L. Pavel, “Stackelberg game approach in OSNR optimization of optical networks with capacity constraints,” Proc. American Control Conf. (ACC), pp. 762-767, 2008.
  * (23) Q. Zhu and L. Pavel, “State-space approach to pricing design in OSNR Nash games,” Proc. IFAC Congress, Seoul, Korea, 2008.