Coordinating tasks in agent organizations Or: Can we ask you to read this paper?1 Virginia Dignum Frank Dignum Universiteit Utrecht, The Netherlands, email: {virginia, dignum}@cs.uu.nl One of the main issues in agent organizations is the specification of coordination mechanisms between agents playing roles in a regulated social environment. Both in Organizational Theory as in MAS, the concept of role plays an important role in the specification of coordination. We present a role-based model for organizations that integrates both views. Role hierarchies define the links through which one role can exercise power over, or otherwise influence, other roles. This means that a role can demand the realization of a goal from another role, or request goals from another role. In organizational contexts this can also mean that the responsibility of some tasks lays with the role in the top of the hierarchy. Role dependencies indicate how the goals of different roles depend on each other, and how interaction is to be achieved. Each role dependency indicates a need for coordination between those roles. The way interaction is to be organized between the roles, depends on the organizational power structures between the roles. In this paper, we discuss the implications of the coordination type to the dependencies between roles. Given that one role depends on another to achieve a goal, the realization of that goal depends on the social relationship between the roles, that is, whether the role has power over the other role. We distinguish between hierarchical, network and market social relationships between roles. Role dependencies indicate the relations between roles through which objectives can be passed. Coordination of behavior is relatively easy when dependencies are defined hierarchically, in which case a request from an agent i enacting a superior role to the role that agent j enacts, will result in an obligation for j. In networks and markets, however, coordination requires some more effort. In general, one can identify three different reasons for an agent j to commit itself to a request from another agent i [1]: (a) Power, through which j accepts a request from i because of some domination relationship between them. (b) Authorization is established by mutual agreement, for a certain time and under certain conditions. It indicates that when j has committed itself to i for a certain service, a request from i leads to an obligation when the conditions are met. Finally, (c) Charity means that j will answer a request from i without having any explicit relation to i that forces it to do so. The main difference between power and authorization relationships is that power is structurally determined and, for a great extent, static; that is, power relations are not influenced by the actions of the agents. On the other hand, authorization relations can be created by negotiation between agents; that is, an agent can decide to authorize another agent to request from it a certain action or resource. In the following, we describe the implications of power and authorization relations over the interaction behavior of the agents. To illustrate the effect of communication between roles in different organization types, we will use the example of the dependency for the objective paper review, r, between agent c enacting the role of Program Chair, C, and agent m enacting the role of PC member, M . Different social dependencies give rise to different attitudes concerning the communication: • In a hierarchical relation, the power relation power(c, m, r) holds. Therefore, after request(c, m, r) the obligation Om,c r holds. 1 Published in: COIN@ECAI’06: Workshop on Coordination, Organization, Institutions and Norms in MAS, Riva del Garda, Italy, 28 August 2006 • In a market relation, after request(c, m, r)) an explicit proposal from m to do r and its acceptance by c is necessary in order to have the obligation. That is, to be able to establish the obligation Om,c r, the following (minimal) dialog must occur: c: request(c, M, r) ; m: propose(m, c, r, true) ; c: accept(c, m, r) • In a network relation, not only m has to accept the request, but also c has to agree to a counter request from m (in a conference setting, this would typically be a request to extend the review deadline, e). The following dialog, results in both the obligation Om,c r as in an authorization counter request auth(m, c, request(m, c, e)): c: request(c, M, r) ; m: propose(m, c, r, e) ; c: accept(c, m, propose(m, c, r, e)) The main difference between the market and network situations is the amount of deliberation needed to reach the obligation. Whereas in a market relation, the program chair agent just has to evaluate the proposals on the exact paper review request it had made, in a network situation, the program chair agent will also need that capability to evaluate the new proposal, and possibly enter a negotiation on the deadline extension parameter as well. Above, we have introduced the differences in task delegation that result from different types of coordination in organizations. From a coordination perspective hierarchical relations are most efficient in achieving the delegation of tasks. They need only one message to achieve the delegation. It seems that the network type is the least efficient to achieve the delegation of a task, basically, because it allows for some more negotiation on counter-activities. However, as remarked before the final agreement usually encompasses more than one interaction. Note that, in the above, we only considered the coordination costs (in terms of the number of messages that have to be send after each other (parallel messages to or from a group count for one)). However, from an organizational perspective we are, of course, mainly interested in getting the actual task done. So, we should also take a look at the costs of performing the task once it is delegated to the agent that should actually perform it. In our formalism (as in reality) the task delegation, no matter which mechanism is used, results in an obligation. There is therefore no absolute guarantee that the task will indeed be done, as the agent is free to not fulfil its obligations. The requesting agent should be able to evaluate the capabilities and availability of the requested agent in order to maximize the certainty of task achievement. Moreover, mechanisms for controlling the realization of tasks are needed. We will not go into the latter aspect here but see [2] for further discussion. In a hierarchy the requesting agent needs to have all the information available to determine the best possible agent for a task. So, it needs to know the capabilities, efficiency, capacity and current workload of all agents. When task requirements and agent capabilities are fairly stable, then it is quite feasible for the delegating agents to maintain this information. It is exactly for situations where the delegating agent cannot maintain all information about the other agents that market mechanisms are meant for. The proposals of the agents answering a request (implicitly) carry the information that the agent needs to make the best possible choice for delegating the task. If an agent is not capable or busy to perform the task it will not answer with a propose, or will be slow responding. As before, the networks have an intermediate position between hierarchies and markets. In networks, besides the agreement concerning the initial request, usually further interaction will happen (concerning the realization of the counter request). The interest in maintaining such long- time relation with the requested agent is often one of the reasons for the requesting agent to enter a negotiation on the counter proposal (see the example above). In this way long-time relations between agents are achieved, without the inflexibility of a hierarchy. References [1] F. Dignum and H. Weigand. Communication and deontic logic. In R. Wieringa and R. Feenstra, editors, Information Systems - Correctness and Reusability. Selected papers from the IS-CORE Workshop, pages 242–260. World Scientific Publishing Co., 1995. [2] D. Grossi, F. Dignum, M. Dastani, and L. Royakkers. Foundations of organizational structures in multiagent systems. In AAMAS’05, pages 690–697. ACM Press, July 2005.