Nesrovnalost hra - Discrepancy game - Wikipedia

A diskrepanční hra je druh poziční hra. Jako většina pozičních her je popsán souborem pozice / body / prvky (${ displaystyle X}$) a rodina sady (${ displaystyle { mathcal {F}}}$- a rodina podmnožin z ${ displaystyle X}$). Hrají ho dva hráči, tzv Vyvažovač a Nevyvážený. Každý hráč si zase vybere prvek. Cílem Balanceru je zajistit, aby se každý set in ${ displaystyle { mathcal {F}}}$ je vyvážený, tj. prvky v každé sadě jsou mezi hráči rozloženy zhruba rovnoměrně. Cílem Unbalanceru je zajistit, aby alespoň jedna sada byla nevyvážená.

Formálně je cíl balanceru definován vektorem ${ displaystyle (b_ {1}, ldots, b_ {n})}$ kde n je počet sad v ${ displaystyle { mathcal {F}}}$. Balancer vyhrává, pokud je v každé sadě i, rozdíl mezi počtem prvků přijatých nástrojem Balancer a počtem prvků přijatých nástrojem Unbalancer je maximálně b_i.

Ekvivalentně můžeme Balancer považovat za označení každého prvku +1 a Unbalancer označení každého prvku -1 a cílem Balanceru je zajistit, aby absolutní hodnota součtu štítků v sadě i byla maximálně b_i.

Hru představili Frieze, Krivelevich, Pikhurko a Szabo,^[1] a generalizovali Alon, Krivelevich, Spencer a Szabo.^[2]

Srovnání s jinými hrami

V Hra Maker-Breaker, Breaker musí vzít aspoň jeden prvek v každé sadě.

Ve hře Avoider-Enforcer musí Avoider vzít nanejvýš k-1 prvek v každé sadě s k vrcholy.

Ve hře o rozporech musí Balancer dosáhnout obou cílů současně: měl by v každé sadě vzít alespoň určitý zlomek a maximálně určitý zlomek prvků.

Vítězné podmínky

Nechat n být počet sad a k_i být počet prvků v sadě i.

• Li ${ displaystyle sum _ {i = 1} ^ {n} exp left ({- b_ {i} ^ {2} přes 2k_ {i}} right) leq 1/2}$, pak má Balancer vítěznou strategii. Zejména pokud pro všechny i, ${ displaystyle b_ {i} geq { sqrt {2k_ {i} ln (2n)}}}$, pak má Balancer vítěznou strategii. Zejména pokud je velikost všech sad k, pak Balancer může zajistit, aby v každé sadě měl každý z hráčů mezi sebou ${ displaystyle {k nad 2} - { sqrt {k ln (2n) / 2}}}$ a ${ displaystyle {k nad 2} + { sqrt {k ln (2n) / 2}}}$ elementy.^[2]
• Li ${ displaystyle sum _ {i = 1} ^ {n} 2 ^ {- k_ {i}} <1/4}$, pak má Balancer vítěznou strategii pro každý případ i, b_i = k_i-1 (takže Balancer může každý hráč mít prvek v každé ze sad).^[1]

Reference