Prof. Seffi Naor found a way to improve online advertising sales using the auction sales method and achieve impressive results of 75% of the maximum income

Prof. Seffi Naor. 
By: Yisrael Benyamini, From the main
Technion website.
In the strange world of online sales, it doesn’t always pay to sell at the highest price. In order to understand why, let’s imagine a wine merchant who gets two orders: Customer A is interested in purchasing 10 bottles, at most, of Merlot or Cabernet wine and is prepared to pay $100 per bottle. Customer B would like to buy ten bottles, at most, of Merlot wine and is prepared to pay $99 per bottle. The seller checks with his suppliers and finds a bottle of Merlot. He decides to send the bottle to Customer A, who offered the higher price. Later on he finds an additional nine bottles of Merlot and sends them all to Customer A. Only towards the end of the day does the seller find ten bottles of Cabernet – except that now he does not have a customer for them and he ends his day making only $1000 in sales. If he would have sold the Merlot to Customer B and the Cabernet to Customer A, he would have made $1990 that day.
When he made his decision, the merchant could not have known that at the end of the day he would find ten additional bottles. Only after making the sale was it possible to know what decision would have generated the maximum income. Issues about which decisions to make before getting all the information are called online decision problems. In these problems every decision is liable to end up as not optimal in light of information that will be received after making the decision. Regardless of this, according to
Prof. Seffi Naor of the
Computer Science Department at the Technion, there is a way for the merchant to always achieve an income that is at least 63% (more exactly, 11/e »0.632) of the maximum income that he would have been able to get had he had all the information from the start. This number is called the competitive ratio of this method: the ratio between the results of the online method and the best results that in hindsight could have been achieved. Our merchant’s greedy method enabled him to earn $1000 instead of $1990 – in other words, a 50% competitive ratio.
Can’t wait
Some readers may perhaps suggest to the merchant not to immediately give the bottles to the customer and rather wait till the end of the day in order to decide how best to divide the bottles between his customers. This possibility does not exist in the area studied by Prof. Naor: advertising on the Internet through “Public Auction of Search Words”. In this time of advertising situation there is an Internet site on which there are ads (e.g., Google) and a large number of advertisers who want their ad on the site. Every advertiser tells the site which search words he is interested in “purchasing”, what his daily budget is, and how much he is willing to pay per search word. When a web surfer keys in one of these search words, the site presents, alongside the search results, ads that have been chosen from among the advertisers interested in the keyedin search words: this is why this process is called a public auction.
This type of advertising presents the same dilemma that the wine merchant faced: sometimes it pays to choose the advertiser who offered a slightly lower price, so that at the end of the day, you can exploit as much as possible the budget allocated by all the advertisers.
Naor (52) completed his undergraduate studies in computer science at the Technion and his graduate and doctoral studies at Hebrew University of Jerusalem. He thereafter did a postdoctoral fellowship at the University of Southern California and Stanford University and since 1991 has been a faculty member of the Technion’s Computer Science Department. Here he focuses on the field of algorithmic theory, and specifically, on online algorithms, approximation algorithms and algorithmic game theory. Naor worked on the online advertising problem with a former student of his,
Dr. Niv Buchbiner, and
Dr. Kamal Jain, while on sabbatical in
Microsoft’s Research Lab in Redmond, USA. Two years earlier a solution that arrived at the same ratio had already been presented but the new solution is far simpler and can be expanded to additional cases, among which advertisers also compete for the position of their ads on the page.
Good balance
In order to reach a new solution, the researchers used techniques drawn from linear programming. The principle is easy to describe: instead of the greedy method in which every time an ad is supposed to be shown, one looks for the maximum profit that can be made off of it, research showed that it is preferable to choose the advertiser who has the best balance between his remaining budget and the price he is ready to pay for the search word.
If the wine merchant had used this method, he would also have sold the first bottle of Merlot to Customer A, which would have reduced Customer A’s available budget so that the second bottle would have been sold to Customer B, who had a higher available budget. True, in this way the merchant would not have reached the amount that, in retrospect, he could have, but certainly more than he made using his greedy method. If he would have sold five bottles of Merlot to Customer A and five to Customer B, and then found the bottles of Cabernet, he would have been able to sell these to Customer B and his income would have reached $1495: a competitive ratio of 75%. There are cases in which the competitive ratio drops to 63% but never below this.
“The algorithm presented in this research is based on a general method that I developed together with my research student
Niv Buchbinder as part of his doctoral research, for a large group of online decision problems with common features,” says Naor. “The method uses techniques from the field of linear programming in order to create a formula for developing suitable algorithms. The strength of the general method proved itself when we used it to solve problems that had already been studied in the past and we obtained simpler and more efficient algorithms than the ones previously known.”
The frequency capping problem
Lately, Buchbinder and Naor used this method to solve the problem of frequency capping. This is another online decision problem from the field of Internet advertising, which was previously researched together with
Moran Feldman, a doctoral student at the Technion, and
Dr. Arpita Ghosh, from Yahoo!’s Research Center. In this problem, too, an ad has to be chosen such that the income for the website presenting the ad will be as high as possible. The requirement here is more typical of a content website such as a news site.
Content websites show identical pages to a large number of surfers, some of whom visit the site many times throughout the day. Research has shown that after a surfer sees a particular ad a number of times in a short period, he stops paying any attention to it – a phenomenon dubbed “ad blindness”. Consequently, many advertisers prefer to limit the number of times their ad is shown to the same surfer.
It turns out that frequency capping creates situations in which greediness does not pay off. For example, ten advertisers are prepared to pay $1 each time their ad is shown, but their budget is only enough to show one ad each day. Let’s call this group of advertisers “Group A”. Another advertiser is ready to pay $0.99 each time his ad is shown and his budget is large enough to show ten ads per day. However, he demands that if the ad is shown to a certain surfer, it must not be shown to that same surfer again the same day. Let’s call this advertiser “Advertiser B”.
Assume that initially ten different surfers arrive at the site. The greedy method would choose to show all of them one of the ads from the Group A advertisers, given that this group is ready to pay one cent more than Advertiser B. Now assume that at this point a new surfer visits the same page ten times. The first time he visits the page he is shown Advertiser B’s ad, and then the next nine times he will not be shown any ads, given that he has already seen Advertiser B’s ad (and can’t be shown it again on that day) and Group A has already used up its budget. Accordingly, the income on this day is $10.99. If we would have known ahead of time the order in which surfers would visit the page, we would have been able to show Advertiser B’s ad to the first visitors and Group A’s ads to the last ten visitors and earn $19.90 for the day – almost twice as much as the greedy method.
A greedy but smart algorithm
Of course, no site knows ahead of time in what order surfers will arrive at the site: this is an online decision problem that requires site managers to make a decision the moment the surfer arrives at the site. Buchbinder, Feldman, Ghosh and Naor’s paper presented a greedy but smarter algorithm that achieves a ¾ competitive ratio, when all the advertisers are ready to pay the same amount for an ad presentation, and proves that this result is the best possible one. For the general case, using the general method explained above, the researchers developed an algorithm that reaches a 0.63 competitive ratio, and they hypothesize that it is possible to obtain an even better ratio.
To what extent are mathematical theories such as these appropriate for real life situations? “A mathematical solution is the starting point, not the end point,” says Naor. “The real world is more complex that the assumptions on which a mathematical model is based, but algorithms can be expanded to cope with the complexity required for practical use.”