Exploring Limited Randomness in Repeated Games
Dive into the world of randomness in repeated games through this insightful research by Moni Naor, Pavel Hubæk, and Jon Ullman. Discover the significance of randomness in algorithms, equilibria, and finitely repeated games. Explore the necessity of randomness in Nash Equilibrium and the computational implications in 2-player 0-sum games. Uncover the role of entropy, strategies, and utility in understanding the complexity of repeated games.
Uploaded on Sep 08, 2024 | 2 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
When Can Limited Randomness Be Used in Repeated Games? Moni Naor Weizmann Institute of Science Joint work with Pavel Hub ek and Jon Ullman Columbia University
Randomness in Algorithms Using Randomness is extremely useful: Algorithms Faster algorithms: MCMC Simpler design Combinatorial constructions Distributed computing Cryptography But before that: randomness in games! Important question: Do we actually need randomness and how much?
Randomness in Equilibria Randomness facilitates equilibria in single-shot games: 2-player 0-sum games (von Neumann 1928) finite strategic games (Nash 1951) correlated randomness (Aumann 1976) What importance has randomness in repeated games? What about parallel games? 3
Randomness in Finitely Repeated Games Heads Tails heads 1, -1 -1, 1 tails -1, 1 1, -1 1 bit of randomness necessary and sufficient for single-shot ? bits of randomness sufficient for ?-stage game Does randomness have to grow with ?? 4
Talk Plan How much randomness does a Nash Equilibrium require Games, equilibria, entropy Unbounded players Repeated games necessitating linear entropy in ? Repeated games admitting constant entropy Computationally bounded players Repeated 2-player 0-sum games: one-way functions exist sub-linear randomness suffices 5
Related Work Neyman and Okada [GEB 00]: Strategic entropy in 2-player 0-sum games Budinich and Fortnow [EC 11]: Limited randomness in repeated matching pennies Halpern and Pass [JET 15]: Costly randomness in machine games Halprin and Naor [SOUPS 09]: Randomness generated by human players 6
Game G Single shot game G Number of players k Set of actions per player ?? Payoff for each player for action profile ui(a1,a2, , a?) Strategy ??: distribution on action options ?? Strategy for other players: ? ? Repeated game: Game is repeated in n rounds Utility: sum of utilities of each round
Entropy of Strategy ? ?(?) ?( ) ?( ) Pr ? logPr[?] ? ? ? Strategy ? in ??: for every history a strategy ?( ) of player ? in ? Entropy of ? at history : Shannon entropy of ?( ) Entropy of ? at terminal ?: total entropy from ? to the root Entropy of ?: maximum over terminal histories ? 8
Nash Equilibrium Set of strategies where no player can profit from deviating. E ui? ?,? ? E ui??,? ? for all ? ?
Enforceable Payoff Minmax payoff Minmax payoff of player i: the lowest payoff the other players can force upon player I ??= min ? ?max E ui??,? ? ?? A minmax strategy of player i is strategy ? s.t. the utility guaranteed to i is at least ??
Talk Plan How much randomness does a Nash Equilibrium require Games, equilibria, entropy Unbounded players Repeated games necessitating linear entropy in ? Repeated games admitting constant entropy Computationally bounded players Repeated 2-player 0-sum games: one-way functions exist sub-linear randomness suffices 11
Repeated Games with Linear Entropy Theorem: if every Nash equilibrium of ? achieves the minmax payoff profile: then every Nash equilibrium of ??has entropy ?(?). Minmax payoff = minimal enforceable payoff Key point: at all histories of ??: must play a Nash equilibrium of ? The Theorem holds for any ?-player strategic game ? special case: 2-player 0-sum games 13
Non-0-Sum Game with Linear Entropy Left Heads Tails Right Row can force 0 can force 0 up 0, -1 0, -1 0, -1 0, 0 Column heads 0, -1 1, -1 -1, 1 -1, 0 tails 0, -1 -1, 1 1, -1 -1, 0 down 0, 0 -1, 1 -1, 1 1, 0 3 mixed Nash equilibria: (1 2? +1 2?,1 2? +1 2?), (1 2? +1 2?,1 2? +1 2?), and (1 2? +1 2?,1 2? +1 2?) All achieve the minmax payoff profile (0,0) 14
Talk Plan How much randomness does a Nash Equilibrium require Games, equilibria, entropy Unbounded players Repeated games necessitating linear entropy in ? Repeated games admitting constant entropy Computationally bounded players Repeated 2-player 0-sum games: one-way functions exist sub-linear randomness suffices 15
Repeated Game with Constant Entropy Coop. Heads Tails Punish coop. 3, 3 -3, 6 -3, 6 -3, -3 heads 6, -3 1, -1 -1, 1 -3, -3 tails 6, -3 -1, 1 1, -1 -3, -3 punish -3, -3 -3, -3 -3, -3 -4, -4 Minmax payoff profile 3, 3 by playing ???? or ???? 1 bit of randomness for the single-shot game 1 bit of randomness for the ?-stage game 17
Repeated Game with Constant Entropy Coop. Heads Tails Punish coop. 3, 3 -3, 6 -3, 6 -3, -3 heads 6, -3 1, -1 -1, 1 -3, -3 tails 6, -3 -1, 1 1, -1 -3, -3 punish -3, -3 -3, -3 -3, -3 -4, -4 Equilibrium in ??: Stages 1, ,? 1: (????,????) Stage ?: (1 1 bit of entropy 2????? +1 2?????,1 2????? +1 2?????) After any opponent deviation: ?????? (resp. ??????). 18
Repeated Games with Constant Entropy Theorem: If for every player there exists a Nash equilibrium of ? that improves over his minmax payoff, then there exists a Nash equilibrium of ??with effective entropy independent of ?. Related to the finite horizon Folk Theorem Effective entropy: the punishment might be randomized 19
Talk Plan How much randomness does a Nash Equilibrium require Games, equilibria, entropy Unbounded players Repeated games necessitating linear entropy in ? Repeated games admitting constant entropy Computationally bounded players Repeated 2-player 0-sum games: one-way functions exist sub-linear randomness suffices 20
Computationally Bounded Players Pseudorandom generators (one-way functions): Stretch short seed to a seemingly random string ? Yields efficiently unpredictable strategies ? ? Existentially: OWF PRG By Yao 82: notions are equivalent ?(?) Are one-way functions essential for low-randomness? In repeated 2-player 0-sum games: If one-way functions do not exist then any computational Nash equilibrium necessitates (?) random bits for ? stages. 22
Computational Nash Equilibrium [Dodis-Halevi-Rabin 2000] Computational repeated game of ?: Family of games = ?? ? Strategy given by poly-size circuit family ? = ?? ? Consistent randomness ? ? 0,1?(?)used in all ? stages Computational Nash equilibrium: Any efficient deviation ? gives negligible improvement 23
Repeated Matching Pennies 2? 1 Game-play stretches 2? 1 random bits to 2? bits ??,?? No OWFs => efficiently predictable for some i, for some player (??,??) Profitable deviation: try to predict opponent; otherwise play at random. ?1,?1, , ??,?? OWF 2? 24
Repeated 2-player 0-Sum Games ?? ?? ??+1 , ?1,?1, , ??,?? ?? ??+1 ?? Reduce predicting to learning adaptively changing distributions 25
Learning Adaptively Changing Distributions ? ? ??+1 ?0, ,?? ? Given ?0, ,??, learner : Asks for ??+1or Outputs ? close to ??(?0, ,??) Naor and Rothblum 2006: If one-way functions do not exist: then there exists efficient that can predict ??after seeing H(?) samples, as well as someone knowing ?. 26
ACD for Game-Play ?? ?: ??+1= ??( ?;??) ??+1 ? ?||(??+1,??+1) ?= ( , ?1,?1, , ??,??) ? If ?? ?(?), then exists that efficiently learns ??after ? ? stages Profitable deviation: use to predict and afterwards play minmax 27
Repeated 2-Player 0-Sum Games Theorem: Suppose one-way functions do not exist. For any 2-player 0-sum game ? with no weakly dominant pure strategies there is no computational Nash equilibrium of ?? using ?(?) randomness. Open Problems: Does any repeated game need 0,1 or ? bits of randomness? OWF Is it possible to exploit bounded players by more than once? Thanks! 28
Exploiting Limited Randomness In matching pennies, ?-Nash equilibrium (1 ?)? entropy: The best response to any (1 ? ) entropy strategy ? achieves at least ? in the stage game. The best response achieves 2? 1, where ? [0.5,1] is the probability of the most likely action in ?. ? = 1 ? ? = 1 + ?log2? + (1 ?)log2(1 ?) 2? 1 For n stages: conditional expectation + (1 ?)? entropy bound 29
Exploitation in Non-0-Sum Games Left Heads Tails Right up 0, -1 0, -1 0, -1 0, 0 heads 0, -1 1, -1 -1, 1 -1, 0 tails 0, -1 -1, 1 1, -1 -1, 0 down 0, 0 -1, 1 -1, 1 1, 0 Cannot always exploit limited randomness in non-0-sum games 30
Exploiting Limited Randomness In two-player zero-sum games, can exploit in all rounds proportionally to the randomness deficiency [NO 00]. Not efficiently! Our results for computational players exploit the limited randomness only in a single round. Can we efficiently exploit up to the randomness deficiency? 31
