Fairness in a Sealed-Bid Allocation
A club of 10 members must choose 3 to sit on a committee. A randomization scheme is proposed: each member independently flips a fair coin, and if exactly 3 heads appear those 3 form the committee; otherwise the process restarts. A member objects that this favors some members because 'coins don't know about fairness.' Separately, the club considers a second scheme: draw 3 names without replacement from a hat. A third proposal: each member submits a sealed bid (a real number), and the 3 highest bidders win, with ties broken randomly.
1. Compare the probability each member is selected under the coin scheme versus the hat scheme.
Read the worked answer
Coin scheme conditioned on exactly 3 heads: by symmetry each member has equal probability, and the conditional distribution is uniform over all 3-subsets because every specific 3-subset has probability (1/2)^3(1/2)^7=(1/2)^10, identical for all subsets. So P(selected) = C(9,2)/C(10,3) = 36/120 = 3/10, same as the hat. The member's objection is unfounded: conditioning on a symmetric event restores symmetry.
2. Compute the acceptance probability of the coin scheme per round and comment on efficiency.
Read the worked answer
P(exactly 3 heads) = C(10,3)/2^10 = 120/1024 ≈ 0.1172. Expected rounds to success ≈ 1/0.1172 ≈ 8.5. The scheme is unbiased but inefficient; the hat draw achieves a uniform 3-subset in one step.
3. Does the sealed-bid scheme select a uniformly random 3-subset?
Read the worked answer
Not in general. If bids are fixed (deterministic), the top 3 are determined, so the outcome is a single subset with probability 1 - far from uniform. Randomness enters only through tie-breaking, which helps only when bids tie. So the sealed-bid scheme is not equivalent to random selection unless bids are themselves random and exchangeable. Fairness requires either explicit randomization or a symmetric bid distribution, not merely the appearance of a procedure.