Reducibility among fractional stability problems

DOI10.1137/120874655MaRDI QIDQ5408759zbMATH OpenOpenAlexFDO

Authors Shiva Kintali, Laura Poplawski, Rajmohan Rajaraman, Ravi Sundaram, Shang-Hua Teng

Publication date 11 April 2014

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0904.1435

zbMATH Keywords

game theorycomplexitycoreeconomicsNash equilibriumkernelssocial choicePPAD-completenesspreference systemsScarf's lemmanetwork connection gamesstable paths problem

Mathematics Subject Classification ID

Cooperative games (91A12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Noncooperative games (91A10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Abstract: 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.

Recommendations

• The complexity of computing a Nash equilibrium
• The complexity of equilibria: Hardness results for economies via a correspondence with games
• On the Complexity of Nash Equilibria and Other Fixed Points
• The complexity of computing a Nash equilibrium
• Settling the complexity of computing two-player Nash equilibria

Cited in

(11)

• The classes PPA-\(k\): existence from arguments modulo \(k\)
• The Hairy Ball Problem is PPAD-Complete.
• The complexity of gradient descent: CLS = PPAD pls
• On the complexity of stable fractional hypergraph matching
• Discrete versions of the KKM lemma and their PPAD-completeness
• Pure-circuit: tight inapproximability for PPAD
• The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
• The classes PPA-\(k\): existence from arguments modulo \(k\)
• On the complexity of stable hypergraph matching, stable multicommodity flow and related problems
• Colorful linear programming, Nash equilibrium, and pivots
• The Hairy Ball problem is PPAD-complete

This page was built for publication: Reducibility among fractional stability problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5408759)