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
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.