دانلود مقاله ISI انگلیسی شماره 79539
عنوان فارسی مقاله

پیچیدگی های جدید در مورد تعادل نش

کد مقاله سال انتشار مقاله انگلیسی ترجمه فارسی تعداد کلمات
79539 2008 21 صفحه PDF سفارش دهید محاسبه نشده
خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.
عنوان انگلیسی
New complexity results about Nash equilibria ☆
منبع

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.

خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.