Coalition Formation among Bounded Rational Agents

1 Introduction

In many domains, self-interested real world parties (e.g. companies) need to solve combinatorial optimization problems to operate efficiently. Often they can save costs by coordinating their activities with other parties. Such settings occur for example in distributed manufactur­ ing among multiple companies and in distributed vehicle routing among dispatch centers. When the planning ac­ tivities are automated, it is useful to also automate the coordination activities via a negotiating software agent representing each party. In such automated negotiations among self-interested agents, the question of coordina­ tion arises: what coalitions should the agents form, are they stable, and how should costs be divided within each coalition? Coalition formation includes three activities. One is coalition structure generation: formation of coali­ tions by the agents such that agents within each coali­ tion coordinate their activities, but agents do not coordinate between coalitions. The second is the solving of the combinatorial optimization problem of each coalition. Conceptually this involves distributing the. tasks of the coalition among the member agents and solving the op­ timization problem of each agent given its resources and the tasks it was distributed. The coalition's objective is to maximize monetary value: money received from out­ side the system for accomplishing tasks minus the cost of using resources. 1 Third, agents within each coalition have to agree on how to divide this value of the gener­ ated solution. These activities interact. For example, the coalition that an agent wants to join depends on the portion of the value that the agent would be allocated in each potential coalition.

"Supported by ARPA contract N00014-92-J-1698.

Coalition formation has been widely studied [Kahan and Rapoport, 1984; van der Linden and Verbeek, 1985; Raiffa, 1982; Shechory and Kraus, 1995; Zlotkin and Rosenschein, 1994; Ketchpel, 1994], but to our knowl-· edge, only among rational agents. Let us call the. entire set of agents A. Say, that the lowest cost achievable by agents S ~ A working together, but without any other agents, is c~ . This is the minimum cost to handle the tasks of agents S with the resources of agents S. A coalition game is defined by a characteristic function vf, which defines the value of each coalition S:

The superscript R emphasizes that we mean the ra­ tional value of the coalition, i.e. the maximum value that is reachable by the coalition given its optimization problem. A rational agent can solve this combinatorial problem optimally without any deliberation costs such as CPU time costs or time delay costs.

If the problem is hard and the instance is large, it is unrealistic to assume that it can be solved without de­ liberation costs. This paper adopts a model of bounded rationality [Simon, 1982; Good, 1971], where each agent has to pay for the computational resources (CPU cy­ cles) that it uses for deliberation. A fixed computation cost Ccomp ~ 0 per CPU time unit is assumed. 2 The domain cost associated with coalition S is denoted by cs(rs) 2: 0, i.e. it depends on (decreases with) the al­ located computation resources r s, Fig. 1. The functions cs ( r s) can be viewed as performance profiles (PPs) of the problem solving algorithm. They are used to decide how much CPU time to allocate to each computation. With this model of bounded rationality, the value of a coalition with BR agents can be defined. Each c;oalition minimizes the sum of solution cost and computation cost:

1 In some problems, not all tasks have to be handled. This can be incorporated by associating a cost with each omitted task. Then problem solving also involves the selection of tasks to handle. The theory of this paper applies to such cases but in our example application, all tasks have to be handled, and no payments from outside the system are received for them.

2 In practice, CPU time can already be bought on super­ computers. The market for CPU time is assumed to be so large that the demand of the agents we are studying does not impact the price of a CPU time unit . It is also assumed that

The coalition value decreases as the CPU time unit cost Ccomp increases, Fig. 1. Our model also incorporates a second form of bounded rationality: the base algorithm may be incomplete, i.e. it might never find the optimal solution. If it is complete, the BR value of a coalition when Cco=p = 0 equals the rational value (vs(O) = vf).

Conceptually the agents use design-to-time algo­ rithms [Garvey and Lesser, 1993; Zilberstein, 1993]: once an agent has decided how much CPU time rs it will allocate to a computation, it can design an algorithm that will find a solution of cost cs ( r s). The design-to­ time framework is used instead of the anytime frame­ work [Dean and Boddy, 1988; Sandholm and Lesser, 1994; Zilberstein, 1993] because to devise a theory of self-interested agents, the po·ssibility that they design their algorithms to time has to be accounted for. With deterministic PPs, for any desired computation time al­ location or solution quality, a noninterruptible design­ to-time algorithm can be constructed that performs no worse than an interruptible anytime algorithm. We as­ sume that the PPs exactly predict the solution cost at­ tained for a given CPU time allocation. So, we have relaxed the assumption that the base level algorithm is optimal (complete and costless ), but instead we assume that the meta-level deliberation controller is optimal (ex­ act and costless) . Assuming optimality of the meta-level is more realistic than assuming optimality of the base level, but it still does not match reality exactly. In prac­ tice there is uncertainty in each PP: the meta-level is not exact. 3 Secondly, the PP depends on several features of the problem instance, and computing the mapping from. the instance to the PP [Sandholm and Lesser, 1994] may take considerable time, thus making the meta-level itself costly. In the limit, the base algorithm would be run at the meta-level to determine what it would achieve for a given time setting. Assuming an optimal meta-level enables analyzing bounded rationality at the base level in isolation from uncertainty of the PPs. It also allows us to sidestep the problem of having a meta-meta-level controlling the meta-level, a meta-meta-meta-level con­ trolling the meta-meta-level, and so on ad infinitum.

this price is common to all agents, which corresponds to an open CPU cycle market .

3 If the PPs are only probabilistically known, anytime algo­ rithms may be desirable due to their flexibility with respect to

We assume that the problem instances (tasks andre­ sources) of all agents are common knowledge. This is somewhat unrealistic in open environments with a large number of agents. In practice it is often necessary to learn the other agents' characteristics from previous en­ counters. Alternatively, the agents can be made to ex­ plicitly declare their tasks and resources, but they may lie in order to gain monetarily. [Rosenschein and Zlotkin, 1994] analyze when rational agents are motivated to de­ clare truthfully. Unfortunately that work assumes only two agents and that they can optimally solve exponen­ tially many NP-complete problems without computation costs. Even under these assumptions, in most cases, truth-telling is not achieved. The effect of bounded ra­ tionality on truthful revelation is unknown.

For now-this is relaxed in Section 5-we assume that the agents solve the combinatorial optimization prob­ lems equally well and that this is common knowledge. For any coalition's problem and for any setting of CPU time, the cost of the solution potentially generated by each agent is the same. The agents need not generate the same solutions, only the same quality.

With such shared deterministic PPs, each agent knows the value vs ( Cco=p) of each potential coalition S upfront. Therefore coalition formation will take place before any computation. After collusion, each coalition computes its solution using the optimal amount of CPU time rs as defined by Equation 2. Because in our model, ratio­ nality is bounded by CPU time cost, it costs the same for one agent to use nt CPU time units as it costs n agents to use t units. Therefore, it is best if a coalition's optimization problem is solved by a single agent. This is trivially true since an agent could simulate distributed problem solving among n agents for time t by using a local algorithm for nt. Conversely, it is not always pos­ sible (due to redundancy etc.) for n agents solving the problem for timet to reach a solution of the same quality as one agent using nt can reach. The computing agent can be arbitrarily chosen from within the coalition, and. the coalition pays that agent its true cost for computing. This cost along with the domain solution cost contribute to vs (cco=p ), which is divided among the agents in the coalition as will be presented later.

termination time. In general, for optimal meta-reasoning, the remaining part of a probabilistic PP should be conditioned on the algorithm's performance on that problem instance on previous CPU time steps (Sandholm and Lesser, 1994; Zilberstein, 1993] . Such conditioning, anytime algorithms , and their integration to coalition formation are part of our current research and are too long to be presented here (Sand­ holm and Lesser, 1995] .

The value of a coalition may depend on the actions of non-member agents due to positive and negative in­ teractions of the agents' solutions. Such settings can be modeled as normal form games (NFGs), Fig. 2. Coali­ tion formation is usually studied in characteristic func­ tion games (CFGs), where the value of each coalition S is given by the characteristic function vf, and is thus not a function of the actions of non-members. CFGs are a strict subset of NFGs. 4 The equivalent of CFGs among BR agents are BRCFGs (Fig. 2) where the value of each coalition S is defined by v s ( Ccomp). This paper mainly studies BRCFGs. Non-BRCFGs are addressed in Sec. 5.

The paper is organized as follows . Section 2 studies the optimal coalition structure for BR agents, and Sec­ tion 3 analyzes its stability. Section 4 presents experi­ mental results in the distributed vehicle routing domain with real data. Section 5 discusses agents with different problem solving capabilities. Section 6 presents related research, and 7 concludes and describes future research.

2 Optimality: BR superadditivity

Any outcome of a game can be analyzed with respect to social welfare, which is defined as the sum of the agents' payoffs. The payoff that agent i gets is called Xi E 'R.. The sum of the agents' x;'s has to equal the sum of the values of the coalitions in the coalition structure (CS) that formed: no wealth is generated from nothing and no wealth disappears. With bounded rational agents, these coalition values incorporate the computation costs.

In superadditive games the agents are best off by form­ ing the grand coalition-from a social welfare viewpoint.

4 The two are equivalent in constant-sum games with un­ restricted side-payments and perfect communication. In such games, the characteristic function value of a coalition is its minimax value from the normal form game [van der Linden and Verbeek, 1985] .

Superadditivity means that the value of one coalition plus the value of another coalition is never more than the value of these coalitions joined into one coalition:

Definition. 2.1 5 A game is superadditive if(VS, T ~ A, S n T = 0) , vfur ~ vf + v~ . See Fig. 2.

When computation cost is ignored, this ·is almost always the case, because at worst, the agents in the composite coalition can use the solutions that they had when they were in separate coalitions. Thus, the agents would al­ most always be better off from a social welfare point of viewbyformingthegrandcoalition, i.e. csR· ={A}. A game can be non-superadditive only if the collusion pro­ cess itself involves some cost, e.g. anti-trust penalties. Some non-superadditive games are subadditive, Fig. 2:

Definition. 2.2 A game is subadditive if (VS, T ~ A, S n T = 0) , vfur < vf + v~ .

In subadditive games, the agents are best off by oper­ ating alone, i.e. csR· = {{al}, {a2}, ... , {alAI}}. Some games are neither superadditive nor subadditive, because the characteristic function fulfills the condition of super­ additivity for some coalitions and the condition of sub­ additivity for others. In such cases, the social welfare maximizing coalition structure varies.

Now we present a new concept for BR agents that is analogous to superadditivity among rational agents. From a social welfare viewpoint , BR agents are best off forming the grand coalition ( C S* = {A}) if the game is bounded rational superadditive (BRS), Fig. 2. This re­ quires that the best value that one coalition can reach given the computation cost plus the best value that an­ other coalition can reach given the computation cost is never greater than the best value that these coalition can reach as a composite coalition given the computa­ tion cost:

Definition. 2.3 A game is bounded rational super­ additive (BRS) for computation cost Ccomp if (V S, T ~ A, s n T = 0), Vsur(ccomp) ~ vs(ccomp) + vr(ccomp) ·

BR superadditivity does not always coincide with super­ additivity. In general, for a given Ccomp ~ 0, a coalition game can be superadditive, BRS, both, or neither, Fig. 2. Only some non-BRS games are BR subadditive, Fig. 2:

Definition. 2.4 A game is bounded rational subad­ ditive for computation cost Ccomp if (V S, T ~ A, S n T = 0), Vsur(ccomp) < vs(ccomp) + vr(ccomp)·

BR superadditivity depends on the performance profiles and the unit cost of computation. The next theorem states a natural condition on the PPs. If the condition holds, the game is BRS for any Ccomp ~ 0.

Theorem 2.1 BRS (sufficient condition). [(VS, T ~ A, S n T = 0, Vrs ~ 0, Vrr ~ 0) , csur(rs + rr) :::; cs(rs) + cr(rr )] => Game is BRS Vccomp ~ 0 . 6

The condition states that the domain cost for coalition S after allocating a certain amount rs of computation plus the domain cost to another coalition T after allocating a certain amount rr of computation is never less than the domain cost of these coalitions combined after allocating rs + rT . This is always achievable if the base algorithm is intelligent enough, because in the worst case, the al­ gorithm can allocate rs on the problem of S and then do the problem ofT using rT separately. Given a large coalition, it is difficult to intelligently guess an efficient decomposition of this type. Usually, the algorithm that is used on the composite problem does not apply this type of a separate solving. Whether the algorithm's per­ formance actually satisfies the condition without using a separate solving approach depends on the problem, the specific instances under study, and the algorithm itself. In general, the game can be BRS Vccomp 2: 0 even if the above condition does not hold on the PPs:

5 Definitions 2.1 , 2.2 and 3.1 are from game theory.

6 Proofs are presented in [Sandholm and Lesser, 1995] .

Theorem 2.2 ((VS, T ~ A, S n T = 0, 'v'rs 2: 0, 'v'rT 2: O) , csuT(rs + rT) ~ cs(rs) + cT(rT)]<j= Game is BRS 'v'Ccomp 2: 0.

It is reasonable to assume that the PP cs ( r) is de­ creasing in r if the agent can inexpensively store the best solution it has arrived at so far. Furthermore, cs ( r) is often convex in r : greater savings are achieved in the early stages of computation and the savings per time unit decrease as problem solving proceeds. We conjecture that PPs of design-to-time algorithms are almost always convex. On the other hand, PPs of anytime algorithms are typically not convex at points where the base algorithm switches from one approach to another. One example is completing an iterative refinement algorithm by running an exhaustive com­ plete algorithm after the refinement phase. Another example is switching from using one refinement oper­ ator (e.g. 2-swap in TSP [Lin and Kernighan, 1971; Sandholm, 1993]) to using another refinement operator (e.g. 3-swap in TSP) . Furthermore, refinements often de­ crease solution cost in a step-wise manner rendering the PPs locally nonconvex-as in our experiments (Fig. 1 left f. The PPs in our experiments exhibited an over­ all convex nature, but also had true local nonconvexities (because the design-to-time algorithms were constructed from anytime algorithms, and were not tailored for each time setting separately, Sec. 4). Convexity is significant because with convex PPs, a domain is BRS for all com­ putation costs if and only ifthe condition of Theorem 2.1 on the PPs holds:

Theorem 2.3 BRS {necessary and sufficient con­ dition). Let us restrict ourselve" to such performance profile" that 'v'U ~ A, cu(r) i" decreasing and convez in r . Now, [(VS, T ~ A, S n T = 0, 'v'rs 2: 0, 'v'rT 2: O),csuT(rs + rT) ~ cs(rs) + cT(rT)] <=> Game is BRS 'v'Ccomp 2: 0.

Analogous ·to Theorem 2.1, there is an easy sufficient condition on the PPs that guarantees that the game is BR subadditive for all computation costs:

Theorem 2.4 Bounded rational subadditivity {sufficient condition). [(VS, T ~A, S n T = 0, 'v'rs 2: 0, VrT 2: 0), csuT(rs + rT) > cs(rs) + cT(rT)] => Game is bounded rational subadditive V Ccomp 2: 0.

7 If the algorithm is stochastic, these step-related noncon­ vex.ities are reduced as the PP is averaged over multiple runs .

If the game is BR subadditive, agents are best off alone, i.e. by colluding with nobody ( c s· {{at}, {a2}, .. . , {alAI}}) . In games that are neither BRS nor bounded rational subadditive, the optimal CS varies, and several CSs may be equally good wrt . social welfare. We denote any one of these best CSs by C s· .

3 Stability: bounded rational core

In the previous section we presented conditions on the PPs that describe what CS the agents are best off form­ ing from the social welfare viewpoint. In this section we analyze the stability of that CS. Can the social good be distributed among the agents so that each agent is motivated to stay with C 5R· (individual rational­ ity)? Furthermore, can it be distributed so that ev­ ery subgroup of agents is better off with C 5R· than by forming a coalition of their own (coalition rational­ ity)? The core (C) is the solution concept that satisfies both of these conditions [Kahan and Rapoport , 1984; van der Linden and Verbeek, 1985; Raiffa, 1982] . The core of a game is a set of vectors i, where each i is a vector of payoffs to the agents in such a manner that no subgroup (individual agents and the group of all agents are also subgroups) is motivated to depart from C 5R· . Given payoffs according to i, the value of each subgroup is less than or equal to the sum of the payoffs that the· agents of that subgroup get under c sR· . Obviously, only CSs that maximize welfare can be stable in the sense of the core, because from any other CS the group of all agents would prefer to switch to a c sR·. Formally,

The core is the strongest solution concept used for coalition formation. It is often too strong: in many cases it is empty, i.e. the social good cannot be di­ vided so that the individual and coalition rationality conditions are satisfied [Kahan and Rapoport, 1984; van der Linden and Verbeek, 1985; Raiffa, 1982]. A lesser problem is that the core may include multiple i's and the agents have to agree on one of them. An often used so­ lution is to pick the nucleolus which is, intuitively speak­ ing, the center of the core [Kahan and Rapoport, 1984; van der Linden and Verbeek, 1985; Raiffa, 1982]. Games with non-empty cores are called weak, Fig. 2.

Now we introduce the analog of the core for BR agents.

If the BRC is not empty, BR agents can divide the so­ cial good among themselves in a way that no subgroup is motivated to break away from C s·. Sometimes the BRC is empty, but this does not always coincide with the core being empty. There are games, where the BRC and the core exist , games where either one of them exists separately, and games where both are empty, Fig. 2. If the agents are best off working separately, the CS with separate agents is stable, Fig. 2:

Theorem 3.1 Bounded rational subadditive core. Game i3 bounded rational subadditive for some Ccomp => BRC(ccomp) f. 0.

In domains that are not BR subadditive, the BRC is sometimes empty. The condition C f. 0 can be con­ verted into necessary and sufficient conditions on the vff's in games where the grand coalition maximizes so­ cial welfare [Shapley, 1967; Charnes and Kortanek, 1966]. We convert the condition BRC(ccomp) f. 0 into con­ ditions on the vs(ccomp)'s analogously. Let B1, ... , Bp be distinct, nonempty, proper subsets of A. The set B = {B1, ... , Bp} is called balanced if there are positive coefficients >.1, ... , Ap such that ViE A, I:{iliEB;} Aj = 1. A minimal balanced set includes no other balanced sets.

Theorem 3.2 Bounded rational core in grand coalition games. In games where cs· ={A} for some Ccomp 1 BRC(ccomp) f. 0 iff for every minimal balanced set B = {B1, ... , Bp}, 2::~=1 AjVS; (ccomp) :::; VA(Ccomp) 0

Example. In any 3-agent game where cs· {A} for some CcompJ BRC(ccomp) i- 0 iff V{1}(Ccomp) + V{2,3}(Ccomp) :::; V{l,2,3}(Ccomp) and V{2}(Ccomp) + V{1,3}(Ccomp) :::; V{l,2,3}(Ccomp) and V{3}(Ccomp) + V{1,2}(Ccomp) < V{1,2,3}(Ccomp) and V{1}(Ccomp) + V{2}(Ccomp) + V{3}(Ccomp) :S V{1,2,3}(Ccomp) and ~V{1,2}(Ccomp) + ~V{1,3}(Ccomp) + ~V{2,3}(Ccomp) :S V{1,2,3}(ccomp)· All but the last inequality are implied by the fact that cs· ={A}.

Example. In any 4-agent game where CS* ={A} for some Ccomp 1 BRC(ccomp) f. 0 iff the 41 inequalities of Table 1 hold. Constraints 1, 2, 3 and 5 correspond to partitions of A (all >.'s are 1). They are thus implied by the fact that cs· ={A}.

In BRS games, a subset of the above inequalities suf­ fices. Let us call a minimal balanced set proper if no two of its elements are disjoint.

Theorem 3.3 BRS bounded rational core. In a game that is BRS for some Ccomp 1 BRC(ccomp) f. 0 iff for eVI .. i"Y proper minimal balanced set B {B1, .. . , Bp}, 2:~=1 AjVS;(Ccomp) :S VA(Ccomp)· Further­ more, thi3 set of inequalities is minimal: no smaller set is sufficient.

Example. In a 3-agent game that is BRS for some Ccomp 1 BRC(ccomp) f. 0 iff tvs{1,2} (ceomp) + tvs{l ,a}(ceomp) + tvs{2,a}(ceomp) :S VS{1,2,,}(Ceomp)· Example. In a 4-agent game that is BRS for some Ccomp 1 BRC(ccomp) f. 0 iff the 11 conditions acquired from Table 1 's constraints 4, 8 and 9 are satisfied.

Next we present conditions on the PPs that are suf­ ficient to guarantee that the BRC exists. According to Theorem 3.1, the conditions on the PPs that guarantee BR subadditivity (Theorem 2.4) form one such set of conditions. The following set suffices for games where cs· ={A}:

Theorem 3.4 BRC in grand coalition games (suf­ ficiency). In games where CS* = {A} for some Ccomp ~ 0, [for every minimal balanced set B = {B1, .. . ,Bp},(VB E B,Vrs ~ 0)2:~= 1 >.icB;(rs;) ~ CA(2:~= 1 AjrB;)] => BRC(ccomp) f. 0.

If cs· = {A} for all Ceomp ~ 0, the above conditions guarantee existence of the BRC( Ceomp) for all Ceomp ~ 0. In BRS games, fewer conditions suffice:

Theorem 3.5 BRC in BRS games (sufficiency). In a game that is BRS for some Ceomp ~ 0, [for ev­ ery proper minimal balanced set B = {B1, .. . , Bp}, (VB E B, Vrs ~ 0) 2::~= 1 AjCB;(rs;) ~ cA(2:~=1 Ajrs;)] => BRC(ccomp) f. 0.

Again, if the game is BRS for all Ceomp ~ 0, the above· conditions guarantee existence of the B RC ( Ceomp) for all Ceomp ~ 0.

Example. In a 3-agent game that is BRS Vceomp ~ 0, [(Vr{l,2} ~ 0, Vr{l,3} ~ 0, Vrp,3} ~ 0), tc{1,2}(r{l,2}) + tc{1,3}(r{l,3}) + tc{2,3}(r{2,3}) ~ C{1,2,3}(tr{l,2} + tr{l,3} + tr{2,3})] => Vceomp ~ 0, BRC(ccomp) f. 0.

4 Experimental results: vehicle routing

BR coalition formation was tested in the vehicle rout­ ing domain using one week real-world vehicle and order data from 5 geographically distributed dispatch centers. Each center had its own vehicles and delivery tasks. In all, they had 771 deliveries to make with 77 vehicles. Each vehicle had to begin and end its tour at the depot of its center, but neither the pickup nor the drop-off lo­ cations of the orders were at the depot. The vehicles had heterogeneous maximum load weight and maximum load volume constraints. All vehicles had the same maximum route length. The domain cost cs ( r s) for a coalition S was the sum of the route lengths of the vehicles of that coalition (while handling all of its orders) in the solu­ tion that had been reached after computation rs. The problem is NP-hard, because ~ TSP can be trivially re- . duced to it . It is in NP, because the cost and feasibility of a solution can easily be checked in polynomial time. Thus, the problem is NP-complete. Moreover, the prob­ lem instances in our example are so large that even the smallest ones are too hard to solve optimally. Therefore, rational coalition formation algorithms for the vehicle routing problem [Lundgren et al., 1992] are unusable.

Our problem is outside the domain classification of [Rosenschein and Zlotkin, 1994], Fig. 2, because agents do not have symmetric capabilities due to heterogeneous fleets. If we extend their definition to allow asymmetric capabilities, our domain is in SOD \ TOD. If we further ~rop the_ maximum route length constraint (this exper­ Iment will also be presented), and restrict ourselves to domains where each center has at least one sufficient vehicle to satisfy the weight/volume constraints of any ord_er _of any center (not true in our data), then the do­ mam IS a TOD. It is not a "Subadditive TOD", because the depots are geographically distributed.

To analyze a game we ran the same algorithm on the vehicle routing problem of each subgroup of agents sep­ arately and thus acquired a PP for each potential coali­ tion. The algorithm first generates an initial solution by ~v~g each vehicle one long delivery and then, in order, givmg each vehicle the delivery that can be added to its ~oute with the least cost without violating the con­ stramts. The second phase of the algorithm is based on iterative refinement. At each step, a delivery (chosen from a randomly ordered circular list) is removed from the routing solution and inserted back to the solution but into the least expensive place while not violating th~ constraints. The drop-off location of the delivery has to be inserted after the pickup location into the same vehicle's route, but not necessarily into the same leg. We ran the refinement algorithm until no remove-insert operation enhanced the solution: a local optimum was reached. ·In the PPs we ignored the time to construct the initial solution, and only viewed how the solution cost decreased with more CPU seconds of iterative re­ finement, Fig. 1 left. The refinement algorithm is an anyti?Ie algorithm, but because the PPs are exact (as explruned, they are precomputed for experimental pur­ poses by running the base algorithm itself), the agents do not gain information from execution on that instance so far. Therefore the algorithm is equivalent to a design­ to-time algorithm for our purposes.

We analyzed all of the m = 10 3-agent games that can be acquired by choosing 3 of the 5 dispatch centers. 8 Figure 1 shows the PPs with agents 1, 2 and 3. Each of our games is superadditive for reasons that were ex­ plained in Section 2. Thus rational agents would be best off by forming the grand coalition. Surprisingly, none of the games were BRS for any Ccomp, Fig. 3. For Ccomp 's in the mid-range, the 3-agent games were often BR sub­ additive (point M in Fig. 2), while in the low and high ranges (point LH in Fig. 2), they were often neither BRS nor bounded rational subadditive. Existence of the core for rational agents is unknown for our games: the points M and LH might really be M' and LH'. The BRC was non-ein:pty in all 3-agent games for all values of Ccomp. s_o, rational agents would be best off forming the pos­ Sibly unstable grand coalition, while BR agents should form varying coalition structures (the grand coalition for some Ccomp's), which are always stable. We also reran th~ e::cperiments without the maximum route length re­ stnctwn, and these results prevailed, Fig. 3.

Centers 2, 3 and 5 were located near to each other, while 1 and 4 were far from each other and the other cen­ ters. Centers 1, 3, 4 and 5 transported heavy low volume items, while 2 transported light voluminous items. Cen­ ters 1..5 had 65, 200, 82, 124, and 300 deliveries, and 10, 13, 21, 18, and 15 vehicles respectively. Both with and without the route length restriction, 2 and 5 were best off by only mutually colluding for any Ccomp· Their deliver­ ies have considerable areal overlap due to adjacency, and the light voluminous items and heavy low volume items · can be profitably joined into the weight and volume con­ strained vehicles. Centers 2 and 3 did not collude as much as 2 and 5 because 3's vehicles had tighter vol­ ume constraints than 5's-hindering the transport of 2's goods. No other two centers besides 2 and 5 were always best off in a 2-agent coalition independent of the third agent of the game. Relaxing the route length constraint increased collusion between the distant 2 and 4 while demoting collusion of the adjacent 2 and 3.

8 There are 7 subgroups of the 3 agents: {1}, {2}, {3}, {1,2}, {2,3}, {3,1}, {1,2,3} and 5 coalition structures: { {1} {2}, {3}}, { {1}; {2,3}}, {{2}, {1,3}}, {{3}, {1,2}}, {{1,2,3}}:

Next we analyzed the (~) = 5 4-agent games and the 5-agent game with and without the route length restric­ tion. I~ every game, the existence of BRC(ccomp) varied many times as a function of Ccomp, but it existed for the largest values of Ccomp · No game was BRS for any c comp, but some games were bounded rational subadditive for interior values, Fig. 3. Thus, depending on Ccomp, the games were at the points M, LH, or 45 (or M' LH' ') . ' ' or 45 m Figure 2. The best coalition structure varied despite the fact that rational agents would be best off forming the grand coalition due to superadditivity. Again, whenever both agents 2 and 5 participated, they were best off by mutually colluding for all computation costs. In those games no other agents colluded.

. Each step ~f the refinement algorithm takes e(vd 2 ) · time, where v IS the number of vehicles and dis the num­ ber of deliveries. Because-this is superlinear in deliveries, a larger coalition can make fewer refinement steps in a given time than the agents in partitions of that coali­ tion. c_an. To compensate, a refinement step of the larger coalition would need to reduce solution cost more than a refinement step of a smaller coalition. The size of the saving has to be averaged over all refinement steps in the optimal time allocation. If Ccomp is low, more time IS allocated, and small coalitions will often run out of profitable refinements. If CcOTnp is high, less time is allo­ cated, and all coalitions will have profitable refinements, though the larger coalition will have time to make fewer of them. Thus it was not surprising that in games where the grand coalition was optimal, it was optimal for very small computation costs only. Surprisingly, two agents colluding was often better than all agents working sep­ arately even for large Ccomp 's. The result that higher computation costs promote smaller coalitions is some­ what deemphasized by our choice of not including the initial solution construction phase in the PPs. Shifting the PPs right to begin at the time when the initial so­ lution was finished (instead of 0) would shift the PPs of small coalitions less than the PPs of large coalitions be­ cause the initial solution construction is superlinear both in tasks and vehicles. Thus small coalitions would gain an advantage-that is most significant for large CcOTnp. If the time of initial solution generation is discarded, the best coalition structure for the greatest computation costs depends only on the quality of the initial solutions of the different coalitions because no refinement steps are beneficial. For example, coalitions {1,3} (Fig. 1), {1,5} and {2,5} achieved a better initial solution cost than the sum of the initial solution costs of the two agents sepa­ rately, Fig. 3.

5 Different performance profiles

So far games where each agent has the same PP for a given coalition were presented. In general, domains where the agents have different PPs-due to different algorithms-are not characteristic function games for BR agents (BRCFGs), because the value of a coalition sometimes depends on the actions of non-members. The value of a coalition can depend on whether an outside agent is willing to compute the solution for the coali­ tion (for a payment) if its algorithm is better than any of the algorithms of the agents in the coalition. Also, interactions between domain solutions of different coali­ tions may exclude some problems from the class BR­ CFG. In non-BRCFGs, BR superadditivity, BR sub­ additivity, and the BRC are undefined, Fig. 2. In­ stead, the Nash equilibrium may be a reasonable solution concept-although only individual agents are motivated to pertain to it: coalitions may prefer to deviate. These issues are discussed in [Sandholm and Lesser, 1995].

6 Related DAI research on collusion

Coalition formation has been widely studied in game the­ ory [Kahan and Rapoport, 1984; van der Linden and Verbeek, 1985; Raiffa, 1982]; only the most relevant con­ cepts were presented here. This section compares our work to other recent DAI work on coalition formation .

[Zlotkin and Rosenschein, 1994] analyze rational agents that cannot make side payments, while our agents do. Their analysis is limited to "Subadditive Task Ori­ ented Domains" (STODs), which are a strict subset of CFGs, Fig. 2. In their solution concept, one agent han­ dles all the tasks, because STODs never exhibit disec­ onomies of scale. We do not assume that one agent can take care of all the agents' tasks. Unlike our work, they also assume that all agents have the same capa­ bilities. With exponential computation they guarantee each agent an expected value that equals its Shapley value [Kahan and Rapoport, 1984; Raiffa, 1982] . In a subset of STODs, "Concave Task Oriented Domains" (Fig. 2), the computational complexity is reduced to linear (in agents) using an encryption scheme. Yet at least one (intractable) combinatorial problem involving all tasks of all agents needs to be solved optimally.

[Ketch pel, 1994] presents a coalition formation method for rational agents which have different expectations of coalition values. The (computational) origin of these ex­ pectations is not addressed. His assumption of imperfect information differs from our setting, where the agents have perfect information, but cannot perfectly deduce. Ketchpel's coalition formation algorithm runs in cubic time in the number of agents, but does not guarantee stability. His protocol is based on mutual offers. In practice it is hard to prevent out-of-protocol offers such as multiagent offers. In our approach, if the agents' pay­ off vector is chosen from within the BRC, the coalition structure is stable against all offers. Finally, his 2-agent auction is manipulable and computationally inefficient . He approaches the coalition formation and the payoff division problems simultaneously.

This is closely related to the contracting protocol of Sandholm [Sandholm, 1993] (TRACONET), where agents construct the global solution by contracting a small number of tasks at a time, and payments are made regarding each contract before new contracts take place. An agent updates its approximate solution after each task transfer . In general equilibrium approaches such as WALRAS [Wellman, 1992], non-manipulative agents iterate over the allocation of resources and tasks, and payments are made only after a final solution is reached.

[Shechory and Kraus, 1995] analyze coalition forma­ tion among rational agents with perfect information in domains that are not necessarily superadditive. Their protocol guarantees that if agents follow it, a certain stability criterion (K-stability) is met. This requires the solution of an exponential number of optimization problems. · Their other protocol guarantees a weaker· form of stability (polynomial K-stability), but only re­ quires the solution of a polynomial number of optimiza­ tion problems. Unfortunately, each one of these may be intractable. Their algorithm switches from one coali­ tion structure to another guaranteeing improvements at each step: coalition structure formation is an anytime algorithm, although each domain problem is solved op­ timally. In our approach, each domain problem is solved using an approximation (design-to-time) algorithm.

7 Conclusions and future research

A normative theory of coalitions in combinatorial do­ mains was presented, where the rationality of self­ interested agents is bounded by computational complex­ ity. A domain classification was presented for rational and BR agents. The algorithms used by the agents significantly impact the coalition structure that should form as well as its stability. Theorems were presented on the PPs guaranteeing BR superadditivity, BR subadditivity, and existence of the BRC. Although almost all domains are superadditive, BR superadditivity is surprisingly all but obvious in practice. None of the vehicle routing games of our experiments-using real data and a reasonable iterative refinement algorithm­ exhibited BR superadditivity. Thus, the optimal CS for BR agents varied, although rational agents should always form the grand coalition. Section 2 developed conditions on the PPs that guarantee BR superadditivity, and it discussed a separate solving approach-based on a non­ deterministic splitting step-that guarantees that the base algorithm fulfills those conditions. We are currently developing methods of constructing algorithms that sat­ isfy the conditions without such splitting. The observed BR subadditivity of some of the games implies a non­ empty BRC: the best CS in those games is stable. Even when BR subadditivity did not hold, the BRC was often non-empty-especially for large Ccomp· Often with su­ perlinear iterative refinement steps, low Ccomp promotes large coalitions while high Ccomp suggests smaller ones. The best BR CSs mostly agreed with our intuitions of what coalitions should form based on strategic domain specific considerations such as adjacency of the dispatch centers and the combinability of their loads.

Our model of bounded rationality is based on costly computation resources. Future work includes analyzing another model, where each agent has a fixed free CPU and no more CPU time can be bought. If the domain cost increases with real time due to a dynamic environ­ ment, such agents with bounded computational capabili­ ties are often best off by distributing the computation. In the costly computation model of this paper, it is best to allocate each coalition's computation to a single agent. The models are equivalent if the domain cost increases linearly with real time and distribution does not speed up computation.

Extensions include generalizing these methods to agents with different PPs, probabilistic PPs, and any­ time algorithms where PPs are conditioned on execu­ tion so far [Sandholm and Lesser, 1995; 1994; Zilber­ stein, 1993]. Agents with probabilistic PPs may want to reselect a coalition if the value of their original coali­ tion is lower than expected-but sunk computation cost has already been incurred. Future research also includes agents that can refine solutions generated by others.