Socially Motivated Partial Cooperation in Multi-agent Local Search
Authors: Tal Ze'evi, Roie Zivan, Omer Lev
IJCAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our empirical study reveals the advantage of the proposed algorithm in multiple benchmarks. Specifically, on realistic meeting scheduling problems it overcomes limitations of standard local search algorithms. |
| Researcher Affiliation | Academia | Tal Ze evi, Roie Zivan and Omer Lev Ben-Gurion University of the Negev Beer-Sheva, Israel {talzee,zivanr,omerlev}@bgu.ac.il |
| Pseudocode | Yes | Algorithm 1 includes the pseudo code of socially-motivated AGC. Algorithm 1 SM AGC input: base Line Assignmenti, base Line Costi, λi and Ωi value base Line Assignmenti; µi,0 base Line Costi; local V iew null; // local V iew is St 1 send(value) to N(i); while stop condition not met do PHASE 1: Collect all value messages and update local V iew for each Aj N(i) do πi,j preferences(Aj); send(πi,j) to Aj; PHASE 2: Collect all π messages; Πi πj N(i) preferences(Ai); alter V ali social Improving Assignment(Πi, Ωi); send(alter V ali, social Gaini) to N(i); PHASE 3: Collect all alter V alj, social Gainj messages; aj agent in N(i) Ai with maximal social Gain s.t. ci(vj alter V alj|St) µi,t (1 + λi,t); can improve social Gaini > 0 & aj = Ai send(Neg!) to N(i) \ aj; PHASE 4: Collect Neg! messages; if did not receive Neg! & can improve then value alter V ali; send(value) to N(i); |
| Open Source Code | Yes | 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. |
| Open Datasets | No | 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 Barabasi Albert 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. |
| Dataset Splits | No | Results were averaged over 50 random instances. |
| Hardware Specification | Yes | Simulations were run on a single PC with two 2.4 GHz Intel processors, each with 6 cores, and 20 GB of RAM. |
| Software Dependencies | No | The development was performed in Java using the Agent Zero framework a dedicated framework for simulating and evaluating Multi-agent algorithms [Lutati et al., 2014], with Eclipse Juno on a Windows operating system. |
| Experiment Setup | Yes | 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. |