# Communication complexity of approximate Nash equilibria

 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.
{"ft_lang_label":"__label__en","ft_lang_prob":0.7614021,"math_prob":0.902034,"size":862,"snap":"2020-34-2020-40","text_gpt3_token_len":222,"char_repetition_ratio":0.11188811,"word_repetition_ratio":0.0,"special_character_ratio":0.2563805,"punctuation_ratio":0.14666666,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9934837,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-08-12T19:06:20Z\",\"WARC-Record-ID\":\"<urn:uuid:8df7b17e-e30c-4ba8-a0db-b230bf0cc39d>\",\"Content-Length\":\"26663\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:737c81e4-00dd-4354-b05c-8e6b72f45911>\",\"WARC-Concurrent-To\":\"<urn:uuid:9b8eb69e-5eb1-4516-97c6-323e73a20609>\",\"WARC-IP-Address\":\"192.16.204.152\",\"WARC-Target-URI\":\"https://www.math.ias.edu/seminars/abstract?event=104214\",\"WARC-Payload-Digest\":\"sha1:OUB7DMVQKWUOB6WWHZSZMRPMQQA4W62T\",\"WARC-Block-Digest\":\"sha1:BVJISAYUTWTSHMLDLCBSOFOKSNFXBDUZ\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-34/CC-MAIN-2020-34_segments_1596439738913.60_warc_CC-MAIN-20200812171125-20200812201125-00014.warc.gz\"}"}