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.

Motivated by publish-subscribe mechanisms in networks, we introduce a new class of multicommodity facility location problems: Multicommodity Group Steiner Facility Location (MGSFL). The input to MGSFL consists of a metric space over a given set of locations, a cost function which provides a building cost for each commodity at each location, a set of clients located at various points in the metric, and the set of commodities that each client is interested in reaching. A solution to MGSFL consists of (a) for each commodity, the locations where facilities are built, and (b) for each client, a tree connecting the client to at least one facility for each commodity in its interest set. The goal is to minimize the sum of the total facility building costs and the metric cost of the client trees. MGSFL is a natural generalization of the well-studied Group Steiner Tree problem, which is equivalent to the special case of MGSFL in which every building cost is either 0 or ∞ and there is only one client. We also note that given the facility locations, the best client tree is an optimal solution to an appropriate Group Steiner Tree instance. Since the Group Steiner Tree problem is hard to approximate to within a factor of Ω(log2–ε m) times optimum unless NP has quasi-polynomial Las Vegas algorithms, where m is the number of commodities, the same hardness result immediately extends to MGSFL. Our main result is a randomized approximation algorithm for MGSFL, where n is the number of clients. We also present deterministic poly-logarithmic approximations for three special cases. We give an O(log n)-approximation algorithm when the facility building costs differ only by commodity, not by location. We present an O(log4 n log m)-approximation algorithm when the interest sets are laminar — i.e., for each pair of clients, either their interest sets do not intersect or else one client's interest set is contained within the other client's interest set. We end with an O(log n)-approximation algorithm when there are no building costs but each commodity must be built exactly once.

In a landmark paper, Papadimitriou introduced a number of syntactic subclasses of TFNP based on proof styles that (unlike TFNP) admit complete problems. A recent series of results has shown that finding Nash equilibria is complete for PPAD, a particularly notable subclass of TFNP. A major goal of this work is to expand the universe of known PPAD-complete 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 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 PPAD is in 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. On a technical note, we wish to highlight our novel "continuous-to-discrete" reduction from exact personalized equilibria to approximate personalized equilibria using a linear program augmented with an exponential number of "min" constraints of a specific form. In addition to enhancing our repertoire of PPAD-complete problems, we expect the concepts and techniques in this paper to find future use in algorithmic game theory.

Motivated by applications in social networks, peer-to-peer and overlay networks, we define and study the Bounded Budget Connection (BBC) game- we have a collection of n players or nodes each of whom has a budget for purchasing links; each link has a cost as well as a length and each node has a set of preference weights for each of the remaining nodes; the objective of each node is to use its budget to buy a set of outgoing links so as to minimize its sum of preference-weighted distances to the remaining nodes. We study the structural and complexity-theoretic properties of pure Nash equilibria in BBC games. We show that determining the existence of a pure Nash equilibrium in general BBC games is NP-hard. We counterbalance this result by considering a natural variant, fractional BBC games- where it is permitted to buy fractions of links- and show that a pure Nash equilibrium always exists in such games. A major focus is the study of (n, k)-uniform BBC games- those in which all link costs, link lengths and preference weights are equal (to 1) and all budgets are equal (to k). We show that a pure Nash equilibrium or stable graph exists for all (n, k)-uniform BBC games and that all stable graphs are essentially fair (i.e. all nodes have similar costs). We provide an explicit construction of a family of stable graphs that spans the spectrum from minimum total social cost to maximum total social cost. To be precise we show that that the price of stability is Θ(1) and the price of anarchy is Ω( n/k) and O( logk n

We design a randomized online algorithm for k-server on binary trees with hierarchical edge lengths, with expected competitive ratio O(log Delta), where Delta is the diameter of the metric. This is one of the first k-server algorithms with competitive ratio poly-logarithmic in the natural problem parameters, and represents substantial progress on the randomized k-server conjecture. Extending the algorithm to trees of higher degree would give a competitive ratio of O(log2 Delta log n) for the k-server problem on general metrics with n points and diameter Delta.