Pick Me: Reducing Wastefulness in the Random Serial Dictatorship Mechanism

Abstract

This thesis investigates algorithmic improvements to the Random Serial Dictatorship (RSD) Mechanism for allocating indivisible goods, focusing on reducing wastefulness in outcomes when truncated preference reports are allowed. It corroborates Erdil's (2014) refutation of the RSD uniqueness conjecture and answers his open question, seeking to identify the frontier of strategyproof improvements. A linear program is devised to minimize wastefulness while enforcing other desirable properties of RSD, such as ex-post efficiency, equal treatment of equals, and strategyproofness. Through this approach, I identify efficient, fair, and incentive-compatible improvements in both the 4-agent, 3-item and 4-agent, 4-item scenarios, uncovering numerous potential profiles for improvements. The proposed approach, based on solving linear programs, poses several scalability challenges. To address this, I exploit symmetry and make use of constraint generation techniques, resulting in empirical improvements.