Computing equilibria: a computational complexity perspective (Q847807): Difference between revisions

With the development of information technology and computer science, we have a great possibility to solve certain hard optimization problems. Because of this there has been a tremendous growth in the field of approximation algorithms, heuristics and metaheuristics. Before using them, it is important to study computational complexity of a considered problem. This survey explains how complexity theory defines ``hard problems'' and illustrates this definition applying these concepts to several equilibrium problems from game theory. At the end, the discussion regarding implications for the choice how to solve the problem is presented.