⚡ electrical engineering

Resource Allocation with Multi-Team Collaboration Based on Hamilton's Rule

This paper proposes a multi-team collaboration framework for resource allocation based on Hamilton's rule, where teams bid for shared agents by weighing transfer costs, benefits, and mission importance, and validates the approach through simulations in a coverage control mission.

Original authors: Riwa Karam, Ruoyu Lin, Brooks A. Butler, Magnus Egerstedt

Published 2026-03-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Riwa Karam, Ruoyu Lin, Brooks A. Butler, Magnus Egerstedt

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the manager of a large construction company. You have four different construction crews (Teams 1, 2, 3, and 4) working on four different buildings across the city. You also have a limited pool of 16 specialized workers (robots) that can be moved between these crews.

Your goal is to get all four buildings finished as well as possible. But here's the tricky part:

Team 1 is building a skyscraper in a very dense, complex area. They need more workers to do a good job.
Team 2 is building a small shed in an open field. They don't need as many workers; adding more would just get in their way.
Team 3 has a high-priority contract (maybe it's a hospital), so their work matters more than the others.
Team 4 has a low-priority contract.

The Problem: If you just leave the workers where they started, you might end up with Team 1 struggling with too few people while Team 2 has workers standing around doing nothing. You need a smart way to move workers from "less important" or "overstaffed" teams to "more important" or "understaffed" teams.

The "Altruistic" Solution: Hamilton's Rule

This paper introduces a clever way to decide who gives up a worker and who gets a new one. They borrow an idea from nature called Hamilton's Rule.

In nature, this rule explains why a squirrel might risk its life to warn its family of a predator. It works like this:

If the benefit to the family (weighted by how related they are) is greater than the cost to the squirrel, the squirrel should take the risk.

The authors apply this to robots:

The "Relatedness": Instead of family ties, they use Mission Importance. If Team 3 is building a hospital, they are "more related" to the company's success than Team 4 building a shed.
The "Benefit" (B): How much better Team 3 will do if they get one extra robot.
The "Cost" (C): How much worse Team 4 will do if they lose one robot.

The Rule: A robot should only move from Team A to Team B if:

(Importance of Team B) × (How much Team B improves) > (Importance of Team A) × (How much Team A suffers)

The "Bidding War" Analogy

Since there are multiple teams, they can't just look at one pair at a time. The paper describes a Bidding Process:

The Pitch: Every team looks at its neighbors. "Hey Team 3, if I give you a robot, how much better will you do?" and "Team 3, if I take a robot from you, how much will I suffer?"
The Calculation: They calculate a "Net Gain Score."
- Example: If Team 3 (High Priority) gets a robot, their score jumps up a lot. If Team 4 (Low Priority) loses one, their score drops only a little. The "Net Gain" is huge.
- Counter-Example: If Team 4 (Low Priority) gets a robot, the gain is small. If Team 1 (High Priority) loses one, the drop is huge. The "Net Gain" is negative.
The Decision: Teams only accept a trade if the Net Gain is positive. They pick the neighbor that offers the biggest positive gain.

The "Diminishing Returns" Concept

The paper also relies on a simple economic truth: Diminishing Returns.

Imagine Team 1 has 1 robot. Adding a 2nd robot helps a lot (maybe they can cover twice the area). Adding a 3rd helps, but not quite as much. Adding a 10th robot might not help at all because they are just stepping on each other's toes.

The algorithm uses this to balance things out. It stops moving robots when adding one more to a team doesn't help enough to justify taking one away from another team.

The Real-World Test: Covering a Map

To prove this works, the authors simulated a "Coverage" mission. Imagine four teams of robots trying to cover different parts of a map with sensors.

Some areas are "dense" (lots of important stuff to watch).
Some areas are "sparse."
Some teams have higher priority.

The Result:
The robots automatically shuffled themselves.

Teams with high-priority, dense areas ended up with more robots.
Teams with low-priority, sparse areas ended up with fewer robots.
The system kept shuffling until it reached the "perfect" balance where the total performance of the whole company was maximized.

Why This Matters

In the past, if you had multiple robot teams, you might have had to manually tell them to swap workers, or they might have acted selfishly (keeping all their robots even if they didn't need them).

This paper gives the robots a "moral compass" based on math. It allows them to be altruistic: "I will give up my robot because it helps the bigger picture more than it hurts me." This ensures that in emergencies (like search and rescue or disaster response), resources flow exactly where they are needed most, automatically and efficiently.

1. Problem Statement

The paper addresses the challenge of optimal resource allocation in large-scale multi-robot systems where multiple distinct teams operate in parallel across geographically separated regions.

Core Challenge: Balancing the mission priorities of individual teams against the need for overall system performance. Specifically, the problem involves dynamically reallocating homogeneous robots (agents) between teams to maximize a global objective.
Context: Traditional approaches often focus on single-team optimization or static allocation. This work tackles the dynamic scenario where teams must "donate" or "receive" agents based on relative mission importance and the marginal utility of adding/removing a robot.
Goal: To develop a framework where altruistic transfers (a team giving up a robot) occur only when they improve the global system effectiveness, preventing greedy local optimizations that harm the collective.

2. Methodology

The authors propose an algorithmic framework inspired by Hamilton's Rule from evolutionary biology ( $rB \ge C$ ), adapted for multi-agent systems.

A. Theoretical Framework

Hamilton's Rule Adaptation:
- In biology, altruism evolves if $rB \ge C$ (relatedness $\times$ benefit $\ge$ cost).
- In this paper, relatedness ( $r$ ) is replaced by a weight ratio ( $w_j/w_i$ ) representing the relative mission importance (priority) of Team $j$ versus Team $i$ .
- Benefit ( $B_j$ ): The marginal gain in mission performance for Team $j$ upon receiving an agent.
- Cost ( $C_i$ ): The marginal loss in mission performance for Team $i$ upon losing an agent.
- Condition: A transfer from Team $i$ to Team $j$ is permitted if:
  $\frac{w_j}{w_i} B_j > C_i$
Mission Evaluation Functions ( $F_k$ ):
- Each team $k$ has a performance function $F_k(n_k)$ based on the number of agents $n_k$ .
- Assumptions: $F_k$ is strictly increasing (more agents = better performance) and exhibits diminishing returns (discrete concavity). This ensures that adding an agent to a team with few agents yields a higher marginal gain than adding one to a saturated team.
Bidirectional Uniqueness (Theorem 1):
- The authors prove that under the assumption of homogeneous agents and diminishing returns, Hamilton's rule cannot be satisfied in both directions simultaneously between two teams. If Team $i$ should give to Team $j$ , Team $j$ cannot simultaneously give to Team $i$ . This ensures unidirectional collaboration logic.

B. Multi-Team Bidding Process

To handle systems with $m > 2$ teams, a bidding mechanism is introduced:

Outgoing Bids: Team $k$ calculates the net gain for every potential neighbor $l$ it could send an agent to: $\Delta_{k \to l} = r_{kl}B_l - C_k$ . It selects the neighbor maximizing this value.
Incoming Bids: Team $k$ calculates the net gain for every neighbor $e$ that could send an agent to it: $\Delta_{e \to k} = r_{ek}B_k - C_e$ . It selects the neighbor maximizing this value.
Global Constraint: Even if local bids are positive, the transfer is only executed if the Global Mission Evaluation Function ( $G = \sum w_k F_k(n_k)$ ) strictly increases.

C. Iterative Algorithm

The process is an iterative loop (Algorithm 1):

Construct a graph of potential interactions.
Filter edges using Hamilton's rule to create a directed graph of beneficial transfers.
Teams bid to select their single best partner (incoming or outgoing).
Execute transfers if the global objective $G$ increases.
Repeat until no further transfers improve $G$ .

Convergence: The authors prove (Theorem 2) that the algorithm terminates in finite steps and converges to a global optimum because the state space is finite and $G$ is strictly increasing with every valid step.

D. Application to Coverage Control

The framework is applied to Voronoi-based coverage control:

Mission Metric: The negative of the locational cost function $L(N, c)$ , where $c$ represents a Centroidal Voronoi Tessellation (CVT).
Cost/Benefit Calculation: To ensure fair comparison, the authors run Lloyd's algorithm to reach a CVT state before and after a hypothetical agent transfer. This avoids bias caused by instantaneous, suboptimal positioning.
Theoretical Proof: They prove that adding a robot to a CVT strictly decreases the locational cost (increasing performance), satisfying the "strictly increasing" assumption.

3. Key Contributions

Ecological Inspiration for Robotics: Successfully adapts Hamilton's Rule (altruism in biology) to multi-team robotic resource allocation, using mission weights as a proxy for genetic relatedness.
Mathematical Guarantees: Proves the unidirectionality of pairwise altruistic transfers and demonstrates that the iterative bidding process converges to a global optimum for the system.
Novel Bidding Protocol: Introduces a mechanism where teams bid based on weighted marginal gains, ensuring that only transfers improving the global objective are executed, avoiding local optima traps.
Integration with Coverage Control: Validates the framework using Voronoi coverage, demonstrating how dynamic agent reallocation improves area coverage efficiency.

4. Results

The paper presents simulations with $m=4$ teams and $N=16$ robots:

Scenario 1 (Different Densities, Equal Weights): Teams with higher density functions (requiring more coverage) naturally attracted more robots, even with equal weights, demonstrating the framework's ability to balance workload based on mission difficulty.
Scenario 2 (Identical Densities, Different Weights): Teams with higher mission weights ( $w_4=20$ vs $w_1=1$ ) received significantly more robots, proving the system prioritizes high-value missions.
Global Performance: In both scenarios, the global objective function $G$ increased monotonically with each iteration, exhibiting diminishing returns as the system approached the optimal allocation. The system stabilized when no further beneficial transfers were possible.

5. Significance

Scalability and Robustness: The framework allows multi-robot systems to self-organize and adapt to changing priorities without centralized control, which is crucial for large-scale applications like disaster response or environmental monitoring.
Altruistic Efficiency: By framing resource sharing as "altruism," the system achieves a Pareto-optimal state where individual teams may sacrifice local resources (agents) for the greater good, provided the weighted benefit to the system is positive.
Future Applications: The authors highlight potential extensions to heterogeneous agents, time-varying mission weights, and complex missions like search-and-rescue or wildfire management, suggesting this is a foundational step toward more autonomous, collaborative robotic swarms.