ACM SIGACT Presents Gödel Prize for Research that Illuminated Effects of Selfish Internet Use

acm
Association for Computing Machinery
Advancing Computing as a Science & Profession

Contacts:

 

Lance Fortnow				Virginia Gold
ACM SIGACT Chair				ACM
847-579-9310				212-626-0505
[email protected]				[email protected]

Printable PDF file

 

NEW YORK, May 16, 2012 – ACM's Special Interest Group on Algorithms and Computation Theory (SIGACT) together with the European Association for Theoretical Computer Science (EATCS) will recognize three groups of researchers for their contributions to understanding how selfish behavior by users and service providers impacts the behavior of the Internet and other complex computational systems.  The papers were presented by Elias Koutsoupias and Christos H. Papadimitriou, Tim Roughgarden and Éva Tardos, and Noam Nisan and Amir Ronen.  They will receive the 2012 Gödel Prize, sponsored jointly by SIGACT and EATCS for outstanding papers in theoretical computer science at the International Colloquium on Automata, Languages and Programming (ICALP), July 9–13, in Warwick, UK.

In their paper "Worst-case Equilibira," Koutsoupias and Papadimitriou introduced the "price of anarchy" concept, a measure of the extent to which competition approximates cooperation.  It quantifies how much behavior is lost due to selfish behaviors on the Internet, which operates without a system designer or monitor striving to achieve the “social optimum.”   Their research examines how much performance is lost due to these selfish behaviors by Internet users and service providers who act in their own interest.  Their answer, surprisingly often, is "not that much."

Roughgarden and Tardos revealed the power and depth of the "price of anarchy" concept as it applies to routing traffic in large-scale communications networks to optimize the performance of a congested network. Their paper "How Bad Is Selfish Routing?" revisits an old conundrum in transportation science known as "Braess's paradox," and provides remarkably complete results on the relationship between centralized optimization and selfish routing in network traffic.

Nisan and Ronen coined the term "algorithmic mechanism design" in their paper of the same title, presenting a whole new range of applications of the theory of mechanism design within computer science. Combining ideas from economics and game theory with concepts and techniques from computer science, they enriched both mechanism design and the theories of algorithms and complexity.

Elias Koutsoupias is a Professor of Computer Science at the University of Athens, and has held professorships at the University of California, Los Angeles (UCLA).  He is associate editor of Journal of Computer and Systems Science (JCSS).  He earned a B.S. degree in Electrical Engineering from the National Technical University of Athens, and a Ph.D. in Computer Science from the University of California in San Diego (UCSD).

Christos H. Papadimitriou is the C. Lester Hogan Professor of Electrical Engineering and Computer Science at the University of California, Berkeley.  He previously taught at Harvard University, Massachusetts Institute of Technology, the National Technical University of Athens, Stanford University, and the University of California, San Diego. He authored Computational Complexity, one of the most widely used textbooks in the field.  He co-authored the undergraduate textbook Algorithms, and the graphic novel Logicomix, which has been translated into 25 languages.  He also wrote a novel about computation titled Turing.  A recipient of the ACM SIGACT Knuth Award, he is a member of the National Academies of Science and Engineering.  He earned a B.S. from the National Technical University of Athens, a M.S. from Princeton University, and a Ph.D. from UC Berkeley.

Tim Roughgarden is an Associate Professor at Stanford University. He wrote Selfish Routing and The Price of Anarchy and co-edited Algorithmic Game Theory.  He received the ACM Doctoral Dissertation Award (Honorable Mention), and the 2003 Tucker Prize from the Mathematical Optimization Society.  A recipient of the ACM Grace Murray Hopper Award, he also won an honorable mention for the ACM Doctoral Dissertation Award. He received B.S. and M.S. degrees from Stanford, and a Ph.D. degree from Cornell University.

Éva Tardos is the Jacob Gould Schurman Professor of Computer Science at Cornell University. She received a Dipl.Math. and a Ph.D. degree at Eötvös University in Budapest, Hungary, and has held teaching positions at Eötvös and Massachusetts Institute of Technology.  She coauthored Algorithm Design and co-edited Algorithmic Game Theory. A member of the National Academy of Engineering and the American Academy of Arts and Sciences, she is an ACM Fellow. She received the Dantzig Prize, presented by the Mathematical Optimization Society and the Society for Industrial and Applied Mathematics (SIAM). She was also awarded the Fulkerson Prize, sponsored jointly by the Mathematical Programming Society and the American Mathematical Society. She is editor of Journal of the ACM.

Noam Nisan is a Professor of Computer Science and a member of the Center for Rationality at the Hebrew University of Jerusalem. He is the co-author of Communication Complexity and co-edited Algorithmic Game Theory.  He is the recipient of an ACM Doctoral Dissertation Series Award, and the Michael Bruno Memorial Award from the Rothschild Foundation.  He received a B.Sc. degree from the Hebrew University and a Ph.D. degree from the University of California, Berkeley.  

Amir Ronen is a research staff member at IBM Research in Haifa, Israel. A post-doctoral research fellow at Stanford University and the University of California, Berkeley, he became a Senior Lecturer (Assistant Professor) in the Industrial Engineering and Management Faculty at the Technion - Israel Institute of Technology. A recipient of the Wolf Prize from the Wolf Foundation in Israel, he and Nisan were awarded the Best Paper Prize from the International Joint Conferences Artificial Intelligence (IJCAI) and the Journal of Artificial Intelligence Research (JAIR). He earned B.Sc., M.Sc., and Ph.D. degrees from the Hebrew University of Jerusalem.  

The Gödel Prize includes an award of $5,000, and is named in honor of Kurt Gödel, who was born in Austria-Hungary (now the Czech Republic) in 1906.  Gödel's work has had immense impact upon scientific and philosophical thinking in the 20th century. The award recognizes his major contributions to mathematical logic and the foundations of computer science.

About ACM
ACM, the Association for Computing Machinery www.acm.org, is the world’s largest educational and scientific computing society, uniting computing educators, researchers and professionals to inspire dialogue, share resources and address the field’s challenges. ACM strengthens the computing profession’s collective voice through strong leadership, promotion of the highest standards, and recognition of technical excellence. ACM supports the professional growth of its members by providing opportunities for life-long learning, career development, and professional networking.  
 
About SIGACT
The ACM Special Interest Group on Algorithms and Computation Theory http://sigact.acm.org fosters and promotes the discovery and dissemination of high quality research in the domain of theoretical computer science.  The field includes algorithms, data structures, complexity theory, distributed computation, parallel computation, VLSI, machine learning, computational biology, computational geometry, information theory, cryptography, quantum computation, computational number theory and algebra, program semantics and verification, automata theory, and the study of randomness. Work in this field is often distinguished by its emphasis on mathematical technique and rigor.

About EATCS
The European Association for Theoretical Computer Science http://eatcs.org is an international organization aimed at promoting research in the wide field of the foundations of computer science (ranging from formal languages, abstract computation models, algorithm design and complexity analysis, to applications of logic and semantics in programming).  It facilitates the exchange of ideas and results among computer scientists, in particular through the organization of the annual International Conference on Automata, Languages and Programming (ICALP).