 Solution

For each user define its set of eligible ads byThis uses the intersection of demographic-group memberships: belonging to one advertised group suffices, because the eligibility condition is a set union. A user in several groups still receives at most one ad.

A direct algorithm is to process users independently. For user $u_i$, scan ads $a_j$ until finding one for which some group $S_{\ell }$ belongs to both ${\mathcal{S}}^i$ and ${\mathcal{S}}_j$. Assign that ad and stop processing this user. If no such ad exists, leave the user unassigned. There is no upper bound on the number of different users who can receive the same ad, so these decisions do not compete for an ad resource.

For correctness, every produced impression has a shared permitted group, and the stopping rule assigns at most one ad to each user. Conversely, a user with $E_i=\varnothing$ cannot receive an ad in any feasible solution. Since every other user can contribute at most one impression, every feasible solution has value at mostThe algorithm attains this bound, provingRepresent each membership set by a length-$k$ array of Boolean variables. Testing one user-ad pair costs $O(k)$, so all tests and input setup take $O(nmk+(n+m)k+n+m+k)$ time in Big O notation, which is polynomial time in all three parameters. For positive $n,m,k$, this simplifies to $O(nmk)$.

A maximum flow formulation gives the same result if desired: add edges $s\to u_i$ with flow network edge capacity $1$, $u_i\to a_j$ with flow network edge capacity $1$ exactly when $j\in E_i$, and $a_j\to t$ with flow network edge capacity $n$. By the integral max-flow theorem, an integral maximum flow selects valid impressions. Setting the last flow network edge capacity to $1$ would impose an extra restriction absent from this paper.