The Workshop Lottery
A middle school runs a Friday enrichment fair with 12 workshops, each capped at 20 students, for 240 students. Each student ranks three workshops. The registrar writes a greedy program: process students in alphabetical order and give each their highest-ranked workshop that still has a seat. After running it, 31 students receive no assignment, even though 31 seats remain empty. The unassigned students are disproportionately those with last names late in the alphabet. The principal asks whether a different alphabetical ordering or a small patch to the greedy rule would fix the inequity, or whether the problem needs a different algorithm.
1. Explain how 31 students can be unassigned while 31 seats remain empty. What does alphabetical processing have to do with it?
Read the worked answer
Greedy processing commits each seat permanently at the moment a student is considered. Early students take seats in popular workshops. Later students may have all three of their ranked workshops already full, even though other workshops still have open seats that those students did not rank. Those open seats are therefore unusable under the stated rule, producing the simultaneous 31 unassigned students and 31 empty seats.
Alphabetical order matters because it decides who gets to claim scarce seats first. Surname order is unrelated to need or preference intensity, so the rule systematically favors early names. The inequity is not caused by a bug in the seat check; it is caused by an arbitrary priority order combined with irreversible commitments. Changing the order would just shift who loses, not whether someone loses.
2. Model the assignment as a graph problem and describe an algorithm that maximizes the number of assigned students. Explain why it avoids the failure above.
Read the worked answer
Build a bipartite graph: a source connected to each student with capacity 1, each student connected to each workshop they ranked with capacity 1, and each workshop connected to a sink with capacity 20. A maximum flow assigns the largest possible number of students while respecting both student and workshop capacities.
The key difference is that flow algorithms can reassign. If a later student needs a seat held by an earlier student, an augmenting path can move the earlier student to another ranked workshop and give the seat to the later one. Greedy never reconsiders, so it can get stuck. Maximum flow is order-independent and therefore removes the alphabetical bias. For 240 students and 12 workshops, the graph is tiny; a standard max-flow or bipartite-matching implementation runs instantly. The principal should also check whether a perfect assignment is possible at all, since conflicting preferences can leave some seats unusable.
3. The principal proposes: after the greedy run, let each unassigned student choose any workshop with an open seat. Evaluate this patch. When would it help and when would it still fail?
Read the worked answer
The patch helps only if the open seats happen to be acceptable to the unassigned students. If a student is willing to attend an unranked workshop, the patch can fill seats and reduce the unassigned count. But it fails on several grounds.
First, it may violate the original preference constraint, so the resulting assignment is not comparable to one produced under the three-choice rule. Second, it does not recover seats that could have been freed by moving an earlier student to another ranked workshop; those reassignments might have given the unassigned student a ranked choice. Third, it leaves the equity problem intact: early-alphabet students still received preferred workshops, while late-alphabet students absorb the leftover options. A better patch is to treat the greedy result as a starting point and run augmenting paths to improve the assignment, then use leftover seats only as a controlled fallback with clear consent.