Loading...

Playing games with bounded entropy

Valizadeh, M ; Sharif University of Technology | 2019

705 Viewed
  1. Type of Document: Article
  2. DOI: 10.1016/j.geb.2019.03.013
  3. Publisher: Academic Press Inc , 2019
  4. Abstract:
  5. 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. © 2019 Elsevier Inc
  6. Keywords:
  7. Bounded entropy ; Entropy minimization ; Information theory ; Randomness extraction ; Repeated games ; Source simulation
  8. Source: Games and Economic Behavior ; Volume 115 , 2019 , Pages 363-380 ; 08998256 (ISSN)
  9. URL: https://www.sciencedirect.com/science/article/abs/pii/S089982561930048X#!