2008 Victor Lesser Distinguished Dissertation Award

Ariel Procaccia
Hebrew University of Jerusalem, Israel

Abstract: New Insights on Where to Locate a Library

Say we would like to select a location for a public facility, given ideal locations reported by multiple selfish agents; this abstract setting has many interpretations, such as locating a library in a city or a router on a communications network. We wish to design mechanisms for this problem that, at the same time, (i) satisfy game-theoretic desiderata, and (ii) approximately optimize a target function, such as the facility's sum of distances to the agents' ideal locations. I will survey recent results with respect to this problem, elaborate on their interfaces with computational social choice and algorithmic mechanism design, and position them in the context of the fresh agenda of approximate mechanism design without money. No background is required, whereas an avalanche of challenging directions for future research is guaranteed.
Based on joint work with Noga Alon, Michal Feldman, and Moshe Tennenholtz.