Dueling algorithms
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...