Two players, Green and Red, play a zero-sum game. It is parametrized by two integers $n\geq 0, k\geq 0$, and a finite family $F$ of sets of size $n$ (each set may appear multiple times in $F$).
Each turn, Green colors an uncolored element green, and then Red colors an uncolored element red.
A set in $F$ is considered "good" if it contains at least $k$ green elements.
The score of Green is the fraction of good sets (number of good sets divided by $|F|$).
Define $g(n,k,F)$ as the maximum score that Green can get in this game, and define: $$ G(n,k) := \min_{F} g(n,k,F) $$ i.e, the maximum score Green can get in a worst-case set-family. What is G(n,k)?
Here are some examples.
- $G(n,0)=1$ for every $n\geq 0$.
- $G(0,k)=0$ for every $k\geq 1$.
- Moreover, $G(n,k)=0$ for every $k>n$.
- Moreover, $G(n,k)=0$ for every $k$ such that $2 k - 2 \geq n$. Proof. Let $F$ contain a single set, i.e, $F=\{\{1,\ldots,n\}\}$. Obviously at most $k-1$ elements will be green, so the single set will not be good and Green's score will be 0. In particular, $G(2,2)=0$.
- $G(1,1)=1/2$. Proof. Green can use the following strategy: each turn, pick the element that appears in the largest number of uncolored sets. Thus, each couple of turns, the number of sets that become good is at least as large as the number of sets that become bad, so Green's score is at least $1/2$. For tightness, let $F = \{\{1\},\{2\}\}$. Regardless of Green's initial move, Red can make at least one set bad, making Green's score at most $1/2$.
- I could also prove that, for every $n\geq 1$, $G(n,1)= 1 - 1 / 2^n$.
The smallest case that I cannot prove is $G(3,2)$. I can prove it is at least $3/8$ and at most $1/2$ but do not know the exact value.
Was this game studied before? Is anything else known about it?
EDIT. I could get many upper bounds with the following strategy.
The state of each set, during the game, can be described as $(n',k')$, where $n'$ is the number of uncolored elements in the set and $k'$ the number of elements it is missing to be good. So initially the state of all sets is $(n,k)$; when an element of such set is colored red or green, its state changes to $(n-1,k)$ or $(n-1,k-1)$ respectively; etc.
To each set we assign a potential $P(n',k')$ based on its state. The potential is determined such that:
- The potential of a good set is 1: $P(n',0)=1$ for all $n'$.
- The potential of a bad set is 0: $P(0,k')=1$ for all $k'\geq 1$.
- The potential increases when an element becomes green and decreases when an element beccomes red, but the increase is at least as high as the decrease: $P(n'-1,k'-1)-P(n',k') \geq P(n',k') - P(n'-1,k')$ for all $k'\geq 1, n'\geq 1$.
- The potential does not decrease when two elements become red and green simultaneously: $P(n',k')\leq P(n'-2,k'-1)$.
Using a simple Google spreadsheet I could numerically calculate some appropriate values of $P$ (I am still working on finding a closed-form formula).
Using this $P$, the strategy of Green is: For every element, calculate its potential loss - how much potential will be lost if this element will be colored red. Pick the element with the largest potential loss.
By construction of $P$, the potential increase when this element becomes green is weakly larger than the potential decrease when another element becomes red. Therefore, the potential weakly increases.
Initially, the total potential is $P(n,k)$ times the number of sets. Finally, the potential exactly equals the number of good sets. Therefore the fraction of good sets is at least $P(n,k)$.
In particular, $P(n,1) = 1 - 2^n$ and $P(3,2)=3/8$, which gives the claimed lower bounds.
