Task Allocation

"I was assigned to inspect the north tower. So was everyone else. We held a brief auction about it, and now only I am there, which is exactly the right number of me."

An Agent That Won Its Bid Fairly

By this point in the chapter the agents can sense their environment, communicate, and coordinate; what remains is to divide the labor. Given a set of tasks and a set of agents, who should do what? In a warehouse, which robot retrieves which pallet. In a search-and-rescue swarm, which drone surveys which sector. In a serving cluster, which worker handles which incoming batch. The question looks deceptively simple, and in the smallest cases you can solve it by hand, but it is a genuine optimization problem with a rich structure, and the way you solve it determines how much the agents must communicate, how close to optimal they land, and how gracefully the system survives a failed agent or a network partition.

This is the multi-robot (or multi-agent) task allocation problem, usually abbreviated MRTA, and it has been studied for decades because it sits at the intersection of combinatorial optimization, economics, and distributed systems. We will frame the problem, place the standard methods on a spectrum from fully centralized to fully distributed, and then run a demonstration that solves one allocation instance both ways and reports the cost and the message count, so the trade-off stops being a slogan and becomes two columns of numbers.

1. The Task-Allocation Problem and Its Taxonomy Beginner

In the simplest and most studied form, there are $N$ agents and $N$ tasks, every agent can do every task, and each agent does exactly one task. Assigning agent $a$ to task $t$ has a cost $c_{a,t}$ (travel distance, energy, time, or the negative of a utility), and we want the one-to-one assignment that minimizes the total cost. Writing $\pi$ for an assignment that sends each agent to a distinct task, the objective is

This is the classical assignment problem, and despite there being $N!$ candidate permutations it is solvable exactly in polynomial time. When utilities replace costs, you maximize instead of minimize, but the structure is identical. The difficulty in real systems comes not from this clean core but from everything the clean core leaves out: agents that can carry several tasks at once, tasks that need more than one agent, tasks that arrive over time, and capability constraints that forbid certain pairings outright.

The standard way to organize these complications is the Gerkey and Mataric taxonomy, which classifies an MRTA instance along three binary axes. Table 29.8.1 lays them out. The clean assignment problem above is the single-task, single-robot, instantaneous corner; most field problems live in a harder corner and are NP-hard, which is precisely why approximate and decentralized methods matter.

The multi-robot column connects directly to the previous section: a task that needs several agents is a task that needs a coalition, so coalition formation (Section 29.7) and task allocation are two views of the same combinatorial object. The time-extended column connects forward, because scheduling tasks over a horizon for a fleet of agents is structurally the same problem a cluster scheduler solves when it places jobs over time, which is why this material rhymes with both distributed load balancing (Chapter 23) and distributed hyperparameter-search scheduling (Chapter 21).

2. The Centralized Optimum: the Hungarian Algorithm Intermediate

When one node can see the whole $N \times N$ cost matrix, the assignment problem has an exact polynomial-time solution: the Hungarian algorithm, due to Kuhn in 1955 and named for the earlier work of the Hungarian mathematicians Konig and Egervary. It runs in $O(N^3)$ time and returns a provably optimal one-to-one matching. The algorithm works by repeatedly subtracting row and column minima to expose zero-cost entries, then finding a maximum matching among those zeros and adjusting until a complete matching of zeros exists; the details are a beautiful piece of combinatorial optimization, but for our purposes the contract is what matters. Feed it a cost matrix, receive the optimal assignment.

The catch is the precondition: one node must hold the entire matrix. In a multi-agent setting that means every agent reports its cost for every task to a coordinator, which is $N^2$ messages of gathering before a single unit of computation. The coordinator then becomes the bottleneck and the single point of failure. If it crashes mid-solve, or if the network partitions it away from half the agents, the allocation stalls. This is the same tension the parameter-server design faced against all-reduce in distributed training (Chapter 27): a central aggregator is simple and optimal but fragile and communication-heavy at the hub.

import numpy as np
from scipy.optimize import linear_sum_assignment

cost = np.array([[40, 60, 25],     # agent 0's cost for tasks 0,1,2
                 [55, 30, 45],     # agent 1
                 [35, 50, 20]])    # agent 2
rows, cols = linear_sum_assignment(cost)   # optimal one-to-one match
print(list(zip(rows, cols)))               # [(0, 1), (1, 0), (2, 2)] or similar
print("total cost:", cost[rows, cols].sum())

3. Market and Auction-Based Allocation Intermediate

If the centralized optimum is too fragile or too chatty, hand the decision to a market. In an auction-based allocation, each task is auctioned and agents bid their valuation (typically the negative of their cost), with each task awarded to its highest bidder. No node ever needs the full cost matrix: an agent reveals only its own bid for the task at hand, and the auctioneer announces only the winner. This is exactly the contract-net protocol introduced in Chapter 27, now read as an optimization method rather than a coordination pattern, and its incentive properties are the subject of mechanism design from Chapter 28: a well-designed auction makes truthful bidding the agent's best strategy, so the market's outcome is both decentralized and incentive-aware.

Single-item auctions, run one task at a time, are fast and cheap but can land on poor global assignments when tasks interact, because an agent that grabs a cheap task early may be forced into an expensive one later. Combinatorial auctions fix this by letting agents bid on bundles of tasks, capturing the fact that doing tasks B and C together may cost less than doing them separately; the price is that clearing a combinatorial auction (the winner-determination problem) is itself NP-hard. In practice, sequential single-item auctions with smart bidding rules recover most of the optimal value at a fraction of the communication, which is the regime the demonstration below explores.

4. Fully Distributed Allocation: CBBA Advanced

An auction still needs an auctioneer, a central referee who collects bids and announces winners. The fully distributed end of the spectrum removes even that. The consensus-based bundle algorithm, CBBA, due to Choi, Brunet, and How, lets each agent build a bundle of tasks greedily, score it, and then reach agreement with its neighbors about who has won what by exchanging only local messages, no central referee required. Each agent maintains a winning-bid list over tasks and runs two interleaved phases: a bundle-building phase where it adds the task that most increases its own score, and a consensus phase where neighbors compare winning-bid lists and resolve conflicts by a deterministic rule, so that two agents who both claimed the same task converge to a single winner.

The consensus phase is precisely the agreement problem that Section 29.9 develops in full: agents must come to a consistent view of the allocation using only neighbor-to-neighbor communication, even though no agent ever sees the global picture. CBBA guarantees convergence to a conflict-free assignment within a number of rounds bounded by the network diameter, and under a diminishing-marginal-gain condition on the scoring function it achieves at least half of the optimal utility, a guarantee that holds with purely local communication and degrades gracefully when agents join, leave, or fail. That robustness is the payoff for giving up the central referee, and it is why CBBA and its descendants are the workhorses of decentralized multi-robot allocation in the field.

5. The Trade-off, Measured Intermediate

The three regimes (centralized, market, fully distributed) trade the same three quantities: optimality, communication, and robustness. Rather than assert the trade-off, the code below measures two of its corners on one concrete instance. It builds a random $6 \times 6$ cost matrix, solves it centrally with the Hungarian algorithm (recording both the optimal cost and the $N^2$ messages a coordinator must gather), then runs a decentralized auction in which each free agent bids on its cheapest unclaimed task each round and the auctioneer awards contested tasks to the lowest bidder. It reports both the cost each method achieves and the number of messages each sends.

import numpy as np
from scipy.optimize import linear_sum_assignment

rng = np.random.default_rng(7)
N = 6  # agents, equal to number of tasks
cost = rng.integers(10, 100, size=(N, N)).astype(float)  # cost[a][t]

# --- Centralized optimum: Hungarian algorithm (one solver sees the whole matrix) ---
rows, cols = linear_sum_assignment(cost)
opt_cost = cost[rows, cols].sum()
# A centralized solver must first GATHER the full N-by-N matrix to one node.
central_msgs = N * N  # every agent reports its cost for every task to the coordinator

# --- Decentralized auction: agents bid round by round on their cheapest free task ---
# Each agent only ever announces ONE bid per round; the auctioneer announces awards.
assigned_task = -np.ones(N, dtype=int)   # task -> agent (which agent won each task)
agent_task = -np.ones(N, dtype=int)      # agent -> task (which task each agent holds)
auction_msgs = 0
rounds = 0
free_agents = list(range(N))
while free_agents:
    rounds += 1
    bids = {}  # task -> (cost, agent) best (lowest-cost) bid this round
    for a in free_agents:
        # agent bids on its cheapest still-unassigned task
        free_tasks = [t for t in range(N) if assigned_task[t] == -1]
        t = min(free_tasks, key=lambda t: cost[a][t])
        auction_msgs += 1  # one bid message broadcast
        if t not in bids or cost[a][t] < bids[t][0]:
            bids[t] = (cost[a][t], a)
    # auctioneer awards each contested task to its lowest bidder
    newly_assigned = []
    for t, (c, a) in bids.items():
        assigned_task[t] = a
        agent_task[a] = t
        auction_msgs += 1  # one award message
        newly_assigned.append(a)
    free_agents = [a for a in free_agents if a not in newly_assigned]

auction_cost = sum(cost[a][agent_task[a]] for a in range(N))

print(f"agents / tasks        : {N}")
print(f"--- centralized (Hungarian) ---")
print(f"total cost            : {opt_cost:.0f}  (provably optimal)")
print(f"messages to gather    : {central_msgs}")
print(f"--- decentralized auction ---")
print(f"total cost            : {auction_cost:.0f}")
print(f"auction rounds        : {rounds}")
print(f"messages exchanged    : {auction_msgs}")
print(f"--- trade-off ---")
print(f"cost gap vs optimum   : {100*(auction_cost-opt_cost)/opt_cost:.1f}%")
print(f"message ratio (auc/ctr): {auction_msgs/central_msgs:.2f}x")

agents / tasks        : 6
--- centralized (Hungarian) ---
total cost            : 233  (provably optimal)
messages to gather    : 36
--- decentralized auction ---
total cost            : 237
auction rounds        : 2
messages exchanged    : 14
--- trade-off ---
cost gap vs optimum   : 1.7%
message ratio (auc/ctr): 0.39x

The numbers tell the whole story of the spectrum. The Hungarian algorithm is exactly optimal, cost 233, but it pays 36 gathering messages and routes the entire decision through one node. The auction reaches cost 237, a gap of under two percent, using fewer than half the messages and converging in two rounds, with no agent ever holding the global matrix. On a six-task instance the absolute savings are modest, but the message count of the centralized scheme grows as $N^2$ while the auction's grows far more slowly, so on a thousand-agent fleet the communication gap is the difference between a saturated coordinator and a system that scales. Whether the two-percent optimality gap is worth that savings is a system-design judgment, and now it is one you can make with measured quantities rather than intuition.

6. Dynamic Reallocation Intermediate

The instantaneous, one-shot view assumes the world holds still while you solve. Real fleets do not enjoy that luxury: tasks appear and vanish, agents fail or recharge, and costs drift as robots move. A static optimal assignment computed once is stale the moment the environment changes, so practical systems reallocate continuously. The centralized approach re-solves the Hungarian problem whenever the world changes enough to matter, which is exact but pays the full gather-and-solve cost on every reallocation. The market and CBBA approaches shine here, because an auction can simply re-auction the affected tasks and a CBBA fleet can drop the failed agent's tasks back into the pool and let the consensus phase reach a new conflict-free assignment, all without restarting from scratch.

Dynamic reallocation is where the robustness column of the trade-off finally pays its way. A coordinator that re-solves on every change is a coordinator that is constantly gathering, and a coordinator that fails takes the whole reallocation loop with it. Decentralized methods absorb churn locally: a failed agent's neighbors notice and redistribute its load, new tasks trigger only local bids, and the system never has a moment where one node holds state that, if lost, halts everything. This is the same insight that made elastic training (Chapter 18) prefer to absorb a lost worker rather than restart, applied now to a fleet of decision-making agents.

7. Where Task Allocation Connects Beginner

Task allocation is not a multi-agent curiosity; it is the same problem distributed systems solve under other names. Distributed load balancing (Chapter 23) assigns incoming inference requests to serving workers to minimize tail latency, which is task allocation with requests as tasks and replicas as agents. Hyperparameter-search scheduling (Chapter 21) assigns trial configurations to workers to maximize throughput under a budget, again an allocation of work to compute. The methods carry over: centralized schedulers are the Hungarian end, work-stealing and bidding schedulers are the market end, and fully decentralized placement is the CBBA end. Recognizing that these are one problem lets you transport a solution from one domain to another, which is the point of seeing the abstraction clearly.

With the agents now able to divide labor efficiently, one question remains from the CBBA discussion: how do agents that talk only to their neighbors come to agree on a single, consistent view of the world, whether that view is an allocation, a shared estimate, or a committed decision? That is the consensus problem, the foundation beneath the consensus phase of CBBA and beneath every distributed agreement in this book, and it is where Section 29.9 turns next.