What a joy it is to stumble upon a seminal paper—then realizing it’s by someone you’ll get to know in the future. Moments like these make research feel like a small, interconnected world:
The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes
Eric Budish link
This paper proposes a new mechanism for combinatorial assignment—for example, assigning schedules of courses to students—based on an approximation to competitive equilibrium from equal incomes (CEEI) in which incomes are unequal but arbitrarily close together. The main technical result is an existence theorem for approximate CEEI. The mechanism is approximately efficient, satisfies two new criteria of outcome fairness, and is strategyproof in large markets. Its performance is explored on real data, and it is compared to alternatives from theory and practice: all other known mechanisms are either unfair ex post or manipulable even in large markets, and most are both manipulable and unfair.
Some of the fairness concepts proposed in the following paper—like EF1 (envy-freeness up to one item) and minimax fairness—have since become central ideas in algorithmic game theory and fair division research.
One day I’ll definitely (have to) read it carefully write a proper deep dive into this. For now, goodnight.