Reducibility Among Fractional Stability Problems

Details Reducibility Among Fractional Stability Problems Reducibility Among Fractional Stability Problems

2009-04-08

arxiv.org/abs/0904.1435v1

Computer Science

Computational Complexity

Scientific paper

In this paper, 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) [21] - Internet routing; Core of Balanced Games [41] - Economics and Game theory; Scarf's Lemma [41] - Combinatorics; Hypergraph Matching [1]- Social Choice and Preference Systems; Fractional Bounded Budget Connection Games (FBBC) [30] - Social networks; and Strong Fractional Kernel [2]- 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.

Affiliated with

Also associated with

No associations

Rating

Reducibility Among Fractional Stability Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Reducibility Among Fractional Stability Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reducibility Among Fractional Stability Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-407960