Reducibility Among Fractional Stability Problems

In a landmark paper, Papadimitriou introduced several syntactic subclasses of the search class TFNP (Total Function Nondeterministic Polynomial) based on proof styles that (unlike TFNP) admit complete problems. One particularly notable subclass of TFNP is PPAD (Polynomial Parity Arguments on Directed graphs), which includes a number of important stability problems, including the celebrated problem of finding Nash equilibria in matrix form games. A recent series of results has culminated in showing that finding Nash equilibria in multi-player games is complete for PPAD.

In this work, we establish the PPAD-completeness of a number of outstanding stability problems that arise in diverse applications, including the following: Fractional Stable Paths Problem (FSPP) -- Internet routing; Core of Balanced Games -- Economics and Game theory; Scarf's Lemma -- Combinatorics; Hypergraph Matching - Social Choice and Preference Systems. In fact, we show that no fully polynomial-time approximation schemes exist for these problems unless PPAD is in FP. In addition to enhancing our repertoire of PPAD-complete problems, we expect the concepts and techniques in this work to find future use in algorithmic game theory.

In the talk, I will motivate the fractional stability problems being studied and will largely focus on the Fractional Stable Paths Problem. I will present two new concepts that play a key role in our completeness reductions -- preference games and personalized equilibria. The talk will be largely self-contained; no significant knowledge of algorithmic game theory will be assumed (joint work with Shiva Kintali, Laura Poplawski, Ravi Sundaram, and Shanghua Teng).

Bio: Rajmohan Rajaraman is a Professor of Computer Science at Northeastern University in Boston. He received his Bachelor's in Computer Science at IIT Kanpur in 1991 and his PhD in Computer Science at the University of Texas at Austin in 1997. He was a postdoctoral fellow at DIMACS before joining the Northeastern faculty in 1998. His research interests include approximation algorithms, algorithmic game theory, distributed computing, and complex networks.