Communication complexity of Nash equilibrium in potential games (extended abstract)

Yakov Babichenko; Aviad Rubinstein

doi:10.1109/focs46700.2020.00137

FOCS2020顶会

Communication complexity of Nash equilibrium in potential games (extended abstract)

Yakov Babichenko, Aviad Rubinstein

arXiv DOI 出版方

2020年份

5被引次数

3顶会引用

摘要

We prove communication complexity lower bounds for (possibly mixed) Nash equilibrium in potential games. In particular, we show that finding a Nash equilibrium requires poly(N ) communication in two-player N × N potential games, and 2 poly(n) communication in n-player two-action games. To the best of our knowledge, these are the first results to demonstrate hardness in any model of (possibly mixed) Nash equilibrium in potential games.