STINT Box 3523
Tel:08-671 19 90
 In Focus

Infinite adversary games

Published 2000-01-22

In 2003 Dr Sergei Vorobyov, Uppsala University received a STINT Institutional Grant for cooperation with Rutgers University, USA. The annual grant of SEK 300 000 is intended for cooperation Game Theory.

The project is devoted to developing scientific and research cooperation between Information Technology Department of Uppsala University (Sweden) and DIMACS, Center of Discrete Mathematics and Theoretical Computer Science, Rutgers University (USA). The Swedish coordinator of the project is Docent Dr. Sergei Vorobyov. Our DIMACS hosts are Professors Leonid Khachiyan and Endre Boros. DIMACS is a ollaborative project of Rutgers University, Princeton University, AT&T Labs--Research, Bell Labs, NEC Laboratories America and Telcordia Technologies, as well as affiliate members Avaya Labs, HP Labs, IBM Research and Microsoft Research. DIMACS is an NSF Science and Technology Center.

The major research domain of our cooperation is algorithmic and complexity-theoretic study of infinite adversary games pertinent to computer-aided verification. Proving software/hardware correctness may be seen as deciding a winner in the game played between the System and the Environment. The System needs to ensure certain objectives (e.g., absence of deadlocks, liveness), while the Environment may behave randomly, unpredictably, or in the worst imaginable way. Verification amounts to demonstrating that the System wins against any strategy (behavior) of the Environment. If, however, the Environment wins, additional analysis encompasses improvements to the System and its subsequent verification. In practice the described simple scenario relies on the analysis of infinite-duration games on astronomically large graphs representing the states of the System and its interaction with the Environment. Computationally this analysis is extremely challenging. Some graph games are known to be intrinsically computationally infeasible, some are currently not known to be feasible (solvable in low-degree polynomial time). Besides, games on graphs have become an indispensable tool in modern computer science. They provide powerful and expressive models for numerous phenomena and are extensively used in automata theory, logic, complexity theory, computational biology, etc. Not surprisingly, Christos Papadimitriou in his invited address to the 2001 ACM Symposium on Theory of Computing characterized computational problems related to games (such as complexity of computing Nash equilibria in games) as the main challenge to Computer Science of the 21st century. The key to the successful practical applications of games lies in developing efficient algorithms resolving games. As a consequence, theory of algorithms and combinatorial optimization theory are the main instruments for succeeding with this goal.

DIMACS affiliated to Computer Science and Mathematics Departments of Rutgers and Princeton Universities, as well as Princeton Institute for Advanced Study (founded by Albert Einstein), form a particularly stimulating environment for conducting this kind of research. Game theory was started in Princeton by John von Neumann, John Nash and other bright mathematicians. Currently these universities boast the best specialists in the world in algorithms, complexity, combinatorial optimization. Enough to say that our DIMACS host is Leonid Khachiyan, who once made first pages of the major US newspapers with his breakthrough proof of polynomial decidability of Linear Programming.There are many diverse research activities at DIMACS and Princeton, seminars, workshop, interesting lectures by prominent visitors from leading universities. Each our visits brings us new contacts and ideas.

More technically our joint research concerns the identification of the new paradigm of the controlled optimization problems, particularly well-suited to analyzing and developing new game-theoretic algorithms. We introduced and first studied the two fundamental controlled optimization problems, longest-shortest paths and controlled linear programming, capturing the essential features of many graph games, and providing solvability of such games in expected subexponential time.

Our three one-month visits to DIMACS in 2004, with graduate students, allowed to settle several open important game-theoretic problems, to publish several conference and journal papers, technical reports. One PhD thesis - Combinatorial Optimization for Infinite Games on Graphs - of my student Henrik Björklund was finalized at DIMACS during 2004 (defended on February 18, 2005). Besides, one Master Thesis was completed and another one half-finished at DIMACS.

Summarizing, this Institutional grant appeared to be very stimulating and allowed us to make a fast and substantial progress in a competitive and challenging domain of contemporary research in computer science. We are looking forward to further exploring a multitude of new promising ideas which emerged from our research at DIMACS.

Sergei Vorobyov
Information Technology Department
Uppsala University

Senast uppdaterad: 05-08-29 11:19

Welcome to Strategic Grants for Internationalisation Seminar

The seminar March 7th facilitates the sharing of experiences when it comes to strategic international-isation. All people involved in such internationalization are welcome. 

STINT & RJ launch: Sweden-Japan 150 Anniversary Grants

To celebrate the 150-year anniversary of diplomatic relations between Sweden and Japan, the Swedish Foundation for International Cooperation in Research and Higher Education (STINT) and the Swedish Foundation for Humanities and Social Sciences (RJ) launch a special call for applications.

STINT invests 10 MSEK in four strategic internationalisation projects

STINT’s board has decided to invest 10 000 000 SEK in four projects within the Strategic Grants for Internationalisation programme for the time period 2017–2020.

Sweden has three international universities in the top category

STINT Internationalisation Index indicates how international the universities in Sweden are. This year three universities are in the top category of internationalisation. Last year´s prize winner Stockholm School of Economics is now accompanied by Chalmers and KTH.