f(x) marks the spot   . . . Abstract . . . Biography Ariel Procaccia, Harvard University     4:15 PM (refreshments 3:45), Stata Center, Room 32-155 CSAIL Theory Colloquium -   Host: Costis Daskalakis, CSAIL, MIT -   Contact: Be, 3-6098, imbe@mit.edu

Abstract

Given a vector x of ideal locations reported by multiple selfish agents, we would like to select a location f(x) for a public facility; 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, e.g., 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, and the presentation will endeavor to replace equations with animations.

Based on joint papers with Noga Alon, Michal Feldman, Felix Fischer, and Moshe Tennenholtz.