Estimating the mean of a random variable from greater than/less than answers Let $X_1,\dots,X_n$ be $n$ i.i.d. samples from a certain probability distribution (e.g, a normal distribution).
Your goal is to estimate the mean of the distribution.
However, you are not allowed to see the samples themselves.
You are allowed, in each time-step $t$, to select a number $Y_t$. 
Then, you are told whether $X_t>Y_t$ or $X_t<Y_t$ or $X_t=Y_t$.

How would you select the numbers $Y_t$? 
And how would you use the answers to estimate the mean?

(As a practical application, consider a person who sells a certain item and wants to estimate the average value of this item in the eyes of potential buyers. The real values are the $X_t$, but the seller cannot see them directly. In each time-step, the seller sets the price of the product to $Y_t$. Then, a buyer comes. If $X_t>Y_t$ then the buyer buys the item, otherwise the buyer just says "it's too expensive for me" and walks away. So the seller wants to estimate the average value based on this yes/no information). 
 A: Here is my take on this question. I will assume that:


*

*$X_i \sim \mathcal{N}(\mu, \sigma^2)$, and the $X_i$'s are independent

*$\mu$ is unknown

*$\sigma^2$ is known (I'll discuss this assumption later.)


Part 1: ML estimation given some data
First, consider the case where we are given some data, and we want to estimate $\mu$. Denote the data by $\mathcal{D} = \{ (y_i, t_i) \mid i = 1, \ldots, n \}$, where $y_i \in \mathbf{R}$ and
$$
t_i = \begin{cases}
1 & \text{if $X_i$ > $y_i$} \\
0 & \text{otherwise}
\end{cases}
$$
Note that I use a lowercase letter for $y_i$ to emphasize that it is a value that we can observe, as opposed to $X_i$.
We have
$$
P(t_i = 1 \mid y_i) = P(X_i > y_i) = \Phi\left( \frac{\mu - y_i}{\sigma} \right)
$$
and the likelihood of $\mu$ given the data is
$$
\ell(\mu ; \mathcal{D}) = \prod_{i=1}^{n} \left( \Phi\left( \frac{\mu - y_i}{\sigma} \right) \right)^{t_i} \left( 1- \Phi\left( \frac{\mu - y_i}{\sigma} \right) \right)^{1-t_i} \qquad (*)
$$
This function is log-concave, and has a unique maximizer if there is at least one $i$ such that $t_i = 1$, and at least one $i$ such that $t_i = 0$.
Furthermore, I suspect that the maximizer is independent of the value of $\sigma^2$ (to be checked).
Part 2: Active learning
I think this is the more interesting part. Here, we'll assume that you start with $\mathcal{D} = \varnothing$, and you want to iteratively pick a value $y_i$ and observe the corresponding $t_i$, in such a way that you "learn the most" about $\mu$.
There are many ways to go about this; in the following I'm taking a bayesian approach. We start by assuming a prior distribution on $\mu$, say
$$
\mu \sim \mathcal{N}(0, \tau^2)
$$
Given some data $\mathcal{D}$, your knowledge about $\mu$ is contained in the posterior distribution
$$
p(\mu \mid \mathcal{D}) \propto p(\mathcal{D} \mid \mu) p(\mu) 
$$
Unfortunately, this posterior is not analytically tractable for the likelihood given above $(*)$. One practical way to bypass this problem is to approximate the posterior with a Gaussian distribution that is "closest" to the true posterior, in some sense. In particular, Expectation propagation and the Variational Gaussian approximation come to mind.
One way to go about picking a value that leads to a lot of "information" about $\mu$ is to greedily maximize the expected reduction in the entropy of the posterior. Informally, the entropy of the posterior tells you how "unsure" you are about the value of $\mu$, and you'll want to pick a $y_i$ that is likely to reduce this uncertainty (I say "likely" because it will depend on the outcome $t_i$).
In this particular case, as we are just estimating a single parameter, reducing the entropy can be understood to be simply reducing the variance of the posterior.
Conjecture. let $p_i$ be the posterior on $\mu$ after $i$ steps (in particular, $p_0 = \mathcal{N}(0, \tau^2)$).
Then, the point $y_{i+1}$ that maximizes the expected reduction in posterior entropy is given by
$$
y_{i+1} = \mathbf{E}_{p_i}(\mu)
$$
Basically, my conjecture is saying: just sample at your current best guess for $\mu$!
Again, I believe that the assumption that $\sigma^2$ is fixed is not too important. I have the impression that what matters really is the ratio $\tau^2 / \sigma^2$. (This is again to be checked.)
