Amnon Meisels


... on our way to Changu Narayan...

my Kids (from Back...)
and Full faces

am@cs.bgu.ac.il

Research interests
Games on Networks (GoNs)
Public Goods Games (PGGs)
Distributed Constraint Processing 
Multi-agent (Distributed) Optimization problems  

 

The general area of distributed constraints processing has been at the center of my research for the last 25years. The natural focal point of my group over the years was that of representing and solving Multi-agent Optimization Problems  Distributed Constraint Optimization Problems (DCOPs) have served for two decades as a crystal clear laboratory for multi-agent search algorithms, due to the unique clarity of the problem definition - Vriables; Domains; (well-defined) Constraints. Our group's work produced the best performing concurrent search algorithms; concurrent measures of performance; and concurrent heuristics.

Having produced the best performing distributed search algorithms on DCOPs, we have moved our focus in the last ten years to Asymmetric DCOPs (ADCOPs). ADCOPs have constraints among agents such that the gains of the agents from a given constraint between them are not equal. In other words, the constraints matrices become Bi-matrices. Consequently, the general constraints are equivalent to normal form games among pairs of agents.

This lead to focusing our research in two fields:

      Games on Networks (GoNs) (ADCOPs JAIR 2013), where the two-agent games are general bi-matrices

       Distributed (multi-agent) search algorithms on some specific GoNs:

o   Charging electric vehicles  

o   Solving Boolean Games by using incentives  

The natural next step was to consider an important family of games on networks that have been studied extensively in both economics and sociology - Public Goods Games (PGGs) and to designing multi-gent (distributed) search algorithms for Solving PGGs by using Incentives

The major step forward was taken in 2018, when the idea of adding side payments among neighboring agents on the network was first added to search algorithms on ADCOP search by Selfish Agents and became the Iterative Nash Efficiency Enhancement (INEA) algorithm presented and published in 2018.

In the same two years my group has also worked on the Public Goods Game (PGG) which is a well researched example of a Game on Networks. PGGs have played an important role in economics and in social sciences for the last two decades. Our research on finding efficient solutions for PGGs produced two major results. One, that PGGs are potential games (for K=1). The other (and more important), is a search algorithm for PGGs that uses side payments among agents and guarantees convergence to stable PGG solutions with higher efficiency.

The next step of my group's intensive research on Games on Networks (GoNs) was taken by Yair Vaknin in designing the best to date search algorithm on Asymmetric DCOPs (ADCOPs). The Bidding Enhanced Efficiency Contracts (BEECon) algorithm uses side payments and improves on the INEA algorithm. BEECon. It turns out that a similar algorithm, that selects the best next option in each neighborhood, can be designed for the Public Goods Game (PGG) and outperforms all former algorithms. Our algorithm guarantees the finding of improved-efficiency PGG solutions, unlike any former algorithm. PGGs by BEECon .

Having established the best search algorithms that use side payments among neighboring agents, for both general binary games (ADCOPs) and general PGGs, the next natural move is to consider the aspect of strategic agents on these GoNs. To this end, we designed our search algorithms to use side payments combined with the VCG mechanism. Thus achieving a truthful enforcing method that guarantees truthful behavior of selfish agents running our search algorithms and guaranteeing convergence to higher efficiency solutions Solving ADCOPs by Strategic Agents.

Recent Publications


ECAI 2023 Tutorial:
Solving Multi-agent Games on Networks by Strategic Agents



 

Address

Department of Computer Science
Ben-Gurion University
Beer-Sheva 84 105, ISRAEL
Phone: +972-8-6461622 (office) Fax: +972-8-6477650
Email: am@cs.bgu.ac.il

Last updated: Wednesday, February 20, 2002