Dueling algorithms

March 18, 2011 by Larry Hardesty

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: Economic game theory studied by Haas professor

Related Stories

Economic game theory studied by Haas professor

January 6, 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

February 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 algorithms are ...

Grant to help researchers build better search engines

November 3, 2010

(PhysOrg.com) -- Two UT Arlington computer science engineering faculty are developing a new Internet search engine that treats the Web more like a massive database.

Turning reviews into ratings

February 3, 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 of a particular ...

New algorithm enables much faster dissemination of information through self-organizing networks

January 11, 2011

As sensors that do things like detect touch and motion in cell phones get smaller, cheaper and more reliable, computer manufacturers are beginning to take seriously the decade-old idea of "smart dust" -- networks of tiny ...

Using mathematics to identify the good guys

October 28, 2010

The Good Samaritan helping an accident victim might really be looking out for himself, argues assistant professor of philosophy and religion Rory Smead.

Recommended for you

Car company offering red light-reading vehicles in Las Vegas

December 7, 2016

On the theory that a driver who knows when a red light will turn green is more relaxed and aware, vehicle manufacturer Audi is unveiling this week in Las Vegas a technology that enables vehicles to "read" traffic signals ...

Solar panels repay their energy 'debt': study

December 6, 2016

The climate-friendly electricity generated by solar panels in the past 40 years has all but cancelled out the polluting energy used to produce them, a study said Tuesday.

Taking back control of an autonomous car affects human steering behavior

December 6, 2016

There you are, cruising down the freeway, listening to some tunes and enjoying the view as your autonomous car zips and swerves through traffic. Then the fun ends and it becomes time take over the wheel. How smooth is that ...

Wall-jumping robot is most vertically agile ever built

December 6, 2016

Roboticists at UC Berkeley have designed a small robot that can leap into the air and then spring off a wall, or perform multiple vertical jumps in a row, resulting in the highest robotic vertical jumping agility ever recorded. ...

Scientists develop robotic hand for people with quadriplegia

December 6, 2016

Scientists have developed a mind-controlled robotic hand that allows people with certain types of spinal injuries to perform everyday tasks such as using a fork or drinking from a cup.

Samsung prevails over Apple in \$399 mn patent appeal (Update 2)

December 6, 2016

The US Supreme Court on Tuesday overturned a \$399 million patent infringement penalty imposed on Samsung for copying Apple's iPhone design, in a case watched for its implications for technology innovation.

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.