Feeds:
Posts

## The Theory of Equilibrium Computation Has Come of Age

Over the last half century, our community has discovered several Chapters from The Book on the theory of algorithms and computational complexity, such as those on randomized algorithms, approximation algorithms, cryptography, and hardness of approximation. (Yes, I agree this sounds Erdosian, but when it comes to our fabulous theory, surely it is justified!)

Spectacular work, much of it done over the last decade, has revealed a new Chapter: on equilibrium computation. The following striking dichotomies, based on these insights, speak for themselves. For the readers’ convenience, all the relevant references have been hyperlinked.

2-Nash k-Nash, k ≥ 3
Nature of solution Rational [1] Algebraic;
irrational example [2]
[4] [5]
FIXP-complete [6]
Practical algorithms Lemke-Howson [1] —?—
Decision version NP-complete [7][8] ETR-complete [9][10]

SPLC utilities PLC utilities
Nature of solution Rational [11][12] Algebraic [12];
irrational example [17]
Complexity PPAD-complete [11] [13] FIXP-complete [14] [15]
Practical algorithms Lemke-based [16] —?—
Decision version NP-complete [11] ETR-complete [14]

SPLC production PLC production
Nature of solution Rational [18] Algebraic [15];
irrational example [18]
Complexity PPAD-complete [18] FIXP-complete [15] [14]
Practical algorithms Lemke-based [18] —?—
Decision version NP-complete [18] ETR-complete [14]

Note: PLC = piecewise-linear concave

SLPC = separable, piecewise-linear concave

In the third table, the utilities of agents are: for all negative results we assume the most restricted utilities, i.e., linear, and for positive results we assume SPLC.

These dichotomies were first identified in [15]. This paper also extends the second and third dichotomies from SPLC to the new class of Leontief-free functions, which properly contains SPLC.