How much information can you transfer by choosing one number out of two? Alice and Bob are playing a game. Alice (A) and Bob (B) agree on a protocol before the game starts.

Alice gets two uniformly random integers (without duplicates) from 1 through $n$, chooses one of the two numbers, and communicates it to Bob. Bob doesn't get to see anything other than the number that Alice chose (and he knows the maximum $n$, which is fixed for the game).

How many bits of information $b(n)$ can possibly be transmitted per number on average, if Alice and Bob play this game for a sufficiently long time?

$b(2) = 1$ is quite obvious, but even $b(3)$ is a difficult to reason about.

One protocol I came up with is that A always output $3$ for inputs $\{1, 3\}, \{2, 3\}$, and output $1$ or $2$ to transfer $1$ bit of information when the input is $\{1, 2\}$. This gets an average transmission rate of $\frac{1}{3}$ bits per number. But I have no idea how to generalize this to bigger $n$ or whether it's even optimal.
For large $n$ we can approach an efficiency of $0.188$ bits per symbol, in the following way:

In the protocol Alice can send a bit to Bob either "reliable-but-slow" or "fast-but-unreliable".

In reliable but slow mode, Bob ignores all symbols other than $0$ or $1$, and Alice simply waits until she gets a pair that allows her to send the symbol she needs. This takes $n/2$ symbols on average.

In fast but unreliable mode, Alice sends any even number for $0$ and any odd number for $1$.  One fourth of the bits she sends will be garbled because she doesn't have a number of the right parity to send.

Alice and Bob agrees in advance on a block size $b$, and the communication starts when Alice has accumulated $b$ bits to send. She sends them using fast-but-unreliable mode. Alice knows which bits went wrong, so she computes a correction sequence that Bob should XOR what he got with in order to get the real message. The bits in the correction sequence are not uniformly distributed: $0$ is three times as common as $1$. Therefore Alice can compress it using arithmetic coding to a length of about $0.811$ of the original $b$ (namely $-\frac34 \log_2(\frac34) - \frac14 \log_2(\frac14)$).

Alice uses reliable-but-slow bits to tell Bob the exact length of the compressed correction sequence, and now sends it using the same procedure as the original block -- that is, with its own correction sequence following, etc.

When the compressed corrections sequence is shorter than some prearranged length, Alice switches to sending it in reliabe-but-slow mode.

Analysis. When $b$ is large, the expected number of fast-but-unreliable symbols sent is
$$ b + 0.811b + 0.811^2b + 0.811^3b + \cdots = \frac{1}{1-0.811} b $$
There will be on the order of $\log b$ nested correction sequences, each needing up to $\log b$ reliable-but-slow bits to encode their lengths. So all in all in the reliable-but-slow phases use about $\frac n2 (\log^2 b+C)$ symbols, where $C$ accounts for the final reliable-but-slow corrections sequence).

For each particular $n$, by choosing $b$ large enough, Alice and Bob can make the $\frac n2 (\log^2 b+C)$ as small compared to $\frac{1}{1-0.811} b$ as they want! So in the limit of large $b$ they ought to achieve $1-0.811 = 0.189$ bits per symbol.



If $n\le 10$, the reliable mode is actually faster than the asymptotic behavior here, and should be used instead.



I suspect this might be asymptotically optimal for large $n$. I tried variants, such as decreasing the error percentage of the "fast" mode at the expense of speed by assigning a fraction of the $n$ symbols as "ignore this symbol" markers instead of letting all of them encode actual bits. But it looks like that always results in worse overall performance.
Alice divides the integers 1 through n into two distinct subsets T and F (for example T = numbers &lt;= n and F = numbers > n, or T = even numbers and F = odd numbers). If n is even then there are n/2 numbers in each subset, if n is odd then she has two sets with n/2 numbers plus an extra number (which can be considered to be the sole element of a third set O).

To transmit TRUE she sends a number from set T if possible, otherwise  from O if possible, otherwise from F if both her numbers are in that set. To transmit FALSE she does the opposite.

Bob assumes any T number is TRUE, and F number is false, and any O number carries no information.

For n = 2, 3, 4, 5, 6, 7... the number of transmitted bits is 1, 2/3, 2/3, 3/5, 3/5, 4/7, 4/7... . I think the pattern is obvious. For sufficiently large n, the limit is 1/2 bits per transmission.