Simulation of a Random Variable and its Application to Game Theory

Mehrdad Valizadeh () and Amin Gohari ()
Additional contact information
Mehrdad Valizadeh: Department of Electrical Engineering, Sharif University of Technology, 1458889694 Tehran, Iran
Amin Gohari: Tehran Institute for Advanced Studies (TeIAS), 1991813741 Tehran, Iran

Mathematics of Operations Research, 2021, vol. 46, issue 2, 452-470

Abstract: 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 Rényi 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 → ∞ 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.

Keywords: Primary: 91A05; Secondary: 91A20; 60E15; Primary: games/group decisions: noncooperative; secondary: probability: distribution comparisons; entropy; communications: information theory; random variable simulation; randomness extraction; repeated games; bounded entropy; max-min value; convergence rate (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2020.1067 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:46:y:2021:i:2:p:452-470

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().