Simulation of a Random Variable and its Application to Game Theory

• 成果类型: Article
• 署名作者: Valizadeh, Mehrdad; Gohari, Amin
• 署名单位: Sharif University of Technology
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2020.1067
• 发表日期: 2021
• 页码: 452-470

摘要

We provide a new tool for simulation of a random variable (target source) from a randomness source with side information. Considering the total variation distance as the measure of precision, this tool offers an upper bound for the precision of simulation, which is vanishing exponentially in the difference of Renyi entropies of the randomness and target sources. This tool finds application in games in which the players wish to generate their actions (target source) as a function of a randomness source such that they are almost independent of the observations of the opponent (side information). In particular, we study zero-sum repeated games in which the players are restricted to strategies that require only a limited amount of randomness. Let be the max-min value of the n stage game. Previous works have characterized lim(n ->infinity)v(n), that is, the long-run max-min value, but they have not provided any result on the value of v(n) for a given finite n-stage game. Here, we utilize our new tool to study how v(n) converges to the long-run max-min value.