Auction Algorithm

The auction algorithm is an algorithm in optimal transport in which a set of buyers exchange goods for varied prices until an eventual equilibrium is reached. It is an iterative approach. The algorithm pertains to the discrete formulation of optimal transport, as well as provides a connection to the dual problem. The algorithm is useful in the field of economics because of its ability to find an equilibrium. The algorithm was invented by Bertsekas, but it was eventually updated.

The Assignment Problem

It is necessary to introduce the assignment problem because it applies a context in which we may apply our algorithm to find such an optimal equilibrium. Suppose we have both $N$ buyers as well as $N$ goods. We introduce $a_{ij}$ to quantify the notion of some sort of utility, benefit, or happiness the buyer receives from their corresponding good. The assignment problem therefore seeks a way to maximize $\sum _{i}a_{i\sigma (i)}$, i.e., we hope to maximize the total utility. Note this is different from maximizing the utility of a particular buyer, because we seek to benefit the whole group the most. We use the index $i$ to denote a particular buyer we use the second index $j=\sigma (i)$ to denote the good, where $\sigma$ is some permutation of the goods among all of the buyers. A final thing to note is that the assignment of people to goods is one-to-one, i.e. there is one distinct good for every distinct buyer.

We've established what the aim of the assignment problem is, but we have yet to establish a sense of equilibrium that the auction algorithm hopes to achieve. First, we must define a price system. We say that a good $j$ has price $p_{j}$, which can be rewritten $p=(p_{j})_{j}$. Next, we define the equilibrium condition. The equilibrium is that all buyers are content with their purchases if

$$a_{i\sigma (i)}-p_{\sigma (i)}=\max _{j=1,...,N}\{a_{ij}-p_{j}\}\ \ \ \ \ \ \ \ \ \ (*)$$

is satisfied. It is important to note that the absolute value is not taken. If the absolute value is taken, then it is possible for the system to be in equilibrium when each buyer has the worst possible good, and $\sum _{i}a_{i\sigma (i)}$ fails to be maximized. Now, another common way to say that the system is in equilibrium is that all of the buyers are "happy." Notationally, we say $(p,\sigma )$ is an equilibrium. If this is an equilibrium, then $\sigma$ is an optimal assignment, and $p$ is optimal in the dual problem.

The Algorithm

The algorithm starts from an arbitrary arrangement of buyers and goods. It does not matter to the algorithm who begins with what good. Denote this arbitrary arrangement with the prices and good permutation as $(p_{0},\sigma _{0})$. The algorithm acts with iterations, and once all buyers satisfy the "happy" condition, our algorithm is done. The algorithm is as follows:

• First, find a particular buyer. We will call this buyer $i^{*}$. We will only choose a buyer such that $(*)$ does not hold. The buyer then finds the good maximizing the difference between their personal utility and the price, i.e. $\max _{j=1,...,N}\{a_{i^{*}j}-p_{j}\}$. This buyer exchanges their good with this other buyer that originally held this other good. Denote this new good $j^{*}$.

• This buyer that just purchased the good maximizing their utility is going to increase the price of this new good by some amount $\gamma _{i}$ until this buyer is indifferent between object $j^{*}$ and the second best option. Mathematically, we say $a_{i^{*}j^{*}}-p_{j^{*}}=\max _{j\neq j^{*}}\{a_{i^{*}j}-p_{j}\}$.

Our iterative procedure continues until each buyer satisfies the "happy" condition.

$\epsilon -$Complementary Slackness

One problem with the algorithm is the possibility that it never ends, i.e. it iterates indefinitely. To fix such a problem, we introduce a scalar $\epsilon >0$ and we alter our condition $(*)$ so that the buyer is within a tolerance of being content with their purchase. Such names for this are $\epsilon -$happy or "almost happy." Specifically, we alter $(*)$ by saying

$a_{i\sigma (i)}-p_{\sigma (i)}\geq \max _{j=1,...,N}\{a_{ij}-p_{j}\}-\epsilon$.

Another name for the above condition is $\epsilon -$complementary slackness. It may be necessary to modify the value for $\epsilon$ so that convergence of the algorithm is reached at a desirable rate. The algorithm maintains $\epsilon -$complementary slackness at each iteration.

Relations with Optimal Transport

The auction algorithm has applications in optimal transport, mostly by extending situations in optimal transport to where the assignment problem applies. Converting optimal transport scenarios to the assignment problem gives us the opportunity to apply the auction algorithm to find a solution. Something to note is that this idea mostly applies to linear optimal transport problems. One area in which this idea can be done is network optimization problems. Shortest path and max-flow problems can be converted into assignment problems, giving the auction algorithm a chance to offer a solution. A second area is transportation problems, and another is minimum cost flow problems. A final area is convex separable network optimization problems.