Finding out a set by intersection comparison
This is a variation of the famous puzzle of finding a counterfeit coin by using the balance.  But before proceeding to that, first let’s solve the question, because the technique in solving it is also useful to see the connection to the counterfeit coin problem.

First, suppose that the query sets A and B do not have to be from the family F.  Then you can find the set S by at most $\binom{n}{2}=O(n^2)$ queries as follows.  Make $\binom{n}{2}$ queries ({a}, {b}) for 1≤a&lt;b≤n.  Note that every element i∈{1,…,n} is used in n−1 queries.  If an element i belongs to S, then the set {i} is answered at least when the opponent does not belong to S, and therefore the set {i} is answered at least n−t times.  If an element i does not belong to S, then the set {i} cannot be answered if the opponent belongs to S, and therefore the set {i} is answered at most n−t−1 times.  Therefore, counting how many times each set is answered, we can determine the whole set S.

This requires query sets not from the family F, which is not allowed in the problem.  But we can work around this by adding the same t−1 elements to both sides.  For example, instead of making the query ({1}, {2}), we can make the query ({1,3,4,…,t+1}, {2,3,4,…,t+1}).  Therefore, the problem can be solved by O(n2) queries.

Now fun part begins.  Consider n coins labeled 1,…,n, and t of them are counterfeits and slightly heavier than the real coins.  All the counterfeit coins have the same weights.  You have to find the set S of the labels of the t counterfeit coins by using a balance only poly(n) times.  Every time you use a balance, you can put at most min{t, n−t} coins to each side of the balance.  The balance is slightly inaccurate in the sense that if the two sides have the same weight, either side can go down (adversarially).  As I hope that you can see by now, this is exactly the same problem as the question.

Edit: Revision 4 and earlier had one error or another (oops) in the precise connection to the counterfeit coin puzzle.