Signal Processing - January 2016 - 96

■ give the reader a global-although necessarily partial-
overview of GT highlighting connections and differences
between strategic- and coalition-form games in a single article
■ delineate differences and connections between GT and
optimization
■ explain the strong relationship between game-theoretic
solution concepts, such as the Nash equilibrium (NE), and
distributed SP algorithms
■ provide many application examples to help the reader
understand the way the described tools can be applied to different contexts.
For absolute beginners in GT, we refer readers to a recent
lecture note [27], whereas we invite those interested in a thorough and textbook-oriented discussion on GT applied to wireless communications and SP to refer to the textbooks [22] and
[23]. For the reader's convenience, Table 1 lists the acronyms for
the game-theoretic terms used throughout the tutorial, and
Figure 1 provides a reference for the structure of this tutorial,
adopting the typical methodology used to address the game-theoretic problems and listing the topics described in each section.

STrATEGIc-ForM GAMES
DEFINITION
A game in strategic (equivalently, normal) form is represented by a
family of multivariate functions u 1, f, u K ; K $ 1. The index set
of this family, which is denoted here by K = {1, f, K}, is called
the set of players and, for each k ! K, u k is commonly called the
utility (equivalently, payoff) function of player k. The strategic
form assumes that u k can be any function of the following form:
u k: S 1 # f # S K $ R
(s 1, f, s K )
8 u k (s),

(1)

where S k is called the set of strategies of player k, s k is the strategy of player k, s = (s 1, f, s K ) ! S is the strategy profile, and
S = S 1 # f # S K . We refer to a strategic-form game by using
the compact triplet notation G = ^K, (S k) k ! K , (u k) k ! K h . The
notation s -k = (s 1, f, s k - 1, s k + 1, f, s K ) is used to denote the
strategies taken by all other players, except player k. With a slight
abuse of notation, the whole strategy profile is denoted by
s = (s k, s -k). The strategic-form representation may encompass a
large number of situations in SP. To mention a few, players in a
game can be radars competing to improve their performance in

terms of the probability of false alarms or missed detections; sensors in a sensor network, which coordinate to estimate a field in a
distributed way; base stations allocating the resources in a cellular
network to optimize the system throughput; several digital signal
processors, which have to compete for or manage computing
resources; or a watermarking device or algorithm, which has to
find a good strategy against potential attackers.
Formally, it is worth noting that, in its general formulation,
the strategic form is characterized by the simultaneous presence
of two key features:
■ Each player k can have its own objective, which is captured by a per-player specific function u k (s).
■ Each player k has partial control over the optimization
variables as it can control its strategy s k ! S k only.
Although the first feature is tied with multiobjective optimization,
a clear difference exists in the control of the optimization variables because, in multiobjective optimization, one has full control
over all the variables. Additionally, quite often in multiobjective
optimization problems (see, e.g., [28]), an aggregate objective
must be defined. The second feature is closely related to the
framework of distributed optimization, although a common
objective function is usually considered in this context, i.e., 6k
u k (s) = u (s). More importantly, the conventional assumption in
distributed optimization is that the decision-making process is
basically driven by a single designer (controller), which provides a
set of strategies that the players strictly follow. Despite being a
possible scenario (which might be very relevant for some algorithmic aspects), in GT, the players, in general, have the freedom to
choose their strategies by themselves.
A central question is how to "solve" a strategic-form game. The
very notion of optimality in this context is unclear since, as previously explained, we are in the presence of multiple objectives, and
the variables, which impact the utility functions, cannot be controlled jointly. This is the reason why the problem needs to be
defined before being solved and why there exists the need for
introducing game-theoretic solution concepts.
SOLUTION CONCEPTS
The NE is a fundamental solution concept for a strategic-form game,
on which many other concepts are built. This section is mostly dedicated to the NE and discusses more briefly other solution concepts
that might also be considered. In [29], Nash proposed a simple but
powerful solution concept, which is now known as an NE (equivalently, Nash point).

[TABLE 1] A LIST oF GT AcronYMS uSEd ThrouGhouT ThIS TuTorIAL.
BR
BRD
CCE
CE
CF
FP
NBS
NE
NTU

BEST RESPONSE
BEST-RESPONSE DYNAMICS
COARSE CORRELATED EQUILIBRIUM
CORRELATED EQUILIBRIUM
CHARACTERISTIC FUNCTION
FICTITIOUS PLAY
NASH BARGAINING SOLUTION
NASH EQUILIBRIUM
NONTRANSFERABLE UTILITY

OCF
PF
PO
POA
RL
RM
SE
SO
TU

IEEE SIGNAL PROCESSING MAGAZINE [96] JANuARy 2016

OVERLAPPING COALITION FORMATION
PARTITION FUNCTION
PARETO OPTIMALITY
PRICE OF ANARCHY
REINFORCEMENT LEARNING
REGRET MATCHING
STRONG EQUILIBRIUM
SOCIAL OPTIMALITY
TRANSFERABLE UTILITY

Table of Contents for the Digital Edition of Signal Processing - January 2016