Most efficient algorithm to distribute n n-bit strings among n people

Question

We are given $n$ people, whom we identify with the elements of $[n]=\{1,\ldots,n\}$. We are also given a finite collection $\mathcal{K}$ of subsets of $[n]$. The problem is to (efficiently) construct a set $M$, together with a map $f$ which assigns to each person $x$ a subset of $M$, in such a way that for any subset $S\subset [n]$, the union $\bigcup_{x\in S} f(x)$ is equal to $M$ iff $S$ contains an element of $\mathcal{K}$.

This can also be interpreted as assigning to each person an $m$-long bitstring such that if you take a subset $S$ of the people, and bitwise-OR their bitstrings, you get the all-ones bitstring iff $S$ contains an element of $\mathcal{K}$.

The problem has a natural interpretation. Certain "special" groups of people are to be granted access to a resource. We want to pick an appropriate number $m$ of coupons, and grant an entity access to the resource iff the entity possesses at least one copy of each coupon. We also want to give each person a carefully chosen set of coupons, in such a way that the only groups of people who can access the resource are groups containing at least one of the special groups.

(Remark: in the original version of the question, $M$ was required to have $n$ elements, but that requirement was later dropped.)

Answer 1

Complexity issues aside, here is one method. Suppose we wanted to allow any group of people access except for one specific group $J\subseteq [n]$. We can do this by having a single coupon which we give to everybody not in $J$ (that is, assign the bitstring 0 to elements of $J$ and the bitstring 1 to the other elements). Of course this rules out subsets of $J$ as well, which is fine given our goal.

Now, given the collection $\mathcal K$ in the problem statement, define $\mathcal J$ to be the collection of all subsets of $[n]$ not containing an element of $\mathcal K$. For each $J\in\mathcal J$, create its own coupon as described above. In other words, to each person, assign a bitstring of length $\#\mathcal J$, where the coordinate corresponding to $J$ is assigned 0 precisely for the elements of $J$. This scheme will prevent any group in $\mathcal J$ from having access and will allow all the others; but "all the others" is precisely the groups containing an element of $\mathcal K$.

(Note that we don't need a coupon for every element of $\mathcal J$, but only one for each maximal element of $\mathcal J$ - that is, one for each element that isn't contained in some larger element of $\mathcal J$. That will cut down on the size of the bitstring significantly, although I can't offer offhand an analysis of that size nor the complexity of finding it.)

Answer 2

Here's a very straightforward solution; I haven't thought about whether it's the most efficient (in terms of keeping $m$ small).

Let $\mathcal{K}=\{K_1,\ldots,K_r\}$ be the "special" subsets, and let $M$ be the "direct product" of these subsets: that is, each coupon $M$ has a list of $r$ names, one person from each subset: $$M=\{ (k_1,\ldots,k_r) \mid k_i\in K_i\}.$$ (Some names may be repeated on some coupons, if the $K_i$'s happen to intersect.) The total number of coupons is the product of the sizes of the special sets; that is, $m=\prod_{i\le r} |K_i|$; a group has to have all of these coupons to access the resource.

Give each person a copy of every coupon that has their name on it. To see that this works: every coupon has the name of someone from group $K_i$ in the $i$-th position, so taken together, group $K_i$ has all the coupons. On the other hand, suppose $S\subset [n]$ is a collection of people that does not contain any $K_i$; i.e. for each $i$, there's some $k_i\in K_i\setminus S$. Then the coupon $(k_1,k_2,\ldots,k_r)$ is not held by anyone in $S$, so this scheme works.