For a finite set, like A = {1, 2, 3}, clearly the super set has higher number of elements (in this case 8), so we can't define an injection from the superset to the original set. For an infinite set, like N = {1, 2, 3, .. }, it is not immediately clear whether we can (or not) define the injection from the superset of N (lets call it S(N)) to N. (So, I have just restated part of the OP!)

Interesting! Thanks for the link. Reading the wiki article exposes one assumption in my solution. I assumed that, while the super set has infinite number of elements, each individual element of the super set has a finite number of elements. In other words, I assumed that (for example), "the set of all even numbers" is NOT a member of super set.
If that assumption is removed, my solution won't work.

For finite sets it is easy to see that a bijection exists, if there are two injections, one from A to B, and other from B to A.
If f: A -> B is an injection from A to B and g: B -> A is an other injection from B to A, then the number of elements in A and B are both same. So, a bijection can be defined from A to B.
I googled a bit on this and read about SchrÃ¶derâ€“Bernstein theorem, which essentially asserts that if there are two injections in reverse directions, then a bijection exists.

karthikgururaj proposes two injections (both of which are far from being surjections also) rather than a single bijection.
So the question is, are two (one each direction) injections equivalent to a bijection?
I thought about this when posting the solution.. In truth, it doesn't appear to be an equivalent to bijection

Thanks, this is interesting
I'm going to agree with plasmid here.
While I'm not discounting plasmid's analysis (since I do not know the answer to this one), one point what you said above seems wrong to me:

@k-man and @DejMar: you have poked a few holes into my question
Let me clarify:
a. The numbers a1, a2, ..an and x, y can have duplicates. Each number is picked using a function like, rand(1, S), which gives a random integer in the specified range.
b. S is always even (this is the easiest way to escape the mid-point issue pointed out in your post). The first question is now modified as: "A. Guess whether the number I'm going to tell you now is (less than or equal to S/2) or (more than S/2)". I think S = 2 case must be allowed as well.
Would your responses change then?
@k-man, thanks for the wikipedia link - was interesting to read. It doesn't apply here (at least not directly) because we can have repeats - as you have pointed out yourself.

Let's see if there are any other thoughts
Is there any sort of probability distribution for Alice's margin of error? Can it be anything between 0 and infinity?
No.. nothing of that sort.. It is non-zero, most likely just "1", or at the max "2", if she is feeling generous.
Also, to clarify, your answer is the same as what I thought was right.

Let's see if there are any other thoughts
Is there any sort of probability distribution for Alice's margin of error? Can it be anything between 0 and infinity?
No.. nothing of that sort.. It is non-zero, most likely just "1", or at the max "2", if she is feeling generous.

Well, I suppose you could say that it implicitly relies on Bayesian analysis in a way that I just don't draw attention to in this approach.
My method is exactly the same. Both you and gavinksong came to the same conclusion, within few mins of each other.
@plasmid, it is Bayes' rule indirectly