Dueling algorithms

Mar 18, 2011 by Larry Hardesty
Ankur Moitra, a PhD student in the Computer Science and Artificial Intelligence Laboratory. Photo: Patrick Gillooly

There's an old joke about two hikers on a trail, one wearing hiking boots and the other running shoes. "Why the running shoes?” the first hiker asks. "In case of bears,” the second answers. The first hiker laughs and says, "Running shoes won’t help you outrun a bear." "I don’t need to beat the bear," the second hiker says. "I just need to beat you."

When computer scientists design algorithms, they’re generally concerned with providing the best possible answer in the shortest amount of time. But for a web company in a competitive market, the best algorithm might just be the one that beats the other guy. At the Association for Computing Machinery’s 43rd Annual Symposium on Theory of Computing in June, Ankur Moitra, a PhD student in the Computer Science and Artificial Intelligence Laboratory, and colleagues will present a new mathematical framework for analyzing such “dueling algorithms.” The work could help answer questions such as when competition between web services helps meet social ends and when it undermines them, and it could also prove useful in the social sciences.

To understand the idea of dueling algorithms, Moitra says, consider a ranking the results of a query. The words of the query could be subject to multiple interpretations: “Cambridge,” for instance, could refer to several different cities. Suppose that in using a given search term, 40 percent of people mean one thing, 30 percent a second and 30 percent a third. A computer scientist designing a search algorithm in the abstract would probably prioritize the most likely interpretation. But in a commercial market, if that’s what the leading search engine does, a competitor might do well to prioritize the other two. Forty percent of its customers will be disappointed, but the other 60 percent will prefer the results they get to those provided by the market leader.

Of course, the leader is unlikely to sit idle as the upstart steals its business. So it might evolve some hybrid ranking strategy, sprinkling some of the less likely interpretations among its top results. That, in turn, would prompt the competitors to revise their strategies, which would prompt another revision from the leader, and so on. Ultimately, the theory goes, the competitors in the market will converge on what economists call an equilibrium, a state in which no competitor has any incentive to change its strategy unilaterally. Any given contest could have many equilibria; which one emerges depends on how the contestants’ strategies evolve over time.

Balance of power

Moitra and his colleagues at Northwestern University, the University of Toronto, the University of Pennsylvania, Israel’s Technion and Microsoft Research have developed methods for finding equilibrium strategies much more efficiently than was previously possible, at least for two-player, winner-take-all contests. Even these simple contests, however, yield enormously complex calculations. Finding equilibria generally requires comparing all possible strategies against each other. In the search engine example, that would mean comparing every ordering of search results against every other ordering. As the number of results gets larger, the complexity of the comparison increases exponentially.

For several different types of contest, however, Moitra and his colleagues found ways to represent the results of different strategies probabilistically. That makes it much easier to calculate equilibria, but the strategies found to be in equilibrium are defined only by their statistics. So the researchers also had to provide computational methods for finding specific sets of strategies that match the statistical profiles of the equilibrium calculation.

In their paper, the researchers consider several cases of dueling algorithms. Among them are two computers searching for an item in a database, two companies trying to hire employees from the same pool of applicants, and two racers trying to plot routes across a town with erratic traffic patterns. In each case they find that an equilibrium strategy for beating an opponent may not be a good strategy in the abstract: the company may not end up with the best possible employees, for instance, and the computer may not find the item in the database as efficiently as it could.

According to Eva Tardos, Jacob Gould Schurman Professor of Computer Science at Cornell University, the researchers’ paper “is more the beginning of research than a definitive result or end product.” The researchers’ models make several simplifying assumptions — including the number of competitors — that make the math easier but limit their applicability. Nonetheless, “just raising the questions is an important step forward,” Tardos says. “With traditional optimization, you just want the to be as good as possible, versus wanting to beat the opponent. Clearly, there’s a tension between these goals. I think they are setting a research agenda to understand this tension.”


This story is republished courtesy of MIT News (web.mit.edu/newsoffice/), a popular site that covers news about MIT research, innovation and teaching.

Explore further: Instagram launches time-lapse video app for iPhone

More information: arxiv.org/pdf/1101.2883v1

Related Stories

Economic game theory studied by Haas professor

Jan 06, 2011

You are running a political campaign with limited resources. How should you spend your money to beat your rival? You are a military commander trying to win a battle. How should you deploy your soldiers to gain an edge? You ...

Retooling algorithms

Feb 25, 2011

At its most fundamental, computer science is about the search for better algorithms — more efficient ways for computers to do things like sort data or filter noise out of digital signals. But most new ...

Turning reviews into ratings

Feb 03, 2011

The proliferation of websites such as Yelp and CitySearch has made it easy to find local businesses that meet common search criteria -- moderately priced seafood restaurants, for example, within a quarter-mile ...

Recommended for you

SHORE facial analysis spots emotions on Google Glass

16 hours ago

One of the key concerns about facial recognition software has been over privacy. The very idea of having tracking mechanisms as part of an Internet-connected wearable would be likely to upset many privacy ...

Does your computer know how you're feeling?

Aug 22, 2014

Researchers in Bangladesh have designed a computer program that can accurately recognize users' emotional states as much as 87% of the time, depending on the emotion.

User comments : 5

Adjust slider to filter visible comments by rank

Display comments: newest first

Quantum_Conundrum
2.7 / 5 (3) Mar 18, 2011
Capitalism doesn't really "care" about what is "best".

Capitalism only cares about convincing the customer that your product is better long enough to put the competitor out of business.

Sometimes, by neccessity, a capitalistic organisation produces a "better" product or manufacturing process, but capitalism itself, and the associated "consumerism" has little to do with what is actually the "best" thing to do.

Capitalism is primarily concerned with the perceptions of the irrational consumer, not the "real" quality of the product or service.

this is one key reason why capitalism ultimately fails, because eventually you have markets flooded with toys and gimmicks, (see any infomercial or even 90% of online job searches,) and of course governments with out of control spending.

Nobody is "really" concerned about making "better" products. They only want products good enough to out compete the competitor, and then when there are no competitors...
Quantum_Conundrum
2 / 5 (2) Mar 18, 2011
When there are few/no competitors, prices actually go back up, and the quality of the products and services go back down intentionally, because there is no reason for the manufacturer to make an investment in improving the technology. Addtionally, in modern capitalism, there is even a direct incentive for companies to cooperate and make the quality of their products LOWER so that they break down more often and must be replaced more often, thus having more sales and profits for the fat cats.
Cave_Man
not rated yet Mar 18, 2011
Yeah big revelation QC, like anyone with half a brain doesn't already know that capitalism is not perfect. But until you personally come up with a better system you should probably keep quiet.....just a thought.

Oh and I would love to watch you attempt to slice a loaf of bread with a dull knife.
frajo
not rated yet Mar 19, 2011
Oh and I would love to watch you attempt to slice a loaf of bread with a dull knife.
You don't need a knife to eat bread. Ever been in a Mediterranean country?
bloodyanarch
not rated yet Mar 21, 2011
Interesting thought.. I believe the big 3 automakers believed the same. Then came this small little country called Japan and provided a better product. I think the big 3 are still feeling the effects of sitting on their butts for so long. I tunes might be another nice example of soemone coming in and stealing the market. It is a short term focused organization the dosen't try to improve their product and sooner or later they are forced to improve or they go out of business.