09 / DECENTRALIZED ALLOCATION · BIDS AND BELIEFS
Consensus-Based
Bundle Algorithm.
Three agents want useful tasks, but no coordinator assigns them. CBBA builds local task bundles, exchanges bids and believed winners, then releases conflicting choices. Watch agreement emerge—or fail when information cannot travel.
Predict: if you lose the first task in your bundle, should you keep all the tasks you added after it?
Name the algorithm and its assumptions
Equations and primary sources ↗- Algorithm and variant
- CBBA / static additive utilities
Greedy bundle construction, timestamp-aware winner consensus and suffix release. A fixed utility table makes marginal bids inspectable. Compare with local greedy selection without exchanges.
- Decision architecture and inputs
- Decentralized, leaderless
Each agent uses its own utility row, the common task catalog and received winner/bid/timestamp packets. It cannot read another agent's private utility row or current bundle.
- Timing, communication and topology
- Synchronous rounds / chain links
Reliable one-hop packets use a pre-exchange snapshot. An undirected A1 ↔ A2 ↔ A3 chain can be cut between A2 and A3, then restored before round 5. No radio or clock drift is modeled.
- Execution and evaluator
- One browser / allocation only
Agents and tasks stay still. The 3D quadrotors and task stations use a fixed illustrative height; colored station bands identify current claimants. Both views show the same claims; no navigation, task service or flight is executed. Global disagreement, conflicts and reference scores are evaluator-only information.
Scope: six known tasks and bounded bundles. “Consensus” means agreement on task winners and bids; it is not arithmetic averaging. CBBA's greedy allocation need not maximize the total utility.
BUILD A BUNDLE · EXCHANGE BELIEFS · RELEASE CONFLICTS
Who thinks they own each task?
● Agent A1–A3◇ Task T1–T6━━ Own-bundle claim┄ Communication link
Select an agent to inspect its local beliefs. Map positions provide context; the fixed utility table determines bids. Claim lines are plans, not executed routes.
LOCAL INFORMATION / SELECTED AGENT
A belief is not global ownership.
| Task | Own utility | Believed winner zᵢ | Winning bid yᵢ |
|---|
Freshness is tracked per agent, not per task. These logical timestamps help decide whether a received claim or reset is newer; they are not synchronized wall-clock measurements.
COMMUNICATION / LATEST RECEIVED SNAPSHOTS
What actually arrived?
Packets carry winners, bids and peer freshness. A sender's bundle and private utilities are not transmitted. Recipient updates do not alter other packets already captured for this round.
Release a suffix, then rebuild
Losing a bundle entry releases that entry and every later acquisition. The planning path removes the same tasks. This protects the dependency of later bids on earlier selections; with constant additive utility, those later bids happen to stay numerically unchanged.
GLOBAL EVALUATOR / ALL OWN-BUNDLE CLAIMS
Agreement, allocation and execution are different.
| Agent | Acquisition bundle bᵢ | Planning path pᵢ | Own-claim utility |
|---|
The bundle records acquisition order. The path records proposed task order. All insertion positions tie under this additive score, so this variant appends: the two orders coincide, but their roles differ.
Inspect the full utility table · evaluator only
Recent protocol events
PREDICT · COMPARE · EXPLAIN
What makes a claim credible?
Load a case, make a prediction, then inspect the packets and released suffixes. Each case starts paused.
Reproduce the reference comparisons
These independent copies run to the same round budget. Opening this table never advances or replaces your active experiment. The centralized exact reference uses the same additive utilities and per-agent capacity; it is an evaluator benchmark, not a message available to CBBA.
| Case | Method | Conflicting tasks | Unique tasks | Agreement | Valid score |
|---|
THE RULE BEHIND THE BIDS
Build locally.
Resolve together.
CBBA combines a greedy bundle-building phase with a consensus phase over believed winners. The original method supports richer sequence-dependent scores; this workshop chooses a small static additive case so you can follow every decision.
A higher bid wins. Equal bids prefer the smaller agent ID. Equal candidate utilities prefer the smaller task ID. Deterministic tie rules avoid two agents resolving the same evidence differently.
cᵢⱼ = max insertion [Sᵢ(pᵢ ⊕ j) − Sᵢ(pᵢ)] = uᵢⱼ
j* = arg max eligible j cᵢⱼ
First lost bundle entry at n ⇒ release bᵢ[n…end]
- uᵢⱼ / static utility
- Agent i's value for task j, in dimensionless points. The utility does not depend on map distance or sequence in this variant.
- bᵢ and pᵢ
- Order of acquisition versus planned task order. These separate roles matter when richer insertion scores change the path order.
- zᵢ, yᵢ and sᵢ
- Local task winners, winning bids and freshness about other agents. A task can be unclaimed in one table and assigned in another.
- Eligible task
- A task outside the bundle whose positive marginal bid can beat the agent's current winner belief, including the declared tie rule.
Freshness changes conflict resolution
A packet can report the sender, receiver, a third agent or nobody as winner. CBBA combines that relationship, bid comparisons and freshness to update, retain or reset the local record. Taking the largest bid alone would not implement these reset cases.
Observe the limits
Disconnected agents can keep incompatible claims. Restored links let current information travel again. Conflict-free agreement can still leave utility below a centralized optimum, and a stationary claim never establishes task completion.
Primary method: Choi, Brunet and How — Consensus-Based Decentralized Auctions for Robust Task Allocation (2009). Author implementation and extensions: MIT Aerospace Controls Laboratory — CBBA. This is an educational JavaScript implementation of a declared static case.