Auction Algorithm: Difference between revisions

From Optimal Transport Wiki
Jump to navigation Jump to search
m (Linked to Discrete Optimal Transport page)
No edit summary
Line 1: Line 1:
The auction algorithm<ref name="Peyré and Cuturi" /> pertains to the [[Discrete Optimal Transport|discrete formulation of optimal transport]]. Particularly, the auction algorithm<ref name="Santambrogio" /> 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 auction algorithm<ref name="Peyré and Cuturi" /> \epsilon </math>.
 
== The Assignment Problem ==
 
We begin by discussing the assignment problem. Consider the specialized case when weights <math> a_i </math> and <math> b_j </math> are equal. Suppose we have <math> N </math> buyers, denoting the index with <math> i </math>, and <math> N </math> goods to be bought, denoted by <math> j </math>. We look for an assignment <math> j = \sigma(i), \sigma \in S_N </math> which maximizes <math> \sum_{i} u_{i \sigma(i)} </math>. The values <math> u_{ij} </math> are the utilities of buyer <math> i </math> when he/she buys item <math> j </math>. Now, we look at a price system <math> p = (p_j)_j </math>. Given a price system <math> p </math> and as assignment <math> \sigma </math>, we say that it is an equilibrium if for every <math> i </math>, we have <math> u_{i \sigma(i)} - p_{\sigma_i} = \max_j u_{ij} - p_j </math>. The buyers <math> i </math> satisfying this condition are said to be "happy."  This only corresponds to writing the equilibrium condition in terms of a coupling <math> \gamma </math> induced by a permutation. If <math> (p, \sigma) </math> is an equilibrium, then <math> \sigma </math> is an optimal assignment (and <math> p </math> is optimal in the dual problem).
 
== The Algorithm ==
 
Start from an arbitrary pair <math> (p_0, \sigma_0) </math>.
 
At every step, we have a pair <math> (p^n, \sigma_n) </math>. If it is an equilibrium, stop the algorithm. Otherwise, pick any <math> i^* </math> among those <math> i </math> such that <math> u_{i\sigma(i)} - p_{\sigma_i} < \max_j u_{ij} - p_j </math>. The selected buyer <math> i^* </math> implements two actions:
 
1) he/she chooses one good <math> j^* </math> realizing the maximum in <math> \max_j u_{i^*j} - p_j </math> and exchanges his/her own good <math> \sigma_n(i) </math> with the buyer <math> \sigma_{n}^{-1} (j^*) </math> who was originally assigned to <math> j^* </math>.
 
2) he/she increases the price of <math> j^* </math> to a new value which is such that he/she is indifferent between <math> j^* </math> and his/her second best object in <math> \max_j u_{i^*j} - p_j </math>.
 
Thus, the new price of <math> j^* </math> is <math> 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^*} </math>.
 
The new price system <math> p^{n+1} </math> is defined by setting <math> p_j^{n+1} = p_j^n</math> for <math> j \neq j^* </math> and <math> p_{j^*}^{n+1} = P </math>. The new permutation <math> \sigma_{n+1} </math> is obtained by composing with the transposition which exchanges <math> j^* </math> and <math> \sigma_n(i^*) </math>.
 
 
== Problems with the Algorithm ==
 
The auction algorithm has a possibility of looping forever. This is because of the possibility of equality in <math> \max_j u_{i^*j} - p_j </math>. 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 <math> \epsilon > 0 </math> that acts as a tolerance. We say a buyer <math> i </math> is <math> \epsilon </math>-happy if <math> \max_j u_{i\sigma(i)} - p_{\sigma_{i}} > \max_j (u_{ij} - p_j) - \epsilon </math>. We now look for a pair <math> (p, \sigma) </math> such that all buyers are <math> \epsilon </math>-happy.




Revision as of 19:36, 14 May 2020

The auction algorithm[1] \epsilon </math>.


References

  1. ↑ G. Peyré and M. Cuturi, Computational Optimal Transport, Chapter 3.

Cite error: <ref> tag with name "Santambrogio" defined in <references> is not used in prior text.

Retrieved from "http://www.otwiki.xyz/index.php?title=Auction_Algorithm&oldid=329"