Website CV Paper
Fields
Theory
Job market paper
The Power of Sperner’s Lemma in Fair Division
This paper develops a general approach to fair and efficient division that does not rely on equilibrium existence. First, I show that when the set of feasible allocations is compact, convex, and invariant to permutations of agents, and utilities are continuous and concave, there exists an allocation that is envy-free and weak Pareto efficient. The result applies to both problems with divisible resources and to indivisible-resource problems after appropriate convexification. In particular, it applies to problems with infinite-dimensional allocation spaces. The proof searches over Pareto weights and uses a regularized weighted welfare problem together with Sperner's lemma to identify weights at which all agents are simultaneously envy-free. Second, the same construction yields a computational counterpart: in finite-dimensional environments, stopping the Sperner procedure at finite resolution produces approximately envy-free and approximately weak Pareto-efficient allocations in polynomial time for a fixed number of agents, under suitable computational-access assumptions. Third, I combine the infinite-dimensional existence result with the finite-dimensional algorithm to allocate fairly, efficiently, and dynamically. The problem of fairness and efficiency of dynamic allocations arises in transportation, infrastructure, natural-resource management, computing, and has been extensively studied in computer science and engineering. Yet these problems cannot be tackled by present-day economic fair-division techniques. I approximate infinite-horizon environments by increasingly rich finite-dimensional truncations and apply the algorithm to each truncation. The approximation error separates into an algorithmic component and a truncation component, which can be controlled independently. Because the computational cost grows polynomially with the finite-dimensional problem size for a fixed number of agents, this approximation scheme remains computationally meaningful as the horizon expands. Applications include transportation capacity, renewable-resource extraction rights, and computing capacity.