کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5072502 | 1373507 | 2010 | 20 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
How long to equilibrium? The communication complexity of uncoupled equilibrium procedures
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
علوم انسانی و اجتماعی
اقتصاد، اقتصادسنجی و امور مالی
اقتصاد و اقتصادسنجی
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We study the question of how long it takes players to reach a Nash equilibrium in uncoupled setups, where each player initially knows only his own payoff function. We derive lower bounds on the communication complexity of reaching a Nash equilibrium, i.e., on the number of bits that need to be transmitted, and thus also on the required number of steps. Specifically, we show lower bounds that are exponential in the number of players in each one of the following cases: (1) reaching a pure Nash equilibrium; (2) reaching a pure Nash equilibrium in a Bayesian setting; and (3) reaching a mixed Nash equilibrium. We then show that, in contrast, the communication complexity of reaching a correlated equilibrium is polynomial in the number of players.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Games and Economic Behavior - Volume 69, Issue 1, May 2010, Pages 107-126
Journal: Games and Economic Behavior - Volume 69, Issue 1, May 2010, Pages 107-126
نویسندگان
Sergiu Hart, Yishay Mansour,