The Dispatch Problem: Assigning N Agents to N Tasks
When an interviewer hands you a cost matrix — N agents, N tasks, a price for every pairing — and asks for the cheapest assignment, they are testing whether you see one global matching or N independent choices. The instinct is to go agent by agent, giving each its cheapest available task. That instinct has a name (greedy) and a failure mode (collisions): agents share favourite tasks, and whoever picks later pays for it.
Concrete, verifiable example. In the puzzle below, 6 agents take 6 distinct tasks. Row-by-row greedy — each agent grabs its cheapest still-free task, in order — pays 47. The provably cheapest matching pays 28; greedy lands at 60% of optimal, spending 68% more. The killer detail: greedy’s very first pick saves agent 1 exactly 1 point versus what the optimal matching gives it — and that pick forces a cascade that costs the roster 19.
That cascade is the interview. Assignment is a min-cost perfect matching, solved exactly by the Hungarian algorithm — or, for small N, by a dynamic program over the bitmask of used tasks, which is what grades this puzzle. This guide gives you the model, the collision intuition, and a free interactive scored against the exact optimum.
Why this question shows up in AI-engineering interviews
Dispatch is everywhere once you look for it, and the interview versions barely disguise the matrix:
- “Route these N jobs to N workers/agents at minimum total cost.”
- “Each model handles each task with a different cost — who does what?”
- “Match drivers to pickups (or reviewers to PRs, pods to nodes).”
- “Why is per-agent greedy wrong here, and what’s right?”
Every one is the assignment problem: a square cost matrix, one task per agent, one agent per task, minimise the total. It shows up in agent-fleet schedulers and classic ops alike, and interviewers ask it because it cleanly separates two habits of mind — optimising each row locally versus optimising the permutation globally. The greedy answer is fluent, confident, and measurably wrong.
The mental model that gets you to optimal
Stop thinking “which task is best for this agent” and start thinking “which permutation is cheapest.” Four ideas get you there:
- It’s a permutation, not N choices. The constraint — every task to exactly one agent — couples all the rows. An agent’s pick is only good relative to what it leaves the others.
- Price the collision, not the cell. When two agents share a cheap favourite, the question is not who wants it more but which agent has the cheapest alternative. Give the shared task to the agent whose second-best is worst.
- Small sacrifices buy big savings. In the puzzle, moving agent 1 off its cheapest task costs it 1 — and unblocks a chain of cheap cells worth 19 to the roster. Optimal matchings are full of these trades; greedy can’t make any of them.
- Exact algorithms exist and are cheap. The Hungarian algorithm solves assignment in O(n³); for small N a bitmask DP over used-task sets (2^N states) is a few lines and exact — it is what computes the optimum this puzzle grades with. Greedy carries no guarantee at all.
Put together: treat the roster as one decision, resolve shared favourites by comparing alternatives, and reach for Hungarian or the bitmask DP when you need the provable minimum. That matching is what the puzzle scores you against.
The trap: row-by-row greedy
| Agent | Greedy takes (cheapest free) | Optimal assigns |
|---|---|---|
| agent 1 | task 1 · 1 | task 5 · 2 |
| agent 2 | task 6 · 4 | task 6 · 4 |
| agent 3 | task 2 · 10 | task 1 · 2 |
| agent 4 | task 5 · 10 | task 4 · 11 |
| agent 5 | task 3 · 9 | task 2 · 3 |
| agent 6 | task 4 · 13 | task 3 · 6 |
Read the cascade: the early agents take their favourites, and every later agent inherits a poorer menu — the last picks are where greedy’s 47 total comes from. The optimal matching pays a point more here and there early to keep the cheap cells available where they matter, landing at 28. Naming the cascade — local wins, global loss — is the senior answer.
The puzzle simplifies on purpose: the cost matrix is known, integer, and static, and all 6 tasks are assigned at once. Real dispatch is online (tasks arrive over time, and you match without seeing the future), costs are estimates, and sometimes the objective is the makespan — the slowest agent — rather than the total. The core survives: assignment is a global matching, and per-agent greed has no guarantee under any of those variations.
Practice it: find the min-cost matching
Describing the collision is not the same as trading your way out of one. Below is the live Dispatch puzzle from The Arena. Assign every agent a distinct task; The Arena computes the min-cost perfect matching by bitmask DP (verified against brute force) and scores your roster as a percentage of it. No login required.
What “good” looks like
When you can find the 28-cost matching where greedy pays 47, you can walk the interviewer through the trade that greedy can’t see: the agent that gives up 1 so the roster saves 19. Then name the exact tools — Hungarian at O(n³), bitmask DP at 2^N for small N — and the question is closed.
Frequently asked
How do you assign N agents to N tasks at minimum cost?
As a min-cost perfect matching on the cost matrix — one task per agent, one agent per task, minimise the total. Solve it exactly with the Hungarian algorithm (O(n³)) or, for small N, a bitmask DP over used-task subsets. In the worked example the optimal matching costs 28 while per-agent greedy pays 47.
Why does greedy fail on the assignment problem?
Because agents share favourite tasks. Giving each agent its own cheapest task either collides (two agents want the same one) or, resolved in order, forces later agents onto expensive leftovers. The optimum often moves an agent off its personal best by a point to free a much cheaper cell for someone else — a trade greedy can never make.
What algorithm solves agent-task assignment optimally?
The Hungarian (Kuhn–Munkres) algorithm, in O(n³) — or an exact bitmask dynamic program over the set of used tasks, O(2ⁿ·n²), which is simpler to write and fast for small n. Both find the min-cost perfect matching; the puzzle here grades with the bitmask DP, verified against brute force.
Is task assignment the same as load balancing?
No — the objectives differ. Assignment minimises the total (or sum) cost of one-to-one pairings; load balancing typically minimises the makespan — the busiest worker — with many jobs per worker allowed. Same matrix instincts, different optimisation, and interviewers like asking which objective a scenario actually needs.
New scored, provably-optimal interview drills, now and then — no spam, unsubscribe anytime.
More interview guides
41 puzzles — RAG tuning, tool routing, agent orchestration, prompt/KV caching, memory compaction — each scored against a provably optimal answer.
Explore the puzzles →