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
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - יולי 2022

ASJC Scopus subject areas

  • ???subjectarea.asjc.2000.2003???
  • ???subjectarea.asjc.2000.2002???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Communication complexity of approximate Nash equilibria'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי