Communication complexity of approximate Nash equilibria

Yakov Babichenko, Aviad Rubinstein

نتاج البحث: نشر في مجلةمقالةمراجعة النظراء

ملخص

For a constant ϵ, we prove a poly(N) lower bound on the (randomized) communication complexity of ϵ-Nash equilibrium in two-player N×N games. For n-player binary-action games we prove an exp⁡(n) lower bound for the (randomized) communication complexity of (ϵ,ϵ)-weak approximate Nash equilibrium, which is a profile of mixed actions such that at least (1−ϵ)-fraction of the players are ϵ-best replying.

اللغة الأصليةالإنجليزيّة
الصفحات (من إلى)376-398
عدد الصفحات23
دوريةGames and Economic Behavior
مستوى الصوت134
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - يوليو 2022

All Science Journal Classification (ASJC) codes

  • !!Finance
  • !!Economics and Econometrics

بصمة

أدرس بدقة موضوعات البحث “Communication complexity of approximate Nash equilibria'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا