Market Making the Population Guessing Game
You are making a market on the population of a country -- say, Indonesia. The interviewer knows the true population and will trade against you: if they think the true value is above your ask, they buy; if it's below your bid, they sell.
Your job is to quote a bid and ask, observe whether the interviewer buys or sells, update your estimate, and repeat. Each round, the interviewer's trade tells you something about where the true value lies relative to your quotes.
Rules:
- Your spread (ask minus bid) can be at most $20$ million at any point during the game.
- The interviewer always trades optimally -- they will buy if the true population is above your ask, sell if it is below your bid, and do nothing if the true value is inside your spread.
- You lose money on every trade: if they buy at your ask and the truth is higher, you are short at too low a price. If they sell at your bid and the truth is lower, you are long at too high a price.
Questions:
- What strategy should you use to set and update your bid-ask spread to minimize your total losses?
- How many rounds does it take to pin down the population to within your spread?
- What is your expected total loss under the optimal strategy?
Hints
- Think of each trade as a yes/no question: is the true value above or below your current midpoint?
- Binary search cuts the feasible range in half each round -- how many halvings do you need to get within $20M$?
- Center your spread on the midpoint of the remaining feasible range, and track your cumulative P&L as you update.
Worked Solution
How to Think About It: This is a classic desk interview game. The interviewer has a number, you have to find it, and every wrong guess costs you real P&L. The key insight: each trade is a binary signal. If they buy, the truth is above your ask. If they sell, the truth is below your bid. This is exactly binary search -- but with a twist: you pay for each "query" in the form of a spread crossing.
The practical instinct is: start with a wide range, center your market on your best guess, and use each trade to cut the remaining uncertainty in half. Each trade is a costly "query": when the interviewer trades, the truth lies beyond your quote, so your loss on that trade is the full distance from your trade price to the true value -- potentially a large fraction of the remaining feasible range. The narrower you can make the remaining uncertainty, the fewer rounds you need, and the less total P&L you bleed.
Key Insight: Each trade reveals whether the true value is above your ask or below your bid. If you center your spread on the midpoint of the remaining feasible range, each trade eliminates roughly half the remaining uncertainty -- classic binary search. Your loss on each trade is the distance from your quote to the truth, so the early trades -- when the feasible range is widest -- dominate your total loss.
The Method:
- Initialize: Start with a feasible range $[L, U]$ for the population. A reasonable prior for Indonesia might be $[100M, 400M]$, giving an initial range of $R_0 = 300M$. Set your midpoint $m = (L + U) / 2$ and quote bid $= m - 10M$, ask $= m + 10M$ (using the full $20M$ spread).
2. Observe the trade: - If the interviewer buys (hits your ask), the true value is above your ask: $m + 10M$. Update $L \leftarrow m + 10M$. - If the interviewer sells (hits your bid), the true value is below your bid: $m - 10M$. Update $U \leftarrow m - 10M$. - If the interviewer does not trade, the true value is inside your spread. You have pinned it down -- stop.
- Re-center: Set the new midpoint $m = (L + U) / 2$, quote bid $= m - 10M$, ask $= m + 10M$. Repeat.
- Termination: The feasible range after $k$ rounds is roughly $R_0 / 2^k + 20M$ (the $20M$ from the spread itself). You stop when the interviewer does not trade, meaning the truth is inside your $20M$ spread. With $R_0 = 300M$, after about $k = 4$ rounds the remaining range is $300/16 \approx 19M$, so your spread covers the entire feasible region. The game ends in roughly $4$-$5$ rounds.
- Loss per round: When the interviewer trades, the truth lies strictly *outside* your quotes, so your loss on that trade is the distance from your trade price to the true value -- which can be most of the remaining feasible range, not just half the spread. With a $300M$ prior range and centered quotes, the first trade misses by up to $\sim 140M$ (truth at the far end of the range) and by about $65M$ on average over a uniform prior. Because the feasible range roughly halves each round, subsequent expected losses shrink geometrically (about $26M$, then $7M$, and so on). Binary search minimizes the total by keeping you centered, but it cannot make the early trades cheap.
Practical Considerations:
- Starting estimate matters. If you have a decent prior (e.g., you know Indonesia is somewhere around $270M$), you can start with $[200M, 340M]$ instead of $[100M, 400M]$, saving $1$-$2$ rounds and reducing total loss.
- Asymmetric information. The interviewer knows the truth and trades optimally. You cannot "trick" them. Every trade costs you money. The goal is to minimize the number of trades.
- Spread width trade-off. A wider spread means less loss per round (the interviewer is less likely to trade, and when they do, your midpoint is closer to the truth). But the constraint caps you at $20M$.
- Don't get cute with asymmetric spreads. Centering on the midpoint of the feasible range is optimal for binary search. Shifting your quotes to one side wastes information.
Answer: Use binary search. Center your $20M$ spread on the midpoint of the feasible range, update the range based on each trade, and repeat. Starting from a reasonable prior range of $\sim 300M$, the game ends in about $4$-$5$ rounds. Your expected total loss is on the order of $100M$ in population units: a trade happens only when the truth is *outside* your quotes, so each trade costs the full distance from your trade price to the truth -- up to $\sim 140M$ (about $65M$ on average) on the first trade, with per-round losses roughly halving thereafter ($\sim 65M + 26M + 7M + \cdots \approx 95M$ in expectation, and above $200M$ in bad cases). The key is that each trade gives you one bit of information, and binary search is the information-theoretically optimal way to use it -- but the size of your loss is driven by how far the truth can sit beyond your quote in the early rounds, not by the spread width.
Intuition
This problem is really about information theory dressed up as a trading game. Each trade the interviewer makes reveals exactly one bit of information -- whether the true value is above or below your current market. Binary search is optimal because it extracts the maximum information per query: each trade cuts the remaining uncertainty in half. The $20M$ spread constraint is the "resolution" of your measurement instrument -- you cannot distinguish values closer than $20M$ apart, so that is where the game naturally ends.
In practice, this game shows up constantly on trading desks in a less formal way. Any time you are making a market on something uncertain -- an illiquid bond, a bespoke derivative, a stat arb signal -- and a better-informed counterparty trades against you, you are playing this game. The lesson is the same: each trade they do tells you something, and your job is to update efficiently and minimize the total cost of learning. The traders who survive are the ones who update fast and keep tight mental "feasible ranges" for where fair value sits.