Reducibility among Fractional Stability Problems

DOI10.1137/120874655zbMath1285.68048arXiv0904.1435OpenAlexW2568879229MaRDI QIDQ5408759

Shiva Kintali, Rajmohan Rajaraman, Laura Poplawski, 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

complexitygame theoryNash equilibriumcoresocial choicekernelseconomicsPPAD-completenesspreference systemsScarf's lemmanetwork connection gamesstable paths problem

Mathematics Subject Classification ID

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

Related Items (9)

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 ⋮ The classes PPA-\(k\): existence from arguments modulo \(k\) ⋮ The classes PPA-\(k\): existence from arguments modulo \(k\) ⋮ On the complexity of stable fractional hypergraph matching ⋮ The Hairy Ball Problem is PPAD-Complete. ⋮ Discrete versions of the KKM lemma and their PPAD-completeness ⋮ The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich

This page was built for publication: Reducibility among Fractional Stability Problems