AI Glossary / Mathematics and optimization / Intermediate
Auction algorithm
Definition
The auction algorithm is an optimization method that solves assignment problems through a sequence of bids and price updates. In its standard assignment form, it matches each person or agent to one object while seeking the greatest total benefit. Prices are computational variables that resolve competition for attractive objects; they need not represent real money or an actual commercial auction.
What it means
Suppose several workers can perform several jobs, with a benefit recorded for each possible pairing. Giving every worker their favorite job independently may assign the same job twice. The assignment problem requires a compatible set of choices.
The auction algorithm, associated with Dimitri Bertsekas, coordinates these choices by making heavily contested objects more expensive. A bidder compares benefit minus current price. The method belongs to a broader family with extensions to network problems, but this entry explains the one-to-one assignment version.
How it works
Begin with prices and a partial assignment. Select an unassigned bidder and calculate the net value of each permitted object: benefit minus price. Identify the best and second-best net values.
Raise the best object's price by the difference between those two values plus a positive amount epsilon. Assign that object to the bidder. If it had an owner, that previous owner becomes unassigned and will bid again.
Continue until the assignment is complete. Epsilon prevents zero-increment bidding cycles. In the standard setting, a complete assignment satisfying epsilon-complementary slackness is within n times epsilon of the optimal total benefit, where n is the number of bidders. With integer benefits and n times epsilon below one, that bound implies an optimal assignment.
Three practical examples
1. A fleet coordinator matches available vehicles to individual pickup jobs using a benefit matrix. Additional routing decisions after those pickups may require a richer model.
2. A simulation assigns robots to inspection stations, with one robot per station. The bids can be implemented as messages even though no robot spends money.
3. A data-processing system matches detected objects in one frame with candidates in another. The benefit matrix encodes compatibility; detection errors and unmatched objects need explicit treatment beyond the basic square assignment model.
Think of it this way
Think of several people choosing desks while popular desks acquire higher prices. Someone may switch to a less contested desk, allowing everyone to be seated. The algorithm's analogy is economic, but it centrally follows a numerical update rule. It does not assume strategic bidders, private budgets, or the rules of a consumer auction platform.
Worked example
Consider two workers, A and B, and two jobs, X and Y. Benefits are A - X = 10, A - Y = 9, B - X = 8, and B - Y = 0. Both workers can perform either job. Start with both prices zero, no assignments, and epsilon = 0.25. Let A bid first.
A's net values are 10 for X and 9 for Y. It selects X and raises X's price by 10 − 9 + 0.25 = 1.25. A now owns X.
B compares X's net value 8 − 1.25 = 6.75 with Y's zero. B raises X's price by 6.75 − 0 + 0.25 = 7, so X's new price is 8.25. B takes X and A becomes unassigned.
A now compares X's net value 10 − 8.25 = 1.75 with Y's 9. It bids for Y, raising its price by 9 − 1.75 + 0.25 = 7.5. The assignment is complete: A receives Y and B receives X.
Total original benefit is 9 + 8 = 17. The other possible complete assignment gives 10 + 0 = 10, confirming optimality directly. Final prices are not subtracted when reporting the assignment objective. Here n epsilon = 0.5, also consistent with the integer-benefit optimality condition. This is a hand-worked trace, not a runtime benchmark.
Illustrative case study
Fictional case: Maple Dispatch builds a daily matching tool for two groups of service technicians and appointments. A prototype treats an impossible pairing as merely unattractive, leading to a complete assignment that violates a qualification requirement.
The team separates permitted pairings from benefit scores and checks that a feasible complete matching exists. It also documents how unfilled appointments should be represented if the numbers differ. Reviewers inspect the original benefits and eligibility constraints rather than reading computational prices as customer charges. The case illustrates modeling checks, not a measured improvement in service delivery.
Common misconceptions and mistakes
Do not confuse the price update with the total value of the final solution. Prices steer assignment; the original benefits define the objective.
Do not omit epsilon merely because a bidder's two best choices tie. A positive increment is central to avoiding stagnation in the basic method.
One-to-one assignment does not automatically express multiple jobs per worker, time windows, or dependencies between jobs. Extensions or different formulations may be needed. Exactness claims also depend on the specified numerical conditions; a large epsilon generally supports an approximation bound rather than unrestricted exact optimality.
Business use
Use the algorithm when the decision can be represented by pairwise benefits and a matching constraint. Compare it with other assignment solvers on the actual matrix size, sparsity, and precision requirements.
Before optimizing, establish what the benefit scores mean. A mathematically optimal matching can still be operationally poor if it omits travel delays, qualifications, or workload restrictions. After solving, validate eligibility and uniqueness, calculate the objective from the input matrix, and preserve the chosen epsilon and stopping conditions with the result.
People also ask
Must bidders be human?
No. They are mathematical roles and can represent workers, tasks, robots, or records.
Are prices actual payments?
Not necessarily. In assignment optimization they usually function as internal coordination variables.
Does every bidder keep their first choice?
No. A later bid can displace an earlier owner, who then bids again.
Check your understanding
Why is total benefit 17 rather than 17 minus the final prices in the worked example?
Answer: The objective sums original pairing benefits. The prices guide the search for a compatible assignment; they are not costs in that stated objective.
Related terms
- Assignment problems
- Linear programming
- Hungarian algorithm
- Assignment problem
- bipartite matching
- duality
- epsilon-complementary slackness
- network flow
- distributed optimisation
Learn next
Study the assignment problem next. Enumerate all matchings for a three-by-three benefit matrix, then trace several bids. Compare original total benefits separately from the changing net values used during bidding.
More in Mathematics and optimization
- Absolute error loss - Absolute error loss measures a numerical prediction's error as the absolute difference between its predicted and reference values: L(y,y-hat)=|y-y-hat|.
- Active-set method - An active-set method is an optimization approach that works with a changing subset of constraints believed to be tight at the solution.
- Adjoint state method - The adjoint state method computes how a chosen objective changes when the parameters of a mathematical model change.
- Σ-algebra
- Algebraic connectivity - Algebraic connectivity is the second-smallest eigenvalue of a graph's Laplacian matrix.
- Algorithm IMED - Algorithm IMED, short for Indexed Minimum Empirical Divergence, is a method for choosing actions in a stochastic multi-armed bandit problem.
Sources
Primary references opened: Bertsekas, “The Auction Algorithm for Assignment and Other Network Flow Problems: A Tutorial,” https://www.mit.edu/~dimitrib/Auction_Interfaces_Published.pdf; and “New Auction Algorithms for the Assignment Problem and Extensions,” https://web.mit.edu/dimitrib/www/Bertsekas_Auction_Assignment_Algorithms_RICO.pdf. The numerical trace and fictional case are original illustrations.
Previous: AUC (Area under the ROC curve) Next: Audio codec