کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6875458 1441955 2018 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Mechanism design for one-facility location game with obnoxious effects on a line
ترجمه فارسی عنوان
طراحی مکانیسم برای بازی یک مکان با اثرات نامطلوب بر روی یک خط
کلمات کلیدی
طراحی مکانیسم، بازی محل تسهیلات الگوریتم تقریبی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The classic obnoxious facility game [4], [11] is a special case of our problem when d1=0 and d2=1. In this work, we first study the hardness of approximate mechanism design on this generalized problem, which states that our problem cannot admit any deterministic strategy-proof mechanism with bounded approximation ratio if d1≥12. Then we limit the thresholds to some ranges, both deterministic and randomized strategy-proof mechanisms are studied, and the approximation ratios vary with the specific values of d1 and d2.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 734, 22 July 2018, Pages 46-57
نویسندگان
, , ,