文章基本信息

标题：Honest Signaling in Zero-Sum Games Is Hard, and Lying Is Even Harder
本地全文：下载
作者：Aviad Rubinstein
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：80
页码：77:1-77:13
DOI：10.4230/LIPIcs.ICALP.2017.77
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We prove that, assuming the exponential time hypothesis, finding an epsilon-approximately optimal symmetric signaling scheme in a two-player zero-sum game requires quasi-polynomial time. This is tight by [Cheng et al., FOCS'15] and resolves an open question of [Dughmi, FOCS'14]. We also prove that finding a multiplicative approximation is NP-hard. We also introduce a new model where a dishonest signaler may publicly commit to use one scheme, but post signals according to a different scheme. For this model, we prove that even finding a (1-2^{-n})-approximately optimal scheme is NP-hard.
关键词：Signaling; Zero-sum Games; Algorithmic Game Theory; birthday repetition