Skip to main content

Research

Job Market Paper

The Power of Sperner’s Lemma in Fair Division

Abstract: 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.

Paper: Download PDF
Slides: Download PDF

Working Papers

Multi-Period House Allocation as a Public Good Problem

Abstract: We prove existence of envy-free and Pareto efficient allocation in a multi-period indivisible goods assignment problem. Since Birkoff-von-Neumann fails in this environment, the allocation problem cannot be reduced to individual-level consumption problem where total demand cannot exceed supply. Therefore, we have to treat economy-wide allocations as a public good. We provide a market-based implementation by showing that such an allocation can be supported as a Lindahl equilibrium. We then look at a large economy and show that for large enough economies, the incentives to misrepresent agents’ preferences vanish.

Draft coming soon.

Implementation in the Cake-Cutting Problem

Abstract: I establish an equivalence between lotteries over deterministic cake partitions and fractional cake allocations—partitions of unity. The former is a common tool for convexifying a set of deterministic allocations, while the latter is an insightful embedding used in mathematical fair division. By proving that these two objects are utility-equivalent, I provide an implementation foundation for a mathematical representation commonly used in fair division. In addition, I show that every simple partition of unity belongs to the convex hull of degenerate partitions of unity, which means it is implementable by a lottery with finite support.

Download PDF

Work in progress

Almost Marginal Product Allocations

Abstract: I investigate the limiting behavior of agents’ utilities along every sequence of Walrasian equilibrium under pointwise convergence of utilities to quasilinear utilities (small income effects). It turns out that the gap between equilibrium utilities and agents’ marginal contributions can remain strictly positive in the limit despite small income effects. Second, I provide a sufficient condition under which the gap goes to zero: equilibrium and welfare-maximizing allocations remain in a common compact interior region on which the utility gradients converge to quasilinear utility gradients.