Steven P. Ketchpel[1]
Stanford University, Computer Science Department, Stanford, CA 94305, USA
Abstract. Coalitions of agents can work more effectively than individual agents in many multi-agent settings. Determining which coalitions should form (i.e., what agents should work together) is a difficult problem that is typically solved by some kind of centralized planner. As the number of agents grows, however, reliance on a central authority becomes increasingly impractical. This paper formalizes the coalition formation problem in decision theoretic and game theoretic terms and presents a fully distributed algorithm that can efficiently determine coalitions that will be approximately "stable." Stable coalitions are resistant to attempts of outsiders to break the coalition, because remaining in the coalition maximizes the expected reward for each agent in the coalition. The algorithm is a variant of the "stable marriage matching with unacceptable partners" [6]. The Shapley value ([11], [12]) is suggested as a fair method to divide the coalition's utility among the members.
Work in DAI has been split into two categories: multi-agent systems and distributed problem solving [9]. The algorithm presented below falls into the multi-agent systems area. It is concerned with the interaction of a large number of self-interested agents. Each agent is "rational" in the economic sense of being a utility maximizer. An independently motivated agent may not be willing to settle for a plan generated by a centralized planner. In many cases the community-optimal plan calls for one or more agents to sacrifice individual utility for the sake of the community. A rational agent would attempt to locate other plans that would maximize its own utility rather than executing the prescribed plan from the centralized planner. In addition, a central planning node is a potential communication bottleneck or system crippling fault point. Therefore, a decentralized solution is preferable, especially in a situation where the agents may be mistrustful of one another.
Agents in a multi-agent planning system may benefit by dynamically forming and dissolving work groups. This benefit may result from one of several reasons: 1) the agents may have partially or fully overlapping goals; 2) the agents may have different abilities, so that by exchanging tasks or resources, the assignment among the larger group may be more efficient; or 3) the agents may place different relative values on present and future gains.
The present work addresses this problem of forming work groups or coalitions. More specifically, if each agent has its own goals, how do agents locate other agents with whom they can beneficially collaborate, and how can they fairly share the joint gain that accrues to the coalition? Formally, we want to partition the set of agents into subsets, each of which is a coalition. Each coalition obtains a certain utility, which is shared among the members of the coalition.
* Stability: Each agent is happy with its position, in that there is no way that agents outside a coalition could break the coalition apart by enticing coalition members away with better offers. The excluded agents must lack either the personal incentive to break it apart (i.e., forming a different coalition with some members of the current one would not be to the excluded agents' benefit,) or the means to lure away coalition members (i.e., an agent currently in the coalition would not expect a higher reward if it left). Furthermore, each agent that is included in a coalition prefers being in that coalition to working alone.
* Efficiency: The coalition formation process is efficient in terms of both computational cost and number of communications among the agents. If the added gain of collaborating with the other agents does not outweigh the cost of establishing the coalition, agents will continue to work independently.
* Decentralization: Each agent should take part directly in the calculation and communication. This property is desirable to prevent reliance on a centralized manager, which would increase both the fragility of the system and the potential for bottlenecks.
* Symmetry: No special computational demands should be made on any one agent. All agents play a comparable role, and new agents can be introduced to the community of agents without disrupting the system.
The use of decision theory techniques to analyze AI problems dates back to [3]. The Shapley value ([11], [12]) is a tool from game theory which is used here to determine a fair division of the utility among the agents in a coalition.
Gusfield and Irving [6] present the stable marriage algorithm which guarantees stable matchings among a set of men and women with ranked preference lists. They also include a variant of that algorithm called the stable roommate algorithm which is designed for a single class of agents that both makes and receives proposals. The algorithm is quadratic, and is guaranteed to find a stable matching if one exists, but it requires a centralized planner with complete knowledge of all of the agents' preference lists. In order for this approach to work, all of the agents would need to send their preference lists to one agent, thereby introducing a potential bottleneck and failure point. Additionally, agents may have privacy concerns that prevent the disclosure of their entire preference list. The central agent also makes changes in the preference lists, requiring that there be absolute trust in the central planner, because it is making decisions for the agents without consulting them. Therefore, the Gusfield and Irving proposal does not meet the design criteria.
1. Communication Phase: Each agent gathers the information it needs to determine the compatibility of potential coalition partners.
2. Calculation Phase: Each agent ranks the potential coalition partners, and determines a fair division of the joint utility.
3. Offers Phase: Agents proceed down the preference lists they constructed in Phase 2, extending offers, and accepting or rejecting offers that they receive.
4. Unification Phase: Pairs of agents that accepted each other's offers unify into a single entity for future rounds of formation.
Fig. 1. Phases in coalition formation process
The major contributions of this paper are in the second and third phases, applying the Shapley value for the division of the coalition's utility, and providing a fully distributed algorithm for efficiently creating coalitions of agents.
* Each agent can communicate with every other agent.
* Agents reveal only true information and are obligated to keep the offers they extend to coalition partners.
* Agents are synchronized, with messages being exchanged in discrete "rounds."
* The communication channels are perfect, so that all messages are transmitted faithfully and arrive at their destinations in the time step following the one in which they were sent.
* Utility units are comparable between agents, and further, they are transferrable among agents.
In addition to the above simplifying assumptions, the following restrictions are made to increase the realism of the scenario.
* Communication occurs between two agents at a time. There is no mechanism for broadcasting information to all agents.
* Communication bandwidth is limited. Agents may only send and receive one message at a time. Additional messages are stored in a buffer.
The Shapley value takes into account the different contributions of the agents and splits the reward accordingly. Selecting the Shapley value also ensures the sum of the utility shares of the coalition members is exactly the combined utility of the coalition. As a result, no further negotiation about the excess is required; also, it is impossible for the coalition to fail to obtain enough utility to pay all of the member shares, assuming that the agents agree on the values of the game, and that their valuations are the true ones. For the effects of weakening these assumptions, see [8].
The Shapley value is calculated by looking at each of the different dynamics that could lead to the coalition under consideration. The assumption is that agents form a coalition either by being the "founding" member, or else by joining, one at a time, a coalition that already exists. So the set of formation dynamics is simply the permutations of the agents in the coalition. Each agent adds value to a given formation process of the coalition based on the marginal utility gain created by that agent. For example, if agent A is joining agents B, C, and D, and Click here for Picture and Click here for Picture , then A's marginal contribution under this formation ordering is Click here for Picture . If agent A joins a coalition started by B, and then they are joined by agents C and D, A's marginal contribution is Click here for Picture . These are only 2 of the 24 different permutations that might lead to the final coalition ABCD. By averaging A's marginal contribution across all the different formation possibilities, A's Shapley value is obtained. The underlying assumption is that all of the different formation processes are equally likely, and therefore, the marginal contributions for each formation are weighted equally. This calculation ensures that the sum of the Shapley values for all of the members of the coalition will be exactly the coalition's combined utility.
In general, the Shapley value requires looking at all of the permutations, an exponential operation. By limiting the formation to pairs of agents only, the expense of computing the Shapley value is a small constant. Computing the Shapley value for the formation of a two member coalition by agents X and Y requires only Click here for Picture , Click here for Picture , and Click here for Picture . In this degenerate case of two entities forming a coalition, the Shapley value of X is: Click here for Picture
(1)
symmetrically, the Shapley value of Y is: Click here for Picture
(2)
Note that the sum of these two values is Click here for Picture .
Each agent creates a preference ordering among the offers, in order of decreasing utility that it expects to receive, including all of the agents that made an offer yielding a positive utility. There may be cases in which a coalition obtains a combined utility that is less than the individual utility obtainable by one or both of the coalition members. In this case, the agents prefer to remain unattached rather than forming a coalition, so these agents are not listed in the preference lists. They correspond to unacceptable partners in the stable marriage problem.
There is a person A such that A prefers some person B to its current partner, and person B prefers A to his or her current state in which he or she is either matched to a lower preference partner or unpaired,
OR
Some person prefers being alone to his or her current partner.
The stable marriage with unacceptable partners algorithm proposed in [6] is Click here for Picture , and guarantees a stable matching.
However, when the two classes ("men" and "women") are conflated to a single class of "agents," certain modifications are required. The efficiency of the modified algorithm is also Click here for Picture , and the modified algorithm is also distributed over symmetric agents. The modified algorithm does not, however, ensure that the matching will be stable, even when stable matchings exist. It will be argued in Sect. 3.2 that the formation process effectively minimizes the impact of this instability by discouraging agents from attempting to break up coalitions.
In the algorithm presented here, each agent lists in its preference list all of the other agents with which it could beneficially collaborate. The agents then extend offers to each other according to their preference lists, accepting offers that improve their positions, declining others, until the situation stabilizes.
Figure 2 gives the pseudo-code implementation of the modified stable marriage algorithm from a centralized point of view. The agents actually execute a somewhat different algorithm, which is shown in Fig. 3. The net result duplicates the behavior of the centralized algorithm, but with a distributed implementation. It is as if the centralized algorithm is called with the agent-list consisting of all the entities in the community.
Both the centralized and distributed algorithms make use of the "Next-Agent-to-Ask" and "Current-Partner" properties of an agent, which correspond to how far down in its preference list an agent is and what its current status is, respectively. In the distributed case, an agent only has access to the values of its own properties. At the termination of either algorithm, the "Current-Partner" property will determine which pairs of entities will form coalitions in that round.
If an agent P accepts the offer of another agent A, P may continue to make offers. Even though P prefers A to its current position, there may be an entity higher in P's preference list that would also like to be paired with P. Therefore, P will ask all of its choices ranked more highly than A before the offers phase terminates. For example, agent A might propose to agent P, and agent P accept but try to better its position. P might extend an offer to a third party S, and leave A if S accepts. If S subsequently leaves P, P will continue down its preference list, potentially asking A to accept on the same terms that A had previously offered, and P spurned.
STABLE (agent-list)
BEGIN
IF agent-list is empty, RETURN.
A := agent from the agent-list.
REPEAT
IF at end of preference-list(A) /*A prefers going solo*/
STABLE(agent-list - A).
RETURN.
END-IF.
A offers to join with the next agent on preference-list(A) call it P.
IF P prefers A to its current status /*whether solo or another partner*/
P accepts A's offer to join.
IF Current-Partner(A) not nil
agent-list := agent-list [[union]] Current-Partner(A).
Current-Partner(Current-Partner(A)) := nil.
END-IF.
Current-Partner(Current-Partner (P)) := nil.
agent-list = agent-list [[union]] Current-Partner(P).
Current-Partner(P) := A.
Current-Partner(A) := P.
STABLE (agent-list - A).
RETURN.
ELSE
P Rejects A's offer.
Advance the position in the preference-list(A) for the next agent to ask.
END-IF.
UNTIL false.
END.
Fig. 2. The centralized version of the modified stable marriage algorithm
The decentralized algorithm requires synchronization among the agents, which is captured in the variable MESSAGE-SYNC of the algorithm in Fig. 3. MESSAGE-SYNC goes through the values: EXTEND-OFFERS, RECEIVE-OFFER/SEND-RESPONSE, RECEIVE-RESPONSE, SEND-DUMP-MESSAGE-1, RECEIVE-DUMP-MESSAGE-1, SEND-DUMP-MESSAGE-2, RECEIVE-DUMP-MESSAGE-2. The round may only end if MESSAGE-SYNC has the EXTEND-OFFERS value.
The restriction of allowing only single messages to be read or sent in a round raises a number of timing issues. For example, since several agents may make offers to a single agent at one time, an agent may not be able to respond to all its offers in a single round. Consequently, an agent may not get a response to its offer in the same round that the offer was extended. An agent is restricted to having a single offer outstanding at a time.
BEGIN.
SWITCH MESSAGE-SYNC
CASE: "EXTEND OFFERS"
IF (Current-Partner is preferred to Next-Agent-to-Ask)
listen for end of phase
ELSE
IF NOT(offer-outstanding)
extend offer to Next-Agent-to-Ask
offer-outstanding := TRUE
ELSE
SEND "I'm not done yet!"
END-IF.
END-IF.
CASE: "RECEIVE OFFER & SEND RESPONSE"
get earliest offer from message buffer, call sender S
IF S is preferred to Current-Partner
DUMP1 := Current-Partner
Current-Partner:= S
SEND "I Accept" to S
ELSE
SEND "I Decline" to S
END-IF.
CASE: "RECEIVE RESPONSE"
IF response in message buffer
get response from message buffer, call Sender S
IF response = "I accept"
IF (S is preferred to Current-Partner)
DUMP2:= Current-Partner
Current-Partner:= S
ELSE
DUMP2:= S
END-IF.
END-IF.
move Next-Agent-to-Ask down 1
offer-outstanding := FALSE
END-IF.
CASE: "SEND DUMP MESSAGE X" (X = 1 or 2)
SEND "I'm no longer interested" to DUMPX
CASE: "RECEIVE DUMP MESSAGE X" (X = 1 or 2)
IF RECEIVE "I'm no longer interested"
Current-Partner:= NIL
END-IF.
END.
Fig. 3. The decentralized version of the modified stable marriage algorithm
Agents recognize the end of an offers phase by listening for silence on the communication channels. It is assumed that any agent can detect the presence of any communication, as though the messages were packets being transmitted on Ethernet. If no offers are extended during the EXTEND-OFFERS phase, then each agent is happy with its current position, and the phase can end. Or, an agent might not be able to extend an offer if it is waiting for a response to an offer it has already extended. In this case, the agent sends a dummy message (to itself, if necessary), preventing the phase from ending.
On first examination, the distributed algorithm of Fig. 3 seems to have the problem that an agent may extend an offer, but as soon as the responding agent accepts, the initiating agent dumps the responder. For example, suppose agent A has the preference list B, C, D (from most preferred to least). Agent B's list is E, A. In this case, it would be possible for A to propose to C (having been declined by B in the previous round), and C is willing to accept. As A is offering to C, however, B (having been dumped by E) may offer to A. Agent A accepts the offer from B, and agent C accepts the offer from agent A. When A receives C's response, A's Current-Partner (which was set to B during EXTEND-RESPONSE) is preferred to the responding agent, so A will send a dumping message to C later that same round. This sequence is not problematic, and corresponds to the serial sequence of A offering to C, C accepting, then B offering to A, and A dumping C to join B.
For the communication round, the agents need to exchange two values. The first of these values is the utility that the single agent can earn without forming a coalition, and it is trivial to calculate, by matching as many as possible buy orders to sell orders for each available security, using first the highest buy prices with the lowest sale prices for the same security. For the second piece of information exchanged in the communication phase, an agent needs to tell its coalition partner the full set of customer orders it has, including the number of shares and the price for each order. By combining this information with the receiving agent's knowledge about its own customer orders, each agent can carry out the calculation to determine the value of the coalition. The agent just appends the new orders to its current orders, then proceeds as if it were a single agent with all of the coalition's orders. Since agents outside the coalition cannot affect the coalition's utility in the securities exchange domain (because any two agents can bilaterally execute a trade, outside agents may not "interfere"), the maximum obtainable utility is independent of the excluded agents.
Figure 4 shows that agent 0 has customer orders to buy 100 shares of AAA stock, at any price up to 35; buy 200 shares of BBB as high as 60; buy 100 shares of CCC as high as 50. Other customers have placed sell orders with agent 0, hoping to sell 100 shares of CCC, as low as 45, and 80 shares of DDD as low as 45. The holdings of agents 1 through 3 can be explained similarly. The single agent utility values result from the fact that agents 0 and 2 have buy orders and sell orders for the same stock. That is, agent 0 can buy the 100 shares of CCC from his customer who wants to sell at 45, and then turn around and sell the same shares to his customer willing to buy at 50, thereby keeping the difference of 5 points per share on each of 100 shares.
Agent BUY SELL
0 AAA: 100@35 CCC: 100@45
BBB: 200@60 DDD: 80@45
CCC: 100@50
1 DDD: 30@60 BBB: 100@55
EEE: 150@40
2 DDD: 80@35 AAA: 200@30 EEE: 90@55 BBB: 60@50
EEE: 100@50
3 FFF: 75@40 GGG: 200@25
HHH: 100@30
v(0) = 500 CCC: 100@5 (0 -> 0)
v(1) = 0
v(2) = 450 EEE: 90@5 (2 -> 2)
v(3) = 0
Fig. 4. Securities exchange example initial holdings and single agent utilities
At the end of the communication round, the agents integrate the information and determine the utility for each of the coalitions which they might join. They then compute the Shapley values of each of the parties in these coalitions, and order the various potential coalition partners based on the expected share of utility that they will obtain. Figure 5 shows the utility to each coalition, and the breakdown of utility calculated by the Shapley value.
v(01) = 500 (100 CCC@5 0 -> 0)
500 (100 BBB@5 1 -> 0)
450 (30 DDD@15 0 -> 1)
= 1450
Shapley Value to 0 = Click here for Picture *(500) + Click here for Picture *(1450 - 0) = 975
Shapley Value to 1 = Click here for Picture *(0) + Click here for Picture *(1450 - 500) = 475
v(02) = 500 (100 CCC @5 0 -> 0)
450 (90 EEE @5 2 -> 2)
500 (100 AAA @5 2 -> 0)
600 (60 BBB @10 2 -> 0)
= 2050
Shapley Value to 0 = Click here for Picture *(500) + Click here for Picture *(2050 - 450) = 1050
Shapley Value to 2 = Click here for Picture *(450) + Click here for Picture *(2050 - 500) = 1000
v(03) = 500 (100 CCC@5 0 -> 0)
Shapley Value to 0 = Click here for Picture *(500) + Click here for Picture *(500 - 0) = 500
Shapley Value to 3 = Click here for Picture *(0) + Click here for Picture *(500 - 500) = 0
v(12) = 1350 (90 EEE @15 1 -> 2)
Shapley Value to 1 = Click here for Picture *(0) + Click here for Picture *(1350 - 450) = 450
Shapley Value to 2 = Click here for Picture *(450) + Click here for Picture *(1350 - 0) = 900
v(13) = 0
Shapley Value to 1 = Click here for Picture *(0) + Click here for Picture *(0 - 0) = 0
Shapley Value to 3 = Click here for Picture *(0) + Click here for Picture *(0 - 0) = 0
v(23) = 450 (90 EEE @5 2 -> 2)
Shapley Value to 2 = Click here for Picture *(450) + Click here for Picture *(450 - 0) = 450
Shapley Value to 3 = Click here for Picture *(0) + Click here for Picture *(450 - 450) = 0
Fig. 5. Utility of two agent coalitions and Shapley values
Figure 5 exhibits two interesting properties of the Shapley value. First, the v(03) shows that including an agent that makes no contribution to the pair (such as agent 3, whose orders are for stocks that none of the other agents can obtain) does not decrease the utility obtained by the other agents in the coalition. Since agent 0 can obtain 500 alone, its group share can not drop below 500. A second interesting point is shown by the coalition of agents 1 and 2. In this case agent 2 is compensated for its option of transferring the 90 shares of EEE stock between its own customers, even though this option is never exercised (i.e., all of the stock that agent 2's customer bought came from agent 1's selling customer.)
Figure 6 gives the preference lists of the four agents, and shows one possible set of formation dynamics for the first round. Since the first step of the algorithm presented in Fig. 2 involves selecting an arbitrary agent from the agent list, there are other dynamics that would work equally well, yielding the same results.
Preference Lists
0: 2, 1
1: 0, 2
2: 0, 1
3:
Agent Selected Action Effects
3 3 makes no offers 3 goes solo
1 1 offers 975 to 0 0 accepts
0 0 offers 1000 to 2 2 accepts, 1 dumped
1 1 offers 900 to 2 2 rejects
1 1 makes no offers 1 goes solo
2 2 offers 1050 to 0 0 accepts.
Final Matching
Agent 0 with Agent 2 obtaining 1050
Agent 1 solo obtaining 0
Agent 2 with Agent 0 obtaining 1000
Agent 3 solo obtaining 0
Fig. 6. Preference lists and formation dynamics
Once the coalition for the first round has been formed, the process repeats. Agents 0 and 2 now behave like a single entity, and one of them is designated the head of the coalition to serve as the contact for future coalition negotiation. In the second round, agent 1 would be added to the coalition of 0 and 2. A third round would result in no new coalitions, so the process would end, with agents 0, 1, and 2 in a coalition, and 3 relegated to a solo role.
There are two reasons that instability is to be avoided. The first is that in many cases the unstable solution is not Pareto optimal. Indeed, in the example above, if agents A and B were to form a coalition, they would be better off, without causing any other agents to be worse off. A second reason to avoid instability is that a non-stable solution will probably not be executed as planned. The blocking pair of the non-stable solution would have the incentive to leave their current coalitions and form a new coalition together. Since there is no "enforcement" mechanism that would prevent this defection, it is rational for the two agents to form their own coalition. The algorithms outlined in Fig. 2 and Fig. 3 minimize the ill effects of the instability from the second reason, because an agent is never forced to go solo unless it has been rejected by every agent with which it would like to form a coalition. Therefore, an agent would be less likely to search for ways to break up coalitions since it had already been rejected by every potential partner, so the efforts are likely to be wasted.
The results are shown in Fig. 7. The x-axis indicates the number of agents that were involved in the negotiation. System memory limitations caused the naive exhaustive search algorithm to fail on problems with more than 12 agents. The y-axis shows the amount of utility that the average agent obtained, averaged over 100 runs. The maximum value that any agent could achieve is 499. Comparing the results of the exhaustive algorithm which examined all of the possible pairings with the modified stable marriage algorithm which examines only a subset of the search space shows, as expected, that the stable marriage approach does not do as well in absolute terms. The modified stable marriage algorithm does obtain a substantial fraction of the optimal utility, however, as Table 1 shows. The "Efficiency" column shows the utility obtained by the stable algorithm as a percentage of the optimal values obtained for the same data.
Fig. 7. Performance compared to optimal
Table 1. Efficiency compared to optimal
# of Agents Optimal Stable Efficiency
4 340.3 319.5 0.939
5 326.6 309.0 0.946
6 377.4 358.6 0.950
7 363.3 347.1 0.956
8 406.6 379.3 0.933
9 388.7 373.9 0.962
10 422.7 391.9 0.927
11 404.2 393.7 0.974
12 437.5 401.6 0.918
As the size of the agent pool increases, the tradeoff between computational effort and quality of the resulting matching favors the modified stable marriage approach, since exhaustive search is growing exponentially, but the modified stable marriage is growing only quadratically. Figure 8 shows that the stable marriage approach retains its ability to find high quality solutions even as the problem size grows very large. In fact, as the number of agents increases, the utility that the average agent obtains nears the absolute maximum of 499, which is not necessarily reachable in every problem instance. Moreover, run times show only a modest increase as the size of the agent set increases, and even sets as large as 350 agents could be handled in less than 1 second using the modified stable marriage algorithm.
Figure 8 compares the stable marriage approach with the simple approach of picking several different pairings at random, and then choosing the one of that set which yields the highest utility for the community. These results are averaged over 100 runs, where each run included selecting 30 different random pairings. The random algorithm took approximately as long to evaluate these 30 different options as the stable marriage method did to come up with its solution for the largest problem sizes. The random approach performed well at small problem sizes, which is unsurprising since there are fewer than 30 different matchings with 4 agents, so the best-of-30 approach is equivalent to an exhaustive search. As the problem size increased, however, the random approach did not perform as well, while the stable marriage algorithm improved noticeably.
The saw-toothed nature of these graphs is due to the coalitions of pairs. Where the number of agents is odd, one agent is forced to go solo, and receives no utility. The "odd one out" pulls down the average by increasing the number of agents without increasing the utility.
Underlying the application of the stable marriage problem to the coalition formation problem is the assumption that coalitions may form by merging two groups at a time. If the utility is a non-decreasing function of the number of agents, this strategy will allow the proper coalitions to form. The securities exchange domain meets this condition, since adding a new agent to a coalition never drags down the utility of the group. However, by restricting negotiations to only bilateral negotiations, many cases of beneficial collaboration may be missed. For example, consider the three agent exercise where the group of three obtains a large utility reward, but any pair of agents has a negative group utility value. In this instance, there will be no incentive for any two agents to get together, so all collaboration will be blocked, and the potential utility gain from the grand coalition will go unrealized. Analysis should be carried out to determine what classes of domains meet this criterion.
2. Ephrati, E., Rosenschein, J.S.: The Clarke Tax as a consensus mechanism among automated agents. In: Proceedings of the Ninth National Conference on Artificial Intelligence. The AAAI Press, Cambridge MA, 1991, pp. 173-178
3. Feldman, J., Sproull, R.: Decision Theory and Artificial Intelligence II: The Hungry Monkey. In: Allen, J.F., Hendler, J., Tate, A. (eds.) Readings in Planning. Morgan Kaufmann, San Mateo CA, 1990, pp. 207-224
4. Grosz, B., Sidner, C.L.: Plans for discourse. In: Cohen, P.R., Morgan, J.L., Pollack, M.E. (eds.) Intentions in Communication. Bradford Books at MIT Press, Cambridge MA, 1990, pp. 417-444
5. Grosz, B., Kraus, S.: Collaborative plans for group activities. In: Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence. Morgan Kaufmann, San Mateo CA, 1993, pp. 367-375
6. Gusfield, D., Irving, R.W.: The Stable Marriage Problem: Structure and Algorithms. MIT Press, Cambridge MA, 1989
7. Ketchpel, S.P.: Deal Making Among Agents of Different Abilities. Unpublished manuscript, 1991
8. Ketchpel, S.P.: Forming Coalitions in the Face of Uncertain Rewards. In: Proceedings of the Twelfth National Conference on Artificial Intelligence. To appear.
9. Kraus, S., Wilkenfeld, J., Zlotkin, G.: Multiagent Negotiation Under Time Constraints. CS-TR-2975, University of Maryland, 1992.
10. Lochbaum, K.E., Grosz, B., Sidner, C.L.: Models of plans to support communication: An initial report. In: Proceedings of the Eighth National Conference on Artificial Intelligence. The AAAI Press, Cambridge MA, 1990, pp. 485-490
11. Raiffa, H.: The Art and Science of Negotiation. Belknap Press of Harvard University Press, Cambridge MA, 1982
12. Rapoport, A.: N-person game theory; concepts and applications. University of Michigan Press, Ann Arbor MI, 1970
13. Rosenschein, J.S.: Personal communication, 1993
14. Wellman, M.: A general-equilibrium approach to distributed transportation planning. In Proceedings of the Tenth National Conference on Artificial Intelligence. The AAAI Press, Cambridge MA, 1992, pp. 282-289
