文章基本信息

标题：Large Supports are Required for Well-Supported Nash Equilibria
本地全文：下载
作者：Yogesh Anbalagan ; Hao Huang ; Shachar Lovett 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2015
卷号：40
页码：78-84
DOI：10.4230/LIPIcs.APPROX-RANDOM.2015.78
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We prove that for any constant k and any epsilon < 1, there exist bimatrix win-lose games for which every epsilon-WSNE requires supports of cardinality greater than k. To do this, we provide a graph-theoretic characterization of win-lose games that possess epsilon-WSNE with constant cardinality supports. We then apply a result in additive number theory of Haight to construct win-lose games that do not satisfy the requirements of the characterization. These constructions disprove graph theoretic conjectures of Daskalakis, Mehta and Papadimitriou and Myers.
关键词：bimatrix games; well-supported Nash equilibria