mathematics//optimization//combinatorial optimization//assignment problem//auction algorithm
The auction algorithm is a method for the assignment problem in which unassigned agents bid for tasks and raise their prices until no two agents want the same task; it is used when a fleet has no central server that sees the whole cost matrix, because each agent needs only its own values and the current prices. Bertsekas proposed it in 1979, and it carries a market's logic: a task that many want becomes expensive until only the agent that values it most still finds it worth taking.
The auction algorithm is a method for the assignment problem in which unassigned agents bid for tasks and raise their prices until no two agents want the same task; it is used when a fleet has no central server that sees the whole cost matrix, because each agent needs only its own values and the current prices. Bertsekas proposed it in 1979, and it carries a market's logic: a task that many want becomes expensive until only the agent that values it most still finds it worth taking.
Agent iii values task jjj at aija_{ij}aij and sees its current price pjp_jpj. It bids for the task ji∗j_i^*ji∗ with the highest net benefit and raises that task's price by
γi=vi−wi+ε,vi=maxj (aij−pj),wi=maxj≠ji∗ (aij−pj)\gamma_i = v_i - w_i + \varepsilon,\qquad v_i=\max_{j}\,(a_{ij}-p_j),\qquad w_i=\max_{j\ne j_i^*}\,(a_{ij}-p_j)γi=vi−wi+ε,vi=jmax(aij−pj),wi=j=ji∗max(aij−pj)
which is the amount that would leave it indifferent between its first choice (viv_ivi) and its second (wiw_iwi), plus a small ε>0\varepsilon>0ε>0 that prevents endless ties. With values of 10 and 7 for two free tasks, a drone bids for the first and raises its price by 3+ε3+\varepsilon3+ε; a second drone that also prefers it must now weigh it at its value minus that price. Each task goes to its highest bidder, outbid agents bid again, and the process ends with every agent assigned.
The answer is within NεN\varepsilonNε of the optimum for NNN agents, and exact when values are integers and ε<1/N\varepsilon<1/Nε<1/N. A small ε\varepsilonε is accurate but slow, because prices creep up by tiny steps on contested tasks; implementations start large and shrink it (ε\varepsilonε-scaling).
It fits a radio network. Prices spread by a max-consensus, each agent keeping the highest bid it has heard, so agreement takes about as many rounds as the diameter of the communication graph; a lost message delays the auction without corrupting it. When each agent takes a bundle of tasks in sequence, the consensus-based bundle algorithm of task allocation extends the idea, mostly still in research.
The book's cold water applies. linear_sum_assignment solves a 1000 by 1000 matrix in under a second, and at light load the nearest free robot works surprisingly well, so auctions earn their place when there is no server or the link to it cannot be trusted, which is a design decision about the fleet architecture more than about the algorithm.
The prices are the same quantities the Hungarian algorithm adjusts as row and column constants, the dual variables of the problem (duality).