Juego posicional sesgado

Un juego posicional sesgado ^{[1] [2] : 27–42} es una variante de un juego posicional . Como la mayoría de los juegos posicionales, se describe mediante un conjunto de posiciones/puntos/elementos ( ) y una familia de subconjuntos ( ), que suelen denominarse conjuntos ganadores . Se juega con dos jugadores que se turnan para elegir elementos hasta que se toman todos los elementos. Mientras que en el juego estándar cada jugador elige un elemento por turno, en el juego sesgado cada jugador toma una cantidad diferente de elementos. ${\estilo de visualización X}$${\displaystyle {\mathcal {F}}}$

Más formalmente, para cada dos números enteros positivos p y q , un juego (p:q)-posicional es un juego en el que el primer jugador elige p elementos por turno y el segundo jugador elige q elementos por turno.

La principal pregunta de interés con respecto a los juegos posicionales sesgados es cuál es su sesgo umbral , es decir, cuál es el sesgo en el que el poder de ganar cambia de un jugador a otro.

Como ejemplo, considere el juego de triángulos . En este juego, los elementos son todos los bordes de un grafo completo en n vértices, y los conjuntos ganadores son todos triángulos (= camarillas en 3 vértices). Supongamos que lo jugamos como un juego Maker-Breaker , es decir, el objetivo de Maker (el primer jugador) es tomar un triángulo y el objetivo de Breaker (el segundo jugador) es evitar que Maker tome un triángulo. Usando un análisis de caso simple, se puede probar que Maker tiene una estrategia ganadora siempre que n sea al menos 6. Por lo tanto, es interesante preguntar si esta ventaja puede ser sesgada al permitir que Breaker elija más de 1 elemento por turno.

De hecho, es posible demostrar que: ^[1]

• Para cada , Maker gana el juego de triángulo (1: q ) en n vértices.${\displaystyle q\leq 0.5{\sqrt {n}}}$
• Para cada , Breaker gana el juego de triángulo (1: q ) en n vértices.${\displaystyle q\geq 2{\sqrt {n}}}$

En un juego Maker-Breaker imparcial , el teorema de Erdos-Selfridge da una condición ganadora para Breaker . Esta condición se puede generalizar a juegos sesgados de la siguiente manera: ^{[3] [2] : 30–32}

• Si , entonces Breaker tiene una estrategia ganadora en el juego (p:q) cuando juega primero.${\displaystyle \sum _{E\in {\mathcal {F}}}(1+q)^{-|E|/p}<1}$
• Si , entonces Breaker tiene una estrategia ganadora en el juego (p:q) incluso cuando juega segundo.${\displaystyle \sum _{E\in {\mathcal {F}}}(1+q)^{-|E|/p}<{1 \over 1+q}}$

La estrategia utiliza una función potencial que generaliza la función de Erdos-Selfridge. El potencial de un conjunto ganador E (no roto) con | E | elementos no tomados se define como . Si Maker gana el juego, entonces existe un conjunto E con | E |=0, por lo que su potencial es 1; por lo tanto, para demostrar que Breaker gana, es suficiente demostrar que la suma potencial final es menor que 1. De hecho, por suposición, la suma potencial en el primer turno de Breaker es menor que 1; y si Breaker siempre elige un elemento que maximiza la caída de potencial, es posible demostrar que la suma potencial siempre disminuye débilmente. ${\displaystyle (1+q)^{-|E|/p}}$

Cuando cada conjunto ganador tiene elementos, para un k fijo , la condición ganadora de Breaker se simplifica a: (cuando juega primero) o (cuando juega segundo). Esta condición es estricta: hay familias de conjuntos k -uniformes con conjuntos donde Maker gana. ^[4]${\displaystyle k}$${\displaystyle |{\mathcal {F}}|<(q+1)^{k/p}}$${\displaystyle |{\mathcal {F}}|<(q+1)^{k/p-1}}$${\displaystyle |{\mathcal {F}}|=(q+1)^{k/p-1}}$

En un juego Maker-Breaker imparcial, un teorema de Beck proporciona una condición ganadora para Maker . Utiliza el grado par del hipergrafo - denotado por . Esta condición se puede generalizar a juegos sesgados de la siguiente manera: ^[3]${\displaystyle d_{2}}$

Si , entonces Maker tiene una estrategia ganadora en el juego (p:q) cuando juega primero.${\displaystyle \sum _{E\in {\mathcal {F}}}{p+q \over p}^{-|E|}>{p^{2}q^{2} \over (p+q)^{3}}\cdot d_{2}\cdot |X|}$

En un juego Evitador-Ejecutor sesgado , las siguientes condiciones garantizan que Evitador tenga una estrategia ganadora: ^{[2] : 47–49}

• Si , entonces Avoider gana el juego (p:q) cuando juega primero, bajo las reglas estrictas y monótonas. Esto es casi estricto: hay una familia infinita de juegos (p:q) en los que esta expresión es ligeramente mayor que 1 y Enforcer gana. ${\displaystyle \sum _{E\in {\mathcal {F}}}(1+1/p)^{p-|E|}<1}$^[5] En particular, en el juego no sesgado la condición se convierte en . Si el gráfico es k -uniforme, la condición se convierte en . Es notable que esta condición no dependa de q en absoluto.${\displaystyle \sum _{E\in {\mathcal {F}}}2^{1-|E|}<1}$${\displaystyle |{\mathcal {F}}|<(1+1/p)^{k-1}}$
• Si cada conjunto ganador tiene como máximo k elementos, y , entonces el que evita gana (p:q) juego cuando juega primero. ${\displaystyle \sum _{E\in {\mathcal {F}}}\left(1+{q \over pk}\right)^{p-|E|}<1}$^[6]

• Juego de hacer cajas