کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
479799 1446020 2014 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Optimal cost sharing for capacitated facility location games
ترجمه فارسی عنوان
به اشتراک گذاری هزینه های بهینه برای بازی های مکان یابی تسهیلات
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
چکیده انگلیسی


• We consider cost sharing in capacitated facility location games.
• Optimal cost sharing protocols (w.r.t. price of anarchy and price of stability) are introduced.
• Computational hardness and inapproximability of optimal cost shares are shown.
• We give a tractable protocol with performance matching the inapproximability bound.

We consider cost sharing for a class of facility location games, where the strategy space of each player consists of the bases of a player-specific matroid defined on the set of resources. We assume that resources have nondecreasing load-dependent costs and player-specific delays. Our model includes the important special case of capacitated facility location problems, where players have to jointly pay for opened facilities. The goal is to design cost sharing protocols so as to minimize the resulting price of anarchy and price of stability. We investigate two classes of protocols: basic protocols guarantee the existence of at least one pure Nash equilibrium and separable protocols additionally require that the resulting cost shares only depend on the set of players on a resource. We find optimal basic and separable protocols that guarantee the price of stability/price of anarchy to grow logarithmically/linearly in the number of players. These results extend our previous results (cf. von Falkenhausen & Harks, 2013), where optimal basic and separable protocols were given for the case of symmetric matroid games without delays.We finally study the complexity of computing optimal cost shares. We derive several hardness results showing that optimal cost shares cannot be approximated in polynomial time within a logarithmic factor in the number of players, unless P=NPP=NP. For a restricted class of problems that include the above hard instances, we devise an approximation algorithm matching the logarithmic bound.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 239, Issue 1, 16 November 2014, Pages 187–198
نویسندگان
, ,