26/06/2025
WHO: Prof. Yair Vaknin, Ben Gurion University of the Negev
WHEN: Thursday, June 26th 2025 at 12:00
WHERE: BUILDING 503 (Computer Science) AUDITORIUM
Title: Solving Games on Networks
Abstract:
Multiagent decision-making settings feature a tension between the individual interests of agents and the promotion of a common good. These typical situations are often modeled as games. Games that are played among a large number of agents on a social network, where the utility of an agent depends on the joint action of a limited set of neighbors, are termed games on networks (GoNs).
In a GoN, all agents are assumed to be selfish. Typical optimization approaches in multiagent systems (MAS) has agents collaboratively execute distributed incomplete search algorithms. Due to the game-like strategic character of agents in a GoN, such a technique that implies fully cooperative agents sharing information to obtain a greater efficiency seems inappropriate.
We propose to take a different stand, and stresses game-theoretical aspects in multi-agent games on networks. All agents are assumed to be selfish, and accordingly – their coordination throughout the execution of the proposed incentive-based distributed algorithm is achieved via calls to a truthful mechanism. The resulting method guarantees the convergence of the system towards a stable state – even for games that do not have an equilibrium state in their original form. This final state is guaranteed to be at least as efficient as the initial state of the system.
An experimental evaluation on various types of GoNs demonstrates the performance of the algorithm and shows several interesting results. The method obtains vast cooperation in a game of Prisoner’s Dilemma on networks, and outperforms a former incentive-based algorithm on Public Goods Games on networks. Efficiency and stability are guaranteed due to payments to the truthful mechanism, and the experimental evaluation compares these payments to the overall gain of the system.
Short BIO:
Yair Vaknin is a PhD student at Ben Gurion University of the Negev. His research integrates concepts from game theory and distributed search / optimization, proposing a distributed protocol that selfish agents in a multi-agent system can execute to enhance global efficiency. This framework offers a new perspective on games on networks and multi-agent systems.
