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.