Advertisement
Published in:
2010 | OriginalPaper | Chapter
Computation of Equilibria and Stable Solutions
Author : Mihalis Yannakakis
Published in: Stabilization, Safety, and Security of Distributed Systems
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Many models from a variety of areas involve the computation of an equilibrium or stable solution of some kind. Examples include Nash equilibria in games; price equilibria in markets; optimal strategies and the values of competitive dynamic games (stochastic and other games); stable configurations of neural networks; analysis of stochastic models like branching processes and recursive Markov chains. It is not known whether these problems can be solved in polynomial time. Despite their broad diversity, there are certain common computational principles that underlie different types of equilibria and connect many of these problems to each other. In this talk we will discuss some of these common principles, the corresponding complexity classes that capture them, and their relationship with other open questions in computation.