On Erdos-Szekeres Maker-Breaker games

Abstract

The Erdős-Szekeres Maker-Breaker game is a two-player competitive game where both players alternately place points anywhere in the two dimensional Euclidean plane without overlapping, such that no three points are collinear. The first player (Maker) starts the game by placing her point and wants to obtain an empty convex polygon of a given size k such that the vertices of the polygon are chosen from these points and the second player (Breaker) wants to prevent it. We show that Maker wins the game for k <= 8. We also present a winning strategy for Maker for any k in general when Maker is allowed to place (1 + eps) times more points (each round on average) in comparison to Breaker, for any eps > 0. Further, we address the models of the game for equilateral empty convex polygons in the plane and empty convex polygons in square grids.