Computer Science/Discrete Mathematics Seminar I | |

Topic: | Communication complexity of approximate Nash equilibria |

Speaker: | Aviad Rubinstein |

Affiliation: | University of California, Berkeley |

Date: | Monday, October 31 |

Time/Room: | 11:15am - 12:15pm/West Building Lecture Hall |

Video Link: | https://video.ias.edu/csdm/2016/1031-AviadRubinstein |

For a constant $\epsilon$, we prove a $\mathrm{poly}(N)$ lower bound on the communication complexity of $\epsilon$-Nash equilibrium in two-player $N \times N$ games. For $n$-player binary-action games we prove an $\exp(n)$ lower bound for the communication complexity of $(\epsilon,\epsilon)$-weak approximate Nash equilibrium, which is a profile of mixed actions such that at least $(1-\epsilon)$-fraction of the players are $\epsilon$-best replying. https://arxiv.org/abs/1608.06580 Joint work with Yakov Babichenko.