IEEE Computational Intelligence Magazine - November 2023 - 61

v4, respectively, fixed and altering the
opinion z5 from1 to 1, the variations
in the winning probabilities and rewards
ofall the agents can be observed.
FIGURE 1 1D Representation: myopic bestresponses
and a PNE.
wheregj ¼
P
v2Gj zi=jnjj represents the
opinion of group Gj and the winning
probability pjðtÞ ofgroup Gj is
nj
pjðtÞ¼
P
e
i2½m;ni >0 e
DE
P
gj;
P
vr2V sr
ni gi;
vr2V sr
;
where ½m denotes f1; 2; ... ; mg. The
following strategic behaviors ofan agent
in such a game will be considered:
❏ Group Joining: Each agent seeks a
specific group that hopefully maximizes
its reward and then joins the
group.
❏ Opinion Updating without Regularization:
Each agent in a certain
group tries to maximize its reward
by changing its own opinion.
❏ Opinion Updating with Regularization:
Each agent in a certain
group tries to maximize its reward
by changing its own opinion, while
the reward includes the regularization
ksi zik2
2, which hopefully
constrains an agent's strategic behavior
by preventing it from moving
too far from its own belief.
III. Group Joining and Pure-Strategy
Nash Equilibria
A. 1D Representation
When the opinions and beliefs are
assumed to be in ½1; 1 R, these vectors
as well as the dynamics of changes
can be illustrated in a real line. For example,
consider the five agents v1; v2; v3; v4,
and v5 in Figure 1. By keeping the opinions
z1; z2; z3, and z4 of v1; v2; v3, and
B. Group Joining: Myopic Best
Responses
Assume that agent i decides tojoin Gj,for
whichj ¼ arg max'p'ðtÞ hg'; sii.Such a
strategy is called a myopic best response.An
agent joins a group by considering not
only its winning probability but also the
utility that the agent can get from the
group beforejoining. The state at the bottomofFigure
1 is an example ofa PNE.
IV. Opinion Updates by Online
Learning
A.2D Representation
The opinions and beliefs as well as the
dynamics of opinion changes are illustrated
in K :¼fx 2½1; 12 : kxk2 1g
R2. The 2-norm constraint that
kzik2; ksik2 1 correlates the dimensions.
A projection of the opinion is
required ifthe constraint is not satisfied.
B. Online GradientAscent
Consider the setting that each agent
tries to maximize its own reward by
" changing its opinion " without deviating
from the group to which it belongs.
Each agent executes the online gradient
ascent algorithm to iteratively update its
opinion so as to maximize its reward.
The update is done by adding a certain
quantity (tuned by the learning rate h)
toward the direction of the gradient. A
" projection " PKðxÞ which projects x
onto the feasible set K by dividing its 2norm
is performed ifnecessary.
Algorithm 1. Multi-Agent Online
Gradient Ascent.
Input: feasible set K, T, learning rate h.
1: for t 1to T do
2:
3:
4:
5:
end for
6: end for
for each agent i do
observe reward riðtÞ, where state
t ¼ðz; s; GÞ
zi;tþ1 PKðzi;t þ hrzi
riðtÞÞ
FIGURE 2 Opinion updates via the online
gradient ascent with regularization.
C. Online GradientAscent With
Regularization
The reward function for agent i includPing
the regularizer, is defined as riðtÞ¼
kzi sik2
2
j¼1 pjðtÞhsi;gjikzi sik2
m
2. Since
is always non-positive, an
agent will be constrained to consider
" not being too far from its belief. " Our
experimental illustrations show that
such a regularization helps the game
converge to a state where agents' opinions
will not be too far from their beliefs
(see Figure 2).
V. Conclusion
This article presents a preliminary study
on the dynamics of group formation.
From the illustrations, readers can have
a better grasp of a pure-strategy Nash
equilibrium in a system of multi-agents
and also learn how an online gradient
ascent algorithm as one of the dynamics
can reach a stable state.
Acknowledgment
This work was supported in part by the
National Science and Technology Council
under Grants NSTC 112-2221-E-032018-MY3,
NSTC 111-2221-E-005-047-,
and NSTC 111-2410-H-A49-022-MY2.
We also thank Victorien Yen for helping
implement the JavaScript codes in the
immersive article.
References
[1] I. Goodfellow et al., " Generative adversarial networks, "
Commun. ACM, vol. 63, pp. 139-144, 2020.
[2] F. Orabona, " A modern introduction to online
learning, " 2022, arXiv:1912.13213.
[3] C.-C. Lin, C.-J. Lu, and P.-A. Chen, " On the
efficiency of an election game of two or more parties:
How bad can it be?, " 2023, arXiv:2303.14405.
NOVEMBER 2023 | IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE 61
IEEE Computational Intelligence Magazine - November 2023

Table of Contents for the Digital Edition of IEEE Computational Intelligence Magazine - November 2023
