پیچیدگی های جدید در مورد تعادل نش
|کد مقاله||سال انتشار||مقاله انگلیسی||ترجمه فارسی||تعداد کلمات|
|79539||2008||21 صفحه PDF||سفارش دهید||13083 کلمه|
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : Games and Economic Behavior, Volume 63, Issue 2, July 2008, Pages 621–641
We provide a single reduction that demonstrates that in normal-form games: (1) it is NPNP-complete to determine whether Nash equilibria with certain natural properties exist (these results are similar to those obtained by Gilboa and Zemel [Gilboa, I., Zemel, E., 1989. Nash and correlated equilibria: Some complexity considerations. Games Econ. Behav. 1, 80–93]), (2) more significantly, the problems of maximizing certain properties of a Nash equilibrium are inapproximable (unless P=NPP=NP), and (3) it is #P#P-hard to count the Nash equilibria. We also show that determining whether a pure-strategy Bayes–Nash equilibrium exists in a Bayesian game is NPNP-complete, and that determining whether a pure-strategy Nash equilibrium exists in a Markov (stochastic) game is PSPACEPSPACE-hard even if the game is unobserved (and that this remains NPNP-hard if the game has finite length). All of our hardness results hold even if there are only two players and the game is symmetric.