*Solving Multi-agent Games on Networks by
Strategic Agents*

*A 90-Minute “spotlight” Tutorial – **ECAI 2023*

*Yair Vaknin and Amnon Meisels*

Two-sentences:

Games on networks (GoNs), played by multi-agents, will be described with
special focus on Public Goods Games. The tutorial will focus on search methods
for finding good solutions to GoNs, on the idea of
side-payments among interacting agents and on a mechanism that enforces truthful
behavior among strategic agents.

Abstract:

Multi-agent games on
networks (GoNs) have nodes that represent agents and
edges that represent games/interactions among agents. An important example in
economics and in multi-agent research is the model of public goods games
(PGGs). In a PGG agents can either contribute the cost of a single good or
free-ride, and agents benefit from copies of the good bought by their
neighboring agents. Another family of examples includes well known games, such as
anti-coordination games played among multiple agents on a network. Solutions to
games on networks are stable states (i.e., pure Nash equilibria - PNEs), and in
general one is interested in efficient solutions (of high social welfare).

The tutorial focuses on Multi-agent search algorithms for GoNs
and in particular algorithms that use side payments among the neighboring/interacting
agents during search. An important result of the last years is that algorithms
that use side payments are proven to converge to solutions that are more
efficient than the initial strategy profile. This is true for GoNs with general binary games among neighboring agents and also for the general family of PGGs. The use of side
payments among agents raises naturally the question of bidding strategically by
the searching agents. The tutorial will introduce the concept of a VCG
mechanism for bidding and propose a method for incorporating it in the search
algorithm. The second major result is that the bidding mechanism does not change
the convergence results and an extensive experimental evaluation will be
presented to demonstrate its interesting behavior on randomly generated scale
free networks of GoNs and PGGs. The proposed
algorithm is shown experimentally to outperforms both best-response dynamics
and a former incentive-based PGG search algorithm. Its solutions are more
efficient and of higher fairness among all agents, as measured by the Gini
index.

Detailed Tutorial Description:

· What are games on networks –
several examples of games among agents on a graph (a social network) will be
introduced: general binary games among neighboring agents (also known as
ADCOPs); networks with well-known 2-person games among neighbors (e.g.,
prisoner’s dilemma and coordination games); an important economic example -
Public Goods Games.

· Solutions – the simplest common
solution concept for games is the pure Nash equilibrium (a PNE) – a stable state from which no selfish
agent would deviate. For multiple agents on a network this solution concept
fits very well. The quality of a solution is given by its efficiency and
fairness, and there are well-known measures for these criteria. When multiple
agents play the game, the important features of a solution become global. The
quality of the solution of each agent (played against several neighboring
agents) is part of the Global Social welfare which is the total gain of all
agents on the graph.

· Finding solutions –
“best-response” is a well-known algorithm for finding stable states of
potential games. This is applicable and will be described for PGGs. The
innovative method that will be presented applies to more general GoNs and uses side payments among agents during search. The
method guarantees convergence to stable states on general multi-agent GoNs.

· Multi-agent search algorithms and
the use of side payments – two recent search algorithms for general binary
games on networks and for public goods games will be described in detail
together with examples of runs on small problems.

· Most important guarantee – the
improved algorithm converges towards a local optimum of the social welfare on a
general multi-agent GoN. In contrast, the former
incentive-based algorithm (as well as best response) running on a general GoN may converge on a stable solution that is not as
efficient as the initial strategy profile.

· An important special case –
public goods games will be highlighted with detailed examples of the run of the
incentive-based algorithms on small examples, that demonstrate the algorithms’
properties and their advantage over former methods.

· A VCG method for enforcing
truthful bidding of side payments during search – a VCG-like bidding mechanism
is integrated into the search process and provides some truthfulness guarantees
with regard to the bids of side payments proposed by
selfish agents during the search process. It turns out that in
order to guarantee truthfulness, the mechanism charges only a small fraction
of the accumulated social welfare.

· Experimental evaluation on
randomly generated large networks – the main evaluation results include fast
convergence; good solutions; only a small fraction of the gain is charged by
the mechanism; an unexpected bonus – the mechanism generates good solutions
which are also of higher fairness.

Target Audience

Researchers and practitioners in the
fields of Multi-agent systems; Games on networks; Distributed
search; Economic multi-agent games on networks; Evolutionary games on networks;
Public Goods Games; Crowdfunding;

The Speakers

*Prof.
Amnon Meisels **am@cs.bgu.ac.il*

*Dept.
of Computer Science, Ben-Gurion University, Beer-Sheva, 8410501, Israel*

Prof. Amnon Meisels has been a faculty member of the
department of Computer Science at Ben-Gurion University for the last 35 years.
He served as head of the Computer Science dept. from 2004 to 2006 and founded
the Software Engineering program in 2000 and served as its head until
2004.

Prof. Meisels’ main field of research centers on
distributed search for constrained optimization and on network-based games that
resemble asymmetric distributed constraints optimization problems (ADCOPs). His
book “Distributed Search by Constrained Agents” was published by Springer
Verlag in January 2008. Prof. Meisels has served and is still serving on
the program committees of all major AI conferences over the last 25 years.

In the last 7 years his group pioneered a major
effort to investigate models for self-interested agents in Distributed
Constrained Search. This research produced several groundbreaking papers. Two
recent examples are "Incentive-based search for efficient equilibria of
the public goods game" (*Artificial Intelligence Journal*, 2018) and "Incentive-based
search for equilibria in Boolean games" (*Constraints*, 2019). Next
came innovative search algorithms for finding efficient pure Nash equilibria in
multi-agent games that were presented in several international conferences (*CP-2018;
WI-IAT 2021; WI-IAT 2022*) and most recently truthful mechanisms for these
algorithms, that validate their use by strategic agents (GAIW-2023).

Prof. Amnon Meisels has published over 140
scientific papers in all main AI Journals, such as AI Journal, JAIR,
Constraints, JAAMAS, and in all major related conferences – IJCAI, AAAI, CP,
AAMAS, and more. Over the years he instructed close to 40 graduate students for
2^{nd} and 3^{rd} degrees at the Computer Science dept. at BGU.

*Mr. Yair Vaknin **yairva@post.bgu.ac.il*

*Dept.
of Computer Science, Ben-Gurion University, Beer-Sheva, 8410501, Israel
*Mr. Yair Vaknin is a
PhD student in his second year, and a teaching assistant at the Computer Science dept.
at Ben-Gurion University. All main subjects of the proposed Tutorial lie at the
core of Mr. Vaknin’s PhD Research. Having explored
distributed optimization for three years, he has focused on the game-aspects of multi-agent systems on networks. His
innovative work integrates related and up-to-date topics of economics, game
theory, and multi-agent search.

Yair published several
papers about the use of side payments in distributed search for optimization
problems. Next, he made the necessary steps into games on networks in general
and has proven his search algorithms guarantee convergence to improved
efficiency solutions. In particular Public Goods Games
(PGGs). His most recent achievement is
the incorporation of a truthful mechanism (i.e., VCG) in the bidding of side
payments by agents during search. This opened the way for using Yair’s
algorithms for strategic agents like those that are expected to play in PGGs.
Yair’s current thrust of research is focused on the design of solving methods
for large games of multiple strategic agents on networks.