Playing games with bounded entropy

• 成果类型: Article
• 署名作者: Valizadeh, Mehrdad; Gohari, Amin
• 署名单位: Sharif University of Technology
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2019.03.013
• 发表日期: 2019
• 页码: 363-380
• 关键词: Repeated games; Bounded entropy; Randomness extraction; Source simulation; Entropy minimization; Information theory

摘要

We study zero-sum repeated games in which the maximizer (player or team) is restricted to strategies with limited randomness. Particularly, we analyze the maxmin payoff of the maximizer in two models: the first model forces the maximizer to randomize her actions just by conditioning them to the outcomes of an observed random source. In the second model, the maximizer is a team of players who are free to privately randomize their corresponding actions but do not have access to any explicit source of shared randomness needed for coordination. While prior works adopted the method of types to address these problems, we use the idea of random hashing being the core of randomness extractors. In addition, we use a tool for simulation of a source from another source. Utilizing these tools, we simplify and generalize the earlier results. We also study the computational aspects of the solution for the first model. (C) 2019 Elsevier Inc. All rights reserved.