As distributed systems of computers play an increasingly important role in society, it will be necessary to consider ways in which these machines can be made to interact effectively. Especially when the interacting machines have been independently designed, it is essential that the interaction environment be conducive to the aims of their designers. These designers might, for example, wish their machines to behave efficiently, and with a minimum of overhead required by the coordination mechanism itself. The rules of interaction should satisfy these needs, and others. Formal tools and analysis can help in the appropriate design of these rules. We here consider how concepts from game theory can provide standards to be used in the design of appropriate negotiation and interaction environments. This design is highly sensitive to the domain in which the interaction is taking place. Different interaction mechanisms are suitable for different domains, if attributes like efficiency and stability are to be maintained. We present a general theory that captures the relationship between certain domains and negotiation mechanisms. The analysis makes it possible to categorize precisely the kinds of domains in which agents find themselves, and to use the category to choose appropriate negotiation mechanisms. The theory presented here both generalizes previous results, and allows agent designers to characterize new domains accurately. The analysis thus serves as a critical step in using the theory of negotiation in real-world applications. We show that in certain task oriented domains, there exist distributed consensus mechanisms with simple and stable strategies that lead to efficient outcomes, even when agents have incomplete information about their environment. We also present additional novel results, in particular that *This is a revised and expanded version of the papers "A domain theory for task oriented negotiation" and "Consenting agents: negotiation mechanisms for multi-agent systems" that appeared in Proceedings Chambery, France, respectively. * Corresponding author. E-mail: jeff@cs.huji.ac.il. ' E-mail: gilad@mit.edu. 0004-3702/96/$15.00 Copyright @ 1996 Elsevier Science B.V. All rights reserved. ssD10004-3702(95)00104-2 111 concave domains using all-or-nothin g deals. no lying by an agent can be beneficial, and that in subadditive domains. there often exist beneficial decoy lies that do not require lull information regarding the other agent's goals. Computers arc making more and more decisions in a relatively autonomous fashion. Telecommunication networks arc controlled by computers that decide on the routing 01' telephone calls and data packets. Electrical grids have decisions made by computer regarding how their loads will bc balanced at times of peak demand. Similarly, research is being done on how computers can react to. and control, automotive and airplane traffic in real time. Some of the decisions that these computcra are generating arc made in concert with other machines. Often. this inter-machine consultation is crucial CO the task at hand. FOI example. with personal digital assistants (PDAs), the individual's palmtop computer will bc expected to coordinate schedules with others' PDAs (c.g., my software agent determines whether my car has been fixed on time at the garage; if not, it contacts the taxi company, reschedules my order lor ;I cub. and updates my day's schedule). No scheduling will take place without inter-machine communication. Rarely will it take place without the resolution of inter-machine conflict (because the humans that these machines represent have conflicting goals). Similarly. the concept 01' intelligent databases relies on sophisticated interactions among autonomous software agents. A user's request for a piece of information may require collecting and synthesizin, 0 information from several distributed databases. Machines need to li)rmulate the ncccssary collection of requests, arrange access to the data (which may be partially restricted), and cooperate to get the information where it is needed. Even when a computer's tasks do not lzcl~~ to involve other machines, it may be beneficial to involve them. Sometimes. for example. we find automated systems controlling resources (like the telecommunications network mentioned above). It is often to the benefit of separate resource-controlling systcrns to share their resources (e.g.. fiber optic lines, short and long term storage. switchin, ~7 nodes) with one another. All of this inter-machine coordination will be taking place within some kind 01' irlternctiorr envirannwrzt. There will inevitably be "protocols" for how machines deal with one another. What concerns us here are not the details of how to stuff information into a packet on the network; it's not even the higher-level issue of how agents will communicate with one another (in a common language, or perhaps using translation filters) Rather, once WC assume that agents cm communicate and understand one another, how will they come to agreements? These "interaction rules" will establish the basis for inter-machine negotiation, agreement, coordination, and cooperation. If the inter-machine protocols are primitive and incapable of capturing the subtletics 01' cooperative opportunities, the machines will act inefficiently. They will make the wrong decisions. The people who depend on those decisions will suffer. Intelligence 86 (1996) 195-244  This article is organized into three parts: (1) (2) (3) In the first part (Sections 1.2-9), we discuss the general approach of our framework for automated negotiation, along with its motivation and related research. We also give a very brief and informal overview of our results. In the second part (Sections lo-14), we present the formal details of our application of the framework to task oriented domains. This second part also includes a more formal discussion of some of the main issues raised in the first part of the article. In Appendix A, we present the proofs to all theorems contained in the second part of the article.  In the field of distributed artificial intelligence (DAI), researchers explore methods that enable the coherent (e.g., coordinated, efficient) interaction of computers in distributed systems. One of the major distinctions in DA1 is between research in distributed problem solving (DPS) [4, 8, 13,63], in which the distributed system has been centrally designed, and multiagent (MA) systems [ 18,38,40,68], in which the distributed system is made up of independently designed agents. In DPS, there is some global task that the system is performing, and there exists (at least implicitly) a global notion of utility that can constrain or direct agent activity. In DPS, there is assumed to be a single body who is able, at design time, to directly influence the preferences of all agents in the system. In multiagent systems, there is assumed to be no single body who is able, at design time, to directly influence the preferences of all agents in the system. The agents' preferences arise from distinct designers. In MA systems, each agent is concerned only with its own goals (though different agents' goals may overlap), and there is no global notion of utility. The MA system agent, concerned with its own welfare (i.e., the welfare of its designer [ 12]), acts accordingly to increase that welfare. The distinction between distributed problem solving and multiagent systems should really be seen primarily as a distinction between research agendas. 2 Certainly it will not always be obvious to an outside observer whether a given distributed system falls into one category or the other. A single designer may have built his agents to act competitively, believing it improves overall system efficiency. Similarly, individually motivated agents might be seen sharing information and helping one another, because they have determined that it is in their own best interests to act that way. However, the research questions asked by a researcher in DPS are sometimes distinct from those asked by an MAS researcher (despite a good deal of overlap). In particular, if a DPS researcher can show that acting in a particular way is good for the system as a whole, 2 in fact, the use of these terms is itself undergoing a change. "Multiagent systems" is now sometimes used to refer to the entire field of distributed artificial intelligence. For more of a discussion about the DPS/MAS  Intelligence 86 (1996) 195-244 199 Another important issue is the relationship that agents have to one another, e.g., the degree to which they are willing to compromise their goals for one another (assuming that such compromise is necessary). Benevolent agents [ 581 are those that, by design, are willing to accommodate one another; they have been built to be cooperative, to share information, and to coordinate in pursuit of some (at least implicit) notion of global utility. In contrast, multiagent system agents will cooperate only when it is in their best interests to do so. Still another potential relationship among agents is a modified master-slave relationship, called a "supervisor-supervised' relationship, where non-absolute control is exerted by one agent over another [ 19, 201. The synthesis, synchronization, or adjustment process for multiple agent plans thus constitute some of the (varied) foci of DA1 planning research. Synchronization through conflict avoidance [ 28,29,66], distribution of a single-agent planner among multiple agents [ 91, the use of a centralized multiagent planner [ 551, and the use of consensus mechanisms for aggregating subplans produced by multiple agents [ 231, have all been explored. Other recent work includes [ 17,24,34,36,40, 11. There exists a large and growing body of work within artificial intelligence that attempts to capture notions of rational behavior through logical axiomatization [6, 7,30,3 1,37,46,47,54]. The approach usually centers on a formalized model of the agent's beliefs, desires, and intentions (the so-called "BDI model"). The purpose of the formal model is to precisely characterize what constitutes rational behavior, with the intent of imposing such rational behavior on an automated agent. The formal axioms might be used at run-time to directly constrain an agent's decision process, or (more likely) they could be used at compile-time to produce a more efficient executable module. The focus of this research, coming as it does from a single-agent artificial intelligence perspective, is on the architecture of a single automated agent. For example, Cohen and Levesque [5, 6] have explored the relationship between choice, commitment, and intention-an agent should commit itself to certain plans of action, and remain loyal to these plans as long as it is appropriate (for example, when the agent discovers a plan is infeasible, the plan should be dropped). Even when looking at multiagent systems, these researchers have examined how a member of a group should be designed-again, looking at how to design an individual agent so that it is a productive group member. For example, in [ 361 axioms are proposed that cause an agent, when he discovers that he will fail to fulfill his role in a joint plan, to notify the other members of his group. Axiomatizations, however, might need to deal with how groups of agents could have a joint commitment to accomplishing some goal [7], or how each agent can make interpersonal commitments without the use of such notions [ 3 11. Another use for the BDI abstractions is to allow one agent to reason about other agents, and relativize one's intentions in terms of beliefs about other agents' intentions or beliefs. Various researchers in distributed artificial intelligence have suggested that it would be worthwhile to isolate "aspects of cooperative behavior", general rules that would cause agents to act in ways conducive to cooperation. The hypothesis is that when agents act in certain ways (e.g., share information. act in predictable ways, defer gfobally constraining choices). it will be easier for them IO carry out effective joint action [3,45,6:5]. Moses, Shoham, and Tenn~nh~~ltz [48.49.6 I .62]. for example, have suggested applying the sociep metaphor to artificial systems to improve the performance of the agents operating in this society. The issues that are to be dealt with are synchronization, coordination of the agents' activities, cooperative ways to achieve tasks, and how safety and fairness constraints on the system can be guaranteed. They propose coordinating agent activity to avoid conflicts; the system will be structured so that agents will not arrive at potential conflict situations. Thus these social laws are seen as a method to avoid the necessity for costly coordination techniques, like planning or negotiation. With agents following the appropriate social laws, the need for run-time coordination will be reduced. This is important, because although agent designers may bc willin, (7 to invest a large amount of effort at design time in building effective distributed systems, it is important that the run-time overhead be as low as possible. There is a similarity between this USC of precompiled, highly structured social laws, and our development of pre-defined interaction protocols. However, the social laws approach assumes that the designer of the laws has full control over the agents; agents are assumed to follow the social laws simply because they were designed to, and not because they individually benefit from the social laws. Obeying the social laws may not bc "stable"; assuming that everyone else obeys the laws, an agent might do better by breaking them. Our approach is concerned with social conventions that are stable, which will be suitable for individually motivated agents. There have been several attempts to consider market mechanisms as a way of efliciently allocating resources in a distributed system. Among the AI work is that of Smith's contract net [ 63,641, Malone's enterprise system 144J, and Wellman's WAL-RAS system f 72,73 1. The contract net is a high-level communication protocol for a distributed problem solving system. It enables the distribution of the tasks among the nodes that operate in the system. A contract between two nodes is established so that tasks can be executed; each node in the net can act as a mmager and/or as a contracmr. A task that has been assigned to a node can be further decomposed by the contractor. A contract is established by a bidding scheme that includes the announcement of the task by the manager, and bids sent in by the potential contractors. Enterprise 144 J is a system that was built using a variation of the contract net protocol. The distributed scheduling pmtocnl locates the best available machine to perform a task. This protocol is similar to the contract net. but makes use of a more well-de~ned assignment criteria. Intelligence 86 (1996) 195-244 201 Another system that takes an economic approach in solving a distributed problem through the use of a price mechanism has been explored by Wellman in [ 72 1. Wellman uses the consumer/producer metaphor to establish a market pricing-based mechanism for task redistribution that ensures stability and efficiency. All agents act as both consumers and producers. Each distinct good has an auction associated with it, and agents can get the good by submitting bids in the auction for that good. The system developed by Wellman, WALRAS, computes for each market the equilibrium price. Negotiation has been a subject of central interest in DAI. The word has been used in a variety of ways, though in general it refers to communication processes that further coordination [ 8, 40,41,63]. These negotiating procedures have included the exchange of partial global plans [ 131, the communication of information intended to alter other agents' goals [ 67,681, and the use of incremental suggestions leading to joint plans of action [ 381. Interagent collaboration in distributed problem solving systems has been explored in the ongoing research of Lesser, Durfee, and colleagues. Much of this work has focused on the implementation and analysis of data fusion experiments, where systems of distributed sensors absorb and interpret data, ultimately arriving at a group conclusion [ 11,14,42]. Agents exchange partial solutions at various levels of detail to construct global solutions; much of the work has examined effective strategies for communication of data and hypotheses among agents, and in particular the kinds of relationships among nodes that can aid effective group analysis. For example, different organizations, and different methods for focusing node activity, can help the system as a whole be far more efficient. Sycara has examined a model of negotiation that combines case-based reasoning and optimization of multi-attribute utilities. In particular, while in our research we assume that agents' goals are fixed during the negotiation, Sycara is specifically interested in how agents can influence one another to change their goals through a process of negotiation (information transfer, etc.). Kraus and her colleagues have explored negotiation where the negotiation time itself is an issue [ 38,391. Agents may lose value from a negotiation that drags out too long, and different agents are asymmetric with regard to the cost of negotiation time. Agents' attitudes towards negotiation time directly influences the kinds of agreements they will reach. Interestingly, however, those agreements can be reached without delay. There is an avoidable inefficiency in delaying agreement. Gasser [27] has explored the social aspects of agent knowledge and action in multiagent systems ("communities of programs"). Social mechanisms can dynamically emerge; communities of programs can generate, modify, and codify their own local languages of interaction. Gasser's approach may be most effective when agents are interacting in unstructured domains, or in domains where their structure is continuously changing. The research we present, on the other hand, exploits a pre-designed social layer for multiagent systems. Intelligence 86 (1996) 195-244 203 actions. For example, semi-cooperative deals proved capable of resolving true conflicts between agents, whereas mixed deals did not. Similarly, multi-plan deals are capable of capturing goal relaxation as part of an agreement. It was also shown that certain other properties were true of some deal types but not of others. In particular, different agent strategies were appropriate ("rational") for different deal types and domains. Agents were shown to have no incentive to lie when certain deal types were used in certain domains, but did have an incentive to lie with other deal type/domain combinations. The examination of this relationship between the negotiation mechanism and the domain made use of two prototypical examples: the postmen domain (introduced in [ 75]), and the slotted blocks world (presented in [ 771). It was clear that these two domains exemplified general classes of multiagent interactions (e.g., the postmen domain was inherently cooperative, the slotted blocks world not). It was, however, not clear what attributes of the domains made certain negotiation mechanisms appropriate for them. Nor was it clear how other domains might compare with these prototypes. When presented with a new domain (such as agents querying a common database), which previous results were applicable, and which weren't? The research lacked a general theory explaining the relationship between domains and negotiation mechanisms. In this article, we present the beginnings of such a general theory. The analysis makes it possible both to understand previous results in the postmen domain more generally, and to characterize new domains accurately (i.e., what negotiation mechanisms are appropriate). The analysis thus serves as a critical step in using the theory of negotiation in real-world applications. The purpose of the research described in this article is to consider how we might build machines that are capable of making constructive agreements. We want our machines to interact flexibly. We want them to represent our interests, and compromise when that is to our advantage. We may want them to be secretive at times, not revealing all their information, and we most likely want them to recognize duplicity on the part of others, when possible. In short, we want our agents to faithfully act as our surrogates in encounters with other agents. When humans interact, they do not do so in a vacuum. There are social conventions and laws that constrain their behavior; the purpose of social conventions and laws is to do exactly that. A tax levied on a company that pollutes the air is intended as a disincentive to a certain kind of behavior. Positive publicity showered on a philanthropic company provides it with benefit for its behavior. One can think of a complicated system of laws and conventions as a kind of social engineering, intended to produce certain behavior among people. We are interested in social engineering for machines. We want to understand the kinds of negotiation protocols, and punitive and incentive mechanisms, that would motivate individual designers to build machines that act in ways that all those designers find beneficial. As mentioned above the development of "social laws" has parallels with the work of [ 621. There, however, the social laws are for centrally designed systems of agents (DPS). and will not necessarily make sense for independently designed agents. For example, a rule might encourage efficient behavior if everyone followed it, but if any single agent could benefit mot-c by not following the rule. the system as a whole will not be stable. Since each of our agents will do what is necessary to maximize its benefit, stability is a critical issue-we need rules that agents will independently find in their best interests to follow. We will return to this issue of stability below. The scenario we consider is as follows. Imagine representatives of various companies (agent designers) coming together to agree on interaction protocols for their automated agents. Given a particular domain (such as balancing telecommunications traffic among wide area networks, or meeting scheduling), they are presented with various interaction mechanisms, and shown that each mechanism has certain provable properties. For example, one mechanism might arrive at guaranteed globally optimal solutions, but at the cost of one agent possibly doing very badly. Another mechanism might ensure that the gap between agents' benefits are minimized, but at the cost of everyone doing a little worse. Moreover, it is shown to these company representatives that Protocol A is immune to deception: it will be in no one's interest to design a cheating agent that deviates from the protocol in any way (e.g., by reportin g higher, or lower, network traffic than is actually present) The representatives consider the various options, and decide among themselves which protocol to build into their agents. The meeting adjourns, agents arc built. and beneficial agreements are reached among them. It turns out that the attributes of a given mechanism are highly sensitive to the domain in which the agents are operating. The rules of interaction that might be appropriate in one domain might be quite inappropriate in another. When those company representatives sit down at the meeting, they need to be told "In this domain, Protocol A has properties I, 2. and 3, and is immune to deception. Protocol B has properties 2, 4, and 5, and is not immune to deception." Our research explores the space of possibilities, analyzing negotiation mechanisms in different domains. When the designers of automated agents meet, this is the kind of information they will need. The alternative to having this analysis is to wander in the dark, and to build negotiation modules without understanding their properties. Will they result in good deals? Could our machines do better? Will someone build a deceptive agent that takes advantage of mine? Should I, myself, design my agent to be secretive or deceptive? Will this further my own goals? Our research is intended to answer these kinds of questions. The builders of complex distributed systems, like interconnected networks, shared databases, assembly line monitoring and manufacturing, and distributed processing, can broaden the range of tools that they bring to bear on issues of interagent coordination. Intelligence 86 (1996) 195-244 20.5 Existing techniques generally rely on the goodwill of individual agents, and don't take into account complex interactions of competing goals. New tools can be applied to the high-level design of heterogeneous, distributed systems through the creation of appropriate negotiation protocols. How can machines decide how to share resources, or which machine will give way while the other proceeds? Negotiation and compromise are necessary, but how do we build our machines to do these things? How can the designers of these separate machines decide on techniques for agreement that enable mutually beneficial behavior? What techniques are appropriate? Can we make definite statements about the techniques' properties? The way we have begun to address these questions is to synthesize ideas from artificial intelligence (e.g., the concept of a reasoning, rational computer) with the tools of game theory (e.g., the study of rational behavior in an encounter between self-interested agents). Assuming that automated agents, built by separate, self-interested designers, will interact, we are interested in designing protocols for specific domains that will get those agents to interact in useful ways. The word "protocol" means different things to different people. As used to describe networks, a protocol is the structure of messages that allow computers to pass information to one another. When we use the word protocol, we mean the rules by which agents will come to agreements. It specifies the kinds of deals they can make, as well as the sequence of offers and counter-offers that are allowed. These are high-level protocols, dealing not with the mechanisms of communication but with its content. Protocols are intimately connected with domains, by which we mean the environment in which our agents operate. Automated agents that control telecommunications networks are operating in a different domain (in a formal sense) than robots moving boxes. Much of our research is focused on the relationship between different kinds of domains, and the protocols that are suitable for each. Given a protocol, we need to consider what agent strategy is appropriate. A strategy is the way an agent behaves in an interaction. The protocol specifies the rules of the interaction, but the exact deals that an agent proposes is a result of the strategy that his designer has put into him. As an analogy, a protocol is like the rules governing movement of pieces in the game of chess. A strategy is the way in which a chess player decides on his next move. Game theory is the right tool in the right place for the design of automated interactions. Game theory tools have been primarily applied to analyzing human behavior, but in certain ways they are inappropriate: humans are not always rational beings, nor do they necessarily have consistent preferences over alternatives. Automated societies, on the other hand, are particularly amenable to formal analysis and design. Automated agents can exhibit predictability, consistency, narrowness of purpose (e.g., no emotions, no humor, no fears, clearly defined and consistent risk attitude), and an explicit measurement of utility (where this can have an operative meaning inside the program controlling the agent ) Even the notion of "strategy" (a specification of what to do in every alternative during an interaction), a classic game theory term, takes on a clear and unambiguous meaning when it becomes simply a program put into a computer. The notion that a human would choose a fixed strategy before an interaction, and follow it without alteration, leads to unintuitive results for a person. Moreover. it seems to be more a formal construct than a realistic requirement-do humans consider eve? alternative ahead of time and decide what to do? On the other hand, the notion that a computer is programmed with a fixed strategy before an interaction, and follows it without alteration, is a simple description of the current reality. Of course, neither humans nor computer programs are ideal game theory agents. Most importantly, they are not capable of unlimited reasoning power, as game theory often assumes. Nevertheless, it seems that in certain ways automated agents are closer to the game theory idealization of an agent than humans are. The work described here, the design of interaction environments for machines. is most closely related to the field of mechanism design in game theory [ 25). Comparison with game rheog The approach taken in this article is strongly based on previous work in game theory, primarily on what is known as "Nash's bargaining problem" [43] or "Nash's model of bargaining" [ 601. Classic game theory [ 32, 43, 50, 60.74] talks about agents reaching "deals", which are defined as vectors of utilities (one for each agent). A bargaining game can end up in some possible outcome (i.e., a "deal"). Each player has a full preference order over the set of possible outcomes; this preference order is expressed by its utility function. For each deal, there is a utility vector which is the list of the utilities of this deal for every participant. There is a special utility vector called "conflict" (or sometimes the "status quo point") which is the utility each player assigns to a conflict (lack of final agreement). Game theory assumes that the set of possible deals is a simplex, i.e., if ~1 and u2 are two utility vectors for two possible deals, then every vector on the line connecting NI to ~2 is a utility vector of some possible deal (meaning that the domain of deals is continuous). Classic game theory deals with the following question: given a set of utility vectors (a simplex), what will be the utility vector that the players will agree on (under particular assumptions)? In other words, classic bargaining theory is focused on prediction of outcomes, under certain assumptions about the players and the outcomes themselves. Nash [50] showed that under some rational behavior and symmetry assumptions, players will reach an agreement on a deal that will be individual rational, pareto optimal, and will maximize the product of the players' utility (see Section 13 for a more complete discussion). Zeuthen [ 741 considered the two-player bargaining problem as a one-player decision process (deciding whether to concede or not), under the ~sumption that if none of the players concede at a particular step they will reach a conflict. Zeuthen evaluated how much risk each player would be willing to take when he decides not to concede (and thereby risks conflict). The player who is least. willing to risk will be the one who will make the next concession. Harsanyi [ 323 showed that the two approaches are equivafent in the sense that two players using Zeuthen's criteria will reach the Nash solution. The above approaches furnish us with tools for our own design and evaluation of negotiation mechanisms, which is our primary concern. Game theorists are usually concerned with how games will be played, from both a descriptive and normative point of view. Game solutions consist of strategies in equilibrium; if somehow a social behavior reaches an equiIibrium, no agent has any incentive to diverge from that equilibrium behavior. That equilibrium is considered to be a solution to the game. There may be one or more (or no) strategies in equilibrium, and there are also different notions of equilibrium (e.g., Nash [ 501, perfect equilibrium, dominant strategy equilibrium). There are also groups of game theorists who consider the problem of how to design games that have certain attributes. It is this area of mechanism design that is closest to our own concerns for automated agents. ~~hanism design is also know in the game theory literature as the impleme~ta-tion problem. The impfeme~tation question [2,25j asks whether there is a mechanism, or game form, with a distinguishable equilibrium point (dominant strategy, or strong, or merely Nash) such that each social profile (i.e., group behavior) is associated, when the players follow their equilibrium strategies, with the desired outcome. In other words, there are assumed to be a group of agents, each with its own utility function and preferences over possible social outcomes. There is also a social welfare function that rates all those possible social outcomes (e.g., a socially efficient agreement may be rated higher than a non-efficient one). The question is then, can one design a game such that it has a unique solution (~uilib~um strategies), and such that when each individual agent behaves according to this ~uilibrium strategy, the social behavior will maximize the social welfare function. If such a game can be designed, then it is said that the game implements the social welfare function. As an example of a social welfare function, consider minimization of pollution. While everyone may be interested in lowering pollution, everyone is interested in others bearing the associated costs. A m~h~ism to implement this social welfare function might include, for example, taxes on polluting industries and tax credits given for the purchase of electric cars. This is precisely the kind of mechanism that would cause agents, following an equilibrium strategy, to minimize pollution. The designer of a mechanism has to deal with every configuration of agent utility functions (which is precisely why he is designing a mechanism, or "game form", and not a specific game). The agents themselves may or may not have complete information about one another's utility functions, and thus may or may not know which concrete game they are playing. This complicates the problem of mechanism design. Usually. there is an assumption that the agents have certain limitations on the form of their utility functions. Thus there exists a known cct of all possible utility functions. Each agent can then be assigned a "type" based on which of those utility functions it is currently using. A mechanism is called a direct mechanism if the agents arc asked straight out what their type is. Then, based on the agents' declared types, the mechanism generates some outcome. If the agents are not asked their type, the mechanism is called an indirect mechanism. The revelation principle states that whatever can be done with an indirect mechanism can also be done with a direct mechanism. In other words, any social function that is implementable by an indirect mechanism can also be implemented by a direct mechanism, where agents will have an incentive to declare their true type. This is called an incentive compatible mechanism. The advantage of a direct mechanism whcrc the agents have an incentive to declare their true type over an indirect mechanism is the simplicity of the agents' strategies. However, the simplicity on the part of the agents may be offset by the need for a complicated mechanism. While we prefer a direct mechanism, it is also important to us that it bc a simple enc. One can look at the work described in this article as a kind of mechanism design, where the social welfare function that is being implemented is "efficiency", i.e., the sum of agents' utilities. Requiring that the sum be maximized c1 priori rules out many social behaviors, but still may allow multiple sum maximization behaviors. In other words, even when the sum is being maximized, the way in which utility is divided among agents may differ. Since each agent wants a bigger share of this group utility, we have a typical negotiation scenario. Either the agents agree on a division, or they reach a conflict. Since we are talking about automated agents. we depend on their designers to reach a consensus about the mechanism and its associated strategies. Therefore, our mechanism design is simpler than that of game theory. In contrast to classic mechanism design, we are not concerned with the uniqueness of the equilibrium strategies. What is important to us is the existence OT an equilibrium strategy that maximizes the social welfare function. We are satisfied with the existence of even one such maximizing equilibrium social behavior, even though there may be other social behaviors in equilibrium that do not maximize the social welfare function. The designers of our automated agents can choose a mechanism that has many equilibrium points (some of which maximize the social welfare function and some of which don't). but then coordinate themselves (by jointly choosing a strategy) so that their agents reach a particular equilibrium point that maximizes the social welfare function. By relaxing our requirement of the mechanism, we may discover social welfare functions that can be implemented using our approach, but cannot be implemented using game theory's (stricter) appreach.  What are the attributes that might interest those company representatives when they meet to discuss the interaction environment for their machines? This set of attributes, and their relative importance, will ultimately affect their choice of interaction rules. We have considered several attributes that might be important to system designers. ( 1) Eficiency: The agents should not squander resources when they come to an agreement; there should not be wasted utility when an agreement is reached. For example, it makes sense for the agreements to satisfy the requirement of pareto optimality (no agent could derive more from a different agreement, without some other agent deriving less from that alternate agreement). Another consideration might be global optimality, which is achieved when the sum of the agents' benefits are maximized. Neither kind of optimality necessarily implies the other. Since we are speaking about self-motivated agents (who care about their own utilities, not the sum of system-wide utilities-no agent in general would be willing to accept lower utility just to increase the system's sum), pareto optimality plays a primary role in our efficiency evaluation. Among pareto optimal solutions, however, we might also consider as a secondary criterion those solutions that increase the sum of system-wide utilities. (2) Stability: No designer should have an incentive to deviate from agreed-upon strategies. The strategy that agents are programmed with can be proposed as part of the interaction environment design. Once these strategies have been proposed, however, we do not want individual designers (e.g., companies) to have an incentive to go back and build their agents with different, manipulative, strategies. (3) Simplicity: It will be desirable for the overall interaction environment to make low computational demands on the agents, and to require little communication overhead. This is related both to efficiency and to stability: if the interaction mechanism is simple, it increases efficiency of the system, with fewer resources used up in carrying out the negotiation itself. Similarly, with stable mechanisms, few resources need to be spent on outguessing your opponent, or trying to discover his optimal choices. The optimal behavior has been publicly revealed, and there is nothing better to do than just carry it out. (4) Distribution: Preferably, the interaction rules will not require a central decision maker, for all the obvious reasons. We do not want our distributed system to have a performance bottle-neck, nor collapse due to the single failure of a special node. (5) Symmetry: No designer wants the negotiation process to be arbitrarily biased against his agent. Thus, no mechanism should treat agents differently because of inappropriate criteria. Exactly what constitutes inappropriate criteria depends on the specific domain, While the mechanism may be asymmetric, for example because one agent has many more tasks to carry out than the other, it should maintain strict impartiality when irrelevant aspects of the agents differ (e.g., the agents' manufacturers). These attributes need not be universally accepted. In fact, there will sometimes be trade-offs between one attribute and another (for example, efficiency and stability are sometimes in conflict with one another [ 831). But our protocols are designed, for specific classes of domains, so that they satisfy some or all of these attributes. Ultimately, these are the kinds of criteria that rate the acceptability of one interaction mechanism over another. As one example, the attribute of stability assumes particular importance when we consider open systems, where new agents are constantly entering and leaving the community of interacting machines. Here, we might want to maintain stability in the face of new agents who bring with them new goals and potentially new strategies as well. If the mechanism is "self-perpetuating", in that it is not only to the benefit of society as a whole to follow the rules, but also to the benefit of each individual member, then the social behavior remains stable even when the society's members change dynamically. When the interaction rules create an environment in which a particular strategy is optimal, beneficial social behavior is resistant to outside invasion [ I]. We have several times alluded to the connection between protocols and domainsfor a given class of interactions, some protocols might be suitable while others arc not. We have found it useful to categorize domains into a three-tier hierarchy of task oriented domains, state oriented domains, and worth oriented domains. This hierarchy is by no means complete, but does cover a large proportion of the kinds of real-world interactions in which we are interested. This article is focused on task oriented domains. For treatments of state oriented domains. see [76-78,82-841; for treatments of worth oriented domains, see [ 59,79,85]. These are domains in which an agent's activity can be defined in terms of a set of tasks that it has to achieve. These tasks can be carried out without concern about interference from other agents; all the resources necessary to accomplish the tasks are available to the agent. On the other hand. it is possible that agents can reach agreements where they redistribute some tasks, to everyone's benefit (for example, if one agent is doing some task, he may, at little or no cost. be able to do another agent's task). The domains are inherently cooperative. Negotiation is aimed at discovering mutually beneficial task redistribution. The key issue here is the notion of tusk, an indivisible job that needs to be carried out. Of course, what constitutes a task will be specific to the domain. Many kinds of activity, however, can be conceived of in this way, as the execution of indivisible tasks. For example, imagine that you have three children, each of whom needs to be delivered to a different school each morning. Your neighbor has four children, and also needs to take them to school. Delivery of each child can be modeled as an indivisible task. Although both you and your neighbor might be interested in setting up a carpool, there is no doubt that you will be able to achieve your tasks by yourself, if necessary. The worst that can happen is that you and your neighbor won't come to an agreement about setting up a carpool, in which case you are no worse off than if you were alone. You can only benefit (or do no worse) from your neighbor's existence. Intelligence 86 (1996) 195-244 21 I Assume, though, that one of my children and one of my neighbor's children both go to the same school (that is, the cost of carrying out these two deliveries, or two tasks, is the same as the cost of carrying out one of them). It obviously makes sense for both children to be taken together, and only my neighbor or I will need to make the trip to carry out both tasks. What kinds of agreements might we reach? We might decide that I will take the children on even days each month, and my neighbor will take them on odd days; perhaps, if there are other children involved, we might have my neighbor always take those two specific children, while I am responsible for the rest of the children (his and mine). Another possibility would be for us to flip a coin every morning to decide who will take the children. An important issue, beyond what deals can be reached, is how a specific deal will be agreed upon (see Section 7.2 below). Consider, as further examples, the postmen domain, the database domain, and the fax domain (these domains are described in more detail, and more formally, below). In the postmen domain, each agent is given a set of letters to deliver to various nodes on a graph; starting and ending at the post office, the agents are to traverse the graph and make their deliveries. There is no cost associated with carrying letters (they can carry any number), but there is a cost associated with graph traversal. The agents are interested in making short trips. Agents can reach agreements to carry one another's letters, and save on their travel. The database domain similarly assigns to each agent a set of tasks, and allows for the possibility of beneficial task redistribution. Here, each agent is given a query that it will make against a common database (to extract a set of records). A query, in turn, may be composed of subqueries (i.e., the agent's tasks). For example, one agent may want the records of "All female employees making over $50,000 a year", while another agent may want the records of "All female employees with more than three children". Both agents share a subtask, the query that involves extracting the records of all female employees (prior to extracting a subset of those records). By having only one agent get the female employee records, another agent can lower its cost. The third example is the fax domain. It appears very similar to the postmen domain, but is subtly different. In the fax domain, each agent is given a set of faxes to send to different locations around the world (each fax is a task). The only cost is to establish a connection. Once the connection is made, an unlimited number of faxes can be sent. Of course, if two agents both have faxes to send to Paris and to London, they may redistribute their faxes, with one sending all the faxes to Paris and the other sending all the faxes to London. Despite the seemingly minor differences in these domains, the attributes of suitable protocols are very different for each, as we will see below. The state oriented domain (SOD) is the type of domain with which most AI research has dealt. The blocks world, for example, is a classic state oriented domain. SODS are a superset of TODs (i.e., every TOD can be cast in the form of an SOD). In an SOD, each agent is concerned with moving the world from an initial state into one of a set of goal states. There is, of course, the possibility of real conflict here. Because of, for example, competition over resources, agents might have fundamentally different goals. There may be no goal states that satisfy all agents. At other times, there may exist goal states that satisfy all agents. but that are expensive to reach-and which require the agents to do more work than they would have had to do in isolation. Mechanisms for dealing with state oriented domains are examined in [76][77][78]83,84]. Again, negotiation mechanisms that have certain attributes in task oriented domains (e.g., efficiency, stability) do not necessarily have these same attributes in state oriented domains. Worth oriented domains ( WODs) are a generalization of state oriented domains, where agents assign a worth to each potential state, which establishes its desirability for the agent (as opposed to an SOD, in which the worth function is essentially binaryall non-goal states have zero worth). This establishes a decision theoretic flavor to interactions in a WOD. One example of a WOD is the TileWorld, as presented in [ 521. The key advantage of a worth oriented domain is that the worth function allows agents to compromise on their goals, sometimes increasing the overall efficiency of the agreement. Every SOD can be cast in terms of a WOD. of course (with binary worth function). Negotiation mechanisms suitable for an SOD need not be suitable for a WOD (that is. the attributes of the same mechanism may change when moving from an SOD to a WOD). Mechanisms for dealing with worth oriented domains are examined in [ 79. 851. Designing a negotiation mechanism, the overall "rules of interaction", is a three-step process. First, the agent designers must agree on a definition of the domain, then agree on a negotiation protocol, and finally propose a negotiation strategy. The complete definition of a domain should give a precise specification to the concept of a goal, and to the agent operations that are available. For example, in the postmen domain, the goal of an agent is the set of letters that the agent must deliver (as in any TOD, the goal is the set of tasks that need to be carried out), along with the requirement that the agent begin and end at the post office. The specification of agent operations that are available define exactly what an agent can do, and the nature of those actions' cost. In the postmen domain, again, it is part of the domain definition that an agent can carry an unlimited number of letters, and that the cost of a graph traversal is the total distance traveled. Intelligence 86 (1996) 195-244 213 This formal domain definition is the necessary first step in analyzing any new domain. If agents are negotiating over sharing message traffic in telecommunications networks, it is necessary to specify completely what constitutes a goal, and what agent operations are available. Similarly, PDAs involved in negotiations over schedules need their goals and operators precisely defined. Once the domain has been specified, we need to specify the negotiation protocol, which establishes the rules of interaction among agents. Here, we need to be concerned both with the space of possible deals, and with the negotiation process. l Space of possible deals: First, we must specify the set of candidate deals. Specifically, what kinds of agreements can the agents come to? For example, we might restrict our agents to only discussing deals that do not involve redundant work (e.g., in the carpool example, the parents will not consider deals that have two parents visiting the same school). Similarly, we might specify that deals cannot involve tossing a coin. l Negotiation process: Given a set of possible deals, what is the process that agents can use to converge to agreement on a single deal? In other words, what are the rules that specify how consensus will be reached? How will one agreed-upon deal be differentiated from the other candidates? In the carpool example, we might specify that each parent will in turn offer a delivery schedule and assignments; the next parent can either accept the offer, or reject it and make his own counter-offer. We might also allow as part of the negotiation process that any parent can, at any point, make a "take-it-or-leave-it" proposition, that will either be accepted or end the negotiation without agreement. Another example of a negotiation process was the monotonic concession protocol that was described in Section 2.5.1 above. Given a set of possible deals and a negotiation process, what strategy should an individual agent adopt while participating in the process? For example, one strategy for a parent in the carpool scenario is to compute a particular delivery schedule and present it as a "take-it-or-leave-it" deal. Another strategy is to start with the deal that is best for you, and if the other parent rejects it, minimally modify it as a concession to the other parent. The specification of a negotiation strategy is not strictly part of the interaction rules being decided on by the designers of automated agents. In other words, the designers are really free to build their agents as they see fit. No one can compel them to build their agents in a certain way (having a certain strategy), and such compulsion, if attempted, would probably not be effective. However, we can provide strategies with known properties, and allow designers to incorporate them. More specifically, we may be able to bring to the table a given strategy, and show that it is provably optimal (for the agent itself). There will be no incentive for any designer to use any different strategy. And when all agents use that strategy, there will be certain (beneficial) global properties of the interaction. So a negotiation strategy is provided to the designers as a service; if a compelling case is made, the designers will in fact incorporate that strategy into their agents. We generally are interested in negotiation protocol/strategy combinations. As mentioned above, the domain examples given in Section 6.1 are all TODs, and seem to have a great deal in common with one another. There are, however, critical differences among them, all focused on the domains' cost functions. To demonstrate these differences, we categorize TODs based on three possible attributes of the cost function: subadditivity, concavity, and modularity. This is a hierarchy; modularity implies concavity, which in turn implies subadditivity. Protocols and strategies that are stable in one kind of TOD are not necessarily stable in other kinds. These issues are discussed at greater length below. In some domains, by combining sets of tasks we may reduce (and can never increase) the total cost, as compared with the sum of the costs of achieving the sets separately. The postmen domain, for example, is subadditive. If X and Y are two sets of addresses, and we need to visit all of them (X U Y), then in the worst case we will be able to do the minimal cycle visiting the X addresses, then do the minima1 cycle visiting the Y addresses. This might be our best plan if the addresses are disjoint and decoupled (the topology of the graph is against us). In that case. the cost of visiting all the addresses is equal to visiting one set plus the cost of visiting the other set. However, in some cases we may be able to do better, and visit some addresses on the way to others. That's what subadditivity means. As another example, consider the database query domain. To evaluate two sets of queries, X and Y, we can of course evaluate all the queries in X, then independently evaluate all the queries in Y. This, again, might be our best course of action if the queries are disjoint and decoupled; the total cost will be the cost of X plus the cost of Y. However, sometimes we will be able to do better, by sharing the results of queries or subqueries, and evaluate X U Y at lower total cost. A relatively minor change in a domain definition, however, can eliminate subadditivity. If, in the postmen domain, the agents were not required to return to the post office at the end of their deliveries, then the domain would not be subadditive. In a concave domain, the cost that arbitrary set of tasks Z adds to set of tasks Y cannot be greater than the cost Z would add to a subset of Y. The fax domain and the database query domain are concave, while the postmen domain is not. Intuitively, a concave domain is more "predictable" than a subadditive domain that is not concave. There is an element of monotonicity to the combining of tasks in a concave domain G. Z&kin, J.S. Rosenschein/Artij?cial Intelligence 86 (1996) 195-244 215 that is missing from non-concave domains. You know, for example, that if you have an original set of tasks (X), and are faced with getting an additional outside set (Z), you will not suffer greatly if you enlarge the original set-the extra work that 2 adds will either be unaffected or reduced by the enlargement of the original set. In a non-concave domain, even if it is subadditive, you might find that the extra work that Z adds is much greater than it would have been before the enlargement. In a modular domain, the cost of the combination of two sets of tasks is exactly the sum of their individual costs minus the cost of their intersection. This is, intuitively, the most well-behaved subadditive domain category of all. When task sets are combined, it is only their overlap that matters-all other tasks are extraneous to the negotiation. Only the fax domain from the above TOD examples is modular. Much of the research that we have been conducting on this model of negotiation considers issues relating to agents that have incomplete information about their encounter [ 781. For example, they may be aware of their own goal without knowing the goal of the agent with whom they are negotiating. Thus, they may need to adapt their negotiation strategy to deal with this uncertainty. One obvious way in which uncertainty can be exploited can be in misrepresenting an agent's true goal. In a task oriented domain, such misrepresentation might involve hiding tasks, or creating false tasks (phantoms, or decoys), all with the intent of improving one's negotiation position. The process of reaching an agreement generally depends on agents declaring their individual task sets, and then negotiating over the global set of declared tasks. By declaring one's task set falsely, one can in principle (under certain circumstances), change the negotiation outcome to one's benefit. Much of our research has been focused on negotiation mechanisms that disincentivize deceit. These kinds of negotiation mechanisms are called "incentive compatible" mechanisms in the game theory literature. When a mechanism is incentive compatible, no agent designer will have any reason to do anything but make his agent declare his true goal in a negotiation. Although the designer is free to build his agent any way he pleases, telling the truth will be shown to be the optimal strategy. This concern for honesty among agents, and for encouraging that honesty by the very structure of the negotiation environment, is an absolutely essential aspect of work on muitiagent systems. Situations in which agents have an incentive to lie are, in general, not stable. Although agent designers may discuss a strategy, they will then be motivated to go back and build their agents differently. This will ultimately result in less efficient systems (and outcomes that are worse for the individual agents). First, agents might reasonably expend a great deal of energy in discovering the true goal of the other negotiator, and all of this effort lowers the simplicity and efficiency of the system. Second, they will be tempted to risk strategies that may result in inferior outcomes. Two agents, coming together, each trying to outguess the other, will sometimes make choices that benefit no one. Thus efficiency and stability are closely related. There is no point, in multiagent systems, in considering efficiency without considering stability. Without stability, efficiency cannot be guaranteed, as agents are tempted to deviate from the globally efficient strategy. A tusk oriented domain (TOD) describes a certain class of scenarios for multiagent encounters. Intuitively, it is a domain that is cooperative, with no negative interactions among agents' goals. Each agent welcomes the existence of other agents, for they can only benefit from one another (if they can reach agreement about sharing tasks). ( I) 7 is the set of all possible tasks. such that for all k t {I,. , II}, TX is a ,finite set of tasks from 7 that Ak needs to achieve. Tk will also be called Ak's Leoai. According to the definition above. the cost function c takes no parameters other than the task set. In general, c might be defined as having other, global, parameters (like the initial state of the world). However, the cost of a set of tasks is independent of others' tasks that need to be achieved. An agent in a TOD is certain to be able to achieve his goal at that cost. Here we give several examples of TODs. which cover a variety of agent interaction situations. Subsequently, we will further classify each of these TOD examples with respect to the cost properties mentioned above in Section 8. Description: Agents have to deliver sets of containers to warehouses, which are arranged on a weighted graph G = G( v E). There is no limit to the number of containers G. Uotkin, J.S. Rosenschein/Artificial Intelligence 86 (1996) 195-244 217 that can fit in a warehouse. The agents all start from a central distribution point. Agents can exchange containers at no cost while they are at the distribution point, prior to delivery. The set of all addresses in the graph, namely V. If address x is in an agent's task set, it means that he has at least one container to deliver to x. Cost function: The cost of a subset of addresses X G V, i.e., c(X), is the length of the minimal path that starts at the distribution point and visits all members of X. Description: Agents have to deliver sets of letters to mailboxes, which are arranged on a weighted graph G = G( YE). There is no limit to the number of letters that can fit in a mailbox. After delivering all letters, agents must return to the starting point (the post office). Agents can exchange letters at no cost while they are at the post office, prior to delivery. Task set: The set of all addresses in the graph, namely V. If address x is in an agent's task set, it means that he has at least one letter to deliver to x. Cost function: The cost of a subset of addresses X C V, i.e., c(X), is the length of the minimal path that starts at the post office, visits all members of X, and ends at the post office. Description: Agents have access to a common database, and each has to carry out a set of queries. The result of each query is a set of records. For example, agent At may want the records satisfying the condition "All female employees of company X earning over $50,000 a year", and agent A2 may want the records satisfying the condition "All female employees of company X with more than 10 years of seniority". Agents can exchange results of queries and subqueries at no cost. Task set: All possible queries, expressed in the primitives of relational database theory, including operators like join, projection, union, intersection, and difference. Cost function: The cost of a set of queries is the minimal number of database operations needed to generate all the records. It is possible to use the result of one query as input to other queries, i.e., the operations are not destructive. Description: Agents are sending faxes to locations on a telephone network (a weighted graph), To send a fax, an agent must establish a connection with the receiving node. Once the connection is established, multiple faxes can be sent at no extra cost. The agents can, at no cost, exchange messages to be faxed. Tusk set: The set of all possible receiving nodes in the network. If node x is in an agent's task set, it means that he has at least one fax to send to n. Cost function: There is a cost associated with establishing a single connection to any node x. The cost of a set of tasks is the sum of the costs of establishing connections 218 G. Zlorkin, J.S. Rosens~hein/Art~~ciuI lntelli~mc~e 86 (I 996) 195-244 to all the nodes in the set. Thus, the cost of a dial-up connection to a given node is independent of other nodes in the task set. Description: There are a set of identical pegs, a basket, and a set of holes. A peg can be in a hole, in the basket, or in an agent's hand. Each hole is labeled as either black or white, and can hold at most one peg. One agent is only concerned with the configuration of pegs in black holes, and the other is only concerned with the configuration of pegs in white holes. Each agent has a list of (his own color) holes to fill or empty. There are enough pegs to satisfy both agents' goals. There are two operations in this world: Pickup (pick up the peg from a non-empty hole or any peg from the basket), and PutDown (put down the peg which is currently being held into an empty hole or the basket). An agent can hold no more than one peg at a time. Tusk set: A single task (s, h) is to have hole s contain h pegs, where h is 0 or 1 (i.e., make hole s empty or have it contain one peg only). 7 = (s, h): s is a hole, h E (0, I}. In each encounter the world is in some initial state (this is an encounterspecific parameter that affects the cost function, but the cost function is still identical for all agents). One agent has a consistent task set that includes only white holes, while the second agent has a consistent task set that includes only black holes. Cost function: The cost of a consistent set of tasks X is the minimal set of Pickup, PutDown operations that need to be done to move the world from its initial state to a final state that achieves all tasks in X. There is at least one minimal cost plan that does not involve the other agent's holes (neither takes nor places pegs into those holes). Having introduced the TODs above, we now turn our attention to attributes that these domains exhibit. These attributes strongly affect their relationships to negotiation mechanisms. We will focus on the attributes of subadditivity, concavity, and modularity. The motivation for these definitions are presented in more detail below. In other words, by combining sets of tasks we may reduce (and can never increase) the total cost, as compared with the cost of achieving the sets alone. All the TOD examples above are subadditive, except the delivery domain. To see why the delivery domain is not subadditive, consider the encounter shown in Fig. I. The cost of task a (i.e., the cost of delivering something to node a from the distribution point) is 1, which is also the cost of task 6. However, the cost of the union of a and b is 3 (the deliverer, after delivering to one, must go back to the distribution point before continuing to deliver to the other). Thus the cost of the union of the tasks (3) is greater than the sum of the costs of the individual tasks (2). In the delivery domain there can be non-subadditive encounters. In this article, we are mainly concerned with two-agent subadditive domains. Definition 4 (Concavity). TOD (7, A, c) will be called concave if for all finite sets of In other words, the cost that an arbitrary set of tasks Z adds to a set of tasks Y cannot be greater than the cost Z would add to a subset of Y. The proof of this theorem and all other theorems, as well as additional lemmas, can be found in Appendix A. The general postmen domain, and the black/white hole domain, are not concave. The other TOD examples (the fax domain and the database query domain) are concave. The postmen domain is not concave because there may be cases such that a task (or a set of tasks) can add more to some other set of tasks than it adds to a subset of it. Such an example can be seen in Fig. 2 . Every edge between nodes has cost 1. LetX={d,e,f,g} CY={b,c,d,e,f,g} and Z=(h). ({h,c,d.r.,f'.g,h}) =9 5, c({h,c,d,e,f,g})  Therefore, we have a violation of the concavity condition: An example of the non-concavity of the black/white hole domain can be seen in Fig. 3 . In the initial state (as can be seen in the top of Fig. 3 ) slot I is empty while slots 2 and 3 are filled. X includes the task ( I. I ) (i.e., slot I is filled). The cost of achieving X from the initial state (c(X) ) is 2. All we need to do is to Pickup one block from the basket or from other slots and then to PutDown the block in slot I. Y includes X and an additional task to empty slot 2 (i.e., Y = { (1, 1). (2,O)) ). To achieve Y we also need to do only one Pickup (this time we will pick the block in slot 2 up) and one PutDown (i.e. c.(Y) = 2). Z includes one task: to empty slot 3 (i.e., Z = ((3,O))). For this reason, c( X L Z) = 2, which is achieved by picking up the block in slot 3 and putting it down in the empty slot I. However. C( Y li Z) = 4. because we will need to move one block (from slot 2 to slot I ) to achieve Y, and then we will need to move another block (from slot 3 to the basket) to achieve Z. Again, we have a violation of the concavity condition: Theorem 6 In other words, the cost of the combination of two sets of tasks is exactly the sum of their individual costs minus the cost of their intersection. Only the fax domain from the above TOD examples is modular. As stated in Theorem 6, the postmen domain restricted to a tree topology is concave. A graph has a star topology if there is no more than one node with degree greater than one (a star topology is a subcase of a tree topology). The node with degree greater than one is called the center of the graph. If we further restrict the postmen domain to trees that have star topologies (where the post office is at the center), then we have a modular TOD. A star example can be seen at the left side of Fig. 4 , where the post office is at node a. In a star topology the cost of visiting two different nodes u, w E 7 is equal to the sum of visiting each node separately, i.e., u # w --+ c( {u} U {w}) = c( {u}) + c<(w)). This implies the modularity condition. The postmen domain restricted to fully connected (there is an arc between any two nodes) and homogeneous (all arcs have the same length) graphs, is also modular. An example of a fully connected and homogeneous graph can be seen in the right side of Fig. 4 . If the length of all the nodes is 1 then the cost of visiting a set of nodes X in a fully connected and homogeneous graph is: c(X) = 1x1 + 1. This simply implies the modularity condition: c(X U Y) = IX U YI + 1 = 1x1 + IYI -IX f? Y( + 1 = (~x~+1)+(~Y~+1)-(~xnY~+1)=c(X)+c(Y)-c(XnY). Non-homogeneous fully connected graphs are not even concave. An example of that is the example seen above in Fig. 3 , with additional sufficiently long additional arcs to make the graph fully connected. C;. Zlotkin. J.S. Hosensc.lzeln/Art~frctul Intelli,  In this section, we develop the framework for formalizing two-agent negotiation mechanisms in subadditive task oriented domains. Similar definitions can be found in our previous work [ 75,77,78 1. Definition 9. Given an encounter ( TI, 7'2 ) within a two-agent TOD (7. {Al, AZ}, c) we have the following: ( I ) A pure deul is a redistribution 01 tasks among agents. It is an ordered list ( DI, 02) such that Dr , D? C 7. and Dl &.J 02 = Tl U Tz. The semantics of such a deal is that each agent An commits itself to executing all tasks in Dk. The cost of such a deal to Ak is defined to he Costk( D1,02) = c( Dk). (2) A mixed deal is a pure deal ( DI, D2) and a probability p, 0 < 11 < I. A mixed deal will he denoted by (D1 1 Dl): p. The semantics of this deal is that the agents will perform a lottery such that, with probability p, DI will be assigned to Al and 02 will be assigned to A?. With probability I -p. DI will be assigned to A2 while D? will be assigned to A 1. The cost of such a deal to Ak is defined to be Costk((Dr, D2): Al has a p chance of executing all the tasks Tl U T, and has a I ~ p chance of doing nothing. With the above definitions of three deal types. we now consider utility, the negotiation set, optimal protocols, and stable negotiation strategies. ( I ) For any deal 6 (pure, all-or-nothing, or mixed) we will define Utilityk( 6) E c(Tk) -Costk(8). (2) The (pure) deal 0 E (TI, Tz ) will be called the conjict deal. (9 is a conflict because no agent agrees to execute tasks other than its own. Note that for all k, Utility,!(O) = 0. When the agents fail to agree, i.e., run into a conflict, they by default execute the conflict deal 0. Our assumption is that rational agents are utility maximizers; since they can guarantee themselves utility 0, they will not agree to any deal that gives them negative utility. For deals 6 and 8' (pure, all-or-nothing, or mixed), we will say that 6 dominates 8, and write 8 + 8, if and only if (Utilityt (a), Utilityz(S)) t (Utility, (6'), Utilityz ( 8) ). We will say that 6 weakly dominates 8, and write 6 k 8, if and only if (Utility, (6), Utilityz( 6) ) k (Utility, (a'), Utility2 (8) ). We will say that 8 is equivalent to 8, and write 6 z 6' if 'Jk(Utilityk(S) = Utilityk (8)). G. Zlotkin, J.S. RosenscheidArtifcial Intelligence 86 (1996) 195-244 223 If S t 6' it means that the deal S is better for at least one agent and not worse for the other. A pareto optimal deal cannot be improved upon for one agent without lowering the other agent's utility from the deal. Since agents are by definition indifferent between two deals that give them the same utility, we are interested in negotiation mechanisms that produce pareto optimal deals (i.e., if agent Al gets the same utility from deals x and y, but A:! prefers y, we don't want them to settle on x). At this point, we are only considering negotiation mechanisms that result in a deal from the NS. These are, in some sense, mechanisms with efficient outcomes. Theorem 16. For any encounter in a TOD, NS over pure deals is not empty. Theorem 17. For any encounter within any TOD, NS over mixed deals is not empty. Having introduced the two mechanisms above (remember that a mechanism includes both a protocol and a strategy), we will shift our attention to the entire class of mechanisms that satisfy the following conditions: l The protocol is symmetrically distributed. l The strategy is in equilibrium with itself. l Given the protocol, if two agents play the strategy they will agree on a deal that maximizes the product of their utilities. If there is more than one product maximizing deal, they will agree on a deal (among those product maximizers) that maximizes the sum of utilities. If there is more than one such sum maximizing product maximizer, the protocol will choose among those deals with some arbitrary probability. This definition implies both individual rationality and pareto optimality of the agreed-upon deals. We will call this class of mechanisms the product nmximizing mechanisms, or PMMs. All PMMs are efficient. Throughout the rest of this article, we will not be concerned with exactly which negotiation mechanism agents use:, as long as it belongs to the PMM class. Their arc a number of existing approaches to the bargaining problem in game theory. One of the earliest and most popular was Nash's axiomatic approach [ 43,501. Nash was trying to axiomatically define a "fair" solution to a bargaining situation. He listed the following criteria as ones that a fair solution would satisfy: ( 1 ) Individual rationality (it would not be fair for a participant to get less than he would anyway without an agreement). (2) Pareto optimality (a fair solution will not specify an agreement that could bc improved for one participant without harming the other). ( 3 ) Symmetry (if the situation is symmetric. that is, both agents would get the same utility without an agreement, and for every possible deal, the symmetric deal is also possible. then a fair solution should also be symmetric, that is, give both participants the same utility). (4) Invariance with respect to lineal-utility transformations. For example, imagine two agents negotiating on how to divide $100. If one agent measures his utility in dollars while the other measures his in cents. it should not influence the fair solution. Similarly, if one agent already has $10 in the bank, and evaluates the deal that gives him .x dollars as having utility 10 + x while the other evaluates such a deal as having utility .t-, it should not influence the fair solution (i.e.. change of origin doesn't affect the solution). ( 5) Independence of irrelevant altcrnativcs. Imagine two agents negotiating about how to divide IO, 000 cents. The Nash solution will be 5,000 cents for each, due to the symmetry assumption above. Now imagine that the same agents arc negotiating over $100. Even though there are now some deals that they can't reach (for example. the one where one agent gets $49.99, and the other gets $30.01). the solution should be the same. because the original solution of 5,000 cents can still be found in the new deal space. Nash showed that the product maximizing solution not only satisties the above criteria. but is the only solution that satisfies them. The first four criteria above are explicitly or implicitly assumed in our own approach (in fact. for example, our version of the fourth assumption above is more restrictive than Nash's). The fifth criteria above is not ussutmd in our work, but turns out to be true in some cases anyway. We USC the Nash solution, in general, as a reasonable bargaining outcome, when it is applicable. Nash, however. had some assumptions about the space of deals that we do not hold. For example, the Nash bargaining problem assumes a bounded, convex, continuous, and closed region of negotiation. In our agent negotiations, we do not assume that the space of deals is convex, nor that it is continuous. Definition 18. A product maximizin g mechanism (PMM) over a set of deals is a mechanism that has a negotiation strategy that is in equilibrium with itself-if all agents use this negotiation strategy, they will agree on a deal in NS that maximizes the product of the agents' utility [SO]. If there is more than one such deal that G. Ziorkin, J.S. Rosen.~chein/Art~ci~l fnteiligence 86 (1996) 195-244 22s maximizes the product, the mechanism chooses one arbitrarily, with equal probability. Note that a PMM by definition satisfies the stability and efficiency criteria mentioned in Section 5. The monotonic concession protocol defined above in Section 2.5. I has an ~uilibrium strategy for each deal type that yields agreement on a deal in NS that maximizes the product of the agents' utility. Those strategies are based on Zeuthen risk criteria [ 741, and were presented in [ 751. Therefore, the monotonic concession protocol (mentioned in Section 25.1) is a PMM.  Sometimes agents do not have full information about one another's goals. This raises the question of whether agents can benefit from concealing goals, or manufacturing artificial goals. This lying can either occur explicitly, by declaring false goals, or implicitly, by behaving as if these false goals were true, depending on the specific negotiation mechanism. Our work in previous papers [ 75,77,78] partly focused on combinations of negotiation mechanisms and domains where agents have no incentive to lie. A negotiation mechanism is called incentive compatible when the strategy of telling the truth (or behaving according to your true goals) is in equilibrium (i.e., when one agent uses the strategy, the best thing the other agent can do is use the same strategy). In the postmen domain [ 751, we identified three types of lies: ( 1) hiding tasks (e.g., a letter is hidden) ; (2) phantom tasks (e.g., the agent claims to have a letter, which is non-existent and cannot be produced by the lying agent); (3) decoy tasks (e.g., the agent claims to have a letter, which is non-existent but can be manufactured on demand if necessary). Since certain deals might require the exchange of letters, a phantom lie can be uncovered, while a decoy lie (and of course a hidden lie) cannot. Thus, a phantom lie under certain negotiation mechanisms is "not safe". Different domains differ as to how easy or hard it is to generate decoy tasks. In this section, we provide a characterization of the relationship between kinds of lies, domain attributes, and deal types. There are three kinds of lies in TODs, and we have considered three domain attributes (subadditivity, concavity, modularity) and three classes of optimal negotiation mechanisms, based on pure, all-or-nothing, and mixed deals. The resulting three-by-three-by-three matrix is represented in Fig. 5 . Its notation is described below. Consider the entry under subadditive, all-or-nothing deal, decoy lie (we'll refer to this as entry [a, j, z] ) . The entry L at that position means that for every optimal negotiation mechanism that is based on all-or-nothing deals, there exists a subadditive domain and an encounter such that at least one agent has the incentive to lie with a decoy lie (L means lying may be beneficial). The entry T at position [b, k. z] means that for every concave domain and every encounter within this domain, under any optimal negotiation mechanism based on mixed deals, agents do not have an incentive to lie with decoy lies (T means telling the truth is always beneficial). The entries in the table marked T/P (such as [ a,j, y] ) refer to lies which are not beneficial because they may always be discovered (in any encounter within the domain) ; if the agent tells the truth, it is because he is afraid of the penalty that will be levied if his lie is discovered. Thus, T/P can be transformed into T if the optimal negotiation mechanism includes a sufficiently high penalty for discovered lies. In the table, there is a relationship between cells. The fact that entry [a,_j,x] is T implies that entry [ b.j, x] will also be T (this is denoted by the /* single shaft arrow in the first cell, and the ,7 arrow going into the T in cell [ b,j, x] ). Similarly, [b, j, x 1 being T implies that entry [ c,j. x 1 will be T (and is also denoted by arrows). This is because modular domains arc concave. and concave domains are subadditive; if there is no incentive to lie even in a subadditive domain, there will certainly be no incentive to lie in concave or modular domains (which are subclasses of subadditive domains). Similarly, the I, entry in [u, i. x 1 implies that [b, i, x] will also have an L entry: if a beneficial lie can be found in a modular domain, then it can certainly be found in a concave domain (a superset). These downward influences of L are also marked in the table. with J arrows. There is also a relationship between certain table entries with the same domain attribute (these relationships are denoted by double shaft arrows like +). For example, if there is no incentive to lie in general mixed deals, there is no incentive to lie in all-or-nothing deals (which are a subset). Thus, the T in cell lb, k, z] implies the T in cell [b,j,z] (it also implies [b,k,y], which in turn implies [b, j, y 1, .). To fill out the table, therefore, we need only demonstrate a small number of "fixed points", which in turn imply all the other table entries. The fixed points that need to be demonstrated are numbered in the table from I to 8. We demonstrate the values for these 8 cells, and present some other theorems that make general statements about optimal negotiation mechanisms. G. Zlotkin,  The four incentive compatible fixed points are determined by the theorems below. Theorem 20 (Fixed point 1) . For any encounter in u ho-agent subaddit~ve TOD, and any optimal negotiation mechanism over all-or-nothing deals, every "hiding" lie is not beneficial. Since an all-or-nothing deal is always a candidate agreement, the negotiation mechanism might arbitrarily choose it. This is the reason that the L in [a, k, z] is implied by the L in [a, j, z] . If there exists an encounter in which one of the agents has an incentive to lie when the negotiation is over all-or-nothing deals, then in the same encounter the same agents have the same incentive to lie when negotiating over general mixed deals: the agreement can always be an all-or-nothing deal. Another consequence is the following theorem. Because of the theorem above, it is clear that for concave domains, agents cannot benefit by lying when all-or-nothing deals are in use-i.e., any optimal negotiation procedure over all-or-nothing deals is incentive compatible. This is also true for modular domains (a subcase). This can be seen in the table, where the entire all-or-nothing row is marked T for modular and concave domains. Additionally, in a subadditive domain where decoy tasks cannot be generated, an optimal negotiation procedure over all-or-nothing deals with a penalty mechanism for discovered lies is incentive compatible (this was shown, in a different form, in [ 751) . This can be seen in the table, where the all-or-nothing row is marked with T and T/P (excluding the decoy column). (Fixed point 4) . For any encounter in a two-agent modular TOD, and any optimal negotiation mechanism over pure deals, every "decoy" lie is not benejicial.  Theorem 25 Non-incentive compatible ,jixed points For an example of a beneficial phantom lie in a concave domain using a negotiation mechanism over pure deals, consider the following example in the postmen domain restricted to graphs that have a tree topology (this domain is concave, due to Theorem 6) : Example of a phantom letter. Consider the graph given on the left of Fig. 6 (the length, and thus the cost, of each edge is written next to it). The post office is at the root of the tree; both agents Ai and A2 need to deliver letters to nodes a and 0. Each agent has a 0.5 chance of delivering the letters to (I (Utility = 2) and a 0.5 chance of delivering the letters to b (Utility = 4). The expected utility for both is 3. What happens when AI creates a phantom letter, and tells A2 that he has another letter to deliver to node c? See the right side of Fig. 6 . The cost for Al of delivering his letters plus the phantom letter is now 12. It would not be individual rational for A2 to visit c; A1 will thus have to visit c, and he could deliver AZ'S letter to b on his way. So they will agree on a deal where A 1 delivers the letters to b and c (with apparent utility of 4, and actual utility of 4). Thus, Al's utility has risen from 3 to 4 by creating this phantom letter. This lie is also a "safe" lie, since A2 cannot verify whether the phantom letter was actually delivered. For an example of a beneficial decoy lie in a subadditive domain (e.g., the postmen domain with an unrestricted graph topology) using a negotiation mechanism over allor-nothing deals, consider the following example. Example. Let the graph be as in Fig. 7 . Every edge between nodes has cost I. Agent Al needs to deliver letters to nodes d. e, f, and g, with a total cost of 6. Agent A2 needs to deliver letters to nodes b and c, with a total cost of 4. If Al tells the truth, both utilities will be 1.5 (Al will do the whole cycle with probability &). After Al lies with producible decoy letter to node h, his apparent cost is still 6. Delivery of the entire set of letters, however, now (apparently) costs 9. They will agree on the deal that gives both agents apparent utility of 0.5. Agent A2 will do the entire delivery, including the decoy letter, with probability 6, in fact getting utility of 0.5. Agent Al, however, will simply do the cycle (i.e., without the decoy letter), with probability g, getting an actual utility of 1.72. Lying is thus beneficial for Al: telling the truth gives him a real utility of 1.5, while lying gives him a real utility of 1.72. The example above is an instance of a more general case. It turns out that if an agent knows the relationship between his and his opponent's total costs in an all-or-nothing negotiation, it is possible for him to reliably generate a beneficial "default" lie that is made up of decoy tasks. In a subadditive domain, like the postmen domain, he can generate extra decoy tasks "along the way" (i.e., that don't increase his stand-alone cost), but which improve his position in the final agreement. This can only be done by A1 when the cost of Ti is greater than the cost of T2. The example above is an instance of this situation. The important result here is that the lie can be generated reliably without having full information about the other agent's set of tasks. To demonstrate fixed points 7 and 8, we bring two examples from the postmen domain that have as their topology that of a star; this is a modular TOD, and represented in Fig. 8 . The post office is in the center of the star, and the length of the lines represent the distances from the post office. Consider the left example in Fig. 8 . Both agents have to deliver letters to nodes b (at a distance of 1) and e (at a distance of 2). Note that c(T,) = c(T2) = c(Tl U T2) = 6. If both agents tell the truth the negotiation mechanism will arbitrarily send one to node b and one to node e. If agent A1 hides his letter to node b, then the only pure deal that maximizes the product of the agents' utilities is the one that sends agent A1 to node b (!) and agent A2 to node e. Thus, agent Al benefits from his lie. Intelligence 86 (1996) 195-244 (AI,A~) Fig. 8 . Slar topologies for postmen delivery. Consider the right example in Fig. 8 . Agent Ai has to deliver a set of letters that includes ones to nodes a, c, d, e. and f. Agent A2 has to deliver a set of letters that includes ones to nodes a, b. c. d. and e. Note that c(Tl) = c(T2) = 10, and c(Tl UT2) = I?. If Al hides his letter to node a, then let r; be his apparent set of tasks (without node a). Note that ,,(r;) = 8, and c(T; i_l T?) = 12. Using any PMM, under the assumption that Al's true set of tasks is T;, they can agree on a mixed deal (X, Y) : p such that X = {a,f}, Y = {b,c,d,e}, and p = i (call this deal a*). Let UT stand for the utility of AI from S*. and cl; stand for AZ'S utility from that same deal. Utility cl: = U; = 3. But Al's real utility is IO -$4 -$ IO = 4.5 which is greater than 4, the utility he would have gotten if he had told the truth. The all-or-nothing deal is not beneficial for Al because the agents would agree on the probability p = 6, which would give agent Al a real utility of 10-h 12-62 = 32 < 4. However, the expected payoff for the lying agent is 4i, i.e., still over 4, even when the negotiation mechanism sometimes chooses the all-or-nothing deal, so the lying agent benefits. To provide agents with a suitable interaction environment in which they can coordinate, it may be desirable to establish high-level protocols that motivate socially beneficial (and individually beneficial) behavior. Game theory can provide tools appropriate to the design of these protocols. Some of the attributes that designers might like to see in interaction environments are efficiency. stability, and simplicity. The design of suitable protocols is closely connected to the domain in which agents will be acting. Certain protocols might be appropriate for one domain, and inappropriate for another. In almost all cases, it is important to provide protocols that can deal with incomplete information on the part of agents, while maintaining the stability of the overall mechanism. In this article we have presented a general domain theory to use in analyzing negotiation protocols. We have characterized task oriented domains (TODs), which cover an important set of multiagent interactions. G. Uotkin, We have presented several examples of TODs, and examined three attributes that these domains can exhibit, namely subadditivity, concavity, and modularity. We have then enumerated the relationship between deal types, domain attributes, and types of deception, focusing on whether an agent in a TOD with a given attribute and deal type is motivated to always tell the truth. In particular, we have shown that in concave TODs, there is no benefit to an agent's lying when all-or-nothing deals are in use. In a general subadditive domain, however, when agents are able to generate decoy tasks, even allor-nothing deals are not sufficient to create stability (discourage lies). In addition, we demonstrated that in subadditive domains, there often exist beneficial decoy lies that do not require full information regarding the other agent's goals.
Most of the research develops protocols and strategies for agents that reallocate tasks between themselves (e.g. REF ).
Mechanism design for automated negotiation, and its application to task oriented domains
ARTIFICIAL INTELLIGENCE
Computer Science