Mathematical Sciences Research Institute

Home » Workshop » Schedules » The fragility of golden games

The fragility of golden games

Berlekamp Memorial Workshop on Combinatorial Games October 21, 2019 - October 22, 2019

October 21, 2019 (12:00 PM PDT - 12:30 PM PDT)
Speaker(s): Urban Larsson (National University of Singapore)
Location: MSRI: Simons Auditorium
Primary Mathematics Subject Classification No Primary AMS MSC
Secondary Mathematics Subject Classification No Secondary AMS MSC



We consider extensive form win-lose games over a complete binary-tree of depth $n$ where  players act in an alternating manner.
We study arguably the simplest random structure of payoffs over such games where 0/1 payoffs in the leafs are drawn according to an i.i.d. Bernoulli distribution with probability $p$. Whenever $p$ differs from the golden ratio, asymptotically as $n\rightarrow \infty$, the winner of the game is determined. In the case where $p$ equals the golden ratio, we call such a random game a \emph{golden game}. In golden games the winner is the player that acts first with probability that is equal to the golden ratio. We suggest the notion of \emph{fragility} as a measure for ``fairness'' of a game's rules. Fragility counts how many leaves' payoffs should be flipped in order to convert the identity of the winning player. Our main result provides a recursive formula for asymptotic fragility of golden games. Surprisingly, golden games are extremely fragile. For instance, with probability $\approx 0.77$ a losing player could flip a single payoff (out of $2^n$) and become a winner. With probability $\approx 0.999$ a losing player could flip 3 payoffs and become the winner. The notion of fragility developed in this work could be developed further, to a fragility of outcome classes and/or game values of (normal play) combinatorial games, and the purpose of this talk is to invite a further discussion on this topic.

Coauthor: Yakov Babichenko

Supplements No Notes/Supplements Uploaded
Video/Audio Files


H.264 Video 948_27648_8064_948_27648_8056_4-Larsson.mp4
Troubles with video?

Please report video problems to itsupport@msri.org.

See more of our Streaming videos on our main VMath Videos page.