کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5071913 | 1477074 | 2014 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the communication complexity of approximate Nash equilibria
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
علوم انسانی و اجتماعی
اقتصاد، اقتصادسنجی و امور مالی
اقتصاد و اقتصادسنجی
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We study the problem of computing approximate Nash equilibria of bimatrix games, in a setting where players initially know their own payoffs but not the other player's. In order to find a solution of reasonable quality, some amount of communication is required. We study algorithms where the communication is substantially less than the size of the game. When the communication is polylogarithmic in the number of strategies, we show how to obtain ϵ-approximate Nash equilibrium for ϵâ0.438, and for well-supported approximate equilibria we obtain ϵâ0.732. For one-way communication we show that ϵ=12 is the best approximation quality achievable, while for well-supported equilibria, no value of ϵ<1 is achievable. When the players do not communicate at all, ϵ-Nash equilibria can be obtained for ϵ=34; we also provide a corresponding lower bound of slightly more than 12 on the smallest constant ϵ achievable.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Games and Economic Behavior - Volume 85, May 2014, Pages 19-31
Journal: Games and Economic Behavior - Volume 85, May 2014, Pages 19-31
نویسندگان
Paul W. Goldberg, Arnoud Pastink,