Algorithms for Economic Environments

The student will first investigate the literature and techniques on a few different, important, modern computational problems in the area of algorithmic game theory, including the computation of pure or mixed Nash equilibria in potential games, truthful mechanisms for facility location, and problems in fair allocation, namely cake-cutting and consensus halving. Furthermore, the student will try to bring knowledge from his strong background in discrete mathematics and combinatorics, to identify possible connections and parallels with total-search problems (i.e., related to the complexity class TFNP) induced by existence results in extremal combinatorics, graph theory, and number theory.

After this initial stage, the student is expected to focus on a selection of two specific sub-problems, and make novel contributions regarding their computational complexity, proving both positive (i.e., algorithmic efficiency under meaningful model assumptions) and negative (i.e., formal classification in appropriate complexity classes) results.