# New Auction Algorithms for Path Planning, Network Transport, and Reinforcement Learning

arXiv: https://arxiv.org/abs/2207.09588 · HTML: https://mlsanity.com/paper/2207.09588/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 48 references that are in the map.
- First posted on arXiv 19 Jul 2022.

## Builds on (most cited first, 10 of 10)

- [BASE Layers: Simplifying Training of Large, Sparse Models](https://mlsanity.com/paper/2103.16716/) (2021)
- [Unified Scaling Laws for Routed Language Models](https://mlsanity.com/paper/2202.01169/) (2022)
- [Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems](https://mlsanity.com/paper/1610.06519/) (2016)
- [Lessons from AlphaZero for Optimal, Model Predictive, and Adaptive Control](https://mlsanity.com/paper/2108.10315/) (2021)
- [A Sparse Multi-Scale Algorithm for Dense Optimal Transport](https://mlsanity.com/paper/1510.05466/) (2015)
- [Optimal transport: discretization and algorithms](https://mlsanity.com/paper/2003.00855/) (2020)
- [Constrained Multiagent Rollout and Multidimensional Assignment with the Auction Algorithm](https://mlsanity.com/paper/2002.07407/) (2020)
- [Expected time complexity of the auction algorithm and the push relabel algorithm for maximal bipartite matching on random graphs](https://mlsanity.com/paper/1401.0119/) (2013)
- [General auction method for real-valued optimal transport](https://mlsanity.com/paper/1705.06379/) (2017)
- [Max-Product for Maximum Weight Matching - Revisited](https://mlsanity.com/paper/1805.06282/) (2018)

## Abstract (arXiv)

We consider some classical optimization problems in path planning and network transport, and we introduce new auction-based algorithms for their optimal and suboptimal solution. The algorithms are based on mathematical ideas that are related to competitive bidding by persons for objects and the attendant market equilibrium, which underlie auction processes. However, the starting point of our algorithms is different, namely weighted and unweighted path construction in directed graphs, rather than assignment of persons to objects. The new algorithms have several potential advantages over existing methods: they are empirically faster in some important contexts, such as max-flow, they are well-suited for on-line replanning, and they can be adapted to distributed asynchronous operation. Moreover, they allow arbitrary initial prices, without complementary slackness restrictions, and thus are better-suited to take advantage of reinforcement learning methods that use off-line training with data, as well as on-line training during real-time operation. The new algorithms may also find use in reinforcement learning contexts involving approximation, such as multistep lookahead and tree search schemes, and/or rollout algorithms.