کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10334499 | 690443 | 2009 | 22 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The structure and complexity of Nash equilibria for a selfish routing game
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: The structure and complexity of Nash equilibria for a selfish routing game The structure and complexity of Nash equilibria for a selfish routing game](/preview/png/10334499.png)
چکیده انگلیسی
We embark on a systematic study of several algorithmic problems related to the computation of Nash equilibria for the selfish routing game we consider. In a nutshell, these problems relate to deciding the existence of a pure Nash equilibrium, constructing a Nash equilibrium, constructing the pure Nash equilibria of minimum and maximum social cost, and computing the social cost of a given mixed Nash equilibrium. Our work provides a comprehensive collection of efficient algorithms, hardness results, and structural results for these algorithmic problems. Our results span and contrast a wide range of assumptions on the syntax of the Nash equilibria and on the parameters of the system.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 410, Issue 36, 31 August 2009, Pages 3305-3326
Journal: Theoretical Computer Science - Volume 410, Issue 36, 31 August 2009, Pages 3305-3326
نویسندگان
Dimitris Fotakis, Spyros Kontogiannis, Elias Koutsoupias, Marios Mavronicolas, Paul Spirakis,