Theory Talk
Wednesday, November 18, 2009
4:00 p.m., AKW 500

Speaker: Ariel Procaccia, Harvard School of Engineering and Applied Sciences (SEAS)

Title: f(x) marks the spot

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.

Bio: Ariel Procaccia is a CRCS fellow at Harvard's SEAS. His research interests include Computational Social Choice, Algorithmic Game Theory, and the interplay between these fields and Artificial Intelligence. He received his Ph.D. summa cum laude from the Hebrew University of Jerusalem, under the supervision of Prof. Jeffrey Rosenschein. His dissertation, entitled "Computational Voting Theory: Of the Agents, By the Agents, For the Agents", has won the 2008 IFAAMAS Victor Lesser Distinguished Dissertation Award and Hebrew University's Schlomiuk Prize. His work in Harvard SEAS is also supported by a Rothschild Postdoctoral Fellowship.