Auction Algorithm

The auction algorithm pertains to the discrete formulation of optimal transport. Particularly, the auction algorithm is an algorithm connected to the dual problem, but it is not based on a sequence of improvements of the dual objective function. Instead, it attempts to seek an equilibrium. Because of such, the algorithm has applications in economics.

The Assignment Problem

We begin by discussing the assignment problem. Consider the specialized case when weights $a_{i}$ and $b_{j}$ are equal. Suppose we have $N$ buyers, denoting the index with $i$, and $N$ goods to be bought, denoted by $j$. We look for an assignment $j=\sigma (i),\sigma \in S_{N}$ which maximizes $\sum _{i}u_{i\sigma (i)}$. The values $u_{ij}$ are the utilities of buyer $i$ when he/she buys item $j$. Now, we look at a price system $p=(p_{j})_{j}$. Given a price system $p$ and as assignment $\sigma$, we say that it is an equilibrium if for every $i$, we have $u_{i\sigma (i)}-p_{\sigma _{i}}=\max _{j}u_{ij}-p_{j}$. The buyers $i$ satisfying this condition are said to be "happy." This only corresponds to writing the equilibrium condition in terms of a coupling $\gamma$ induced by a permutation. If $(p,\sigma )$ is an equilibrium, then $\sigma$ is an optimal assignment (and $p$ is optimal in the dual problem).

The Algorithm

Start from an arbitrary pair $(p_{0},\sigma _{0})$.

At every step, we have a pair $(p^{n},\sigma _{n})$. If it is an equilibrium, stop the algorithm. Otherwise, pick any $i^{*}$ among those $i$ such that $u_{i\sigma (i)}-p_{\sigma _{i}}<\max _{j}u_{ij}-p_{j}$. The selected buyer $i^{*}$ implements two actions:

1) he/she chooses one good $j^{*}$ realizing the maximum in $\max _{j}u_{i^{*}j}-p_{j}$ and exchanges his/her own good $\sigma _{n}(i)$ with the buyer $\sigma _{n}^{-1}(j^{*})$ who was originally assigned to $j^{*}$.

2) he/she increases the price of $j^{*}$ to a new value which is such that he/she is indifferent between $j^{*}$ and his/her second best object in $\max _{j}u_{i^{*}j}-p_{j}$.

Thus, the new price of $j^{*}$ is $P=p_{j^{*}}^{n}+\max _{j}(u_{i^{*}j}-p_{j}^{n})-\max _{j\neq j^{*}}(u_{i^{*}j}-p_{j}^{n})\geq p_{j^{*}}$.

The new price system $p^{n+1}$ is defined by setting $p_{j}^{n+1}=p_{j}^{n}$ for $j\neq j^{*}$ and $p_{j^{*}}^{n+1}=P$. The new permutation $\sigma _{n+1}$ is obtained by composing with the transposition which exchanges $j^{*}$ and $\sigma _{n}(i^{*})$.

Problems with the Algorithm

The auction algorithm has a possibility of looping forever. This is because of the possibility of equality in $\max _{j}u_{i^{*}j}-p_{j}$. In this case, prices can stay constant and buyers may exchange the same set of items among themselves. To rectify this problem, introduce a parameter $\epsilon >0$ that acts as a tolerance. We say a buyer $i$ is $\epsilon$-happy if $\max _{j}u_{i\sigma (i)}-p_{\sigma _{i}}>\max _{j}(u_{ij}-p_{j})-\epsilon$. We now look for a pair $(p,\sigma )$ such that all buyers are $\epsilon$-happy.