Game theory is the formal study of conflict and cooperation, and it has become a cornerstone of economic theory. Algorithmic Game Theory combines algorithmic thinking with game-theoretic concepts. It is inherently interdisciplinary, sitting at the interface of mathematics, economics, computer science, and operations research.

The internet has been responsible for much of the recent explosion in research in algorithmic game theory. A defining characteristic of the internet is that it was not designed centrally, but emerged from the interaction of many economic agents, such as network operators, service providers, and users, in varying degrees of competition and collaboration.

Topics in which DIMAP has particular expertise include:

• Algorithms for computing equilibria in games and markets
• Computational auctions and mechanism design
• Network and routing games
• Games and logic, in particular for model checking and verification of systems

DIMAP has also organized a DIMAP Workshop on Algorithmic Game Theory 2007, which was one of the major conferences in this field, attracting a number of distinguished researchers working in this area.

Sample publications:

• M. Jurdziński, M. Paterson, and U. Zwick. A Deterministic Subexponential Algorithm for Solving Parity Games. SIAM Journal on Computing, 38(4): 1519 - 1532, 2008.
• A. Czumaj and B. Vöcking. Tight Bounds for Worst-Case Equilibria. ACM Transactions on Algorithms, 3(1), February 2007.
• R. Beier, A. Czumaj, P. Krysta, and B. Vöcking. Computing Equilibria for a Service Provider Game with (Im)perfect Information. ACM Transactions on Algorithms , 2(4): 679 - 706, 2006.
• R. Savani and B. von Stengel. Hard-to-Solve Bimatrix Games. Econometrica, 74(2): 397-429, March 2006.
• S. Fischer, B. Vöcking, and H. Räcke. Fast Convergence to Wardrop Equilibria by Adaptive Sampling Methods. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC'06), 653 - 662, 2006.

---

More complete list of publications:

• D. Avis, G. Rosenberg, R. Savani, and B. von Stengel. Enumeration of Nash Equilibria for Two-Player Games. Economic Theory, to appear.
• H. Aziz, O. Lachish, M. Paterson, and R. Savani. Wiretapping: the Nucleolus of Connectivity. Submitted 2009.
• H. Aziz, O. Lachish, M. Paterson, and R. Savani. Power Indices for Connectivity Games. In Proceedings of the Algorithmic Aspects in Information and Management (AAIM'09), accepted.
• H. Aziz and M. Paterson. False Name Manipulations in Weighted Voting Games: Splitting, Merging and Annexation. In Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS'09).
• M. Jurdziński, R. Lazic, and M. Rutkowski. Average-Price-per-Reward Games on Hybrid Automata with Strong Resets. In 10th International Conference on Verification, Model Checking, and Abstract Interpretation (VMCAI'09), 167 - 181, 2009.
• M. Jurdziński. Algorithms for Solving Infinite Games. Invited presentation at the 35th Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'09), 46 - 48, 2008.
• M. Jurdziński and A. Trivedi. Average-Time Games. In Proceedings of the Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 08), 2008.
• H. Aziz. Complexity of Comparison of Influence of Players in Simple Games. In Proceedings of the 2nd International Workshop on Computational Social Choice (COMSOC'08), 61 - 72, 2008.
• H. Aziz and M. Paterson. Complexity of Some Aspects of Control and Manipulation in Weighted Voting Games. Annales du Lamsade, 9: 1 - 16, October 2008.
• B. Chen , X. Chen, and X.-D. Hu. The Price of Atomic Selfish Ring Routing. Journal of Combinatorial Optimization, 2008.
• M. Englert , T. Franke, and L. Olbrich. Sensitivity of Wardrop Equilibria. In Proceedings of the 1st International Symposium on Algorithmic Game Theory (SAGT'08), 158 - 169, 2008.
• M. Jurdziński, M. Paterson, and U. Zwick. A Deterministic Subexponential Algorithm for Solving Parity Games. SIAM Journal on Computing, 38(4): 1519 - 1532, 2008.
• M. Jurdziński and R. Savani. A Simple P-matrix Linear Complementarity Problem for Discounted Games. In Proceedings of Computability in Europe, Logic and Theory of Algorithms, (CiE 2008), 283 - 293, 2008.
• M. Jurdziński and A. Trivedi. Reachability-Time Games on Timed Automata. In Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP'07), 838 - 849, 2007.
• A. Czumaj and B. Vöcking. Tight Bounds for Worst-Case Equilibria. ACM Transactions on Algorithms, 3(1), February 2007.
• R. Beier, A. Czumaj, P. Krysta, and B. Vöcking. Computing Equilibria for a Service Provider Game with (Im)perfect Information. ACM Transactions on Algorithms , 2(4): 679 - 706, 2006.
• R. Savani and B. von Stengel. Hard-to-Solve Bimatrix Games. Econometrica, 74(2): 397-429, March 2006.
• S. Fischer, B. Vöcking, and H. Räcke. Fast Convergence to Wardrop Equilibria by Adaptive Sampling Methods. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC'06), 653 - 662, 2006.
• K. Chatterjee, T. A. Henzinger, and M. Jurdziński. Mean-payoff Parity Games. In Proceedings of 20th Annual IEEE Symposium on Logic in Computer Science (LICS'05), 178 - 187, 2005.
• A. Czumaj. Selfish Routing on the Internet. Chapter 42 in Handbook of Scheduling: Algorithms, Models, and Performance Analysis, edited by J. Leung, CRC Press, Boca Raton, FL, 2004.
• R. Savani and B. von Stengel. Exponentially Many Steps for Finding a Nash Equilibrium in a Bimatrix Game. In Proceedings 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), 258 - 267, 2004.
• K. Chatterjee, M. Jurdziński, and R. Majumdar. On Nash Equilibria in Stochastic Games. In Proceedings of 13th Annual Conference of the European Association for Computer Science Logic (CSL'04), September 2004.
• A. Czumaj and A. Ronen. On the Expected Payment of Mechanisms for Task Allocation. In Proceedings of the 23rd Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC'04), 98 - 106, 2004.
• K. Chatterjee, T. A. Henzinger, and M. Jurdziński. Quantitative stochastic parity games. In Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA'04), January 2004.
• K. Chatterjee, T. A. Henzinger, and M. Jurdziński. Simple Stochastic Parity Games. In Proceedings of 12th Annual Conference of the European Association for Computer Science Logic (CSL'03), 100 - 113, August 2003.
• A. Czumaj, P. Krysta, and B. Vöcking. Selfish Traffic Allocation for Server Farms. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC'02), 287 - 296, 2002.
• M. Jurdziński and J. Vöge. M. Jurdziński. A discrete strategy improvement algorithm for solving parity games. In Proceedings of 12th International Conference on Computer Aided Verification (CAV'00), 202 - 215, 2000.
• M. Jurdziński. Deciding the Winner in Parity Games is in UP and co-UP. Information Processing Letters, 68(3):119 - 124, November 1998.
• U. Zwick and M. S. Paterson. The Complexity of Mean Payoff Games on Graphs. Theoretical Computer Science, 158(1&2): 343 - 359, 1996.