Building a Smarter Planet. A Smarter Planet Blog.

Ever since his grad student days at Hebrew University of Jerusalem, Amir Ronen, now a scientist at IBM Research -  Haifa, has been thinking about the intersection of game theory and computer science. In fact, he’s one of the leaders in a sub-discipline, called algorithmic game theory, which lies at the intersection of the two fields.

Ronen believes that this line of thinking could lead to important breakthroughs that will help us improve everything from transportation systems in cities to environmental protection regimes.  “I’m dreaming of an ultimate game theory engine–a miracle engine that helps us make better decisions,” he says.

He is one of six scientists who recently received the prestigious Godel Prize, which is awarded each year  by the Association for Computing Machinery for academic papers what contribute significantly to scholarship concerning algorithms and computing theory. The ACM cited Ronen and his co-author, Noam Nisan, along with the authors of two other papers, for laying the foundation for growth in algorithmic game theory.

Ronen and Nisan authored the first version of their paper  in 1999, and have developed their theory since then. They coined the term “algorithmic mechanism design” to describe a new way of taking on problems in systems that include self-interested participants.

They explored the fact that glitches arise when people attempt to apply conventional computer science thinking to complex systems like the Internet, utility grids and urban transportation systems. Typically, when people design computing algorithms, they seek to optimize the systems they’re addressing to be as efficient and effective as possible based on their design goals. So far, so good. But problems emerge when they approach systems operating in the world as if they’re going to behave like computing systems, which follow the rules that are written for them. Every social, business or economic system includes individuals and organizations that have their own self-interests in mind when they interact with the system. ” Instead of simply acting as instructed,” Ronen says, “such entities are likely to take advantage of quirks in the solution and utilize them on their own behalf. And That kind of behavior can undermine the solution.”

Consider a transportation scenario. A city with severe automobile traffic problems decides to design a congestion pricing system to change the behavior of individual drivers and reduce traffic jams. The city leaders set up a new tolling system in an effort to discourage truckers and non-commuters from driving on major highways during rush hours. But, as a result, drivers in large numbers leave the major arteries to avoid tolls–bringing traffic on city streets to a standstill.

The theory of algorithmic mechanism design aims to provide mathematical tools for coping with such situations.

Here’s how it works: Game theory aims to evaluate situations in which participants act strategically and create mathematical models that help designers produce solutions that address the diverse interests of the parties involved. When designers combine game theory with computer science, Ronen says, they are better able to write algorithms that take those variables into account. At the same time, machine learning, a branch of computer science, has the potential to make game theory models produce more accurate predictions of what will happen in real-world situations.  Machine learning makes it possible for computing systems to become smarter as they encounter additional data.

Ronen cautions that it will take a lot of time and effort to meld computer science and game theory in this way. But he’s hopeful. “You have to work in many small steps, but the potential is huge,” he says.

Technorati Tags: Amir Ronen, Associating for Computing Machinery, IBM