کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6853005 1436971 2018 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The complexity of decision problems about equilibria in two-player Boolean games
ترجمه فارسی عنوان
پیچیدگی مشکلات تصمیم گیری در مورد تعادل در دو بازیکن بازی بولین
کلمات کلیدی
نظریه بازی، بازی های بولین، پیچیدگی، منطق پیشنهاد
ترجمه چکیده
بازی های بولی اجازه می دهد ما را به طور خلاصه نشان دادن بازی های استراتژیک با پرداخت های دودویی در مورد که در تنظیمات بازیکنان ساختار به راحتی قابل بیان در منطق گویا است. از زمان معرفی آنها، جنبه های محاسباتی از بازی های بولینی علاقه چندانی به جامعه داشت، اما تا کنون تمرکز صرفا بر تعادل استراتژی خالص بوده است. در این مقاله، ما پیچیدگی مشکلات مربوط به تعادل استراتژی استراتژیک را، مانند وجود یک تعادل که رضایتبخش محدودیت پرداختی است، در نظر می گیریم. نتایج به دست آمده توسط مشاهده است که یک استراتژی مختلط می تواند اطلاعات کافی برای رمزگذاری از تاریخ محاسبه یک زمان نمایش ماشین تورینگ نگه دارید.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
پیش نمایش مقاله
پیچیدگی مشکلات تصمیم گیری در مورد تعادل در دو بازیکن بازی بولین
چکیده انگلیسی
Boolean games allow us to succinctly represent strategic games with binary payoffs in the case where the players' preferences have a structure readily expressible in propositional logic. Since their introduction, the computational aspects of Boolean games have been of interest to the multiagent community, but so far the focus has been exclusively on pure strategy equilibria. In this paper we consider the complexity of problems involving mixed strategy equilibria, such as the existence of an equilibrium satisfying a given payoff constraint. The results are obtained by the observation that a mixed strategy can hold enough information to encode the computation history of an exponential time Turing machine.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Artificial Intelligence - Volume 261, August 2018, Pages 1-15
نویسندگان
, ,