Selecting elements from overlapping sets in any order without repetition

Question

(there are examples below in this question, which probably explain it all better)

Consider a finite set $R = \{1, 2, ..., N\}$ and a tuple of sets $Q = (S_1, S_2, ..., S_M)$, which are possibly non-empty overlapping subsets of $R$, which can repeat, that is: $\forall i \in \{1, 2, ..., M\} S_i \subseteq R, S_i \neq \emptyset$. It can also be assumed, that union of the sets is $\bigcup_{i\in\{1...M\}} S_i = R$, because we are not interested in unused points of $R$. (Also, for simplicity lets assume $M=N$).

Now, consider a procedure of taking elements of $Q$ in any order from the tuple, and with each taken element on $j$th step - $S_{q_j}$ - we select one element $x_j \in S_{q_j}$, which was not used on any previous steps. I can define it formally by adding a series of growing sets and take $x_j$ from $ S_{q_j} \cap U_{j-1}$, where $U_{j-1}$ will be by definition set of all elements selected before step $j$. But it's more important: elements from $R$ are taken without repetition. So, for each of $M!$ different selections we can define at least one function $f: \{1, ..., M\} \to R$ to reflect the choices.

Now, the problem is: Given $R$ and $Q$, how to determine whether there exists a function $f$, which is defined for all it's inputs?

An example. For a situation where we have $R=\{1, 2, 3\}$ and $Q=(\{1\}, \{2\}, \{3\})$ such a function can be trivially build no matter in what order the sets of $Q$ are selected - it's identity function from $R$ to $R$. With $R=\{1, 2, 3\}$ and $Q=(\{1, 2, 3\}, \{1, 2, 3\}, \{1, 2, 3\})$ there are several function, no matter in which order sets are selected or elements from those sets are selected.

Lets consider even simpler case $R=\{1,2\}$ and $Q=(\{1, 2\}, \{2\})$. Now, the answer is "no": there are situations, when we will not be able to select an element. For example, if $\{1, 2\}$ is selected first, and $2$ selected as $x_1$ - then when we select $\{2\}$, there will be nothing to select as $2$ has been already used.

First of all, I am sure the exact same model I describe above is not my invention, and it is called somehow and has some real-life applications. Any pointers? Is it from operational research, optimization problems? I described set representation above, but before I posted it here I studied it with matrix representation and graph theory representation.

We can imagine $R$ is a set of resources, which can't be shared, and $Q$ as consumers, which require any available (not yet used) resource from $S_i$, and consumers can come in any order to grab resources.

The question then can be formulated as, what is the condition there will be no situation a consumer will be left without a resource, no matter in which order consumers will claim the remaining resources.

Another question is, how to remove a minimal number of resources from some consumers so, that with the new $Q$ consumption will always be possible? For example, in our negative case above the measure is simple: We can remove $2$ from the first consumer and get $Q'=(\{1\}, \{2\})$, which works.

Quick researching that problem and around it was very interesting (it is even possible to formulate it as a game), structures involved are not trivial, so I am very curious to find what I reinvented.

Another possible application as I see it can be avoidance of deadlocks in concurrent software, where processes grab resources in arbitrary order and some processes may be left without resources. Also maybe resource allocation in cellular networks may be relevant.

Formulation in matrices:

$Q$ can be represented by a matrix with $M \times N$ (we consider square case here though) by encoding subsets, using our negative example from above:

$P = \begin{pmatrix}1 & 1\\\ 0 & 1\end{pmatrix}$

The procedure then can be explained like this: Given problem matrix P, find any non-zero element and remove corresponding column and row. If there is any way (by selection of elements) repeated procedure comes to a matrix with all zeros, we have negative case. In the example above it can be clearly seen that removing first row and second column leads to a matrix with all zeros of size $1\times 1$. It can also be noted, that arbitrary reordering of the rows and columns does not affect the end result, so decomposing matrix to block-diagonal form allows to solve the problem for each block independently.

I've not yet proved this, but it seems that in that case each block must be a matrix of ones - at least I am unable to find any counterexamples. This explains our two positive examples above, because they correspond to $3 \times 3$ matrix of ones and a block-diagonal matrix with 3 blocks of size $1 \times 1$:

$P' = \begin{pmatrix}1 & 1 & 1\\\ 1 & 1 & 1\\\ 1 & 1 & 1\end{pmatrix}$

and

$P'' = \begin{pmatrix}1 & 0 & 0\\\ 0 & 1 & 0\\\ 0 & 0 & 1\end{pmatrix}$

And if we use graph representation, this means that our consumer-resource bipartite graph should actually consist of one or more bicliques. The matrices $P$ above then can be understood as biadjacency matrices. I wonder if bipartite network projection technique may bring insights to this question (there are useful articles cited there), but still I've not found any known class of bipartite graphs with the property described here!

My problem is somehow connected to Maximum bipartite matching problem (see eg this question/answer). Namely, how to reduce edges of "consumer-resource" bipartite graph so that perfect matching will happen regardless of the order, in which consumers come to select their resources.

Update after first answer for those whose search end up in this question: Some practical algorithmic considerations for SDR, transversals, and term rank of (0,1)-matrices - in Systems of Distinct Representatives and Linear Algebra by Jack Edmonds

Answer 1

What you are looking for is called a system of distinct representatives. You can simplify the notation a little if you forget about the ordering of the subsets and the elements. You want a function $f: Q \rightarrow R$ so that $f(S) \in S$ for all $S\in Q$, and f is one-to-one.

Note that if such an $f$ exists, then for any subfamily $Q' = \{S_{i_1}, S_{i_2}, \ldots, {S_{i_k}}\}$ we have that $f(Q') = \{f(S_{i_1}), \ldots, f(S_{i_k})\}$ are $k$ distinct elements of $\bigcup Q':= S_{i_1} \cup S_{i_2} \cup \ldots \cup {S_{i_k}}$ so $|\bigcup Q'| \geq k = |Q'|$. Hall's Marriage Theorem says that, perhaps surprisingly, the converse is also true:

A system of distinct representatives for a family of subset $Q$ exists if and only if $$\left|\bigcup Q'\right| \geq |Q'|$$ for every subfamily $Q' \subseteq Q$.

The condition that $$\left|\bigcup Q'\right| \geq |Q'|$$ for every subfamily $Q' \subseteq Q$ is called the marriage condition. The theorem gets its name from a cute application. Quoting from Wikipedia:

The standard example of an application of the marriage theorem is to imagine two groups; one of $n$ men, and one of $n$ women. For each woman, there is a subset of the men, any one of which she would happily marry; and any man would be happy to marry a woman who wants to marry him. Consider whether it is possible to pair up (in marriage) the men and women so that every person is happy.

If we let $A_i$ be the set of men that the $i$-th woman would be happy to marry, then the marriage theorem states that each woman can happily marry a man if and only if the collection of sets $\{A_i\}$ meets the marriage condition.