Norm-based Coordination in Multi-Agent Systems

12^th September 2014, 10:00 Ashton Lecture Theater
Prof Mehdi Dastani
Intelligent Systems Group
Utrecht University
NL

Abstract

Norms have been widely proposed as a means of coordinating the behaviours of agents. This presentation provides a programming view on norms and how they can be enforced and regimented by means of sanctions. The enforcement and regimentation of norms require monitoring of the agents' behaviours. It is often the case that monitors are imperfect in the sense that they have insufficient observational capabilities to determine if agents' behaviours complies with or violates norms. Instead of enhancing the observational capabilities of monitors one can synthesise an approximation of an ‘ideal’ norm that can be perfectly monitored given a monitor, and which is optimal in the sense that any other approximation would fail to detect at least as many violations of the ideal norm. We give a logical analysis of (im)perfect monitors, study the computational complexity of the norm approximation problem, and give an optimal algorithm for generating optimal approximations of norms given a monitor.