دانلود مقاله ISI انگلیسی شماره 70500
عنوان فارسی مقاله

بهبود HkHk محدود در قیمت ثبات در بازی های طراحی شبکه Shapley بدون جهت☆

کد مقاله سال انتشار مقاله انگلیسی ترجمه فارسی تعداد کلمات
70500 2015 8 صفحه PDF سفارش دهید محاسبه نشده
خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.
عنوان انگلیسی
Improving the HkHk-bound on the price of stability in undirected Shapley network design games ☆
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Theoretical Computer Science, Volume 562, 11 January 2015, Pages 557–564

کلمات کلیدی
بازی طراحی شبکه Shapley بدون جهت؛ قیمت ثبات؛ قیمت پتانسیل بهینه از ثبات؛ قیمت بالقوه بهینه از هرج و مرج
پیش نمایش مقاله
پیش نمایش مقاله بهبود HkHk محدود در قیمت ثبات در بازی های طراحی شبکه Shapley بدون جهت☆

چکیده انگلیسی

In this article we show that the price of stability of Shapley network design games on undirected graphs with k   players is at most k3(k+1)/2−k21+k3(k+1)/2−k2Hk=(1−Θ(1/k4))Hk, where HkHk denotes the k  -th harmonic number. This improves on the known upper bound of HkHk, which is also valid for directed graphs but for these, in contrast, is tight. Hence, we give the first non-trivial upper bound on the price of stability for undirected Shapley network design games that is valid for an arbitrary number of players. Our bound is proved by analyzing the price of stability restricted to Nash equilibria that minimize the potential function of the game. We also present a game with k=3k=3 players in which such a restricted price of stability is 1.634. This shows that the analysis of Bilò and Bove (2011) [3] is tight. In addition, we give an example for three players that improves the lower bound on the (unrestricted) price of stability to 1.571.

خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.