Coordinating non cooperative planning agents: complexity results

Whenever independent, non-cooperative actors jointly have to solve a complex task, they need to coordinate their efforts. Typical examples of such task coordination problems are supply chain management, multi-modal transportation and patient-centered health care management. Common elements in such problems are a complex task, i.e., a set of interdependent subtasks, and a set of competitive actors. Solving a task coordination problem first of all requires solving a task allocation problem (how to assign competitive actors to the subtasks). As a result, each of the actors receives a set of subtasks to complete and needs to make a plan for this set of tasks. Due to dependencies between tasks, a plan coordination problem has to be solved (how to ensure that a joint plan can always be composed, whatever plan is chosen by the individual actors). The aim of this paper is twofold: first of all to present a general formal framework to study some computational aspects of this non-cooperative coordination problem, and secondly to establish some complexity results and to identify some of the factors that contribute to the complexity of this problem.