کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4951142 | 1441193 | 2017 | 41 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Query complexity of approximate equilibria in anonymous games
ترجمه فارسی عنوان
پیچیدگی پرس و جو از تعادل تقریبی در بازی های ناشناس
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم ها، پیچیدگی محاسباتی، نظریه بازی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We study the computation of Nash equilibria of anonymous games, via algorithms that use adaptive queries to a game's payoff function. We show that exact equilibria cannot be found via query-efficient algorithms, and exhibit a two-strategy, 3-player anonymous game whose exact equilibria require irrational numbers. We obtain positive results for known sub-classes of anonymous games. Our main result is a new randomized query-efficient algorithm for approximate equilibria of two-strategy anonymous games that improves on the running time of previous algorithms. It is the first to obtain an inverse polynomial approximation in poly-time, and yields an efficient polynomial-time approximation scheme.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 90, December 2017, Pages 80-98
Journal: Journal of Computer and System Sciences - Volume 90, December 2017, Pages 80-98
نویسندگان
Paul W. Goldberg, Stefano Turchetta,