Seminar: Complexity in Game Theory
The goal of this seminar is to highlight some of the most interesting questions that arise when looking at game theory through the lens of computational complexity. This is a relatively new and dynamic field of research that has produced some very fundamental and exciting results within the last 15 years.
Participants will have the opportunity to study original research papers at the forefront of this area. More specifically, potential topics will cover (but are not limited to) the following:
- Auction and market theory: how computational complexity can play a role in designing "good" mechanisms.
- Hardness of finding equilibria in games: computational complexity and communication complexity considerations.
- Tractable relaxations of equilibria.
Students will be assigned papers and will be expected to deliver a presentation, demonstrating in-depth understanding of the problem, the key technical ideas and proofs, related bibliography and open questions.
Detailed information will be given at the kick-off meeting (date tba).
Students are expected to have taken courses in algorithmic theory, discrete optimization and/or computational complexity, and be familiar with the notions of optimization problems, polynomial-time algorithms and NP-completeness.
A previous course in (algorithmic) game theory (e.g., MA5226 or IN2239) will be a plus, but it is not essential.