Algorithmic Game Theory

Introduction and common usage of decentralized networks such as Internet, as well as advancements in multi-agent technologies

led game theory to be used often in the abstraction of the problems computer scientists encounter. However, the classical theory

of games is mostly a nonalgorithmic theory. The goal of research along this line is to develop new games to model complex agent

interactions we encounter in information systems, as well as providing an algorithmic counterpart to the classical theory of games.

Research in our lab concentrates on network design and routing games as well as design of new solution concepts


Approximation Algorithms

Many interesting combinatorial computational problems are provably intractable. In approximation algorithms research the goal is

to provide polynomial-time algorithms for such optimization problems that return provably good results. Inapproximability research

is an intimately related area, where the goal is to provide theoretical bounds on what can be achieved by approximation algorithms.

Research in our lab concentrates on designing approximation algorithms to various graph problems.


Network Design