Title: Essays on market design
Description: The first two essays of this thesis study the problem of combinatorial assignment, e.g., allocating schedules of courses to students, or schedules of shifts to interchangeable workers. Impossibility theorems have established that the only efficient and strategyproof mechanisms in this environment are dictatorships, which seem unfair. Any non-dictatorship solution will involve compromise of efficiency or strategyproofness. The first essay (joint with Estelle Cantillon) uses unusual data--consisting of agents' strategically reported preferences as well as their underlying true preferences--to study strategic behavior in the course-allocation mechanism used at Harvard Business School. We show that the mechanism is manipulable in theory, manipulated by students in practice, and that these manipulations cause meaningful welfare losses. However, we also find that ex-ante welfare is higher than under the random serial dictatorship. The second essay proposes a solution to the combinatorial assignment problem. I begin by proposing two new criteria of outcome fairness. The maximin share guarantee, based on the idea of divide-and-choose, generalizes and weakens fair share. Envy bounded by a single good weakens envy freeness.

Both criteria recognize that indivisibilities complicate fair division, but exploit the fact that bundles of indivisible objects are somewhat divisible. Dictatorships fail both criteria. Envy bounded by a single good weakens envy freeness. Both criteria recognize that indivisibilities complicate fair division, but exploit the fact that bundles of indivisible objects are somewhat divisible. Dictatorships fail both criteria. I then propose a specific mechanism, the Approximate Competitive Equilibrium from Equal Incomes Mechanism, which satisfies the fairness criteria while maintaining attractive compromises of efficiency and strategyproofness. An exact CEEI may not exist due to indivisibilities and complementarities. I prove existence of an approximate CEEI in which: (i) incomes (in artificial currency) must be unequal but can be arbitrarily close together; (ii) the market clears with some error, which approaches zero in the limit and is small for realistic problems. The third essay concerns auction markets for imperfectly substitutable goods. I show theoretically that two aspects of eBay's multi-auction marketplace design--strict sequencing of auctions, and provision of information about both current and near-future objects for sale--each strictly increase the social surplus generated by its single-unit auction design. Simulations suggest that the remaining inefficiency from not using a multi-object auction is small.