Organisator: Dr. Marco Seiler
Speaker: Júlia Komjáthy (TU Delft)
Abstract: tba
Speaker: Anja Sturm (Uni Göttingen)
Title: On min-max games on trees and beyond
Abstract: We study a random game in which two players in turn play a fixed number of moves. For each move, there are two possible choices. To each possible outcome of the game we assign a winner in an i.i.d. fashion with a fixed parameter p. In the case where all different game histories lead to different outcomes, a classical result due to Pearl (1980) says that in the limit when the number of moves is large, there is a sharp threshold in the parameter p that separates the regimes in which either player has with high probability a winning strategy.
We are interested in a modification of this game where the outcome is determined by the exact sequence of moves played by the first player (as in a game tree) and by the number of times the second player has played each of the two possible moves. We show that also in this case, there is a sharp threshold in the parameter p that separates the regimes in which either player has with high probability a winning strategy. Since in the modified game, different game histories can lead to the same outcome, the graph associated with the game is no longer a tree which means independence is lost. As a result, the analysis becomes more complicated and open problems remain.
This is joint work with Jan Swart (UTIA Prague) and Natalia Cardona Tobon (Universidad Nacional de Colombia).
