Reducibility among Fractional Stability Problems

DOI10.1109/FOCS.2009.57MaRDI QIDQ5171181zbMATH OpenOpenAlexFDO

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

Publication date 25 July 2014

Published in 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/focs.2009.57

Mathematics Subject Classification ID

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

Cited in

(8)

• Stable multicommodity flows
• Perfect graphs with polynomially computable kernels
• Deciding probabilistic bisimilarity distance one for probabilistic automata
• Equilibrium computation of the Hart and Mas-Colell bargaining model
• \(\mathsf{PPAD}\)-completeness of polyhedral versions of Sperner's lemma
• Constant rank two-player games are PPAD-hard
• The complexity of computing a bisimilarity pseudometric on probabilistic automata
• Bounded budget connection (BBC) games or how to make friends and influence people, on a budget

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 Q5171181)