Socially Motivated Partial Cooperation in Multi-agent Local Search

Tal Ze'evi, Roie Zivan, Omer LevIJCAI 2018 · DOI

TL;DR

This paper introduces a novel "Socially Motivated" local search algorithm for multi-agent systems. It extends existing partial cooperation models by allowing agents' willingness to cooperate to dynamically change based on their utility gains or losses, mirroring real-world human behavior. The proposed algorithm significantly outperforms previous methods, especially in complex scenarios like meeting scheduling, by enabling agents to leverage social cues from their neighbors to find better, more cooperative solutions.

What Problem Does This Paper Address?

Multi-agent systems often involve a trade-off between agents acting purely selfishly to maximize their own utility and agents acting fully cooperatively to achieve a global optimum. The paper focuses on "partial cooperation," where agents are willing to sacrifice some personal utility for the greater good, but only up to a certain threshold. Existing models for partial cooperation assume agents have a fixed "reference point" for their cooperation decisions. However, this doesn't capture the reality that human cooperation is dynamic and influenced by factors like changes in personal wealth or perceived fairness. For instance, a person might be more willing to help out at work if they've recently received a benefit that makes their personal tasks easier. This paper addresses the limitation of static cooperation models by proposing a more realistic, dynamic model and a corresponding algorithm that can handle these nuanced agent behaviors.

Methods

The core contribution is a new model for partial cooperation and a novel local search algorithm called Socially Motivated (SM) AGC.

Dynamic Cooperation Model: The paper extends the partial cooperation model by introducing time-varying reference costs ($\mu_{i,t}$) and cooperation intention parameters ($\lambda_{i,t}$). This allows an agent's willingness to cooperate to change over time based on their current utility and the utility changes experienced in the previous iteration. They define three types of agents based on how their cooperation parameters evolve:

  • Type 1 (Fixed): Agents with static cooperation parameters, similar to previous models.
  • Type 2 (Dynamic Reference Cost): Agents whose cooperation threshold adjusts based on their own utility changes.
  • Type 3 (Reciprocal Altruism): Agents whose cooperation threshold is influenced by whether utility changes are due to their own actions or their neighbors'.

Socially Motivated AGC Algorithm: This algorithm builds upon the Asymmetric Gain Coordination (AGC) approach. The key innovation is an additional "social motivation" phase where agents:

  1. Share Preferences: Agents share their preferences for their own value assignments and receive "votes" or "taboo" indications from their neighbors. "Taboo" indications signal assignments that would violate a neighbor's cooperation threshold.
  2. Socially Beneficial Assignment: Agents then attempt to find a value assignment that not only satisfies their own (potentially dynamic) cooperation constraints but also considers the preferences and indications received from their neighbors.
  3. Consensus and Update: Agents then coordinate to select an assignment that maximizes social gain while respecting cooperation bounds, and update their values.

Datasets

The paper evaluates its algorithm on five types of DCOP benchmarks:

  1. Random uniform DCOPs: Standard benchmarks for testing DCOP algorithms.
  2. K-regular graphs: Problems with a fixed number of neighbors for each agent.
  3. Scale-Free networks: Graphs generated using the Barabasi-Albert model, reflecting real-world network structures.
  4. Graph-Coloring problems: A common benchmark for constraint satisfaction.
  5. Meetings-Scheduling DCOPs: A newly introduced, more realistic benchmark. In this setting, agents (representing individuals) need to schedule multiple meetings, with variables representing possible time slots for each meeting. Constraints include unique time slot requirements and individual meeting priorities.

Key Insights and Ideas

  • Human-like Cooperation is Dynamic: The most significant insight is that modeling agents' cooperation as dynamic, influenced by their current utility and past experiences, leads to more realistic and effective multi-agent systems. Static cooperation thresholds are a simplification that misses crucial aspects of human behavior.
  • Social Cues Improve Cooperation: By allowing agents to share and act upon their neighbors' preferences (even indirectly through "taboo" signals), the SM_AGC algorithm can find solutions with higher global utility than algorithms that rely solely on individual utility calculations.
  • "Taboo" Signals are Powerful: Sharing "taboo" information (assignments that violate a neighbor's threshold) proved to be particularly effective, especially when agents had tighter cooperation constraints (lower $\lambda$). This is because it effectively prunes the search space to feasible solutions.
  • Binary Votes Can Be Best: Surprisingly, for some scenarios (like meeting scheduling), sharing simple binary "votes" for preferred assignments yielded better results than sharing more detailed cost information. This suggests that sometimes, simpler communication can be more effective by avoiding information overload.
  • Privacy Trade-offs: While SM_AGC improves social welfare, sharing more information (like votes) naturally leads to higher privacy loss compared to standard AGC. However, the "taboo"-only version maintains similar privacy levels to standard AGC while achieving better results.

Key Results

  • Superior Performance: SM_AGC consistently outperformed baseline algorithms (Goods-MGM and AGC) across various benchmarks, especially in finding feasible and high-quality solutions.
  • Meeting Scheduling Success: The algorithm showed a significant advantage in the realistic meeting scheduling problems, achieving substantially higher social welfare and attendance rates compared to baselines.
  • "Taboo" Variants Lead: Versions of SM_AGC that incorporate "taboo" indications generally performed better than those that didn't, particularly in scenarios with tighter cooperation constraints.
  • Type 3 Agents are More Cooperative: Agents of Type 3 (reciprocal altruism) generally achieved better results than Type 2 and Type 1 agents, indicating that a model of cooperation influenced by others' actions leads to more beneficial outcomes.
  • Privacy vs. Welfare: The study highlights a trade-off: more informative communication (e.g., binary votes) leads to better social welfare but also increased privacy loss.

Limitations and Future Work

  • Importance Weights: The paper notes that the investigation of varying importance weights ($w_{i,j}$) between agents was omitted for space but is a promising area for future work.
  • Heterogeneous Agent Populations: The current study primarily focuses on scenarios with agents of the same type or compares different types. Investigating interactions within a truly heterogeneous population of agents is a natural next step.
  • More Complex Agent Behaviors: The paper suggests exploring more agent types and more complex interaction patterns between them.
  • Privacy Analysis: While privacy was discussed, a more in-depth analysis of the privacy implications across all SM_AGC variants and benchmarks would be valuable.

Summary updated

BibTeX
@inproceedings{zeevi2018socially,
  author = {Tal Ze'evi and Roie Zivan and Omer Lev},
  title = {{Socially Motivated Partial Cooperation in Multi-agent Local Search}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/81},
}

Loading related content...

Figure