Auction Algorithm

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. It is well known that 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}$.