کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
439318 690510 2007 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the structure and complexity of worst-case equilibria
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On the structure and complexity of worst-case equilibria
چکیده انگلیسی

In the resource allocation game introduced by Koutsoupias and Papadimitriou, n jobs of different weights are assigned to m identical machines by selfish agents. For this game, it has been conjectured by several authors that the fully mixed Nash equilibrium (FMNE) is the worst possible w.r.t. the expected maximum load over all machines. Assuming the validity of this conjecture, computing a worst-case Nash equilibrium for a given instance was trivial, and approximating the Price of Anarchy for this instance would be possible by approximating the expected social cost of the FMNE by applying a known FPRAS.We present a counter-example to this conjecture showing that fully mixed Nash equilibria cannot be used to approximate the Price of Anarchy. We show that the factor between the social cost of the worst Nash equilibrium and the social cost of the FMNE can be as large as the Price of Anarchy itself, up to a constant factor. In addition, we present an algorithm that constructs so-called concentrated equilibria that approximate the worst-case Nash equilibria within constant factors.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 378, Issue 2, 6 June 2007, Pages 165-174