کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5000107 | 1460639 | 2017 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Price of anarchy and an approximation algorithm for the binary-preference capacitated selfish replication game
ترجمه فارسی عنوان
قیمت هرج و مرج و یک الگوریتم تقریبی برای بازی تکراری خودخواهانه توانایی دوگانه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
سایر رشته های مهندسی
کنترل و سیستم های مهندسی
چکیده انگلیسی
We consider the capacitated selfish replication (CSR) game with binary preferences, over general undirected networks. We study the price of anarchy of such games, and show that it is bounded above by 3. We develop a quasi-polynomial algorithm O(n2+lnD), where n is the number of players and D is the diameter of the network, which can find, in a distributed manner, an allocation profile that is within a constant factor of the optimal allocation, and hence of any pure-strategy Nash equilibrium (NE) of the game. Proof of this result uses a novel potential function. We further show that when the underlying network has a tree structure, every globally optimal allocation is an NE, which can be reached in only linear time. We formulate the optimal solutions and NE points of the CSR game using integer linear programs. Finally, we introduce the LCSR game as a localized version of the CSR game, wherein the actions of the players are restricted to only their close neighborhoods.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Automatica - Volume 76, February 2017, Pages 153-163
Journal: Automatica - Volume 76, February 2017, Pages 153-163
نویسندگان
Seyed Rasoul Etesami, Tamer BaÅar,