IEEE Computational Intelligence Magazine - November 2023 - 60

AIeXplained
Chuang-Chieh
Lin
Tamkang University, TAIWAN
Chih-Chieh Hung
National Chung Hsing University, TAIWAN
Chi-Jen Lu
Academia Sinica, TAIWAN
Po-An Chen
National Yang Ming Chiao Tung University, TAIWAN
Group Formation by Group Joining and Opinion Updates
Via Multi-Agent Online Gradient Ascent
Abstract
T
his article aims to exemplify
best-response dynamics and
multi-agent online learning
by group formation. This extended
abstract provides a summary of the full
paper in IEEE Computational Intelligence
Magazine on the special issue
AI-eXplained (AI-X). The full paper
includes interactive components to
facilitate interested readers to grasp the
idea of pure-strategy Nash equilibria
and how the system of strategic agents
converges to a stable state by the
decentralized online gradient ascent
with and without regularization.
I. Introduction
GAME theory has been applied in a
variety of situations due to its predictability
of outcomes in the real world. It
can also be used in solving problems,
such as saddle-point optimization that
has been used extensively in generative
adversarial network models [1]. In general,
a game consists of strategic agents,
each of which acts rationally to maximize
its own reward (or utility) or minimize
its cost. A Nash equilibrium is a
stable state composed ofthe strategies of
all agents such that none of the agents
wants to change its own strategy unilaterally.
Therefore, such a stable state is
Digital Object Identifier 10.1109/MCI.2023.3304084
Date ofcurrent version: 17 October 2023
possibly achievable or even predictable.
However, how to achieve a Nash equilibrium
in a game may not be quite
straightforward, especially when agents
behave in a " decentralized " way.
Indeed, when an agent's reward function
depends on the strategies of the
other agents, the maximizer of one
agent's reward function is not necessarily
a maximizer for any other agent, and
it may change whenever any other
agent changes its strategy.
This article examines the group formation
of strategic agents to illustrate
their strategic behaviors. A strategic
agent can either join a group or change
its opinion to maximize its reward. The
eventual equilibrium ofthe game hopefully
suggests predictable outcomes for
the whole society. For the case in which
agents apply group-joining strategies,
the pure-strategy Nash equilibrium (PNE)
is considered as the solution concept,
where a pure strategy means a strategy
played with a probability of 1. For the
case in which agents change their opinions,
each agent executes an online gradient
ascent algorithm, which guarantees the
time-average convergence to a hindsight
optimum for a single agent (see [2]
for the cost-minimization case), in a
decentralized way, and then the possibly
convergent state of the system is
investigated.
Corresponding author: Chih-Chieh Hung (e-mail:
smalloshin@nchu.edu.tw.
60 IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE | NOVEMBER 2023
II. Group and Opinion Formation
Given a set V of n agents v1; v2; ... ; vn,
each agent vi is represented by a public
preference vector zi and a private preference
vector si, such that the former (i.e., an
opinion) corresponds to the preference
revealed to all the agents while the latter
corresponds to its belief, which is
unchangeable. Consider si; zi 2K such
that K :¼fx 2½1; 1k
: kxk2 1g
Rk is the feasible set. Each dimension of
the domain stands for a certain social
issue, where1 maps to the far-left
politics, while 1 maps to far-right politics.
The bounded 2-norm constraint is
in line with the bounded rationality ofa
person, or the bounded budget for a
group. Denote by z ¼ðz1; z2; ... ; znÞ
and s ¼ðs1; s2; ... ; snÞ the two profiles
that include each agent's opinion and
belief, respectively. Each agent is initially
regarded as a group. The opinion of
a group is the average of the opinions of
its members. Similar to the monotone setting
in [3], a group wins with higher
odds if its opinion brings more utility to
all the agents. The reward (i.e., payoff) of
an agent is the expected utility that it
can get from all the groups. Specifically,
assume there are currently m n groups
G1; G2; ... ; Gm, and denote by jGij¼
ni the number ofmembers in group Gi.
Let G¼ ðG1; G2; ... ; GmÞ denote the
profile of the groups. To ease the notation,
let t ¼ðz; s; GÞ denote the state of
the game. The reward function of
agent i
is riðtÞ¼
Pm
j¼1 pjðtÞhsi;gji,
1556-603X ß 2023 IEEE
https://orcid.org/0000-0001-5145-5839 https://orcid.org/0000-0002-6972-6577 https://orcid.org/0000-0003-0835-1190 https://orcid.org/0009-0004-0135-1918
IEEE Computational Intelligence Magazine - November 2023

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