Given $n$ subsets $S_1,\ldots,S_n$ of $\{1,\ldots,d\}$.
Check whether there are sets $S_i,S_j$ with $S_i \subsetneq S_j$. (If so, find an example, if not, simply say "no")
The trivial solution to this problem goes through all pairs of sets and checks inclusion for a pair in time $O(d)$, so the overall runtime is $O(n^2 d)$. Can this problem be solved faster? Is there a name for it in the literature?
You cannot solve it in $O(n^{2-\epsilon})$ time for any constant $\epsilon>0$ unless the Strong Exponential Time Hypothesis is false.
That is, if we had such an algorithm, we could solve $n$-variable CNF Satisfiability in $O((2-\epsilon')^{n})$ time for some $\epsilon'>0$. The reason is that we could divide the variables in two equal parts $P_1$ and $P_2$ of $n/2$ variables each. For each part we construct a family $F_1$ and $F_2$ respectively of subsets of the clauses in the following way. For each assignment we add a subset consisting of the clauses not satisfied by the assignment. This construction runs in $poly(n)2^{n/2}$ time.
To finish the construction, we note that the original CNF instance has a solution iff there is a subset in $F_1$ which is disjoint to some subset in $F_2$.
Adding some extra elements to your ground set in addition to the ones for each clause, it is not too hard to embed this disjointness problem as a question of set inclusion. You basically take the complements of the subsets in $F_1$. To make sure two sets in $F_1$ isn't counted as an inclusion you add a code from an anti-chain on the extra elements. Another anti-chain code (on other extra elements of the ground set) is used on the subsets of $F_2$ to make sure no pair of subsets from $F_2$ form an inclusion. Finally, all sets formed from $F_1$ includes all elements of $F_2$'s anti-chain codes.
This is a set inclusion question on $2^{n/2+1}$ subsets on a $d=poly(n)$ ground set. The argument basically goes back to some early paper of Ryan Williams (can't remember which).
If you're interested in set families with $n = \omega(2^{d/2})$, then an another solution conceptually very similar to the one outlined in Yuval's answer is to compute zeta transform
$$f\zeta(T) = \sum_{S \subseteq T} f(S)\,,$$
where $f \colon 2^{[d]} \to \mathbb{R}$ is the indicator function of the input family $\mathcal{F} = \{ S_1, S_2, \dotsc, S_n \}$. That is, $f(S) = 1$ if $S \in \mathcal{F}$ and $f(S) = 0$ otherwise. Clearly there are sets $S_i \not= S_j$ such that $S_i \subseteq S_j$ if and only if $f\zeta(S) > 1$ for some $S \in \mathcal{F}$.
The zeta transform can be computed in time $O(d2^d)$ using Yates's algorithm, see for example Knuth's TAOCP, vol. 2, §4.6.4. The algorithm itself is a fairly straightforward dynamic programming, and it is easy to modify it to give an example of an included set if one exists.
This problem can be solved by using an algorithm for fast matrix multiplication, and I also suspect it is computationally equivalent to matrix multiplication (although I don't know of any way to prove this, and I don't think techniques for proving this exist). This solution would have a running time of O(n^{2.373}) when n=d, and other running times for other relations between d and n.
Here is how you solve it using matrix multiplication: You write the characteristic vectors of the sets in the rows of an n by d matrix A, and the characteristic vectors of the complements of the sets in the columns of a d by n matrix B. You then multiply A by B. The pairs of sets that intersect are exactly the locations of the product A*B that are equal to zero.
For the best running time known for this problem, see the paper of Huang and Pan on the subject. If I remember correctly, when d becomes large enough, the running time will become the obviously-optimal O(nd). For n=d, you'll have a running time of O(n^{2.373}). For other relations of n and d, you will get other values. If an optimal algorithm for rectangular matrix multiplication exists, you'll will get an algorithm with running time O(n^2+nd) for your problem. I suspect there is no better way than this to solve your problem, but I am far from sure.
This solution is probably not of practical use, since the constants of these algorithms is too large. Strassen's algorithm might give an improvement over the naive solution for reasonable values of n and d, but I'm not even sure about that. However, problems that seem so related to matrix multiplication seem to rarely have combinatorial algorithms that are better than the naive algorithm (by more than polylogarithmic factors), so if I had to guess, I would guess that there's no good algorithm for your problem that is significantly better than the naive one, using current-day techniques.
If $n > \binom{d}{d/2} \approx \frac{2^d}{\sqrt{\pi d/2}}$ then we know that the set is not an antichain by Sperner's lemma, and so the decision version of the problem becomes trivial. But it might be interesting to consider the case where $n$ is close to that value.
Friedgut's work on the Erdős-Ko-Rado theorem shows that given the characteristic vector $f$ of a family of subsets of $[m]$, one can find in time $O(m2^m)$ whether $f$ is an intersecting family (every two elements of $f$ intersect). More generally, his method allows us to compute $$ \Sigma = \sum_{x,y \in f} S(x,y), $$ where $S(x,y) \geq 0$ is some (specific) known function which is non-zero only if $x,y$ are disjoint. $S(x,y)$ depends only on the histogram of $\{(x_i,y_i) : i \in [d]\}$, where $x_i$ is the indicator for $i \in x$.
(As an aside, we comment that his method also works if we are given two families $f,g$, and are interested in $\Sigma = \sum_{x\in f, y\in g} S(x,y)$. In both cases, we need to compute the $p$-skewed Fourier-Walsh transforms of $f,g$ for an arbitrary $p \in (0,1/2)$, and then $\Sigma = \sum_x T(x) \hat{f}(x) \hat{g}(x)$, where $T(x)$ depends only on the Hamming weight of $x$.)
How does all this relate to the problem at hand? Consider the family $$ F = \{ S_i \cup \{x\} : i \in [n] \} \cup \{ \overline{S_i} \cup \{y\} : i \in [n] \}. $$ Every $S_i \cup \{x\}$ is disjoint from every $\overline{S_i} \cup \{y\}$. Since $S(x,y)$ is given explicitly, we can compute the contribution of these pairs to $\Sigma$. Are there any more disjoint pairs? If $S_i \cup \{x\}$ is disjoint from $\overline{S_j} \cup \{y\}$ then $S_i \cap \overline{S_j} = \emptyset$ and so $S_i \subseteq S_j$. So $S_1,\ldots,S_n$ is an antichain iff $$ \Sigma = \sum_{i=1}^n S(S_i \cup \{x\}, \overline{S_i} \cup \{y\}). $$
This algorithm runs in time $\tilde{O}(n + 2^d)$, ignoring factors polynomial in $d$. When $n$ is close to $2^d$, this is significantly better than $\tilde{O}(n^2)$. In general, we get an improvement as long as $n = \omega(2^{d/2})$.
Given that we know that a pair satisfying $S_i \subseteq S_j$ exists, how do we find it? Suppose we divide all sets $S_1,\ldots,S_n$ into two groups $G_1,G_2$ at random. With probability roughly $1/2$, the sets $S_i$ and $S_j$ will find themselves in the same group. If we are so lucky, we can run our algorithm on $G_1$ and $G_2$, find in which one do these belong to, and so halve the number of sets we need to consider. If not, we can try again. This shows that with an expected number of $O(\log n)$ oracle calls to the decision version, we can actually find a pair satisfying $S_i \subseteq S_j$.
We can also derandomize the algorithm. Without loss of generality, suppose $n = 2^k$. In each step, we partition according to the each of the $k$ bits. One of these partitions will always put $x$ and $y$ in the same part, unless they have opposite polarities; we can test for this explicitly using only $O(nd)$ operations. This gives a deterministic algorithm using $O(\log^2 n)$ oracle calls to the decision version.
