n couriers, n delivery jobs, each courier takes exactly one job — the classic assignment problem, with distance as the cost. Watch the algorithm run it as a literal auction: couriers bid for the jobs that suit them best, prices rise (the ring around each job), outbid couriers get displaced and bid again, and the tangle of edges settles into the cheapest possible one-to-one matching. Every step you see is a real event from the solver — compare the final total against the greedy "everyone grabs the nearest job" baseline below.
Controls
Live readout
Auction vs. greedy baseline
Run a solve to compare.
Result
.txt or .apf problem file — it will be loaded into the editor.
Errors come from the same C++ parser the CLI uses (problem.cpp), running in your browser via WebAssembly — line numbers refer to the text above.
Result
| Person | → Object | Cost |
|---|
01Bidding for objects
The auction algorithm treats the assignment problem as a literal auction. Every person holds a
price they'd pay for each object — initially zero — and repeatedly bids for whichever
object gives them the best deal. For person i, the value of object
j is its benefit minus its current price. Each unassigned person finds their
best object (highest value) and their second-best, and bids on the best one with
bid = best_value − second_best_value + ε
That bid raises the object's price by exactly enough to erase the person's margin over the runner-up option. Whoever now holds the highest price for that object wins it; if someone else already owned it, they're displaced and thrown back into the pool of unassigned bidders, to rebid on their own next-best object next round. Prices only ever go up, and they persist across rounds — which is what keeps the process converging instead of cycling.
02ε-scaling
A single fixed ε makes each bid a coarse, decisive jump, which is fast but can lock in ties incorrectly. The algorithm instead runs in phases: start with a large ε (coarse, fast convergence, possibly imprecise), run the bidding process to completion, then shrink ε by a constant factor and run it again. Prices carry over between phases; only the assignment resets. Each phase refines the previous one's answer.
Termination and optimality: for integer costs, the assignment produced by a
completed phase is exactly optimal once that phase runs with n·ε < 1.
Below that threshold, the total bidding "slack" across all n people can't add up to a single unit
of cost — so a locally greedy, ε-approximate equilibrium is forced to be the global
optimum. That's the whole termination condition: keep scaling ε down and stop after the
first full phase where n·ε < 1.
Original reference: D. P. Bertsekas, "The Auction Algorithm: A Distributed Relaxation Method for the Assignment Problem", MIT LIDS, 1988.
03How fast is it?
Benchmarked on Linux, single-threaded, median of 3 runs, against
scipy.optimize.linear_sum_assignment — itself a C++ Hungarian /
Jonker–Volgenant implementation, not a naive baseline. Honestly: scipy wins across this range.
The gap narrows steadily as n grows and as the cost range widens — down to about a 5% gap at
n = 2000 on wide cost ranges. The auction algorithm's case isn't raw single-thread speed;
it's conceptual simplicity (a handful of lines of bidding logic) and that the bidding step is
embarrassingly parallel across people, which Jonker–Volgenant is not.
| family | n | auction median (ms) | scipy median (ms) | ratio |
|---|
ratio = auction / scipy (lower is closer to parity). uniform_narrow draws costs from 1…n; uniform_wide from 1…1000n.