On Erdős-Szekeres Maker-Breaker games

Kód výsledku v 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>

Výsledek na webu

<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

—

Jazyk výsledku

angličtina

Název v původním jazyce

On Erdős-Szekeres Maker-Breaker games

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

On Erdős-Szekeres Maker-Breaker games

Popis výsledku anglicky

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.

Druh

O - Ostatní výsledky

CEP obor

—

OECD FORD obor

10102 - Applied mathematics

Projekt

<a href="/cs/project/GA24-12046S" target="_blank" >GA24-12046S: Výpočet a aproximace ekvilibrií ve hrách se složitými prostory strategií</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2024

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů