Enhancing MAS Cooperative Search Through Coalition Partitioning

1 Introduction

Cooperative search [Sarne and Kraus, 2005] is a coalition formation based process aiming to improve the performance of agents engaged in costly individual searches for opportunities/resources. To illustrate this idea, consider several agents (representing different users) interested in buying a desktop over the internet. Each of the agents can have its own set of preferences for valuing any given offer. Obviously the process of finding and evaluating any potential opportunity for buying the desktop is time consuming (i.e. costly). Therefore each agent sets a strategy for itself in which it decides to what extent to continue its search. As good as an agent's own search may be, often it can gain from forming a coalition and searching cooperatively with others. In this manner a group of agents can share, reuse and re-allocate opportunities (that otherwise might have been discarded) among themselves. A

detailed review of the advantages and potential uses of cooperative search is given in [Sarne and Kraus, 2005].

A fundamental component of the cooperative search model (as in any search model) is the search cost [McMillan and Rothschild, 1994]. Search costs reflect the resources (not necessarily monetary) that need to be invested/consumed for maintaining search-related activities, such as locating opportunities, analyzing and comparing them and negotiating over them with other agents. The existence of such search costs in Multi-Agent systems (MAS) is widely recognized [Bakos, 1997; Choi and Liu, 2000; Kephart and Greenwald, 2002] and used. The importance of these costs increases as a function of the amount and richness of opportunities that can be potentially found in the MAS environment. Thus even in settings where technology can reduce the cost of obtaining a single opportunity (e.g. when buying a specific product over the internet) the cost of evaluating all possible opportunities available becomes an important parameter affecting the agents' search strategy. Alas, when considering a cooperative search one needs to take into consideration additional overhead costs associated with the process of coalition coordination. These costs can be of various forms and are usually modeled as a function of the number of the agents forming the coalition [Sarne and Kraus, 2005].

Former analysis of cooperative search [Sarne and Kraus, 2005] suggests a significant potential improvement for the agents' performance when using the new method in various environments (in comparison to an individual search [McMillan and Rothschild, 1994]). However this improvement cannot be generally guaranteed for all environments. Principally, this is because the strategies proposed for the cooperative search assume the coalition structure is fixed for the entire search process (i.e., force the coalition members to keep the coalition in its initial setting until it is decided that the coalition as a whole should terminate the search). In this paper we show that the coalition can further improve its performance by considering intelligent self-restructuring (i.e., partitioning) strategies along the cooperative search process. Furthermore, the use of our proposed cooperative search strategy guarantees that the search through a coalition outperforms individual search. In fact, as discussed throughout the paper, both the traditional cooperative and individual search techniques, denoted FSCS (Fixed-Structure Cooperative Search) and SAS (Single Agent Search), respectively, can be considered specific cases of our proposed search technique, termed VSCS (Variable Structure Cooperative Search).

The main advantage of our approach is that it takes into consideration the expected contribution of any subset of agents to the coalition's utility and to its cost of search at any search stage (instead of merely considering the gain in having the coalition maintain the search as a whole). Notice that in many scenarios the expected incremental individual utility from resuming the search (given a set of known opportunities) for the different agents in the coalition highly varies. This is particularly true when different coalition members have non-correlated preferences for the requested product. Here, the coalition may identify opportunities in which it is more beneficial to have some of its members terminate the search (taking advantage of any of the currently known opportunities) while the remaining members resume the search in a reduced coalition structure hence with a smaller coalition overhead. Alternatively, the coalition can partition itself into several sub-coalitions that search more efficiently.

The suggested partitioning process can be seen as coalition reconstruction [Ogston et al., 2003], and is very similar in its nature to the coalition formation process. It is used whenever the coalition can increase its overall utility by acting as several autonomous sub-coalitions (as detailed below). As in other coalition formation models [Ohta et al., 2006; Kahan and Rapoport, 1984], we assume that there is an option for side payments, thus a strategy maximizing the overall coalition utility is always preferred by all members.

The integration of the partitioning option into the coalition's search strategy is computationally difficult. With this option the coalition needs to evaluate the potential benefit from any possible partition of itself as well as additional future partitions of the sub-coalitions created throughout any future sequence of opportunities encountered. This imposes a significant computational challenge. Therefore an important contribution of this paper, alongside modeling and comprehensively analyzing the general case, is the introduction of a computational algorithmic-based means for facilitating the calculation process of such a coalition strategy in common MAS environments. The uniqueness of our algorithm relates to the fact that its computational complexity does not depend on the potential number of coalition partitions

In addition to the formal proofs for the superiority of the new method, we use a simulation to demonstrate its advantages. The simulation is based on authentic settings, fully correlated with a genuine eCommerce specific vertical market. Our computational algorithm runs within less than a second in this setting that contains thousands of opportunities. Thus alongside the theoretical importance of the results, we present a model that has the potential of actually being implemented.

In the following section we address relevant literature in the area of MAS coalition formation and search. Then we formally introduce the VSCS model, present its analysis and introduce appropriate computational means as described above. As expressed at the end of the paper, overcoming the computational complexities associated with extracting the coalition's optimal search strategy in the VSCS model paves the way for further important research.

2 RelatedWork

Today, search models can be found in various research areas such as eCommerce, real-estate, data mining and social studies. In its most basic form, search theory considers the problem of a searcher seeking to maximize his long term utility by fulfilling his search objective, while operating in a costly environment ([Lippman and McCall, 1976; McMillan and Rothschild, 1994], and references therein). Nevertheless, search theory has been focused mostly on a single searcher, looking for a single opportunity, either as a one sided (taking the environment's reaction to the search strategy used by the agent to be static) or two sided (as a matching model, analyzed from the equilibrium perspective) model. The problem of a group that searches cooperatively has never been addressed in search theory literature. This, is in-spite of the fact that cooperative search has been proven [Sarne and Kraus, 2005] to be inherently different from a single agent's search in relation to its complexity, strategy structure and solution methodology. These differences definitely hold when considering the partitioning option, since partitioning is not a feasible alternative in a single agent search.

Research most related to cooperative search can be found in coalition formation literature. Coalition formation is a favorable process in MAS, particularly desirable in environments where group coordination results in more efficient task performance in comparison to individual performance [Lermann and Shehory, 2000]. A review of the extensive literature in this area can be found in [Kahan and Rapoport, 1984]. Three basic stages are common to all coalition formation models [Sandholm et al., 1999; Tsvetovat et al., 2000]: coalition structure generation, executing the coalition task and dividing the generated value among the coalition members. Nevertheless, in most of the proposed models studying coalition formation the focus is on coalition generation and payoff division. The tendency to avoid research of the task execution stage relates to the assumption often made that agents have complete knowledge concerning the opportunities found in their environment.

The formal introduction of cooperative search in MAS and the initial research of this topic can be found in [Sarne and Kraus, 2005; Manisterski et al., 2006]. However, as discussed above, these papers do not allow coalition restructuring, thus the models described therein are limited in the level of performance improvement that they are able to achieve using cooperative search.

3 Model and Analysis

Similar to many other coalition formation models [Tsvetovat et al., 2000; Yamamoto and Sycara, 2001], we adopt the legacy buyers-coalition application for the electronic marketplace and in particular the B2C (Business-to-Consumer) market, where sellers can supply almost any volume of demand. Notwithstanding, we do wish to emphasize that the cooperative search strategy we present in this paper is general and can be applied to any MAS where cooperative search is feasible.

We base our model description and formulation on the definitions given in [Sarne and Kraus, 2005] and extend them to support partitioning as part of the set of actions in the strategy definition. We consider an electronic marketplace where numerous buyer and seller agents can be found, each interested in buying or offering to sell a well defined product. A product can be offered by many different seller agents under various terms and policies (including prices). We assume that while buyer agents are ignorant of individual seller agents' offers, they are acquainted with the overall distribution of opportunities (whereas an opportunity is defined as the option to buy the product under specific terms and policies) in the marketplace.

In the absence of central matching mechanisms or mediators, each agent needs to search for appropriate opportunities to buy its requested product. This process of a single agent search (SAS) is described in [McMillan and Rothschild, 1994]. Throughout its search the buyer agent locates seller agents sequentially (i.e. one at a time) and learns about their offers by interacting with them. Upon learning the new opportunity details, the buyer agent evaluates it using its own utility function. We consider the agents to be heterogeneous; each having its own utility function defined over product attributes, terms and policies as well as reputation and trust factors. Based on the evaluation the agent makes a decision whether to exploit any of the opportunities encountered until this point (i.e. buy from any of the sellers) or resume its search in a similar manner.

The search activity is assumed to be costly [Choi and Liu, 2000; Kephart and Greenwald, 2002] - each search stage process induces a search cost. We assume utilities and costs are commensurable and additive. Recognizing the benefits of a cooperative search, buyer agents, interested in similar products or interchangeable products, may form coalitions. Any coalition which has been formed conducts its search in a similar manner (i.e. sequentially, encountering a single seller at each search stage, thus accumulating new opportunities along time). There are various methods by which the coalition members can coordinate their cooperative search (e.g. assigning a representative agent that will search on behalf of the coalition or simply taking turns searching), each deriving a different search cost overhead structure. As in [Sarne and Kraus, 2005; Manisterski et al., 2006] the search cost associated with each additional search stage increases as a function of the number of agents forming the coalition.

Once formed, the coalition needs to generate its search strategy. This strategy determines the action to be taken when reaching any potential search stage while in its current structure. The possible actions for each stage include: (a) terminating the search; (b) resuming the search while keeping the current structure; and (c) partitioning the coalition into sub-coalitions (where each member in the partitioned coalition is assigned to one of the sub-coalitions) that set their optimal search strategy from this point onward, independently (i.e. search autonomously or terminate their search). The optimal strategy is the one that maximizes its expected utility (utility obtained from opportunities exploited by the coalition members less the search costs). As in other coalition formation models [Kahan and Rapoport, 1984; Ohta et al., 2006], we assume that there is an option for side payments and set the coalition's goal to maximize the overall coalition utility. Given this goal, the coalition's strategy is not influenced by the payoff division protocol, nor by stability considerations, but rather influences these two factors [Sarne and Kraus, 2005]. Since the pre-determined payoff division mechanism used for creating the coalition defines the portion of the agent's utility from the overall coalition utility, any increase in this latter value will increase any of the agents' shares. Thus the overall utility maximization strategy is the preferred strategy by all agents at every stage of the search (i.e. no conflict of interests).

3.1 The Search Strategy

In order to formally present our search strategy we use O to denote the space of potential opportunity types the coalition may encounter. The opportunity types' distribution in the marketplace is denoted by the probability function p(-→o ). We consider a coalition Ag = {a1, a2, ..., a|Ag|} of a general size, where aj is the j -th buyer agent in the coalition. Each buyer agent, aj, evaluates opportunities using a utility function Uj : O → R, where Uj(⃗o) is the agent's utility from opportunity type ⃗o.1 The search cost associated with having a coalition of size n (i.e. having n agents in the coalition) for each search round is denoted by the function c(n).

We can reduce the number of world states in which the coalition can be, by adopting a representation of states through sets of effective known opportunities. Given a set of known opportunities θ and a coalition Ag, it is sufficient to maintain a subset s of θ to represent the current state of this coalition. Subset s stores the opportunities from θ that maximize the utility of each of the agents in Ag. Formally, we can calculate the state s of a coalition Ag acquainted with a set θ of known opportunities by using the function 2 s = state(θ,Ag) = {⃗osaj |aj ∈ Ag,⃗osaj ∈ θ, Uj(⃗osaj ) ≥ Uj(⃗o), ∀⃗o ∈ θ}. We use SAg to denote the set of all possible states of a coalition Ag. Reaching a state s, the expected utility of a coalition Ag from this point onwards when using its optimal strategy is denoted V ∗ (Ag, s).

We begin our analysis by developing the appropriate expected utility achieved by the different possible actions the coalition may take, leading to the appropriate equations from which the optimal strategy can be extracted.

The first possible action for the coalition is terminating the search. If the search terminates at state s then the coalition's utility Vt(Ag , s) is the aggregated coalition member's utilities when each coalition member, aj, is assigned the opportunity ⃗osaj which maximizes its utility function, Uj, from the set of currently known opportunities in s:

Next we consider the scenarios in which coalition Ag resumes its search at state s while keeping its current structure. Here we can make use of the analysis methodology given in [Sarne and Kraus, 2005], dividing the opportunities space into two sub-spaces, containing improving and nonimproving opportunities for the coalition's utility, respectively. Hence, the expected utility the group of agents Ag can obtain if all agents in Ag resume the search, Vr(Ag, s), is attained by:

1⃗o is noted as a vector since it assigns a value for each product's attributes e.g. an opportunity to buy a calculator can be ⃗o = (scientif ic, 20$, smallDisplay, pocket)

2 If more than one maximizing opportunity exists, state() will return a single opportunity according to a predefined order.

where s′ is the new sate of coalition Ag after encountering opportunity⃗o, s′ = state(s∪{⃗o}, Ag). Os improve denotes the set of opportunities that changes the coalition's current state and Os stay denotes the complementary set (opportunities that do not change the coalition's current state).

Applying some basic mathematic manipulations on the above equation, we obtain:

(3)

Since 1 - ∑⃗o∈Os stayp(o) = ∑⃗o∈Os improvep(⃗o) we obtain:

The third possible scenario is where coalition Ag = {a1, ..., an} partitions into a set P = (A1, ...,Ak) of disjoint non-empty sub-coalitions (Ai ∩ Aj = ∅ ∀i, j ≤ k, ⋃ki=1 Ai = Ag ) that set their search strategies independently. MAg denotes the set of all possible partitions of coalition Ag. The selected partition will be the one yielding the maximum expected utility, assuming all the sub-coalitions created use their optimal strategies. The expected utility of the partitioned coalition Ag in this case, denoted Vp, is given by:

where s′ = state(s, Ai)

As stated in the previous section, the optimal strategy is mapping (Ag, s) → {resume, terminate, P}, maximizing the expected utility V ∗ (Ag , s) which can now be formulated as: V ∗ (Ag, s) = max{Vr(Ag, s), Vt(Ag, s), Vp(Ag, s)} This can also be expressed in a more efficient manner as:

where V ∗ Ai = V ∗ (Ai, state(s,Ai)), V ∗ Aj = V ∗ (Aj, state(s,Aj)), Ai ∪ Aj = Ag, Ai ∩ Aj = ∅, Aj ̸= ∅, Ai ̸= ∅. Notice that in the above equation we simplified the calculation to include only size-two partitions (i.e. partition into two sub-coalitions). This is because every partition P ∈ MAg has already been taken into account recursively in one of the size-two partitions as part of the definition of V ∗ (Ai, s) and V ∗ (Aj, s). Furthermore, the latter definition used for representing a partition also covers the option in which all agents terminate the search.

Notice that in the case where partitioning the coalition into sub-coalitions is a costly process, the integration of such split costs is quite straightforward. For example, if we have a cost Csplit(k) which is a function of the number of sub-coalitions into which Ag partitions, then all we need to do is subtract the value Csplit(|P|) from the right hand side of equation 5 and the rest of our analysis remains unchanged.

The proposed VSCS search strategy will always be the preferred strategy as proposition 1 states.

Proposition 1. The VSCS searchmodel is a generalization of both the FSCS and the SAS and weakly dominates them (i.e. guarantees a better or equal overall performance).

The proof of the proposition is quite straightforward. FSCS and SAS are both specific cases of the VSCS where the coalition always chooses to resume the search in its original structure or partitions into a set of coalitions of size one (i.e. single agents), respectively. Therefore, if any of these two search mechanisms produce the maximum utility for a given environment, the coalition will adopt this structure. Notice that between the two methods FSCS and SAS, neither generally dominates the other (but rather the selection of the optimal one is environment-dependent). The only advantage of these two methods in comparison to the VSCS is in terms of the computational complexity of the optimal strategy. Nevertheless, in many common environments even the calculation complexity can be overcome and reduced to the one similarly obtained for the FSCS model, as we demonstrate in the next section.

3.2 Reducing Calculation Complexity

In many environments the marginal cooperative search cost (cost of adding an additional agent to a coalition) has a fixed or non-increasing structure (formally, described as: c(n + 2) - c(n + 1) ≤ c(n + 1) - c(n)∀n ≥ 0). This is typical due to the fact that most of the coalition overhead is associated with communication. A characteristic example of this is where one of the coalition members in each stage of the search conducts the search on behalf of the coalition. The agent conducting the search needs to send the results to the other agents. The other agents do not have to communicate among themselves, therefore the search cost is at most linear and depends on the number of coalition members. In such environments, as we prove and demonstrate in the following paragraphs, many of the calculation complexities induced by allowing coalition partitioning can be overcome. We begin by introducing the following lemma 1 which lays the foundations for our algorithmic-based solution.

Lemma 1. Given a state s and a coalition Ag there is an optimal strategy for coalition Ag in which at most one subcoalition resumes the search.

The above lemma Ag suggests that any strategy in which the coalition partitions into two or more sub-coalitions that resume the search in parallel is weakly dominated by a strategy in which k (k ≤ n) coalition members terminate their search at the current stage while the rest n-k coalition members continue as a unified coalition in a cooperative search.

Though the proof below is quite detailed, it is intuitive. If the optimal strategy is to have two sub-coalitions searching in parallel then merging them into one coalition for just one additional search stage and then returning to their initial coalition structures will necessarily yield a better performance (since the expected utility will remain the same whereas the aggregated cost of such a move can only decrease). The immediate implication is that in each state an agent needs to decide whether to resume or terminate the search. Since all agents who resume the search conduct the search together, there is no need to decide which coalition to join.

Proof. Assume that according to the best strategy, coalition Ag splits to at least two sub-coalitions that resume the search separately. Consider two scenarios: (1) Each coalition separately draws the opportunity it encounters from distribution P. (2) There is a list of infinite opportunities ⃗o1 ,⃗o2 ... that were taken randomly from distribution P. All coalitions in their ith search encounter the same opportunity, ⃗oi . The probability that a coalition will encounter a given opportunity is exactly the same in both scenarios. Moreover each coalition's utility depends merely on the other opportunities it encounters and doesn't depend on the other coalition's utility. Therefore in both scenarios each coalition has the same expected utility.

Consider that after a coalition Ag splits to sub coalitions, each sub-coalition resumes the search according to the second scenario. If in the next stage of the search all sub-coalitions of Ag conduct the search together instead of conducting the search separately, they can only benefit. This is because their search cost can only decrease. However after conducting the search each sub coalition still can make the same decisions as in the second scenario. Therefore they can only benefit by conducting the search together. In similar way we can eliminate other cases where a coalition splits into sub coalitions that resume the search separately.

Our analysis suggests a simple mechanism for determining the agents that will cooperatively continue the search at each state for any given coalition. For this purpose we introduce several supporting definitions and notations. Given a coalition Ag and a state s we use:

ˆ

• V (s, aj) - the additional expected utility (without including the search cost) that agent aj ∈ Ag obtains from terminating its search after conducting one additional search stage rather than terminating the search in the current state s it is in. Thus:

• Aorder = {a′1 , ..., a′|Ag| } - the list of agents in Ag sorted in a descending order according to their ˆ V values.
• Ar = {a′1 , ..., a′k }, At = {a′k+1 , ..., a′n} - a partition of the sorted list Aorder, where k is the first index in Aorder satisfying both conditions: (C1) ∑kj=1 ˆ V (s, a′j ) ≥ c(k); and (C2) ̸ ∃i, i > k that satisfies

If such a k does not exist then Ar = Ø and At = Ag.

In the above definitions the condition (C1) is used to ensure that the incremental expected utility encapsulated in one additional search stage is smaller than its cost for the subcoalition Ar. The second condition (C2) ensures that the additional utility obtained frommoving any subset of At to Ar results in a negative expected net utility. At this point, we have all the necessary tools to establish theorem 1.

Theorem 1. The optimal strategy of coalition Ag when in state s is to have the agents in Ar resume the search cooperatively and have the rest of the agents in Ag (i.e. the agents in At) terminate the search.

The general sketch of the proof for theorem 1 begins by proving that it is sufficient to consider ˆ V for the proposedprocess rather than using the actual values of the additional expected utility for each agent (i.e. the optimal strategy of each agent given the option to resume its search in future states). The proof for this is derived by showing that each agent's marginal expected utility obtained from resuming the search decreases throughout the search whereas the marginal cost of adding the agent to the coalition resuming search can only increase throughout the search (given the search cost structure and the fact that the coalition size throughout the search can only decrease). Therefore if it is not beneficial for the agent to resume its search in the current state given the ˆ V criteria then certainly this is also the case when using the optimal future strategies. Next we prove that the optimal strategy for all agents in Ar is to resume their search cooperatively as one coalition. This is achieved by showing that under condition (C2), a scenario where one of the agent's expected additional utility from resuming the search is smaller than its own induced cost will not exist.

Before presenting an algorithm that is based on theorem 1 for computing the coalition's optimal strategy we illustrate this theorem by using the following example:

Example 1. Suppose there are 4 agents {a1, a2, a3, a4} conducting the search in a market associated with 4 types of opportunities {⃗o1,⃗o2,⃗o3,⃗o4}. Agents' utilities and opportunities' distribution are given in Table 1. The search cost associated with n agents is c(n) = 0.4ln(n + 1).

We compute the coalition's optimal strategy, where the

coalition encounters opportunity ⃗ o1 and its current state is s = {⃗ o1}. First we compute ∀aj ∈ Aj Vone({⃗ o1}, aj ). Vone({ ⃗ o1}, a1) = p( ⃗ o3)(U1( ⃗ o3)-U1( ⃗ o1)) +p( ⃗ o4)(U1( ⃗ o4)- U1( ⃗ o4)) = 0.1(9 - 5) + 0.6(10 - 5) = 3.4 Vone({ ⃗ o1}, a2) = p( ⃗ o2)(U2( ⃗ o2)-U2( ⃗ o1)) +p( ⃗ o3)(U2( ⃗ o3)- U2( ⃗ o1)) = 0.1(4.4 - 4) + 0.1(5 - 4) = 0.14 Vone({ ⃗ o1}, a3) = p( ⃗ o3)(U3( ⃗ o3) - U3( ⃗ o1)) = 0.1(8.5 - 7) = 0.15 Vone({ ⃗ o1}, a4) = p( ⃗ o2)(U4( ⃗ o2) - U4( ⃗ o1)) = 0.1(8.5 - 8) = 0.05

The sorted agents list is Aorder = (a1, a3, a2, a4). We start by checking whether the two conditions C1 and C2, are satisfied for k = 1. Condition C1 is satisfied as Vone({ ⃗ o1}, a1) = 3.4 > c(1) = 0.2772588. To check whether C2 is satisfied we should check that ∀i > 1 equation 7 isn't satisfied. For i = 2 equation 7 is not satisfied as Vone({⃗ o1}, a2) = 0.15 < c(2) - c(1) = 0.161286.

However i = 3 satisfies equation 7 as Vone({⃗ o1}, a2) + Vone({ ⃗ o1}, a3) = 0.14 + 0.15 = 0.29 > c(3) - c(1) = 0.2772588. Consequently k = 1 doesn't satisfy condition C2.

Next we check whether k = 2 satisfies the two conditions. Condition C1 is satisfied as Vone({⃗ o1}, a1) + Vone({ ⃗ o1}, a2) = 3.4 + 0.15 = 3.55 > c(2) = 0.439944. To check whether C2 is satisfied we should check that for all i > 2 equation 7 isn't satisfied. However i = 3 satisfies equation 7 as Vone({ ⃗ o1}, a3) = 0.14 > c(3) - c(2) = 0.115072. Consequently k = 2 doesn't satisfy condition C2.

The next index k = 3 satisfies C1 as Vone({⃗ o1}, a1) + Vone({ ⃗ o1}, a2) + Vone({ ⃗ o1}, a3) = 3.4 + 0.15 + 0.14 = 3.69 > c(2) = 0.439944. To check whether C2 is satisfied we should check that for i = 4 equation 7 isn't satisfied. Indeed i = 4 doesn't satisfy equation 7 as Vone({⃗ o1}, a4) = 0.05 < c(4) - c(3) = 0.089. Therefore k = 3 is the first index that satisfies both conditions C1 and C2. From theorem 1 we conclude that {a1, a2, a3} should resume the search and {a4} should terminate the search.

Based on theorem 1 we present algorithm 1 for computing the best strategy for a coalition Ag when reaching a state s. The significance of the algorithm is that it enables us to ex-

Algorithm 1 Computes the best strategy for coalition Ag when reaching a state s

Input: U = {U1, ..., U|Ag|} - coalition members' utility Output: (Ar,At) - the sub-coalition that needs to resume the search and the complimentary set of agents that needs to terminate the search at the current stage, respectively.

• 1: Generate the sorted descending set Aorder by computing ˆ V (s, aj) ∀aj ∈ Ag using equation 6

ˆ

• 2: size ⇐ 0; VaddCoalition ⇐ 0
• 3: for index = 1 to |Aorder| do
• 4: ˆ VaddCoalition ⇐ ˆ VaddCoalition + ˆ V (s, a′index )
• 5: if ( ˆ VaddCoalition ≥ c(index) - c(size)) then

ˆ

• 6: size ⇐ index ; VaddCoalition ⇐ 0
• 7: end if
• 8: end for
• 9: return ({a′1, ...a′size },{a′size+1 , ...a′|Ag|})

tract the optimal strategy for a coalition without considering all possible states. Its complexity doesn't depend on the number of states and it is polynomial by the market opportunities and agents, which extensively reduce the search space.

4 Illustrative Comparison

In this section we demonstrate the difference in the optimal strategy structure and in the overall performance between the proposed VSCS model and the FSCS and SAS models. Notice that given proposition 1 the superiority of the VSCS over FSCS and SAS is unquestionable and therefore our goal is mainly to demonstrate different aspects of the optimal search strategy to be used in each of the different search methods.

We base the illustration on authentic environment 1, which was built based on opportunities collected over the internet and utility functions that were defined by human searchers whomwe interviewed.

Environment 1. The searching coalition consists of seven agents interested in buying a calculator. Each agent is associated with a different utility function, based on typical attributes of calculators (price, handled\non-handled, display type, scientific functions, warranty, calculator's company, 2\1 line display, etc.). The utility functions of the different agents are constructed according to real preferences of 7 people (which evaluates the different attributes using monetary units) whom we interviewed. For example, a person searching for a handled scientific calculator with a fraction display that worth to him 30$ (a calculator that doesn't satisfy all these conditions is not useful for this person and worth nothing to him) or a person searching for an handled scientific calculator that worth to him 15$ and a last digit erase option worth to him 2$. The opportunities to buy the calculator in this environment are drawn from a distribution that is based on one that can be found on the internet in US-based ecommerce web-sites. The cooperative search is executed by having one of the coalition members conduct the search at each stage and inform the results to the other coalition members. Therefore the search cost of the coalition is equal to the sum of the interaction cost (the cost of locating a seller and communicating with her to learn her offer) and the cost of communicating the search results to the other n-1 agents 3 , i.e. c(n) = cinteraction + ccommunication ∗ (n - 1). The interaction cost we used is 0.01$.

Figure 1 depicts the average overall utility over 10000 searches using the three methods as a function of the communication coalition search cost (notice that the agents' performance is not affected by this value in SAS). As expected the FSCS performs better than SAS for some ccommunication values (and SAS performs better for others) while VSCS dominates both methods for any ccommunication value.

5 Discussion and Conclusions

The ability to maintain an adaptive coalition that can restructure itself is inherent in multi-agent domains [Ogston et al., 2003]. Therefore, when considering the expected performance of a coalition searching cooperatively, one must take into consideration the appropriate beneficial partitioning decisions that may be taken along its search. Having the partitioning option, the coalition should adopt a new strategy, different in its structure in comparison to the optimal strategy used in the fixed structure cooperative search (FSCS) and inherently different from the strategy used when each agent We re-emphasize the fact that the proposed VSCS model is a generalization of FSCS and SAS and its use is always favorable for the coalition. This significantly enhances the importance and usefulness of cooperative search, since the dominance of the traditional method (FSCS) over individual search (SAS) can not be guaranteed.

3 If a representative agent conducts the search on behalf of the coalition (substituting n - 1 in the search cost with n), we attain similar results.

Naturally the attempt to integrate "search theory" techniques into day-to-day MAS applications raises the applicability question. Justification and legitimacy considerations for the integrated search-MAS models in general and cooperative search model in particular were widely discussed in the literature reviewed throughout the paper, emphasizing both the synthesis of the two domains [Sarne and Kraus, 2005; Manisterski et al., 2006] and applications [Kephart and Greenwald, 2002; Choi and Liu, 2000]. The current paper does not focus on re-arguing applicability, but rather on the improvement of the well established cooperative search model. The mechanisms described in this paper are an important step towards an improved cooperative search, however there are many other aspects of the VSCS that should be addressed, such as: coalition stability, payoff division mechanisms (in particular when partitioning the coalition along its search) and truth telling [Sandholm et al., 1999; Tsvetovat et al., 2000]. Though these were not included in the current paper, we wish to emphasize that not only is the coalition's optimal strategy not influenced by these factors but rather it influences them [Sarne and Kraus, 2005]. The analysis of these important issues is based on the ability to properly derive the coalition's utility given its initial specific self structure (i.e. the number of agents it represents and their reported, not necessarily true, utility functions) and the environment in which it operates. By supplying this functionality, we enable extensive important research in the future and support the integration of various relevant ideas from rich literature in the area of game theory and MAS research [Sandholm et al., 1999; Li et al., 2003] into the proposed model. An additional extension of the model would be to integrate the concept of concurrency into the VSCS model, taking advantage of the results obtained in [Manisterski et al., 2006] for the FSCS model.

6 Acknowledgment

This work was supported in part by ISF #8008. Kraus is also affiliated with UMIACS.