On Erdős-Szekeres Maker-Breaker games
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F24%3A00377917" target="_blank" >RIV/68407700:21240/24:00377917 - isvavai.cz</a>
Result on the web
<a href="https://cosc.brocku.ca/~rnishat/CCCG_2024_proceedings.pdf" target="_blank" >https://cosc.brocku.ca/~rnishat/CCCG_2024_proceedings.pdf</a>
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
On Erdős-Szekeres Maker-Breaker games
Original language description
The Erdős-Szekeres Maker-Breaker game is a two-player competitive game where both players alternately place points in the plane such that no three points are colinear. 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 + ε) times more points (each round on average) in comparison to Breaker, for any ε > 0. Further, we address the models of the game for equilateral empty convex polygons in the plane and empty convex polygons in square grids.
Czech name
—
Czech description
—
Classification
Type
O - Miscellaneous
CEP classification
—
OECD FORD branch
10102 - Applied mathematics
Result continuities
Project
<a href="/en/project/GA24-12046S" target="_blank" >GA24-12046S: Computing and Approximating Equilibria in Games With Complex Strategy Spaces</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2024
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů