> For concreteness, a game requiring 6 bits of information to identify the perfect matching will take 6 steps on average, and may sometimes require many more

I'm not following your logic. Consider the setup we actually have:

1. You get to ask a series of yes/no questions. (Ignoring the matchups.)

2. Each question can produce, in expectation, up to one bit of information.

3. In order to achieve this maximum expectation, it is mathematically necessary to use questions that invariably do produce exactly one bit of information, never more or less. If your questions do not have this property, they will in expectation produce less than the maximum amount of information, and your expected number of steps to the solution will increase, which contradicts your stated goal of minimizing that quantity.

You get the minimum number of steps needed in expectation by always using questions with maximum entropy. Yes. But those questions never have any variation in the amount of entropy they produce; a maximum entropy strategy can never take more - or fewer - steps than average.¹

¹ Unless the number of bits required to solve the problem is not an integer. Identifying one of three options requires 1.585 bits; in practice, this means that you'll get it after one question 1/3 of the time and after two questions the other 2/3 of the time. But identifying one of 128 options requires 7 bits, you'll always get it after 7 questions, and you'll never be able to get it after 6 questions. (Assuming you're using a strategy where the expected number of questions needed is 7.)

▲

dmurray 18 hours ago | parent | next [-]

You're correct but the complexity is in the things you're ignoring for simplicity.

This game is constructed such that the questions you can ask are not arbitrary, so you cannot choose them to always produce one bit of entropy (you need to frame your questions as ten matchups in parallel, using all the contestants exactly once) and the number of bits you need may indeed not be an integer.

Because you can't choose your questions to partition the state space arbitrarily, that affects not just the question you ask today, but also previous days: you want to leave yourself with a partitionable space tomorrow no matter what answers you get today.

In the Guess Who analogy, it's against the rules or at least the spirit to ask "does your character have a name which is alphabetically before Grace?". That would allow a strategy which always divides the state space exactly in two.

	▲	thaumasiotes 4 hours ago \| parent [-]
		> and the number of bits you need may indeed not be an integer. That's true but not relevant; needing a non-integer number of bits makes it possible for some games to end one turn faster than other games, but it doesn't make it possible for a maximum-entropy strategy to have more variation than that one maybe-necessary-maybe-not turn. The scenario described by my parent comment still isn't possible. > This game is constructed such that the questions you can ask are not arbitrary, so you cannot choose them to always produce one bit of entropy (you need to frame your questions as ten matchups in parallel, using all the contestants exactly once) You're confusing two types of questions. The question where you're targeting one bit of information is "are Matt and Felicia a match?", just one pair. A full proposed matchup of n pairs has n+1 possible answers and so your goal is to produce log₂ (n+1) bits. (Better conceptualized as one base-n+1 "bit".) I agree that it's not obvious how to do this or to what extent it's possible.

▲

akoboldfrying 16 hours ago | parent | prev [-]

> Unless the number of bits required to solve the problem is not an integer.

That is one case where root-to-leaf path lengths can vary, though it's not obvious to me that it exhausts all such cases -- in particular, even if we have "ideal leaves" (numbering a power of 2, and each equally likely), it's not clear that there is always a question we can ask that divides a given node's leaves exactly in half.