5
$\begingroup$

Given $m$ persons (men and women) and $n$ balls, each person randomly selects $3$ balls. Once all of them complete the selection process, we color the balls with $2$ colors, white and black, such that (1) for any set of three balls selected by a same man, there are at least $2$ black balls, and (2) for any set of three balls selected by a same woman, there are at least $2$ white balls. The problem is to design a coloring algorithm satisfying the above constraints. Is it related to some known problem in random graphs? Is there a threshold $n_0$ that once $n\ge n_0$, the algorithm will succeed w.h.p.? We may allow reselection of balls but we want to limit the reselection to $O(1)$ times.

$\endgroup$
9
  • $\begingroup$ So it's possible that any particular ball gets selected by more than one person? $\endgroup$ Nov 6, 2020 at 11:31
  • $\begingroup$ @GerryMyerson Yes. That is the tricky part. $\endgroup$
    – lchen
    Nov 6, 2020 at 11:50
  • $\begingroup$ What happens if e.g. a man and a woman select the same 3 balls? $\endgroup$
    – user44191
    Nov 6, 2020 at 17:46
  • $\begingroup$ My interpretation is that there is no guarantee of such a coloring; the algorithm only needs to return a solution if one exists. $\endgroup$ Nov 6, 2020 at 17:48
  • $\begingroup$ Yes on the existence of a threshold because eventually all the triples will be disjoint. $\endgroup$
    – Ben Barber
    Nov 6, 2020 at 18:08

2 Answers 2

1
$\begingroup$

It appears to me that you are essentially asking two questions that are independent:

Question 1. Is there an algorithm that finds a solution should one exists?

Question 2. Under what conditions on $M$ and $N$, there is guaranteed to be a solution w.h.p.?

I can exactly answer the first question, and provide some empirical data for the second one. Let me start with reformulation this problem.

Reduction to 2-SAT

A 'random selection' can be seen as a random instance of a constraint satifaction problem (CSP) with $n$ constraints and $m$ variables: Each ball corresponds to a Boolean variable $v_i$ that can attain one of two values (black or white), for simplicity I will use True (or 1) for black and False (or 0) for white. Each person corresponds to a constraint that involves 3 variables, the constraints then requires that at least two of the three variables are True or at least two of them are False. These two variant constraints can be formulated in a CNF as: $$ \beta(x, y, z) \equiv (x \vee y) \wedge (y \vee z) \wedge (z \vee x) $$ and $$ \upsilon(x, y, z) \equiv (\neg x \vee \neg y) \wedge (\neg y \vee \neg z) \wedge (\neg z \vee \neg x) $$ This essentially allows us to formulate an instance of this CSP as an instance of 2-SAT.

An efficient algorithm

2-SAT is a well-known tractable problem, so there is a lot of efficient algorithms. One can certainly be found in Schaefer's classification of Boolean CSPs (Schaefer, 1978), but any algorithm for 2-SAT will work here.

The key property of this problem, and consequently of your problem is that it can be solved by checking local consistency. More precisely, if there is a system $\mathcal F$ of partial solutions defined on at most 3-element subsets of variables (i.e., every $f\in \mathcal F$ is a function $f\colon X \to \{0, 1\}$ where $\lvert X\rvert \leq 3$ and $f$ satisfies any constraints on its values (the latter only applies if $X$ is the set of balls chosen by someone) such that:

  1. for each $X$ with at most 3 elements, there is $f \in \mathcal F$ with $\operatorname{dom} f = X$,
  2. for each $Y \subset X$ and $f \in \mathcal F$ with $\operatorname{dom} f = X$, the restriction of $f$ onto $Y$ belongs to $\mathcal F$, i.e., $f|_Y \in \mathcal F$; and
  3. for each $Y \subset X$ adn $g \in \mathcal F$ with $\operatorname{dom} g = Y$, there is $f\in \mathcal F$ with $\operatorname{dom} f = X$ and $f|_Y = g$.

(such a system is said to be consistent). Intuitively this consistency just requires that any of the function in $\mathcal F$ defined on $X$ is consistent with some other function defined on any given $Y$. One consistent system can be found by starting with the system of all partial solutions and inductively removing functions that invalidate (2) or (3). If at any point, we remove the last function with some domain $X$, there is no solution. This gives an algorithm which decides whether there is a solution.

For finding a solution there are a few tricks: one trick is to guess a value for some variable and repeat the decision algorithm to decide whether there is a solution using this value and repeat. This might require a few guesses for each value, but in your case any $f$ from an above system will extend to a full solution. (See Section 5.3 of (Barto, Krokhin, Willard, 2017) for more insights about 2-SAT.)

A test

To give some light on the second question, note that there is a lot of research on random CSP instances, see e.g. (Coja-Oghlan, 2009). Based on my quick search, it seems that these usually have a sharp transition in terms of the parameter $m/n$, i.e., there is a constant $\alpha$ s.t. if $m/n < \alpha$, then there is no solution w.h.p., and if $m/n > \alpha$, there is a solution w.h.p.. The below data might give some insights on what the threshold might be.

To get some idea about this threshold (if there is one), I used a SAT-solver (PicoSAT developped by Armin Biere) to empirically check what are chances that a random instance of the given CSP is satisfiable. Though this SAT solver is able to solve general SAT which is way harder than 2-SAT, none of my implementations of a theoretically more efficient algorithm were able to provide a solution in comparable times.

The code that I used is this:

import pycosat
import random

def man(x, y, z):
    yield (x, y)
    yield (y, z)
    yield (x, z)

def woman(x, y, z):
    yield (-x, -y)
    yield (-y, -z)
    yield (-x, -z)

def generate_instance(m, n):
    for i in range(n):
        scope = random.sample(range(1, m+1), 3)
        relation = random.choice((man, woman))
        yield from relation(*scope)

def test(m, n, repeat=100):
    positive = 0
    for i in range(repeat):
        solution = pycosat.solve(generate_instance(m, n))
        if solution != "UNSAT":
            positive += 1
    return positive

Roughly, the functions man and woman provide the translation to 2-SAT, and generate_instance(m, n) generates a random instance with m balls and n people. The probability of genders of these people is 50/50. The function test then generates and tests 100 random instances and counts the number of solvable ones.

Using this code I tested different fractions $n/m$ for $m \in \{10, 100, 1000, 10000\}$. The graph below shows the fraction of solvable ones. Each line corresponds to a fixed value of $m$. Looking at the graph, I think it is unlikely that a random instance with $n > m/3$ will have a solution. Hope this helps!

Fraction of satisfiable random instances for m = 10, 100, 1000, 10000

$\endgroup$
0
$\begingroup$

Not quite a full answer, but an observation. This problem gets easier to solve the larger the vat is. If there are only 3 balls in the vat then it is impossible to find such a coloring. If on the other hand there are $N^2$ balls in the vat where $N$ is the number of people then this should be easy for a random instance; each person will have 3 balls not shared with anyone else.

EDIT The threshold is $\theta(N)$, here $N$ is the number of people. If the number of balls is $(3+\epsilon)N$ then putting an edge between a man and a woman iff they share a ball, iff there exists a good coloring, then there exists a good coloring within each component. But then it looks like whp the size of the largest components would be only $O(\log N)$, using a similar line of reasoning that the largest cc in a graph $G$ drawn according to ER$(N,\frac{1-a}{N})$ is $O(\log N)$ for all $a \in \Omega(1); 0<a \le 1$.

If the number of balls is $cN$ with $c$ is some small constant say $c \le .1$, then with high probability there is no such coloring. Informally, let $S$ be the set of balls, and let $S_W$ be the set of balls picked by the women and let $S_M$ the set of balls picked by the men. Then $S_W, S_M$, and $S$ are almost the same set, with most balls picked about the same number of times by each gender. So then for there to be such a coloring, about 2/3 of the balls in $S_W$ would have to be white and about 2/3 of the balls in $S_M$ would have to be black. But then this makes impossible to simultaneously satisfy both conditions as $S_M$ and $S_W$ have such high-overlap.

$\endgroup$
7
  • $\begingroup$ Thank you for your comment Mike. $3N$ seems intuitive. What I really want to see is whether it is possible with $<2N$ balls, say $1.5N$. This may need some algorithmic operations. Note that we allow $O(1)$ rounds of reselection of balls, $\endgroup$
    – lchen
    Nov 7, 2020 at 1:52
  • $\begingroup$ In these subsequent rounds, does everyone have to partivipate, or only those unhappy with the coloring? i.e., can we keep parts of the colorimg and throw thevremaining balls back into the bin? $\endgroup$
    – Mike
    Nov 7, 2020 at 2:16
  • $\begingroup$ Everyone needs to participate. It's like we change the seed for random selection. $\endgroup$
    – lchen
    Nov 7, 2020 at 2:29
  • $\begingroup$ @Ichen OK. I will think about it this weeknd but this is what I am thinking now, maybe or maybe not this idea will hold up: Lets go w only 1 round for now I dont think trying $O(1)$ times will help. There hopefully are at least, after the balls are picked, an epsilon-fraction that are picked only by one gender. Color those balls white or black. In turn there will be a certain fraction of people who are already satisfied. Remove those people grom consideration... $\endgroup$
    – Mike
    Nov 7, 2020 at 4:09
  • 1
    $\begingroup$ Thank you Mike. I totally agree with you. What we need is to have a "proper" coloring with $O(1)$ prob. Probably we can map the problem as below. If we can prove that with $O(1)$ prob., there is no cycle (without counting the triangle), we can properly color the graph. If my reasoning is correct, the pb becomes whether it is possible with $1.5N$ to ensure no cycle exists. $\endgroup$
    – lchen
    Nov 7, 2020 at 5:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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