Colloquium on Coordination

Often a problem has to be solved by distributed solvers who are not able to communicate with each other during the problem solving process.
Examples range from reconnaissance missions and distributed violation detection in P2P systems to consistency maintenance in distributed databases.
In this talk, we consider the use of decomposition methods in obtaining a global result (the solution of the problem) by purely local computations (the outcomes of the distributed solvers).

To study decomposition methods we model a problem as a collection of variables whose values are constrained by a set of constraints. To solve such a problem we have either to find an  assignment of values to variables satisfying the constraints or to ensure that some global property such as consistency is preserved.
Such a problem can also be solved in a distributed way. For example, in distributed constraint systems, the set of variables is partitioned and each block of variables is usually viewed as controllable by a separate local agent. Such an agent assigns values to the variables, and the aim is to provide distributed methods enabling a set of agents to come up with a global assignment (solution) that satisfies all the constraints.  Alternatively, the system might be understood as a distributed database.  Here, the focus is on ensuring consistency of the global system if local constraints (the distributed parts of the database) change. In this setting, the aim is to determine whether the existence of a global solution can be guaranteed.  

We say that such a distributed constraint system is decomposed if we can find a global solution, or are able to preserve some global property, by allowing each agent to apply only local constraint processing steps without allowing for communication between the agents. In our talk we discuss some main issues arising in such distributed constraint solving processes without communication. 

First we develop a decomposition framework for distributed constraint systems. Next, we show that the problems of computing a solution a distributed way and the problem of maintaining a property (such as consistency) in a distributed way are in fact equivalent. Then we show that the problem of finding a solution for a constraint system and the problem of finding a suitable decomposition of a constraint system are polynomially related. This fact  explains the popularity of decomposition applied to tractable constraint systems.
Finally, we discuss some applications of decomposition in planning and scheduling.

In this talk, an introduction to the fundamentals of Game theory and Evolutionary Game theory is provided, including some results concerning the effect of complex interaction networks on the learning dynamics of agents in competitive games. In a first part, a number of well-known game theoretical examples are used to explain stability notions, like a (mixed) Nash equilibrium and a Sub-game Perfect equilibrium, and how these equilibria can be determined for symmetric two-player games. The second part will focus on the evolutionary perspective to game theory, after having clarified some other standard approaches to learn these equilibria. In this evolutionary session, the notion of an Evolutionary Stable Strategy will be explained together with the replicator dynamic that allow this type of equilibrium to be reached. In the third part, all this theory will be used to examine the evolution of cooperation/coordination in social dilemmas as defined by games like the prisoners dilemma, the stag hunt game the snowdrift game. Different mechanisms that enhance the survival of cooperative behavior will be discussed, showing how they alter the learning dynamics of the original game into a transformed game. In the final part of this talk, our own contributions to the research on the co-evolution complex networks and individual strategies will be discussed.

Multi-agent systems provide a design approach for developing systems that are able to operate in complex and dynamic environments. Recently many new exciting developments have emerged that facilitate the development multi-agent systems. New technologies for interacting with environments and for managing the organization of agents are now available to ease the design of complex systems. At the same time, agent programming language technology has matured and more sophisticated development environments are available for coding and debugging multi-agent systems. These technologies are now also being applied to build more challenging applications such as real-time games. The aim of this tutorial is to provide participants with a thorough understanding of these new technologies and developments and to provide them with basic skills to develop multi-agent systems themselves.