کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
7359767 | 1478747 | 2015 | 39 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Approximate Nash equilibria in anonymous games
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
علوم انسانی و اجتماعی
اقتصاد، اقتصادسنجی و امور مالی
اقتصاد و اقتصادسنجی
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Approximate Nash equilibria in anonymous games Approximate Nash equilibria in anonymous games](/preview/png/7359767.png)
چکیده انگلیسی
We study from an algorithmic viewpoint anonymous games[22], [4], [5], [19]. In these games a large population of players shares the same strategy set and, while players may have different payoff functions, the payoff of each depends on her own choice of strategy and the number of the other players playing each strategy (not the identity of these players). We show that, the intractability results of [12] and [10] for general games notwithstanding, approximate mixed Nash equilibria in anonymous games can be computed in polynomial time, for any desired quality of the approximation, as long as the number of strategies is bounded by some constant. In addition, if the payoff functions have a Lipschitz continuity property, we show that an approximate pure Nash equilibrium exists, whose quality depends on the number of strategies and the Lipschitz constant of the payoff functions; this equilibrium can also be computed in polynomial time. Finally, if the game has two strategies, we establish that there always exists an approximate Nash equilibrium in which either only a small number of players randomize, or of those who do, they all randomize the same way. Our results make extensive use of certain novel Central Limit-type theorems for discrete approximations of the distributions of multinomial sums.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Economic Theory - Volume 156, March 2015, Pages 207-245
Journal: Journal of Economic Theory - Volume 156, March 2015, Pages 207-245
نویسندگان
Constantinos Daskalakis, Christos H. Papadimitriou,