5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you share your proof on that lower bound? I'm not seeing an easy way to show that. Upper bounds are easy by example, lower bounds I don't see. $\endgroup$ – JKreft Aug 6 '18 at 14:47
  • $\begingroup$ @JKreft add a proof of lower bound $\endgroup$ – Erel Segal-Halevi Aug 6 '18 at 18:23
  • $\begingroup$ I'm sorry, I should have been clearer, I meant the lower bound of $\frac{3}{8}$ on $G(3,2)$. $\endgroup$ – JKreft Aug 6 '18 at 18:26
  • $\begingroup$ @JKreft I added a more general lower bound proof $\endgroup$ – Erel Segal-Halevi Aug 8 '18 at 8:31
3
$\begingroup$

$G(3,2)=\frac{1}{2}$.

For any set $F$ composed of 3-element sets, let's assume there's a sequence of choices $a_1,b_1,\dots a_k,b_k$ where B gains the upper hand and has two elements chosen out of more than half the sets in $F$, despite A playing optimally. If B can force such a sequence, then A can force the sequence $b_1,?,b_2,?\dots,b_k$ for itself, leaving it with more than half the sets in $F$, despite B playing optimally. Therefore, B can never gain the upper hand at any move in $G(3,2)$, so it can have at most half the sets with two of its chosen elements in them.

$\endgroup$
  • $\begingroup$ In fact, following this reasoning, I believe I can posit that $G(2k,i) \geq \frac{1}{2}$ if $i\leq k+1$. $\endgroup$ – JKreft Aug 6 '18 at 15:46
  • $\begingroup$ I take it that A and B are your nicknames for Green and Red, respectively. $\endgroup$ – Gerry Myerson Aug 6 '18 at 22:51
  • $\begingroup$ Yes, I was thinking player A player B. $\endgroup$ – JKreft Aug 6 '18 at 23:25
  • $\begingroup$ Cool proof. I wonder if this can be extended to other values, e.g, $G(4,2)$. $\endgroup$ – Erel Segal-Halevi Aug 7 '18 at 4:45
  • $\begingroup$ Rejected an edit that changed the proof to be incorrect. Note that in my version, A doesn't make an arbitrary first move, it just starts with B's optimal strategy as its first move. If B can force the win going second, A can force it going first. $\endgroup$ – JKreft Aug 7 '18 at 11:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.