The Chinese University of Hong Kong
Department of Computer Science and Engineering


Title: Distributed Search by Self-Interested Agents
Date: May 19, 2015 (Tuesday)
Time: 11:00 a.m. - 12:00 noon
Venue: Room 121, 1/F, Ho Sin-hang Engineering Building,
The Chinese University of Hong Kong,
Shatin, N.T.
Speaker: Prof. Amnon Meisels
Department of Computer Science
Ben Gurion University



Distributed search by constrained agents is a well-developed field of research (many times called distributed constraints reasoning - DCR). Its basic assumption is that all participating agents are cooperative. In other words, that all agents exchange messages truthfully about their costs and states and cooperate in arriving at a globally optimal solution. However, in many real world situations Agents are naturally self-interested and cannot be expected to cooperate on search for a global solution. Rather they are naturally viewed as performing only actions that lead to a higher utility for them. The talk will start by describing this common situation and relating it to Asymmetric Distributed Constraints Optimization (ADCOPs). Next, an example of a very simple network based multi-agents interaction will be presented and an interesting "solution" for it will be defined and shown to be reachable by cooperative search of the agents. This example demonstrates, in our view, that cooperative search may be used for network situations of self-interested agents. To better understand the presented view, simple questions about the rationality of cooperation will be raised. In order to move on in the direction of cooperative search by self-interested agents, one can attempt to look at a more general model of network-based games - Boolean games. The simple model of Boolean games will be presented and the fundamental question of incentives for the agents to arrive at an equilibrium state. Our answer to this question will be presented if time permits and shown to use distributed search algorithm for ADCOPs. In general, the talk will assume no prior knowledge of distributed constraints or network based games and will present these concepts through simple examples. Some of our preliminary results on these domains will be presented and (I hope) many thought-provoking multi-agents situations and questions.



Prof. Amnon Meisels has been a faculty member of the department of Computer Science at Ben-Gurion University for the last 25 years. Served as head of the Computer Science department from 2004 to 2006. The main field of research of Amnon Meisels is Distributed Constraints Reasoning and in the last 5 years a major effort has been to investigate models for self-interested agents in Distributed Constrained Search. His book "Distributed Search by Constrained Agents", was published by Springer Verlag in January 2008. Since 2002 Prof. Meisels has lead a group of graduate students at BGU that have established algorithmic standards for distributed search on distributed constraints satisfaction problems (DCSPs) and distributed constraints optimization problems (DCOPs). These include the best performing DCR algorithms for DCSPs - AFC & ConcDB - and for DCOPs - AFB & ConcFB. Prof. Meisels has served on the program committees of all major AI conferences that deal with constraints-based reasoning over the last 7 years. Specifically for Constraints Processing (CP conferences); IJCAI; ECAI; and the series of PATAT conferences on Automatic Timetabling, where he serves on the steering committee since 2000. In addition he has been part of the organizing committee of the series of workshops on distributed constraints reasoning (DCR series) every year since 2003.


Enquiries: Miss Evelyn Lee at tel 3943 8444

For more information, please refer to