Un juego Avoider-Enforcer [1] : 43–60 (también llamado Avoider-Forcer [2] o Antimaker-Antibreaker [3] : sec.5 ) es un tipo de juego posicional . Como la mayoría de los juegos posicionales, se describe por un conjunto de posiciones/puntos/elementos ( ) y una familia de subconjuntos ( ), que aquí se denominan los conjuntos perdedores . Lo juegan dos jugadores, llamados Avoider y Enforcer, que se turnan para elegir elementos hasta que se toman todos los elementos. Avoider gana si logra evitar tomar un conjunto perdedor; Enforcer gana si logra hacer que Avoider tome un conjunto perdedor.
Un ejemplo clásico de este tipo de juego es Sim . En este juego, las posiciones son todas las aristas del grafo completo en 6 vértices. Los jugadores se turnan para sombrear una línea con su color y pierden cuando forman un triángulo completo de su propio color: los conjuntos perdedores son todos los triángulos.
La condición ganadora de un juego de Evitar-Ejecutar es exactamente la opuesta a la condición ganadora del juego de Hacer-Destruir en el mismo . Por lo tanto, el juego de Evitar-Ejecutar es la variante de Misère del juego de Hacer-Destruir. Sin embargo, existen diferencias contraintuitivas entre estos tipos de juego.
Por ejemplo, considere la versión sesgada de los juegos, en la que el primer jugador toma p elementos cada turno y el segundo jugador toma q elementos cada turno (en la versión estándar p = 1 y q = 1). Los juegos Maker-Breaker son sesgados-monótonos : tomar más elementos siempre es una ventaja. Formalmente, si Maker gana el juego Maker-Breaker ( p : q ), entonces también gana el juego ( p +1: q ) y el juego (p: q-1). Los juegos Avoider-Enforcer no son sesgados-monótonos: tomar más elementos no siempre es una desventaja . Por ejemplo, considere un juego Avoider-Enforcer muy simple donde los conjuntos perdedores son {w, x} e {y, z}. Entonces, Avoider gana el juego (1: 1), Enforcer gana el juego (1: 2) y Avoider gana el juego (2: 2).
Existe una variante monótona de las reglas del juego ( p : q ) Evitador-Ejecutor, en la que el Evitador tiene que elegir al menos p elementos en cada turno y el Ejecutor tiene que elegir al menos q elementos en cada turno; esta variante es monótona en cuanto a sesgo. [1] : 45–46
De manera similar a los juegos Maker-Breaker , los juegos Avoider-Enforcer también tienen generalizaciones fraccionarias.
Supongamos que el Evitador debe evitar tomar al menos una fracción t de los elementos en cualquier conjunto ganador (es decir, tomar como máximo 1- t de los elementos en cualquier conjunto), y el Ejecutor debe evitar esto, es decir, el Ejecutor debe tomar menos de una fracción t de los elementos en algún conjunto ganador. Defina la constante: (en la variante estándar, ).
Juego posicional sesgado#Una condición ganadora para el Evitador
