The Games Researchers Play

Google is tapping into Israeli expertise in cultivating research into algorithmic game theory at Tel Aviv University, Hebrew University of Jerusalem, and the Technion.

By ZIV HELLMAN
Google in Israel (photo credit: Baz Ratner/Reuters)
Google in Israel
(photo credit: Baz Ratner/Reuters)
GIVEN ISRAEL’S WELL-KNOWN PROWESS IN Internet software development, it is no surprise that Google, the world’s most dominant web-industry company, has for several years had a significant presence in Tel Aviv and Haifa.
Since Israel joined a select list of international sites hosting Google R&D centers, including Zurich, London, Beijing, Moscow and Tokyo, in 2007, it has already contributed to the search engine giant’s success.
Made-in-Israel Google innovations include “Autocomplete,” which gives search results while a user is still typing in a query, and Google ”Insights for Search,” a tool allowing any user to get a glimpse into what large numbers of users are searching for and what their interests are, along with a project digitizing the Dead Sea Scrolls.
Alongside the men and women innovating in software programming and engineering at start-ups throughout the country, Israel has also built up superb academic faculties of theoretic computer science. Google – a company that cultivated ties with academia ever since the original websearch idea that became Google occurred to two Stanford University graduate students, Larry Page and Sergey Brin – is now conducting a program in which it is tapping into the nation’s wealth of academic researchers. And it is casting its net not only in computer science, but also looking to gain from another field in which Israelis have built a formidable international reputation for themselves: the study of game theory.
The web search giant is sponsoring researchers at Tel Aviv University, the Hebrew University of Jerusalem and the Technion in Haifa to conduct over 20 research projects that address issues related to the Internet economy, posing questions touching on the economic effects of viral networking, the dynamics of electronic markets, and new formats of selling and auctioning advertisements that may be beneficial to users and advertisers, according to Google’s press release announcing its new initiative. Aparticular focus will be devoted to the fundamentals of on-line auctions and algorithmic game theory.
The initiative is markedly interdisciplinary, reflecting the large scale and scope of the questions and problems being tackled. The grants are being awarded to researchers in computer science, statistics, mathematics, game theory, artificial intelligence, electrical engineering, industrial engineering, economics, business and operations research. Formal administration of the project is being conducted by Yissum Research Development Company (the technology transfer company of the Hebrew University), Ramot (a similar company of Tel Aviv University), and TRDF Ltd., the Technion Research and Development Foundation.
“This is the first Focused Research Award offered [by Google] in Israel,” says Yossi Matias, managing director of Google’s R&D center in Israel. “It is the first [in the world] in the area of Market Algorithms and Auctions.”
The researchers involved say they are as excited as Google, expecting the contact with the Internet industry – exposing them to its innovations and products along with its challenges and questions – will yield insights into their own research in algorithmic game theory and mechanism design.
“Meeting with Google’s engineers sparks discussions,” says Eyal Winter, Professor of Economics at Hebrew University and director of its Center for the Study of Rationality. “We exchange ideas. We have different perspectives, and that improves the work that we do, for both the academic researchers and the engineers involved.”
BEHIND GOOGLE’S INTENSIVE INTEREST IN CULTIVATING research into algorithmic game theory is its reliance on the auctioning of key-words used in Web search for much of its revenue stream. Advertisers rely on key-words that they have purchased to trigger the ads that users see after they input Web search requests containing those key-words, with the key-words indicating what the user is interested in and therefore which ad is most likely to appeal to him or her.
By auctioning individual key-words, Google seeks to maximize the advertising revenue it can receive from every Web search.
When Google was initially founded in the late 1990s, there were venture capital investors who were wary of backing search engine companies because they questioned where those companies would obtain revenues, given that Web searches were given to users for free. Advertising was an obvious possible source of revenues, but traditional advertising models did not seem to fit the new medium. In print and television advertising, advertisers had long targeted ads by the expected demographic composition of the audience. Advertisers know that the readership of a magazine aimed at young motorcycle enthusiasts is likely to differ significantly from that of, say, a magazine whose content consists mainly of sewing patterns, and therefore tailor their advertising accordingly. Once a demographic is established for a publication or television program, fixed numbers of ads are purchased, with the price charged rising in proportion with the expected size of the targeted audience.
With Web searches, those traditional formulas are generally not implementable.
Purchasing fixed advertisements on a search engine site is unlikely to be effective, because a search engine user may at any given time enter any imaginable word or combination of words in a search query and it is impossible to guess ahead of time what the search will consist of.
Google successfully overcame this challenge with its AdWords program. Under the AdWords system, the words entered into a search query are used to identify the advertisers’ target audience. Advertisers select key-words to trigger their ads and when a user enters the word purchased by an advertiser in a Google search, the relevant ads are shown as “sponsored links” on the right side of the screen or above main search results. The program is so successful that Google’s advertising revenues in 2010 came to some $28 billion.
A significant element of AdWords is that advertisers buy advertisements on Google by submitting bids to an on-line computerized auction running a sophisticated algorithm that determines in real-time the ranking and placement of a particular advertisement. This in turn has generated intense interest in Google in the subject of auctions and ways of maximizing the efficiency and revenue stream generated by auctions.
Auctions have been systematically studied by academics since the 1960s and 1970s. There are several interesting questions that arise immediately once one begins to explore the subject of auctions. For one thing, there are many different ways one can conduct an auction. Bidders may be required to submit sealed bids, not knowing what the others are bidding, or bids can be solicited openly and competitively. Bidders may be charged for the privilege of bidding, or allowed to submit as many different bids as they want for free. A“reserve price” may be announced in advance, with no bids below that price accepted. There are even auctions, known as Dutch auctions, in which the auctioneer begins with a high asking price that is systematically lowered until some participant indicates willingness to pay the last announced price.
How does each such auction structure affect the bidding process and the expected sale price? In which auctions do bidders have the greatest incentives to reveal their “true” private valuations of auctioned items? Which auctions are likeliest to give auctioneers the greatest revenue, and which are optimal from the perspective of potential bidders? These are just some of the most salient questions in the field today.
SOME OF THE INSIGHTS GAINED FROM THE STUDY OF auctions have been so significant for the discipline of economics that Nobel Prizes in economics have been awarded to researchers who devoted a good part of their careers to researching auctions. William Vickrey, for example, who won a Nobel Prize in 1996 only three days prior to his death, pioneered the idea of awarding auction prizes not to the highest bidders, but to the second-highest bidders. Although this strikes many as counter-intuitive, the approach has proven to have many advantages and is implemented by Google’s AdWords, according to papers published by Hal Varian, an economist who works as a consultant for Google.
Other Nobel Prize winners who have worked deeply on auction theory include Roger Myerson and Eric Maskin, who were awarded the prize in 2007. Maskin, a professor at Princeton University’s Institute for Advanced Studies, comes to Israel annually to direct the Jerusalem Summer School in Economics. The co-director of the Summer School is Eyal Winter, who shares with Maskin a specialization in the application of game theory to economics.
Researchers of auctions were led to game theory because the field of game theory is, in a sense, the study of decisions taken interactively by individuals with possibly divergent or even mutually exclusive goals. In an auction, each bidder selfishly seeks to be the exclusive one to win the auctioned item, but at a minimal cost. The optimal bid one should submit, however, depends very much on what the other bidders intend to bid, thus making the circumstances highly interactive.
Game theory was invented to model, in the abstract, such situations of interactive decision making. A “game” in general is a situation in which each player seeks to attain a goal by choosing one action out of several possible actions, but the outcome depends on the choices of all the players – a concise depiction of interactive decision making. The subject has found application in a wide spectrum of fields, ranging from economics, politics and warfare to biology, law and philosophy.
ISRAELHAS BECOME AN INTERNATIONALPOWER-HOUSE in the study of game theory, to such an extent that internationally prominent experts in the field have been known to joke that without learning Hebrew one cannot properly learn the subject. Professor Yisrael (Robert) Aumann of the Hebrew University, one of the legendary figures in the discipline, was awarded the Nobel Prize in Economics in 2005.
Generations of students of his students have filled faculty positions in universities in Israel and abroad. Amajor international conference in the subject is scheduled to be held in Tel Aviv in June.
Alittle over a decade ago, computer scientists began intensely applying concepts from game theory to their discipline. In a sense, this was closing a circuit, because the man who essentially founded the field of game theory, John von Neumann, perhaps the foremost mathematician in the world in the mid-20th century, was also deeply involved in the inauguration of the study of digital computing and algorithms.
Computer science once mainly studied algorithms and software programs running on stand-alone machines. But with the explosive growth of the Internet, looking at strategic interaction became increasingly important to computer scientists. Users competing for access to servers, for example, are in an interactive situation, in which the actions of one user may have implications for the access of another.
E-commerce, online advertising, computerized stock trading, on-line auctions and social networks, to name only a handful of innovations that have appeared relatively recently in computer
eco-systems, spurred further interest in computer interactions, to say nothing of the strategic arms race pitting the creators of malicious computer viruses and Trojan horses against defenders building ever higher firewalls. Algorithms have become the natural environment for strategic decision making in today’s world.
Considerations such as these spawned new fields, such algorithmic game theory and algorithmic mechanism design.
In algorithmic game theory, researchers study how agents finding themselves in strategic situations may efficiently compute optimal strategies, and how the strategies such agents compute for themselves interact to lead to outcomes in the market and on the Web. In algorithmic mechanism design, researchers take a reverse approach: given a socially desired outcome, how can one design the rules underlying a strategic situation in order to give the participants, who are selfishly thinking of their own interests first, incentives to achieve that outcome?
MANY OF THESE STRANDS CAME TOGETHER WHEN Noam Nisan, professor of computer science at the Hebrew University, was on sabbatical leave at Google’s R&D center in Tel Aviv in the years 2007 – 2009. Nisan, who earned his PhD at the University of California at Berkeley, has authored nearly 100 papers and several books in computer science and was a founding pioneer of algorithmic game theory. He is also one of the world’s foremost experts on the subject of on-line auctions.
“The roots of Google’s grant project started when Yishai Mansour [professor of computer science at Tel Aviv University] and I were at Google on sabbatical,” Nisan tells The Report. “We had a very positive experience, and this led us to considering as how we can strengthen the connections between Google and academia, culminating in the first Google-focused research grant in Israel. Computer science studies in Israel are among the best in the world. We consistently score very high in international rankings of computer science faculties.”
The research paid for by Google’s grants will eventually find their way to open publications in scientific journals, leading naturally to the question: What is in it for Google? “The grant deals with fundamentals that touch on some important aspects of the Internet economy and will hopefully lead to a better understanding,” Matias tells The Report. “Interaction and collaboration between Google and the scientific community will hopefully give new insights to all parties. Amore effective Internet economy has global benefit, and in particular benefits users, businesses, Internet companies and - amongst them - Google. I should note also that we encourage publication by our own researchers and engineers for the benefit of the scientific community.”
Nisan explains that there are at least three reasons for Google to pay for research grants. “First of all, Google is actively interested in on-line auctions, from the perspective of its revenues,” he points out. “Advances in research in the subject are of use to them. They will also be of use for other companies, but technological advance is not a zero-sum game.
Second, by strengthening ties with universities, Google is laying the groundwork for a pipeline of future consultants, researchers on sabbatical, and graduating students to work for them. And thirdly, but just as importantly, it is a way to influence the way researchers regard certain problems and think about them.”
The Hebrew University’s Winter agrees with most of this explanation. “Google’s revenues clearly depend on implementing auctions [in an optimal way],” says Winter, “and they clearly hope that by giving these grants the university researchers will lead to more research being conducted on subjects related to problems they are working on.” Winter also points out that the grants are given through the universities to individual researchers to support student work, post-doctoral researchers, and travel to conferences. “It does not go directly into our pockets,” he explains.
Winter, who has authored over 50 scientific papers, has a broad range of academic interests that include microeconomic theory, game theory, incentives in organizations, finance and behavioral economics. Winter tells The Report that as part of the program he attends meetings at Google’s Tel Aviv office once every month or month and a half, in which two lectures are presented, one by a university researcher and one by a Google engineer, which he says always sparks fruitful discussions.
He is excited at the opportunities that being a principal investigator in Google’s program may contribute to his career. “The access to vast amounts of data will lead to some very interesting work,” says Winter.
“Take for example Insights for Search, which gives statistics on distributions on Google search queries. You can check, for example, how often the word “Obama” is searched for. You can get it at any time scale, over minutes, hours, days, or between one date to another date. It can be country or geography specific.”
“Insights for Search was conceived and developed in the Israeli R&D center and provides deep insights into search trends to various users,” says Matias, who is himself a professor of computer science (on leave) at Tel Aviv University and an expert on massive data sets, “from business users interested in particular trends for their marketing or investment decisions, to consumers interested in pop-culture and up to academia, professional analysts and researchers using the data to build statistical and economic models (for predictions). Interesting examples are national banks (like the Bank of Israel) which are using this for real time identification of economic trends that may influence decisions; academic researchers using the data to learn about unemployment and housing trends; and TVshows or news articles seeded from rising trends. Another interesting usage is identification of health related trends, based on corresponding search trends.”
“I have been researching how emotional states affect economic behavior,” says Winter, pointing to one research project of his that will benefit from a Google grant, along with access to Google’s Insights for Search. “There are indications, even at the neurological level, that when people are angered they are more willing to undertake risky behavior, and when they are feeling threatened, or fearful, they are more risk averse. We are seeking evidence for how emotional states influence risk attitudes, by looking at search query trends. If, for example, there is a major terrorist attack in a country, do people conduct fewer searches for ‘casinos’ or ‘bungee.’” Nisan is convinced that the further advances in the study of algorithmic game theory will continue to impact the lives of all of us, even if we are not always directly aware of it. “Algorithmic game theory and online auctions are fields that are already breaking through to the world of applications,” says Nisan. “It may be more difficult to spot than, say, breakthroughs in electronics, but it is there. It affects the way people analyze situations, their perspectives on problems they are trying to solve. It even changes the language that we use to talk about things.”