Juego de discrepancias

Un juego de discrepancia es un tipo de juego posicional . Como la mayoría de los juegos posicionales, se describe por su conjunto de posiciones/puntos/elementos ( ) y una familia de conjuntos ( - una familia de subconjuntos de ). Lo juegan dos jugadores, llamados Balancer y Unbalancer . Cada jugador, a su vez, elige un elemento. El objetivo de Balancer es asegurar que cada conjunto en esté equilibrado, es decir, los elementos de cada conjunto se distribuyan de forma aproximadamente igualitaria entre los jugadores. El objetivo de Unbalancer es asegurar que al menos un conjunto esté desequilibrado. ${\displaystyle X}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle X}$ ${\displaystyle {\mathcal {F}}}$

Formalmente, el objetivo del equilibrador se define mediante un vector donde n es el número de conjuntos en . El equilibrador gana si en cada conjunto i , la diferencia entre el número de elementos tomados por el equilibrador y el número de elementos tomados por el desequilibrador es como máximo b _i . ${\displaystyle (b_{1},\ldots ,b_{n})}$ ${\displaystyle {\mathcal {F}}}$

De manera equivalente, podemos pensar que Balancer etiqueta cada elemento con +1 y Unbalancer etiqueta cada elemento con -1, y el objetivo de Balancer es garantizar que el valor absoluto de la suma de etiquetas en el conjunto i sea como máximo b _i .

El juego fue introducido por Frieze, Krivelevich, Pikhurko y Szabo, ^[1] y generalizado por Alon, Krivelevich, Spencer y Szabo. ^[2]

Comparación con otros juegos

En un juego Maker-Breaker , Breaker tiene que tomar al menos un elemento de cada conjunto.

En un juego Avoider-Enforcer, Avoider debe tomar como máximo k-1 elemento en cada conjunto con k vértices.

En un juego de discrepancia, Balancer debe alcanzar ambos objetivos simultáneamente: debe tomar al menos una cierta fracción, y como máximo una cierta fracción, de los elementos de cada conjunto.

Condiciones de victoria

Sea n el número de conjuntos y k _i el número de elementos del conjunto i .

• Si , entonces Balancer tiene una estrategia ganadora. En particular, si para todos los i , , entonces Balancer tiene una estrategia ganadora. En particular, si el tamaño de todos los conjuntos es k , entonces Balancer puede asegurar que en cada conjunto, cada uno de los jugadores tenga entre y elementos. ^[2] ${\displaystyle \sum _{i=1}^{n}\exp \left({-b_{i}^{2} \over 2k_{i}}\right)\leq 1/2}$ ${\displaystyle b_{i}\geq {\sqrt {2k_{i}\ln(2n)}}}$ ${\displaystyle {k \over 2}-{\sqrt {k\ln(2n)/2}}}$ ${\displaystyle {k \over 2}+{\sqrt {k\ln(2n)/2}}}$
• Si , entonces Balancer tiene una estrategia ganadora para el caso de que para cada i , b _i = k _i -1 (por lo que Balancer puede cada jugador tiene un elemento en cada uno de los conjuntos). ^[1] ${\displaystyle \sum _{i=1}^{n}2^{-k_{i}}<1/4}$

Referencias

1. Frieze, Alan; Krivelevich, Michael; Pikhurko, Oleg; Szabó, Tibor (2005). "El juego de JumbleG". Combinatoria, probabilidad y computación . 14 (5–6): 783–793. doi :10.1017/S0963548305006851. ISSN  1469-2163. S2CID  16104089.
2. Alon, Noga; Krivelevich, Michael; Spencer, Joel; Szabó, Tibor (29 de septiembre de 2005). "Juegos de discrepancia". Revista Electrónica de Combinatoria . 12 (1): 51. doi : 10.37236/1948 . ISSN  1077-8926.