Feeds:
Posts

## Auction Algorithm for Bipartite Matching

Undergraduate algorithms courses typically discuss the maximum matching problem in bipartite graphs and present algorithms that are based on the alternating paths (Hungarian) method.  This is true in the standard CLR book as well as in the newer KT book (and implicitly in the new DPV book that just gives the reduction to max-flow.)  There is an alternative auction-like algorithm originally due to Demange, Gale, and Sotomayor that is not well known in the CS community despite being even simpler.  The algorithm naturally applies also to the weighted version, sometimes termed the assignment problem, and this is how we will present it.

Input: A weighted bipartite graph, with non-negative integer weights.  We will denote the vertices on one side of the graph by B (bidders) and on the other side by G (goods).  The weight between a bidder i and a good j is denoted by $w_{ij}$.  We interpret $w_{ij}$ as quantifying the amount that bidder i values good j.

Output: A matching M with maximum total weight $\sum_{(i,j) \in M} w_{ij}$.  A matching is a subset of $B \times G$ such that no bidder and no good appear more than once in it.

The special case where $w_{ij} \in \{0,1\}$ is the usual maximum matching problem.

Algorithm:

Initialization:

1. For each good j, set $p_j \leftarrow 0$ and $owner_j \leftarrow null$.
2. Initialize a queue Q to contain all bidders i.
3. Fix $\delta = 1/(n_g+1)$, where $n_g$ is the number of goods.

While Q is not empty do:

1. $i \leftarrow Q.deque()$.
2. Find j that maximizes $w_{ij} - p_j$.
3. If $w_{ij} - p_j \ge 0$ then
1. Enque current $owner_j$ into Q.
2. $owner_j \leftarrow i$.
3. $p_j \leftarrow p_j + \delta$.

Output: the set of $(owner_j, j)$ for all j.

Correctness: The proof of correctness is based on showing that the algorithm gets into an “equilibrium”, a situation where all bidders “are happy”.

Definition: We say that bidder i is $\delta$-happy if one of the following is true:

1. For some good j, $owner_j=i$ and for all goods j’ we have that $\delta + w_{ij}-p_j \ge w_{ij'}-p_{j'}$.
2. For no good j does it hold that $owner_j=i$ and  for all goods j we have that that $w_{ij} \le p_{j}$.

The key loop invariant is that all bidders, except those that are in Q, are $\delta$-happy.  This is true at the beginning since Q is initialized to all bidders.  For the bidder i dequeued in an iteration, the loop exactly chooses the j that makes him happy, if such j exists, and the $\delta$-error is due to the final increase in $p_j$.  The main point is that this iteration cannot hurt the invariant for any other i’: any increase in $p_j$ for j that is not owned by i’ does not hurt the inequality while an increase for the j that was owned by i’ immediately enqueues i’.

The running time analysis below implies that the algorithm terminates, at which point Q must be happy and thus all bidders must be $\delta$-happy.

Lemma: if all bidders are $\delta$-happy then for every matching M’ we have that $n\delta + \sum_{i=owner_j} w_{ij} \ge \sum_{(i,j) \in M'} w_{ij}$.

Before proving this lemma, we notice that this implies the correctness of the algorithm since by our choice of $\delta$, we have that $n\delta < 1$, and as all weights are integers, this implies that our matching does in fact have maximum weight.

We now prove the lemma.  Fix a bidder i, let j denote the good that he got from the algorithm and let j’ be the good he gets in M’ (possibly j=null or j’=null).  Since i is happy we have that $\delta + w_{ij}-p_j \ge w_{ij'}-p_{j'}$ (with a notational convention that $w_{i,null}=0$ and $p_{null}=0$, which takes care also of case 2 in the definition of happy)  Summing up over all i we get $\sum_{i=owner_j} (\delta + w_{ij}-p_j) \ge \sum_{(i,j') \in M'} (w_{ij'}-p_{j'})$.  Now notice that since both the algorithm and M’ give matchings, each j appears at most once on the left hand side and at most once on the right hand side.  More over if some j does not appear on the left hand side then it was never picked by the algorithm and thus $p_j=0$.  Thus when we subtract $\sum_j p_j$ from both sides of the inequality, the LHS becomes the LHS of the inequality in the lemma and the RHS becomes at most the RHS of the inequality in the lemma.  QED.

Running Time Analysis:

Each time the main loop is repeated, some $p_j$ is increased by $\delta$ or some bidder is removed from Q forever.  No $p_j$ can ever increase once its value is above $C = max_{i,j} w_{ij}$.  It follows that the total number of iterations of the main loop is at most $Cn/\delta = O(Cn^2)$ where n is the total number of vertices (goods+bidders).  Each loop can be trivially implemented in O(n) time, giving total running time of $O(Cn^3)$, which for the unweighted case, C=1, matches the running time of the basic alternating paths algorithm on dense graphs.

For non-dense graphs, with only $m=o(n^2)$ edges (where an edge is a non-zero $w_{ij}$), we can improve the running time by using a better data structure.  Each vertex maintains a priority que of goods ordered according to the value of $w_{ij} - p_j$.  Whenever some $p_j$ is increased, all bidders that have an edge to this j need to update the value in the priority queue.  Thus an increase in $p_j$ requires $d_j$ priority queue operations, where $d_j$ is the degree of j. Since each $p_j$ is increased at most $C/\delta = O(Cn)$ times, and since $\sum_j d_j =m$ we get a total of O(Cmn) priority queue operations.  Using a heap to implement the priority queue takes $O(\log n)$ per operation.  However, for our usage, an implementation using an array of linked lists gives O(1) amortized time per operation: entry t of the array contains all j such that $w_{ij} - p_j = t\delta$, updating the value of j requires moving it down one place in the array, and finding the maximum $w_{ij} - p_j$ is done by marching down the array to find the next non empty entry (this is the only amortized part).  All in all, the running time for the unweighted case is O(mn).

• As shown by DGS, a similar procedure terminates with close to VCG prices, which are also the point-wise minimum equilibrium prices.
• The algorithm was presented for the assignment problem where bidders never desire more than a single item.  It does work more generally as long as bidders are “gross substitutes”.
• The algorithm, like many auctions, can be viewed as a primal-dual algorithm for the associated linear program.
• Choosing a small fixed value of, say, $\delta=0.01$ gives a linear time 1.01-approximation for the maximum matching.
• Choosing the value $\delta = 1/\sqrt{n}$ gives a matching that misses at most $\sqrt{n}$ edges, that can then be added using $\sqrt{n}$ alternating path computations, for a total running time of $O(m \sqrt{n})$.
• Many algorithmic variants were studied by Dimitry Bertsekas.
• A wider economic context appears in this book.

### 31 Responses

1. on July 13, 2009 at 10:16 pm | Reply Ali Sinop

Isn’t this just maximum residual augmenting path algorithm for the associated flow network?

• on July 14, 2009 at 8:39 pm | Reply algorithmicgametheory

I don’t think so… the algorithm does not find or use augmenting paths even implicitly.

2. on July 13, 2009 at 10:17 pm | Reply John Mount

Great point, I have to admit intellectual laziness in almost always reducing bipartite matchings to flows (without thinking deeply). You have probably mentioned this paper before, but a great treatment of using online bipartite matching to design an auction strategy:

“AdWords and Generalized On-line Matching.” Aranyak Mehta, Amin Saberi, Umesh V Vazirani, Vijay V Vazirani. Jornal of the ACM (2007) vol. 54 (5).

3. on July 22, 2009 at 4:24 pm | Reply Someone

I do not know what you mean by “bidders are gross substitutes”. But the algorithm does NOT work when items are gross substitutes. You need more sophisticated algorithms when items are gross substitutes – see Gul and Stacchetti (2000), who generalize the “exact auction” (based on the idea of overdemanded items) in DGS.

4. […] Auction Algorithm for Bipartite Matching « Algorithmic Game […]

5. on February 23, 2010 at 11:08 pm | Reply sifta

Actually, Bertsekas has a 1979 reference for the auction algorithm (LIDS Working Paper).

[Ber79] Bertsekas, D. P., 1979. “A Distributed Algorithm for the Assignment Problem,” Lab. for Information and Decision Systems Working Paper, M.I.T., Cambridge, MA.

Click to access Orig_Auction.pdf

6. on July 15, 2010 at 6:06 am | Reply killing games

can you please teach me algorthm about AI games

thanks
killing games

7. Good and Bad Social Technology…

I found your entry interesting thus I’ve added a Trackback to it on my weblog :)…

8. on January 11, 2011 at 4:37 pm | Reply Unreal Name

🙂
This will certainly help me in a future endeavour of mine.

9. on March 3, 2011 at 8:48 pm | Reply Rencontres

But the algorithm does work when items are gross substitutes. maybe

10. on December 12, 2012 at 12:16 am | Reply Mae

Thanks , I’ve just been looking for info about this topic for ages and yours is the greatest I’ve discovered so far.
However, what in regards to the conclusion? Are you
positive concerning the supply?

11. on May 3, 2013 at 5:03 am | Reply Damion

I’m not that much of a online reader to be honest but your sites
really nice, keep it up! I’ll go ahead and bookmark your site to come back later. All the best

12. on May 5, 2013 at 3:58 am | Reply OSMAX-55HZ HYPER

Pretty nice post. I just stumbled upon your blog and
wished to say that I have truly enjoyed browsing your
blog posts. After all I’ll be subscribing to your feed and I hope you write again very soon!

13. on May 5, 2013 at 5:24 am | Reply http://www.youtube.com/watch?v=UFzC2di3ciU

Hi would you mind stating which blog platform you’re working with? I’m looking to start my own
blog soon but I’m having a hard time deciding between BlogEngine/Wordpress/B2evolution and Drupal. The reason I ask is because your design and style seems different then most blogs and I’m looking for something unique.
P.S My apologies for being off-topic but I had to ask!

14. on May 6, 2013 at 11:29 pm | Reply Clyde

Its like you read my mind! You appear to know so much about this, like you wrote the book in it or something.
I think that you could do with some pics to drive the message home a little bit, but instead
of that, this is wonderful blog. A great read. I will certainly be back.

15. on May 7, 2013 at 7:53 pm | Reply Path of Exile Commentary

Hello There. I found your blog using msn.
This is a really well written article. I’ll make sure to bookmark it and return to read more of your useful information. Thanks for the post. I will definitely comeback.

16. on May 9, 2013 at 3:54 pm | Reply Ingrid

It is appropriate time to make a few plans for
the future and it is time to be happy. I’ve learn this submit and if I could I desire to suggest you few attention-grabbing issues or advice. Perhaps you can write next articles referring to this article. I wish to learn even more issues about it!

17. on May 15, 2013 at 10:15 pm | Reply Minecraft

Good day! This is my first visit to your blog! We are a collection of volunteers and
starting a new project in a community in the same niche.
Your blog provided us useful information to work on. You have done a outstanding job!

18. on May 16, 2013 at 12:18 am | Reply how to hack an email

Good day I am so grateful I found your website, I really found you by accident, while I was
searching on Google for something else, Nonetheless I am here now and would just like to say cheers
for a tremendous post and a all round thrilling blog (I also love
the theme/design), I don’t have time to look over it all at the minute but I have saved it and also included
your RSS feeds, so when I have time I will be back to read a lot more, Please do keep up the
great jo.

19. on May 26, 2013 at 9:14 am | Reply prodazhba na gobleni

Hi, I think your blog might be having browser compatibility issues.
When I look at your website in Opera, it looks fine but when opening
in Internet Explorer, it has some overlapping.
I just wanted to give you a quick heads up! Other then that, very good
blog!

20. on July 16, 2013 at 6:51 am | Reply video poker

Excelllent post I’m a huge slots player from Germany

21. […] found some algorithms that may be solution for my problem. First is Hungarian algorithm, second is Auction Algorithm. This is my first contact with linear programming… I understand how Hungarian algorithm […]

22. […] In graph theory, the Hungarian algorithm by Kuhn produces a matching in polynomial time maximizing the total weight of the edges. Independently, Bertsekas from operations research and Demange, Gale, and Sotomayor from the economics perspective both use an underlying auction to solve the same problem. The auction provides additional intuition for this problem not transparent when using only graph-theoretic techniques. Here we describe a simple auction algorithm, largely following the presentation from this blog post. […]

23. on February 8, 2017 at 1:32 am | Reply Thomas saisonnier

Avis bien pensé. J’ai découvert par hasard ce blog et vais continuer à le lire !

24. on May 12, 2017 at 12:48 pm | Reply genericiowed

Opinioni ipertrofia disfunzione cialis sildenafilo prostatica e comprare senza ricetta in farmacia online erettile

25. on August 29, 2017 at 4:06 pm | Reply Nice PHP Scripts

Thought I would comment and say great theme, did you make it for yourself? It’s really superb!

26. […] biết đến thuật toán này do tình cờ đọc được trên một bài viết trên blog Algorithmic Game Theory. Bài viết gốc hơi ngăn gọn súc tích quá, nên bài này mình viết lại và thêm […]

27. […] Giải thuật đấu thầu cho bài toán cặp ghép trong đồ thị hai phía. Mặc dù giải thuật được phát triển đã lâu nhưng giờ mình mới biết đến. Một giải thuật rất đẹp, mình đã viết lại bằng tiếng Việt tại đây. https://agtb.wordpress.com/2009/07/13/auction-algorithm-for-bipartite-matching/ […]

28. on September 11, 2018 at 8:34 am | Reply Alternative

Alex , Algorithm , Allows , Ally , Alt textual content Tags on pictures , Alternate , Alternative , Alternatives , Altova , Always ,