Applications of Matching
In class we’ve seen how to use bipartite matching to solve the issue of buyer and seller markets. We’re able to generate a set of market clearing prices which ensures that all buyers want to make a purchase, while also maximizing revenue for the sellers. This in and of itself is a wonderful application of bipartite matching. But what about when we’re a seller with a product and we don’t know about all of the possible buyers before we need to start making decisions about who to sell to. This type of problem is known as an “online” problem and is characterized by having requests for which a decision has to be made, without knowing what the rest of the requests will be. Thus, as a seller, we have to match a buyer to a product we’re selling in an attempt to maximize revenue. This is exactly what the sourced paper discusses. Building upon previous work by Karp and others, they produce a 1-1/e competitive online matching algorithm for maximizing adword revenue. But what exactly does this mean?
First, they present the nature of the problem. We have the “offline” side of the algorithm which represents the set of buyers and their bids on certain items as well as their budget. We know this at initialization. Then we have the “online” side which represents an incoming set of requests which are the words for which the seller can sell ads for. The static version of this problem it what we’ve seen at work in class. Simply increase prices where we have a restricted set of buyers until we have a set of market clearing prices. But we can’t do that here; we have to make a decision about the price we’ll charge for each request as soon as we have it. Thus, there is a rather complex algorithm embedded in this paper which I’ll leave to the intrigued reader to understand. For the purposes of this discussion we’ll focus on other ramifications of tackling this problem (and not the beauty of algorithms).
First, we note that this is an interesting extension of the matching problem. We observe that the authors take their algorithm farther by generalizing to even more realistic situations such as a bidder only paying if a user actually clicks on their ad, second price auctioning, and allowing advertisers themselves to come on and offline. I think this is a great example of how for every problem, we see many different intricacies that appear in the real world. Furthermore, the authors of their paper note that with some basic ML and statistical aid, they hope the algorithm will be able to perform much better than the worst case.. They also observe their method is somewhat resilient to some of the inherent problems with sealed second price bidding by taking down “ghost bidders”. It’s great to see these different examples of matching and auctions in the form of this single problem.
Now, we really see that this is an application of something that may seem purely academic to something that is actually very important to the real world. The paper states that across 3 months in late 2004 over a billion dollars was generated in ad revenue. The naive greedy solution to this problem achieves a 1/2 competitive ratio, while the solutions presented by the authors achieve a 1-1/e competitive ratio which results in a worst case improvement of over 100 million dollars for this 3 month period. Now fast forward to the most recent data I can find which states a revenue of 28 billion dollars in 2010. The difference between the naive solution and the improved algorithm is billions of dollars for the year. This is clearly a pretty big improvement.
Thus, in a couple of different ways, we can see a direct and interesting, albeit more complex, application of some of the concepts we learned in class. Honestly, I think that’s great.
Source: http://www.stanford.edu/~saberi/adwords.pdf
– Acerbus Hospes