Socially Motivated Partial Cooperation in Multi-agent Local Search

1 Introduction

Multi-agent systems commonly seek to reach an optimal state. One approach considers fully cooperative agents that perform actions in order to achieve a common global goal (cf. [Stranders et al., 2009; Modi et al., 2005; Gershman et al., 2009]), while another explores agents that are selfinterested, which take rational actions that increase their personal gains (cf. [Grant et al., 2011]).

A partially cooperative model that handles scenarios, which do not fall into these two extreme classes was proposed in [Zivan et al., 2012; Grubshtein et al., 2012]. In such settings, agents act cooperatively - motivated by a desire to increase global (group) utility - as long as a minimum condition on their personal utility is satisfied. Such scenarios are common in many real-world settings, e.g., in a working environment where workers are expected to hold meetings, a worker may be willing to participate in a meeting at a time that is inconvenient for her, as long as she is able to hold meetings she considers urgent. A professor asked to teach an additional course for the benefit of the department in which she works may agree in one case, but if she is asked to teach yet another course, she refuses as she would not have enough time to conduct her own research. Car navigation applications are another relevant example, where in order to avoid generating traffic jams, some vehicles would be directed to slower routs. However, the driver would not follow the system's instructions if the delay is over some tolerance threshold. The partial cooperation model represents the willingness of agents to cooperate by defining thresholds of minimum requirements for cooperation, i.e., agents are willing to perform actions that may result in more utility for the group and less utility for themselves, as long as some minimum on their personal utility is preserved. Such willingness has support in social science theory [Wiepking and Breeze, 2012].

However, previous attempts to design partially cooperative models assumed people have a fixed reference point according to which they determine their cooperation intentions, and they are so altruistic as to give away any profit they gain, even if they themselves brought it about. In real life, people's intentions for cooperation are affected by changes in their wealth and by who brought it about [Kahneman and Tversky, 1979; Wiepking and Breeze, 2012]. This dynamic nature of intentions cannot be expressed by the existing partial cooperation model. Instead, we introduce a model in which agents' cooperation is based on the amount of utility they gain or lose. For example, if the professor is allocated a personal assistant that performs many of her everyday tasks, she might be willing to contribute some additional free time by teaching additional hours. In the navigating system example, a removal of a road block, which shortens the driving time may result in the driver willingness to tolerate a detour.

The adjustment of the partial cooperative model to realistic social behavior of humans allowed us to analyze the results produced by the two local search algorithms proposed in [Grubshtein et al., 2012] when solving problems that include additional types of agents, i.e., agents whose cooperation willingness changes in different patterns following changes in their personal utility. This investigation revealed a weakness of these distributed local search algorithms: the agents in these algorithms attempt to find feasible solutions (solutions that satisfy the minimum personal utility requirements of all agents) that maximize their own gains according to their own knowledge. Hence, the willingness of agents to cooperate under some conditions was used only to maintain the validity of the solutions rather than reach the desired high social welfare solution. The optimization process was identical to standard distributed local search algorithms as long as the minimum requirements were satisfied. Thus, when agents performed operations that decreased the utility of other agents, they were oblivious to the damage they incurred as long as the utility did not drop beneath the minimal threshold. This limited the ability of agents to perform socially beneficial actions.

Following these insights regarding the existing partial cooperative distributed local search algorithms, we propose a novel approach towards partial cooperative local search in which agents indicate to their neighbors which value assignments are preferred by them. These indications allow agents to make socially beneficial selections of value assignments.

Our empirical results demonstrate the advantage of the proposed algorithm over previously proposed partially cooperative local search algorithms in solving structured, unstructured and realistic DCOPs (Distributed Constraint Optimization Problem) including agents of novel partial cooperative types. Specifically, for realistic meeting scheduling problems, the proposed algorithm produces high quality results on scenarios where standard local search algorithms are known (and empirically found) to be ineffective. Moreover, we show that the proposed algorithm can be performed with privacy loss not significantly different than the privacy loss of other (existing) algorithms.

2 Background

2.1 Distributed Constraint Optimization

Without loss of generality and unless stated otherwise, we will assume that all problems are minimization problems.

A DCOP is a tuple 〈A,X,D,R〉. A is a finite set of agents {A1,A2, ...,An}. X is a finite set of variables {x1,x2,...,xm}. Each variable is held by a single agent. D is a set of domains {D1, D2,...,Dm}. Each domain Di contains the finite set of values that can be assigned to variable xi. An assignment of value d ∈ Di to xi is denoted by an ordered pair 〈xi, d〉. R is a set of relations (constraints). Each constraint C ∈ R defines a non-negative cost for every possible value combination of a set of variables, and is of the form C : Di1 × Di2 × . . . × Dik → R+ ∪ {0}. A binary constraint refers to exactly two variables and is of the form Cij : Di × Dj → R+ ∪ {0}. 1 A binary DCOP is a DCOP in which all constraints are binary. A partial assignment (PA) is a set of value assignments to variables, in which each variable appears at most once. vars(PA) is the set of all variables that appear in PA. A constraint C ∈ R of the form C : Di1 ×Di2 ×. . .×Dik → R+ ∪{0} is applicable to PA if xi1 , xi2 , . . . , xik ∈ vars(PA). The cost of a PA is the sum of all applicable constraints to PA over the assignments in PA. A complete assignment (or a solution) is a partial assignment that includes all the DCOP's variables (vars(PA) = X). An optimal solution is a complete assignment with minimal cost.

1 We say that a variable is involved in a constraint if it is one of the variables the constraint refers to.

For simplicity, we make standard assumptions that all DCOPs are binary DCOPs in which each agent holds exactly one variable (unless stated otherwise). These assumptions are commonly made in DCOP studies, e.g., [Modi et al., 2005].

2.2 Asymmetric DCOP

ADCOPs generalize DCOPs by explicitly defining for each combination of assignments of constrained agents, the cost for each participant in the constraint [Grinshpoun et al., 2013].

More formally, an ADCOP is defined by the following tuple 〈A, X , D, R〉, where A, X and D are defined the same as in DCOP. Each constraint C ∈ R of an asymmetric DCOP defines a set of non-negative costs for every possible value combination of a set of variables, and takes the following form: C : Di1 ×Di2 × · · · Dik → Rk+.

Notice that here Rk+ is a vector that includes for each agent Aj , 1 ≤ j ≤ k her cost for each combination of value assignments, so in practice each agent 1 ≤ j ≤ k holds her part of the constraint Cj, Cj : Di1 ×Di2 × · · ·Dik → R+. As before, an optimal solution is a complete assignment of all variables with minimal cost.

2.3 Partial Cooperation

In contrast to early studies of ADCOPs, which assumed full cooperation by the agents [Brito et al., 2009; Grubshtein et al., 2010], partial cooperation models represent agents that cooperate only under some conditions. The level of cooperation (which is represented by λ) determines the reference point according to which agents intentions are modeled. In order to allow the agents to consider solutions with high global quality, which may reduce their personal utility, the parameter λ bounds the losses that an agent is willing to undertake in order to contribute to the global objective, i.e., agents perform actions only if they do not result in a cost that exceeds the maximum cost they are willing to endure. Formally, the following parameters are used by the model:

Definition 1. We note by µi the base-line cost of agent i (i.e., the cost for agent i that she assumes she will pay if she acts selfishly).

Definition 2. The cooperation intention parameter λi ≥ 0 defines the maximal increase in the value of µi that is acceptable by agent i.

These cooperation bounds can significantly decrease the number of feasible outcomes for a distributed incomplete algorithm, as can be seen in the next definition.

Definition 3. A feasible outcome for a distributed algorithm is defined to be any outcome (solution) o in the set of all possible outcomes O, that satisfies the following condition.

where ci(o) is the cost for agent Ai in outcome o2 .

2 The rest of our definitions are multiplicative in λi, and this definition can also be reformatted this way with a simple change, but we chose to present this as defined by Grubshtein et al. [Grubshtein et al., 2012].

Two distributed local search algorithms, based on the Max Gain Messages (MGM) algorithm [Maheswaran et al., 2004], were proposed in [Grubshtein et al., 2012]. In the first, unsatisfied agents (agents whose current costs exceed the limit) send nogood messages to indicate to their neighbors that an assignment replacement is required, and good messages that remove a restriction imposed by a nogood when it does not apply anymore. Thus, this algorithm is called Goods-MGM.

In the second algorithm, Asymmetric Gain Coordination (AGC), agents exploit possible improvements until they converge to some local optimum, which cannot be further improved without breaching the cooperation bound of one of the agents. Before replacing a value assignment, an agent requests her neighbors' approval, which is given only if this value assignment replacement does not cause a breach of the cooperative bound for the neighbor. Only if all neighbors approve, the agent replaces her value assignment.

2.4 Privacy Loss

When agents inform others of their preferences - directly or implicitly (e.g., by changing an assignment) - they are revealing information that they may be reluctant to share. Therefore, distributed algorithms are often evaluated not only by the cost/utility of their solutions, their speed and use of the communication network, but also by the amount of private information they make agents divulge. The common approach towards evaluating privacy loss in algorithms solving distributed constraint problems is by measuring the entropy with respect to the knowledge of agents regarding the preferences of other agents [Greenstadt et al., 2006; Brito et al., 2009; Grinshpoun et al., 2013]. Implementing this approach in the scenarios we consider, would mean evaluating privacy loss regarding preferences of an agent over the possible value assignment alternatives of her neighbors. This would be calculated by dividing the number of possible ways to order the alternatives given the revealed information, by all possible ways to order these alternatives. Multiplying one minus the result of this division by a hundred, will give the percentage of privacy lost.

3 Reference Dependent Partial Cooperation

Economics literature indicates that peoples' intentions change with respect to changes in their wealth (i.e., "reference-dependence"). Reference-dependent theories indicate that people are more sensitive to changes in wealth rather than to absolute wealth level [Kahneman and Tversky, 1979; Wiepking and Breeze, 2012]..

In order to allow the partial cooperative model to represent dynamic reference points, we redefine some parameters of the model:

Definition 4. Let µi,t be the reference cost of agent Ai at iteration t of the algorithm (where µi,0 is the baseline cost as defined above).

Definition 5. Let λi,t be the cooperation intention parameter for agent Ai at iteration t of the algorithm, which as before defines the maximal increase in the cost acceptable by agent Ai, only with respect to µi,t.

Definition 6. A complete assignment S is feasible in iteration t if it satisfies the following condition:

The outcome of a distributed algorithm that runs for m iterations is the complete assignment at the end of the m'th iteration (Sm), and it is feasible if the definition above holds for µi,m and λi,m.

Next, we present a number of examples of types of agents that can be represented by the extended model: 3

Type 1 Fixed reference and cooperation parameters, i.e., for each agent Ai, for each iteration t, µi,t = µi,0 and λi,t = λi,0. This type of agents is identical to the types described in [Grubshtein et al., 2012].

Type 2 Fixed λ, i.e., λi,t = λi,0 and a calculation of µ in each iteration as follows:

This type resembles people or organizations that allocate specific budget for charity [Staples, 2004], or people that maintain and manage 'mental budgets' for philanthropic giving (based on mental accounting mechanisms cf. [LaBarge and Stinson, 2014]).

Type 3 This type is inspired by reciprocal altruism, in which an individual is willing to cooperate and give up personal wealth for others, with the expectation that they will act in a similar manner in the future [Trivers, 1971]. Formally this behavior is represented by a fixed λ, i.e., λi,t = λi,0 and a calculation of µ in each iteration as follows:

where Φi,t = 0 if the change in agent Ai's cost (i.e., c(St) - c(St-1)) was caused by an action performed by their neighbor; and Φi,t = 1 if the change was brought about only by agent Ai's own actions. Thus, only a decrease in cost caused by actions of neighbor agents affects the cooperation budget. 4

Dominance

Next, we establish domination properties among the cooperation intentions of the agent types listed above. We will show that the type 1 agents are the most altruistic, type 2 agents the most selfish, and type 3 agents between them.

Let Bi,t be the cost that agent Ai is willing to incur for the benefit of other agents at iteration t.

3 While both µi,t and λi,t are dynamic in the proposed extended model, for the example types of agents we fixed λi,t and varied µi,t. The representation of other types of agents may be more convenient by varying both or just λi,t.

4 Although in the algorithms addressed in this paper, concurrent assignment replacements by neighboring agents are avoided, our definition is general so the model can be applied to other algorithms, which allow such actions.

Proposition 1. If in some iteration t′ , an agent Ai of type 1 and an agent Aj of type 2 or type 3 have similar cooperation thresholds, i.e. λi,t′ = λj,t′ and µi,t′ = µj,t′ , then, for any further iteration t′′ > t′ , if c(Si,t′′) = c(Sj,t′′), then, Bj,t′′ ≤ Bi,t′′ .

Proof. Bℓ,t′′ = µℓ,t′′(1 + λℓ,t′′) - cℓ(St′′) (for ℓ ∈ {i, j}) and since c(Si,t′′) = c(Sj,t′′) and by definition λℓ,0 = λℓ,t for any t, we only need to examine the change in µℓ,t′′ . As µi,t′ = µi,t′′ , we focus on agent Aj . For both type 2 and type 3 agents' µj,t is monotonically decreasing in t (because of min(0, . . .) component of the µj,t definition). Hence, µj,t′′ ≤ µj,t′ , and therefore, Bj,t′′ ≤ Bj,t′ = Bi,t′ = Bi,t′′ .

Proposition 2. Let agent Ai be of type 2 and agent Aj be of type 3. If they have similar cooperation thresholds, i.e. λi,t′ = λj,t′ and µi,t′ = µj,t′ and have a similar history - ci(St) = cj(St) for t′ ≤ t - then, for any further iteration t′′ > t′ , Bi,t′′ ≤ Bj,t′′ .

Proof. As in the previous proof, Bℓ,t′′ = µℓ,t′′ (1 + λℓ,t′′ ) - cℓ(St′′ ) (for ℓ ∈ {i, j}) and since c(Si,t′′ ) = c(Sj,t′′ ) and by definition λℓ,0 = λℓ,t′′ for any t′′ , we only need to examine the change in µℓ,t′′ . Agents of type 2 will decrease their µi,t′′ value when ci(St′′ ) - ci(St′′-1) < 0, while agents of type 3 will decrease their µj,t′′ values by the same amount, but only in a subset of these cases. Hence, µi,t′′ ≤ µj,t′′ for t′ ≤ t′′ , and therefore, Bi,t′′ ≤ Bj,t′′ .

4 Socially-Motivated Local Search

In the partial cooperative local search algorithms described above, agents, besides exploiting their local knowledge, cooperate in order to preserve a level of personal utility that is acceptable by all agents.

In order to allow agents to exploit the cooperative intentions of their neighboring agents, and so to improve the solution's quality (social welfare), we propose a novel approach towards partial cooperative local search, in which agents take an extra step in the interaction process before selecting an assignment. In this new stage each agent shares with their neighbors some information regarding their preferences over their assignment selection After exchanging this information, each agent attempts to find a variable assignment, taking into consideration their own preferences as well as the indications received from their neighbors. We combine this approach with the AGC algorithm (cf. [Grubshtein et al., 2012]) and propose Socially Motivated (SM) AGC.

Definition 7. Let ωi,j ∈ Ωi be the importance that agent Ai ascribes to agent Aj's preferences. s.t. : 0 ≤ ωi,j ≤ 1, and ∑j∈N(i)∪{Ai} ωi,j = 1 where N(i) is the set of agent Ai's neighbors.

When ωi,i = 0, agent Ai will be completely altruistic, selecting her value assignment in accordance with the preferences of her neighbors and ignoring her personal interest. In contrary, when ωi,i = 1, Ai completely ignores the preferences of her neighbors and chooses her value assignment taking into consideration only her own interest.

Algorithm 1 includes the pseudo code of sociallymotivated AGC.

Algorithm 1 SM AGC

input: baseLineAssignmenti, baseLineCosti, λi and Ωi value ← baseLineAssignmenti ; µi,0 ← baseLineCosti; localV iew ← null; // localV iew is St-1 send(value) to N(i); while stop condition not met do PHASE 1: Collect all value messages and update localV iew for each Aj ∈ N(i) do πi,j ← pref erences(Aj ); send(πi,j) to Aj; PHASE 2: Collect all π messages; Πi ← πj∈N(i) ∪ preferences(Ai); alterV ali ← socialImprovingAssignment(Πi, Ωi); send(alterV ali, socialGaini) to N(i); PHASE 3: Collect all 〈alterV alj , socialGainj〉 messages; aj ← agent in N(i) ∪ Ai with maximal socialGain s.t. ci(vj ← alterV alj |St) ≤ µi,t · (1 + λi,t); can improve ← socialGaini > 0 & aj = Ai send(Neg!) to N(i) \ aj ; PHASE 4: Collect Neg! messages; if did not receive Neg! & can improve then value ← alterV ali; send(value) to N(i);

In each round of the algorithm, each agent can send/receive a message for each of its constraints, and therefore, the overall number of messages per round is 2|R|. Since every agent can proceed concurrently with others, the running time of each round is bound by the agent with the maximal number of constraints - maxi∈A |{Cij |j ∈ A; Cij ∈ C}|.

For the selection of the alternative value assignment (alterV ali) in Phase 2 we propose (and use in our experiments) the following heuristic for this selection: After collecting the indications πj received from her neighbors, the agent calculates a sampling probability for each value in her domain, as follows:

where:

Afterwards, the agent randomly samples a value from the underlying distribution.

The main novelty of the proposed algorithm is in the sharing of indications regarding preferences on the selection assignment of neighboring agents. Thus, the information that agents share in this stage of the algorithm (Phase 1) is expected to have a dramatic effect on the performance of the algorithm. We propose five versions of the algorithm, which we compare in our experimental study.

We make a distinction between two categories of indications that agents share with their neighbors. The first, we call 'taboo' assignments, i.e., an agent informs her neighbor which of the neighbors' value selections will cause a breach of the current cooperation threshold. The second, which we call a 'vote' allows agents to direct their neighbors to a specific value that they wish the neighbor will select. Such a vote can be binary or weighted. Table 1 summarizes the differences between the various versions of the SM AGC algorithm that will be further discussed.

5 Experimental Evaluation

In order to evaluate the performance of the different versions of the socially motivated proposed local search algorithm, we compared their performance on five DCOP benchmarks:

1. Random uniform DCOPs: unstructured binary minimization DCOPs with density p1 = 0.1, 100 agents (n = 100), each holding a single variable with 10 values in its domain (d = 10) (for more details see [Grubshtein et al., 2012]).
2. K-regular graphs: similar problems with randomly generated graphs in which all agents had the same number of neighbors (5).
3. Scale Free networks: constructed by using the BarabasiAlbert model [Albert and Barab´asi, 2002], as used in [Zivan et al., 2014].
4. Graph-Coloring problems: included 100 agents, each with 3 colors in the domain and a density parameter p1 = 0.05 as used in [Zivan et al., 2014].
5. Meetings-Scheduling DCOPs: modeling n agents trying to coordinate m meetings, where a particular agent Ai has probability pi,k to be invited to meet k (1 ≤ k ≤ m). The agents (unlike in the other benchmark setting) can hold more than one variable, each representing a meeting they hope to attend. The values in each domain represent the possible time-slots for the meeting to be scheduled and a value representing the option that the agent does not attend the meeting. Additional constraints express the unique time slot scheduling requirement, while local constraints express the priorities for an agent between her own meetings.

Following [Grubshtein et al., 2012], for the first four benchmarks listed above, the baseline solutions were obtained by running a greedy distributed local search algorithm. For the meeting scheduling problems, such a procedure produces a very low quality solution, therefore, we produced the baseline solutions by ordering all meetings according to the number of participants from high to low, and assigning each meeting to a free time-slot according to this order.

The development was performed in Java using the 'AgentZero' framework - a dedicated framework for simulating and evaluating Multi-agent algorithms [Lutati et al., 2014], with Eclipse Juno on a Windows operating system. Simulations were run on a single PC with two 2.4 GHz Intel processors, each with 6 cores, and 20 GB of RAM. The source code for both the various algorithms as well as the different benchmarks we explored in this paper can be found at: https://github.com/IEMAI/ SMPC/tree/master.

5.1 Results

For each benchmark we compared the algorithms in scenarios with the three different types of agents presented in Section 3. In all SM AGC versions agents ascribe equal importance to their neighbors, 5 and any taboo values have zero sampling probability. Each algorithm ran for 1000 iterations on each problem. Results were averaged over 50 random instances.

Random uniform DCOPs: Figures 1a and 1b present the aggregated social cost in each iteration of the search, when the initial cooperation parameter is set to λ = 0.1, and λ = 0.8 respectively. In both settings, for all types of agents, both Goods-MGM and AGC yielded significantly inferior aggregated (social) cost (p < 0.001) than the various versions of SM AGC. Goods-MGM failed to find any feasible solutions for smaller values of λ. Versions in which agents share 'taboo' indications, found significantly better solutions for λ = 0.1 (p < 0.001), however for λ = 0.8, the significant advantage of these versions was found mainly for agents of type 1, and type 2 who have shared their costs (p < 0.01). Under both settings, agents of type 2 were first to converge to solutions with low social cost across all algorithms. In contrary, agents of type 1, continued to explore the solution space for significantly better solutions (p < 0.05). 6 Surprisingly, for lower λ values and without the 'taboo' indications, sharing the precise costs performed worse than the binary option, i.e., the increased information hurt the search for social welfare. Similar results were obtained for K-regular graphs and for scale free nets, and are omitted for lack of space.

Graph-Coloring problems: Figure 2 presents the social cost of solutions produced for the graph coloring problems, using λ = 0.1. In contrast to the previous setups, Goods-MGM and AGC achieved results which are competitive with some versions of SM AGC. While the version of SM AGC in which agents share only 'taboo', found solutions with lower costs for problems with agents of type 2, and solutions of high costs for problems with agents of type 1. Similar results when using λ = 0.8 were omitted.

Meetings-Scheduling problems: Both AGC and GoodsMGM failed to exploit the willingness of agents to cooperate and produced solutions with very low social welfare. On the other hand, using the SM AGC algorithm agents were able to improve their baseline attendance rate (∼75%) by approximately 4%-20%. Agents who shared binary votes were able to achieve the highest social welfare and attendance rates (p < 0.001), while sharing only 'taboos' or both 'taboos' and 'votes' with exact costs achieved much lower social welfare (p < 0.01). Agents of type 3 achieved better results than agents of type 2 for all variants of SM AGC (p < 0.001), and better than agents of type 1 when agents share only 'taboos' or both 'taboos' and 'votes' with exact costs (p < 0.01).

5 We left the investigation of the algorithm's behavior in scenarios with various importance levels for future work.

6 Similar results were obtained for denser problems with p1 = 0.7 and were omitted for lack of space

Social Cost

Social Cost

25000

20000

15000

10000

25000

20000

15000

10000

0

0

100

200

300

Type 1

Type 2

Type 3

400

500

600

700

800

900

100

200

300

Type 1

0

100

200

300

400

500

600

700

800

900

(a) λ = 0.1

Type 2

100

200

300

400

500

600

700

800

900

100

200

300

Type 3

400

500

600

700

800

900

Algorithm AGC

1000

1000

0

Goods-MGM

100

200

300

400

500

600

700

800

900

Iteration

SmAGC_BI

SmAGC_CI

1000

1000

0

0

400

500

600

700

800

900

SmAGC_T

SmAGC_T_BI

(b) λ = 0.8

Figure 2: Social cost for Graph Coloring problems (λ = 0.1).

5.2 Analysis

Our results indicate in general, that the binary variants of the algorithm perform worse than those that reveal costs, except for meeting scheduling problems. This seems to be because, the binary values create a more egalitarian outcome, since each agent's unsatisfied constraints are treated the same. For the meeting scheduling problem, egalitarian solutions make sense as agents' loss from not attending meetings is the same. Adding information here - as with weighted 'vote' indication - actually adds noise to the algorithm, making it more difficult to reach an optimal solution. A similar phenomenon - more information leading to inferior end states - has been observed in many domains (e.g., in decision making processes, Meir et al. [Meir et al., 2014]).

Turning to the other variant we have - adding 'taboo' to the different algorithms - we can see that, generally, 'taboo' variants perform better than the non-'taboo' versions. However, this advantage is stronger for λ = 0.1 than for λ = 0.8. We hypothesize that this is since the usage of 'taboo' guarantees a feasible assignment. Therefore, when the search space of feasible solutions is small (that is, when λ is small), using 'taboo' allows examining a much smaller space, and hence, reaching a good result fast. However, when λ is larger and

SmAGC_T_CI

1000

1000

Social Benefit

60000

50000

40000

30000

20000

0

100

200

300

Type 1

Type 2

Type 3

400

500

600

700

800

900

1000

0

100

200

300

400

500

600

700

800

900

1000

0

100

200

300

400

500

600

700

800

900

1000

(a) Social benefit

(b) Attendance rate

Figure 3: Social benefit and Attendance rate for meeting scheduling problems (n=100, m=50, p=0.05, d=8, λ = 0.1).

the search space is much larger, the convergence speed advantage of 'taboo' versions is less pronounced.

5.3 Privacy

For lack of space we omitted our privacy results and only discuss the two main insights they bring about. First, the vote sharing versions of SM AGC, share information that is not shared by standard AGC, and therefore obviously they are less private. However, the version that only shares 'taboo' messages has similar privacy loss results to standard AGC. Yet, the social welfare results of this version are significantly better than standard AGC.

The second is that privacy loss for type 1 agents is far larger than for other agent types. This probably has to do with type 1 agents being far more willing to cooperate (as their threshold does not change as iterations progress), and therefore they have more chances to pass on information to other agents. In other words, there is a (natural) correlation between the cooperation intentions and the willingness to share private information.

6 Conclusion

We proposed an extension of the partial cooperative paradigm, which allows simulation of realistic scenarios, in which agents intentions for cooperation can change with respect to utility gains. Alongside it, we presented a local search algorithm in which the cooperative intentions of agents can be exploited, not only to ensure that the solution obtained is acceptable by all agents , but also in order to select a high quality solution. A significant advantage of the proposed algorithm over the existing partial cooperative algorithms was found even when only insatiability indications ('taboo') were shared. The socially motivated local search algorithm produces high quality solutions on realistic problems with hard equality constraints (meeting scheduling) where standard local search fails.

This is a first step in a deeper exploration of agents' behaviors - more types can be introduced in future work, and interactions between different types of agents (i.e., a heterogeneous population of agents, instead of a single type) can be investigated.