Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Thursday, November 20, 2014, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Gal Kronenberg (Tel Aviv University)

Maker-Breaker games with one random player

Let P be a monotone increasing graph property. The (m:b) Maker-Breaker game is played on the edge set of K_n, in every round Breaker claims b edges and then Maker claims m edges. The game ends when all edges have been claimed. Maker wins if the graph claimed by him satisfies the property P. Otherwise, Breaker is the winner of the game.

In the (1: b) Maker-Breaker game, a primary question is to find the maximal value of b such that Maker wins by playing according to his best strategy (the so called critical bias b^*). Erdos suggested the following guess which has become known as the probabilistic intuition. Consider the (1:b) Maker-Breaker game on K_n. Then the critical bias b^* is the same as the maximal value of b for which Maker typically wins if both players play randomly. Therefore, a natural question to ask is how the critical bias changes when only one player plays randomly.

A random-player Maker-Breaker game is a two-player game, played the same as an ordinary Maker-Breaker game, except that one player plays according to his best strategy and claims one element in each round, while the other plays randomly and claims b elements. In fact, for every (ordinary) Maker-Breaker game, there are two different random-player versions: the (1:b) random-Breaker game and the (b:1) random-Maker game. In this talk, we analyze the random-player version of several classical Maker-Breaker games such as the Hamilton cycle game, the perfect matching game and the k-vertex-connectivity game. For each of these games we find or estimate the asymptotic values of b that allow each player to typically win the game. We also provide an explicit winning strategy for the "smart" player for the corresponding values of b. Joint work with Michael Krivelevich.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login