Reducibility among Fractional Stability Problems

We resolve the computational complexity of a number of outstanding open problems with practical applications. Here is the list of problems we show to be ${\bf{PPAD}}$-complete, along with the domains of practical significance: 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; fractional bounded budget connection games (FBBC)---social networks; and strong fractional kernel---graph theory. In fact, we show that no fully polynomial-time approximation schemes exist (unless ${\bf{PPAD}}$ is in ${\bf{FP}}$). This paper is entirely a series of reductions that build in nontrivial ways on the framework established in previous work. In the course of deriving these reductions, we created two new concepts---preference games and personalized equilibria. The entire set of new reductions can be presented as a lattice with the above problems sandwiched between preference games (at the “easy” end) and personalized equilibria (at the “hard” end). Our completeness results extend to natural approximate versions of most of these problems.