Auction Algorithm

The hard problem hiding here is called task allocation: given a fleet of robots and a list of jobs, who does what? The obvious answer, a central planner that crunches every pairing and barks out orders, works beautifully right up until the planner's radio drops a packet, or the fleet grows to a thousand robots, or the one machine running the optimizer falls over. Then your whole swarm is staring at a dead leader, waiting.

So we throw out the leader. The robots will figure it out themselves, by bidding.

The auction analogy

Picture an estate sale. Each item on the block is a task. Each bidder is a robot. Every robot privately knows how much a given task is worth to it: a task right next door is worth more than one across the warehouse. The current asking price of each task is public.

A robot's bid is dead simple: it wants the task with the best value minus price.

$$b_{ij} = \text{value}_{ij} - \text{price}_j$$

The highest bidder takes the task. Then the price of that task ticks up. Repeat. That's the entire algorithm:

1. Each unassigned robot bids on the task with the best value-minus-price.
2. The highest bidder wins it, bumping whoever held it back into the pool.
3. The won task's price rises by a small step: $\text{price}_j \leftarrow \text{price}_j + \epsilon$.
4. Repeat until nobody wants to switch.

The genius is in step 3. The rising price is the only coordination signal there is. No robot ever tells another robot what to do. A popular task simply gets expensive until it's no longer the best deal for everyone but one, and the losers, priced out, drift toward jobs nobody else wanted. The market does the planning.

Watch it settle (in your head)

There's no live canvas on this page, so run the auction on your mental whiteboard. Three robots, three tasks.

• Round one. Everybody's broke, so all prices are zero and bids are pure value. Two robots both love Task A (it's closest to both). One wins; the loser is evicted.
• Prices climb where demand is. Task A's price ticks up. Now it's a slightly worse deal. The evicted robot recomputes and finds Task B is suddenly the better bargain. It bids there instead.
• Convergence. Rounds repeat until no robot can improve by switching. The assignment freezes. Crucially, it freezes within a provable margin of the cheapest possible total assignment: not "probably fine," but bounded-optimal.

The bid, with the costs spelled out

In a real fleet the "value" of a task is mostly reward minus the cost of getting there. So the bid grows a couple of terms:

$$b_{ij} = r_{ij} - c \cdot d_{ij} - p_j$$

• $r_{ij}$ is the reward robot $i$ collects for doing task $j$
• $c$ is the cost per unit of travel
• $d_{ij}$ is the distance from robot $i$ to task $j$
• $p_j$ is the current price of task $j$

Read it plainly: a robot wants a high-reward task that's close and not yet expensive. The price term $p_j$ is the one the other robots get to push on. Everything else is private.

The auction was not the first solution to this problem, and it isn't the only one. There's an older, centralized method that gets the exact same job done.

↘ Why does raising prices guarantee a near-optimal answer?

The auction is solving the assignment problem (pair $n$ robots to $n$ tasks to maximize total reward), and it does so by keeping a running set of prices $p_j$ and bidding only on tasks that satisfy approximate complementary slackness. A robot $i$ is "happy" with task $j$ if that task is within $\epsilon$ of its best available net value:

$$r_{ij} - p_j \;\ge\; \max_{k}\,\bigl(r_{ik} - p_k\bigr) - \epsilon$$

When every robot is happy under this rule, the assignment is locked, and Bertsekas proved its total reward is within $n\epsilon$ of the true optimum:

$$R^\* - R_{\text{auction}} \;\le\; n\,\epsilon$$

That's where "$\epsilon$-optimal" comes from. Each bid raises the winning task's price by at least $\epsilon$, so prices are strictly increasing and the process must terminate: no infinite haggling. Shrink $\epsilon$ and the bound tightens toward exact optimality, at the cost of more rounds. The single parameter trades optimality against speed, and the proof hands you the exact exchange rate.

A reference step

The core loop is almost embarrassingly short. Every robot scans the tasks, picks its best net bid, and nudges the price if it switched:

fn auction_step(robots: &[Agent], tasks: &mut [Task], epsilon: f32) -> bool {
    let mut changed = false;

    for i in 0..robots.len() {
        let mut best_j = None;
        let mut best_bid = f32::NEG_INFINITY;

        for j in 0..tasks.len() {
            let dist = robots[i].pos.distance(tasks[j].pos);
            let bid = tasks[j].reward - dist - tasks[j].price;
            if bid > best_bid {
                best_bid = bid;
                best_j = Some(j);
            }
        }

        if let Some(j) = best_j {
            if robots[i].assigned_task != Some(j) {
                changed = true;
                robots[i].assigned_task = Some(j);
                tasks[j].price += epsilon;
            }
        }
    }

    changed
}

Call it until it returns false (that's the "nobody wants to switch" condition) and the fleet has divided its own labor. To stress-test it, make the messages arrive late: have robots act on stale prices and watch convergence merely slow, not fail.

Key takeaways

• Robots bid, prices coordinate. Each robot wants the task with the best value-minus-price; there is no central planner.
• Demand becomes price. A contested task is bid up until only one robot still wants it; the rising price is what steers everyone else away.
• It's provably good. The settled assignment is $\epsilon$-optimal, within $n\epsilon$ of the perfect split.
• One knob, $\epsilon$. Big $\epsilon$ converges fast and a little sloppy; small $\epsilon$ converges slow and nearly perfect.
• It tolerates a bad network. Stale prices slow the haggling but don't corrupt the result.