Computing equilibria: a computational complexity perspective (Q847807)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 5673330
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Computing equilibria: a computational complexity perspective |
scientific article; zbMATH DE number 5673330 |
Statements
Computing equilibria: a computational complexity perspective (English)
0 references
19 February 2010
0 references
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.
0 references
computational complexity
0 references
NP-hardness
0 references
NP-completeness
0 references
game theory
0 references
equilibrium computation
0 references
0 references
0.814406156539917
0 references
0.7900895476341248
0 references
0.7890737056732178
0 references
0.7882103323936462
0 references
0.7880812287330627
0 references
