A Negotiation-Based Coalition Formation Model for Agents with Incomplete Information and Time Constraints Leen-Kiat Soh Department of Computer Science and Engineering University of Nebraska, Lincoln, NE 68588 Tel: (402) 472-6738 Fax: (402) 472-7764 E-mail: [email protected] Abstract In this paper we describe a coalition formation model for a cooperative multiagent system in which each agent has incomplete information about its dynamic and uncertain world and must respond to sensed events within time constraints. With incomplete information and uncertain world parameters while lacking time, an agent cannot afford organizing a rationally optimal coalition formation. Instead, our agents use a two-stage methodology. When an agent detects an event in the world, it first compiles a list of coalition candidates that it thinks would be useful, and then negotiates with the candidates. A negotiation is an exchange of information and knowledge for constraint satisfaction until both parties agree on a deal or one opts out. Each successful negotiation adds a new member to the agent’s final coalition. The agent that initiates the coalition needs to determine the task distribution among the members of the coalition and designs its coalition strategy to increase the chance of successfully forming a working coalition. Since the environment is dynamic, noisy, and the agents are resource-constrained, agents must form the working coalition to react to events as soon as possible and with whatever partial information they currently hold. 1. Introduction In this paper we describe a coalition formation model for agents with incomplete information and time constraints within a dynamic and uncertain world. A coalition is a group of agents that collaborate to perform a coordinated set of tasks, that may be a response to an event that has occurred in the environment. A dynamic coalition is one that is formed as a response to an event and dissolved when the event no longer exists or when the response is completed. A coalition is necessary when an agent cannot respond to an event all by itself due to lack of information, knowledge, or functional capabilities. Ideally, the agent would prefer to form an optimal coalition to maximize the yield of the system as a whole. However, such optimal rationalization requires the agent to have complete information about its world and its neighboring agents, and also about the uncertainty associated with all factors related to the multiagent infrastructure. When that information is not readily available and the collection of that information is too costly, an agent cannot afford such optimality. In the following, we elaborate on some of the problem characteristics. First, our model applies to an environment where each agent has incomplete information about its world. Incomplete information may be due to (1) polling and updating costs, (2) constrained resources, and (3) decentralized information base. In a time-critical domain, agents may not afford to poll for information or update the changes in their perceived environments constantly. Moreover, in cases where resources are constrained such as the size of a centralized blackboard, or shared communication channels, agents can only exchange information when necessary. Further, in a domain where each agent senses its local world and maintains a local 1 Report Documentation Page Form Approved OMB No. 0704-0188 Public reporting burden for the collection of information is estimated to average 1 hour per response, including the time for reviewing instructions, searching existing data sources, gathering and maintaining the data needed, and completing and reviewing the collection of information. Send comments regarding this burden estimate or any other aspect of this collection of information, including suggestions for reducing this burden, to Washington Headquarters Services, Directorate for Information Operations and Reports, 1215 Jefferson Davis Highway, Suite 1204, Arlington VA 22202-4302. Respondents should be aware that notwithstanding any other provision of law, no person shall be subject to a penalty for failing to comply with a collection of information if it does not display a currently valid OMB control number. 1. REPORT DATE 3. DATES COVERED 2002 2. REPORT TYPE 00-00-2002 to 00-00-2002 4. TITLE AND SUBTITLE 5a. CONTRACT NUMBER A Negotiation-Based Coalition Formation Model for Agents with 5b. GRANT NUMBER Incomplete Information and Time Constraints 5c. PROGRAM ELEMENT NUMBER 6. AUTHOR(S) 5d. PROJECT NUMBER 5e. TASK NUMBER 5f. WORK UNIT NUMBER 7. PERFORMING ORGANIZATION NAME(S) AND ADDRESS(ES) 8. PERFORMING ORGANIZATION University of Nebraska - Lincoln,Department of Computer Science and REPORT NUMBER Engineering,Lincoln,NE,68588 9. SPONSORING/MONITORING AGENCY NAME(S) AND ADDRESS(ES) 10. SPONSOR/MONITOR’S ACRONYM(S) 11. SPONSOR/MONITOR’S REPORT NUMBER(S) 12. DISTRIBUTION/AVAILABILITY STATEMENT Approved for public release; distribution unlimited 13. SUPPLEMENTARY NOTES 14. ABSTRACT 15. SUBJECT TERMS 16. SECURITY CLASSIFICATION OF: 17. LIMITATION OF 18. NUMBER 19a. NAME OF ABSTRACT OF PAGES RESPONSIBLE PERSON a. REPORT b. ABSTRACT c. THIS PAGE 37 unclassified unclassified unclassified Standard Form 298 (Rev. 8-98) Prescribed by ANSI Std Z39-18 information base at remote sites, it is prohibitive for every agent to share all local information bases as some information may not be needed and keeping the information concurrent may impose constraints on local agents unnecessarily. As a result, when an agent needs to rationalize based on its profile of other agents to form a successful coalition, it can only do so based on partial or outdated information. In a coalition formation process, that means the coalition- initiating agent may know which other agents can be useful but can only guess at their willingness to help. Our goal is to provide a model that increases the chance of a successful coalition formation. Second, an optimal rationalization for coalition formation may not be possible due to (1) noise and uncertainty in the environment, and (2) time constraints. For example, the communication channels among the agents may be congested or faulty, messages may be noisy or lost, perceived events may be qualified inaccurately, and so on. These uncertainties as a whole render rationally optimal (but otherwise arduous) planning less cost efficient compared to one that is more reactive, since the longer the initiating agent takes to respond to an event, the more likely it is going to change in the dynamic environment. Thus, an initiating agent has to compromise on the optimality of its coalition formation strategy before a change in the world pre-empts its effort. Moreover, the domain environment that we want to address is highly time- critical. A coalition formation process has limited time to complete depending on the time available to respond to an event. Third, in our problem domain, we assume all agents are peers—there is no hierarchy among the agents. Each agent is able to sense its environment, revise its own perceptions, and form its own coalitions. This allows the agents to be reactive to environmental changes, without having the directives passed from a higher-up agent while encouraging diversity in information stored at each agent. We also assume agents are cooperative as opposed to self-interested. Each agent is implicitly motivated to cooperate for the common good of the system while managing the usage of its allocated resources. This allows our model to relax the computation of cost-benefit ratio requirements, which would have to be adhered to in an optimal rationalization. Fourth, we propose using negotiations to refine a coalition. We see negotiation as an exchange of necessary information pertinent to individual constraints, perceptions, and commitments. This exchange of information is performed only when the coalition-initiating agent approaches potential coalition partners to request for help. Thus, the exchange is efficient. It also allows both parties of a negotiation to update their viewpoints of each other, and that results in better-informed decision making in the future. The motivation of a negotiation is for the initiating agent to persuade a potential coalition partner to agree to help. Our negotiation- based coalition formation also implies that even though the coalition-initiating agent is in charge of the entire formation process, the responsibility of making the decision to join lies on the shoulders of the potential coalition partners. All the coalition-initiating agent can do is to prepare an initial coalition—based on whatever the information that it currently has—that it thinks has a high chance of success and proceed from there. This negotiation allows the initial coalition to be less than optimal and to be computed hastily. Fifth, unlike traditional coalition formation work that assume potential coalition members are readily willing to help, our model expects coalition members to refuse to join in a coalition, especially in a resource-constrained environment and also plans for failed communication due to congestion, noise, or message loss. Thus, the initial coalition may not survive after negotiations as the working coalition is finalized. Our model is also designed to withstand noise and uncertainty by incorporating insurance policies and algorithms that are greedy or worried. 2 Briefly, our proposed model works as follows. When an event is detected in a multiagent system, one of the agents initiates the coalition formation process in hope of organizing a group of cooperative agents to perform tasks in response to the event. This initiating agent (also known as the “computing agent” (Sandholm and Lesser 1995)) shoulders the responsibility of designing the best coalition given the situated information to increase the chance of forming a working and useful coalition at the end of the process. The model consists of two stages. First, during the coalition initialization, the initiating agent extracts a ranked list of useful agents. Then, the initiating agent approaches the potential coalition partners and requests for negotiations during a coalition finalization step. Our negotiation is based on a case-based reflective argumentative model (Soh and Tsatsoulis 2001). Finally, the agent re-designs its coalition if it fails to satisfy its response to the triggering event and if time permits. This three-step model allows an agent to form an initial coalition quickly to react to an event and to rationalize to arrive at a working final coalition as time progresses. In the following, we first discuss the agent characteristics of multiagent system that our model assumes. Then, we present our dynamic negotiation-based coalition formation model in Section 3. Subsequently, we describe our current work using the model in a multiagent sensor tracking problem domain and discuss some experimental results. In Section 4 we describe some related work in coalition formation. Finally, we conclude. 2. Agent Characteristics Readers are referred to (Wooldridge and Jennings 1995) for a detailed discussion on various agent characteristics. In general, our model assumes that agents have the following characteristics: (1) Autonomous – Each agent runs without interactions with human users. (2) Rational – Each agent is rational in that it knows what its goals are and can reason and choose from a set of options and make an advantageous decision to achieve its goal. In the resource allocation domain, each agent is selfish as each attempts to preserve its control of CPU resources and conserve its power usage, for example. Yet, each agent is bounded by a global objective that demands each agent cooperate to share resources. The two balancing goals drive the rationality of our agents. (3) Communicative (4) Reflective – According to Brazier and Treur (1996) in their DESIRE framework, a reflective agent reasons based on its own observations, its own information state and assumptions, its communication with another agent and another agent’s reasoning, and its own control or reasoning and actions. (5) Honest – Each agent does not knowingly lie or intentionally give false information. This characteristic is also known as veracity (Galliers 1988). (6) Cooperative -- Each agent is motivated by a set of global directives to help each other when possible to achieve global goals. Each agent is honest and sincere during a negotiation— does not intentionally provide faulty information just to convince another to perform a task or give up a certain resource. The initiating agent trusts the responding agents that they must have their reasons for not agreeing to a deal during a negotiation, and also trusts the responding agents to commit to an agreement as best as possible. There are in general three reasons why agents cooperate (Shehory et al. 1997). First, an agent cannot perform a specific task by itself. Second, an agent can perform a specific task, but other agents are 3 more efficient in performing the task. Third, an agent can perform a specific task, but working on it collaboratively will increase the benefits from the task (or reduce the costs). We also assume that each agent exists in a neighborhood (Section 3.1) where it knows some basic properties of its neighbors (such as functional capabilities) and can communicate to them directly. Each agent has one neighborhood, and each can exist in multiple neighborhoods of others. It is from this neighborhood that an agent forms a coalition. 3. Dynamic Negotiation-Based Coalition Formation Model In this section, we present our dynamic negotiation-based coalition formation model. As discussed in Section 1, our agents operate in a dynamic, real-time and uncertain world. When an agent detects an event, it selects from its neighborhood a subset of neighbors as the initial coalition candidates. It determines the task allocation among the candidates and how it should approach these candidates via negotiations. Thus, it shoulders the initial computation cost for the coalition formation. Subsequently, the agents negotiate to exchange information on their respective constraints, commitments, and perceptions. This allows the coalition to be refined as time progresses. Eventually, all negotiations complete with either a success or a failure. The initiating agent and the candidates that agree to help become members of the final coalition. In our domain, due to the uncertainty in message loss and noise and the dynamic nature of the system, not all coalition candidates become the eventual coalition members. Thus, an initiating agent must design its coalition formation strategy with that in mind. Our coalition formation model consists of two stages: coalition initialization (Section 3.3) and coalition finalization via negotiations (Section 3.4). An interruptible mechanism can be installed in the initialization stage; for example, to stop coming up with feasible coalitions when the time allocated to the step runs out. The coalition finalization stage is interruptible and adaptive as an agent can elect to stop negotiations when it sees fit. 3.1. Neighborhood As previously discussed in Section 2, each agent, a , has a neighborhood, h . It knows some i a i intrinsic information about all neighbors, h ˛ h , in this neighborhood such as a neighbor’s k,a a i i physical location, its functional capabilities, and so on. The functional capabilities of an agent a are denoted as f . An agent can belong to different neighborhoods concurrently; however, it i a i does not necessary have knowledge about those neighborhoods except its own. An agent can communicate directly with all its neighbors, and each neighbor can communicate with the agent directly as well. However, those neighbors may not be able to communicate with each other directly because they are not necessarily neighbors of each other. Suppose we denote the ability ( ) to communicate directly by an agent, a , with another, a , as Comm a ,a . Then in a ( ) i ( ) j i j neighborhood of a , Comm a ,a and Comm a ,a are true for all a ˛ h . i i j j i j a i 3.2. Events When an agent senses an event, it measures and collects its properties to perceive it. It is this perception that quantifies the event to facilitate the subsequent coalition design. Suppose an 4 event is denoted as e . It has a time stamp when it was detected, t , a time stamp when it i detected,e i is no longer valid, t , and a categorical type of the event, type . The agent has knowledge end,ei ( ) ei about events of the type type , denoted as K type =t . It contains three basic items: d e e expected,t i i for the expected duration during which the event will be valid, Q for the set of tasks devised as t the standard response to the event, and W for the coalition formation strategy. t Q determines the sequence of tasks that an agent performs in reaction to an event. For t example, suppose an agent senses that it is currently using close to the level of CPU resource that it has been allocated with, then it declares an event, t =CPU_SHORTAGE. Q t=CPU_SHORTAGE may specify the following: (1) re-organize the CPU distribution within all the processing threads of the agent, (2) check to see whether the CPU shortage still persists (2.1) if yes, then go to step (3); (2.2) otherwise, exit from Q , t (3) compute the desired additional CPU allocation, (4) request from the operating system for additional CPU allocation, (4.1) if granted, then exit from Q ; t (4.2) otherwise, go to step (5), (5) obtain from the operating system all the agents (including their respective CPU allocations) sharing the same CPU resource on the same platform, (6) perform dynamic, negotiation-based coalition formation using W , t (7) carry out all deals resulted from successful negotiations, (8) check to see whether the CPU shortage still persists (8.1) if yes, then go back to step (1); (8.2) otherwise, exit successfully from Q . t Equipped with this knowledge, an agent can react to events consistently and plan out its tasks. W specifies the coalition formation strategy which we discuss in detail in the ensuing t sections. 3.3. Coalition Initialization The first stage of the dynamic, negotiation-based coalition formation algorithm is the ( ) determination of the set of the initial coalition candidates, denoted as L a ,e for agent a and ini i j i event e . This notation allows an agent to have concurrent multiple coalitions, one for every j event that it is currently handling. We denote a candidate as a . In this section, we first discuss k different approaches to coalition initialization. Then, we discuss the ranking of coalition members, and even coalitions. Subsequently, we present some task allocation algorithms. 5 3.3.1. Approaches to Coalition Formation In our model, we identify four general scenarios of coalition formation: resource-driven, task- driven, function-driven, and utility-driven. In a resource-driven coalition formation process, the underlying objective is resource ( ) allocation among the agents. For an initiating agent to generate L a ,e , it needs to know the ini i j ( ) list of agents currently using the same resource. Let us denote this list as Y t for agent a , r,a i i resource r, and at time t. If the event e calls for the re-allocation of a resource r, then ( ) j ( ) L a ,e = Y t ˙ h . ini i j r,a a i i In a task-driven approach, the agents are homogeneous in their functional capabilities and only differ in what they know based on their experience, perception, and database. For example, in a multiagent database query system, some information sharing or exchange needs to take place to satisfy a query. The agents in this example are homogeneous in their functional capabilities but differ in what information they can maintain and provide. As a result, an initiating agent ( ) needs to obtain a Y t , for example, that contains the candidates with the necessary q,a i information for responding to the query q. As such, the flexibility in the coalition design is reduced compared to the resource-driven approach discussed above. IThus, the initiating agent ( ) obtains Y t in which all members in the list have the same functional capability f that is f,a i needed to respond to event e . We also denote all functional capabilities that an agent a knows j i how to perform as F . This information may be stored in each agent during start up, or be a i furnished on request, or be registered with a centralized service, or advertised at a common ( ) ( ) blackboard. The initiating agent then obtains L a ,e =Y t ˙ h . Note that the set of ini i (j f,ai) ai functions needed to tackle an event is documented in K type =t . We also denote such a set of e i functions for an event type t as F . t In a function-driven approach, the agents are heterogeneous in their functional capabilities— each knows how to perform a different set of functions. As a result, the coalition design is even less flexible compared to the task-driven approach discussed above. For example, suppose there is a multiagent system that maintains a large database with three different agents: an interface agent, a search agent, and a reporting agent. When a query comes in through the interface agent, a coalition is formed by the interface agent that calls upon the search agent to retrieve the queried results from the database and the reporting agent to output in a format specified by the user. Since each agent is specialized to do a particular set of functions, the interface agent must pick the other two agents as the coalition members. In this restrictive manner, the coalition formation is rather straightforward. Once again, we denote a set of functions required to respond to an event type t as F , and in this function-based approach, F >1. An initiating agent obtains the t t ( ) ( ) ( ) list of useful agents as Y t and L a ,e =Y t ˙ h . Ft,ai ini i j Ft,ai ai When there is flexibility in the coalition design, one can have a utility-driven approach to coalition initialization. For example, in the resource-driven or the task-driven approaches, the ( ) initiating agent may want to narrow down L a ,e to include only what it considers the most ini i j helpful agents. In a strict function-based approach, there is not much flexibility to facilitate 6 utility-based optimization. However, in a system where each agent is capable of some overlapping set of functions, one can then improve the coalition initialization using utility. Suppose an event type t with F is detected, and thus the initiating agent knows that the t { } eventual coalition must perform F = f , f , , f to respond to the event. It also knows that t 1 2 (cid:0) N all agents in its neighborhood know how to perform all the functions but does not know whether they can do it as requested at the current time and situation. As a result, for each function, it ( ) { ( ) ( ) ( )} forms a sub-coalition such that L a ,e = L a , f ,L a , f , ,L a , f . Each sub- ini i j ini i 1 ini i 2 (cid:1) ini i N coalition can then adopt a task-driven approach and enjoys greater flexibility in its design. We will discuss general inter-coalition issues in Section 3.6. 3.3.2. Evaluation of Coalitions and Coalition Members In our dynamic, negotiation-based coalition formation model, the initiating agent a first ( ) (i ) generates the initial coalition candidates, L a ,e , to deal with an event e . L a ,e ini i j j ini i j represents the neighbors that it thinks can be of help to respond to e . To find out whether these j candidates are willing to help, the initiating agent needs to negotiate. Negotiation is a process of exchange of information on individual commitments, constraints, and perceptions and may be lengthy and time-consuming. Hence, the initiating agent must think twice about whom to approach first. This motivates the agent to evaluate its coalition members. The objective is to rank the candidates on their potential utility values to the coalition so that the initiating agent can negotiate with the agents with the highest utility values first. ( ) For a candidate a ˛ L a ,e , we base its potential utility, PU , on three sets of k ini i j a ,a k i ( ) attributes: (1) the past relationship between the initiating agent and the candidate, rel a ,t , past,a k i where t is the point in time when the set of attribute-value pairs in the relationship is collected, ( ) (2) the current relationship between the initiating agent and the candidate, rel a ,t , and (3) ( ) now,ai k the ability of the candidate in handling the event, ability a ,e ,t . All these sub-utility a k j i ( ) ( ) measures map into ´ :0 1 and each is asymmetric such that rel a ,t „ rel a ,t . (cid:2) past,ai k past,ak i Now, we define the past relationship between an agent a and a candidate a . First, suppose i k ( ) that the number of negotiations initiated from an agent a to a is S a fi a , the number i k negotiate i k of successful negotiations initiated from an agent a to a is success (a fi a ), the number of i k negotiate i k negotiation requests from a that a agrees to entertain is entertain(a fi a ), the total number k i neg(otiate k ) i of all negotiations initiated from a to all its neighbors is S a fi h , and the total number i negotiate i a i ( ) of all successful negotiations initiated from a to all its neighbors is success a fi h . In our i negotiate i ai ( ) model, rel a ,t includes the following: past,a k i success (a fi a ) (a) the helpfulness of a to a : negotiate( i k) , k i S a fi a negotiate i k 7 ( ) a fi a (b) the importance of a to a : negotiate( i k) , k i S a fi h negotiate i a i success (a fi a ) (c) the reliance of a on a : negotiate( i k), i k success a fi h negotiate i ai entertain(a fi a ) (d) the friendliness of a to a : negotiate( k i), i k a fi a negotiate k i success (a fi a ) (e) the helpfulness of a to a : negotiate k i , and i k entertain(a fi a ) negotiate k i ( ) a fi a (f) the relative importance of a to a : negotiate k i . i k (a fi a ) negotiate i k The higher the value of each of the above attributes, the higher the potential utility the agent a j ( ) may contribute to the coalition; i.e., each is proportional to rel a ,t . The first three past,a k i attributes tell the agent how helpful and important a particular neighbor has been. The more helpful and important that neighbor is, then it is better to include it in the coalition. On the other hand, the second last attributes tell the agent the chance of having a successful negotiation. The agent expects the particular neighbor to be grateful and more willing to agree to a request based on the agent’s friendliness, helpfulness and relative importance to that neighbor. Note that the above attributes are based on data readily collected whenever the agent a initiates a request to j its neighbors or whenever it receives a request from one of its neighbors. To further the granularity of the above attributes, one may measure them along different event types: for each event type, the initiating agent records the above six attributes. This allows the agent to better analyze the utility of a neighbor based on what type of events that it is currently trying to form a coalition for. In that case, an event type would qualify all the above attributes. Now, we define the current relationship between an agent a and its neighbor a . Suppose i k the number of concurrent negotiations that an agent can conduct is #negotiation_threads, and the number of tasks that the agent a is currently executing as requested by a is i k ( ) task:initiator(task)=h . Suppose success (a fi a ) is the number of ongoing execute k,ai negotiate i k ( ) negotiations initiated from a to a . In our model, rel a ,t includes the following: i k now,a k i ongoing (a fi a ) (a) negotiation strain between a anda : negotiate i k , i k #negotiation_threads ongoing (a fi a ) (b) negotiation leverage between a and a : negotiate k i , and i k #negotiation_threads ( ( ) ) task:initiator task =a (c) degree of strain on a from a : execute( k). i k task:initiator(task)˛ h execute ai 8 ( ) The first attribute is inversely proportional to rel a ,t and the other two are proportional to now,a k ( ) i rel a ,t . The first attribute approximates how demanding the agent is of a particular now,a k i neighbor. The more negotiations an agent is initiating to a neighbor, the more demanding the agent is and this strains the relationship between the two and the negotiations suffer. The last two attributes are used as a leverage that the agent can use against a neighbor that the agent is negotiating with, about a request initiated by the neighbor. ( ) Now, we deal with the ability of the candidate to handle an event e , ability a ,e ,t . ( ) ( ) j ai ( k j ) While rel a ,t and rel a ,t are both domain-independent utilities, ability a ,e ,t past,a k now,a k a k j i i i is domain-specific. For example, in a database system, if a coalition requires a reporting agent and a is a reporting agent, then it has a high ability measure. In a computing system, if an k agent a has a high CPU allocation and the coalition formed is for CPU re-allocation to alleviate k ( ) ( ) a computing crisis for agent a , then ability a ,e ,t is high. Note also that both rel a ,t i a k j past,a k ( ) i i and rel a ,t are time-dependent because the measures change over time as the agent now,ai k ( ) interacts with its neighbors and world. ability a ,e ,t is also time-dependent though not as a k j i obvious. An event is dynamic and thus may require different responses depending on its ( ) characteristics even if its is of the same type. ability a ,e ,t is further influenced by the a k j i current status of the agent a . Depending on the ability of the agent itself to handle an event due i to its current schedule of tasks and computing resources, a candidate a that can perform k approximately what a wants may be better than another candidate that can perform exactly what i { } a wants but for a shorter duration1. For example, suppose an event requires F = f , f , f and i t 1 2 3 a knows how to perform all three functions, candidate a knows how to perform f , and i k 2 candidate a knows how to perform f . Suppose that a is currently performing f and f for l 3 i 2 3 another event, and thus it needs its neighbors to perform f and f for the current event while it 2 3 shoulders the responsibility for f . On the other hand, suppose that a has only one negotiation 1 i thread available, meaning that it can only negotiate with one coalition candidate. Thus, it needs ( ) to decide between a and a . When ability a ,e ,t is further analyzed, the agent realizes that k l a l j i it will soon finish its own execution of f , hence the adjusted ability of a decreases since the 3 l agent a can rely on itself to perform the function in a short time. In addition, functions or tasks i can be prioritized. Here are some priority heuristics that add to the ability of a candidate: (a) if a candidate can provide a functional capability of high uniqueness to the coalition, (b) if a candidate can provide a functional capability of high importance (with inflexible constraints) to the coalition, (c) if a candidate can provide a functional capability that is very time consuming, or (d) if a candidate can provide a functional capability that is resource taxing. 1 Assuming that it is more likely to reach a deal when the request is flexible from the initiating agent, it is then easier to form a coalition when approximated abilities are acceptable. 9