CRCS Lunch Seminar

Date: Monday, November 14, 2011
Time: 12:15pm – 1:45pm
Place: Maxwell Dworkin 119

Speaker: Michal Feldman, Harvard CRCS and Hebrew University of Jerusalem

Title: Providing performance guarantees without assuming rationality of others

Abstract: We study performance guarantees that can be provided to decision makers in a game, without making any assumptions on the rationality of the other players. The first setting is a symmetric two-person repeated game, where one player — our decision maker — never observes a single payoff (but observes the opponent’s play), while her opponent has full knowledge of the game. Naturally, the decision maker should attempt to mimic the opponent’s play. However, one has to be careful about how one mimics opponents who may know that they are being mimicked. As we show, a good copycat can reap tremendous rewards without ever observing a single payoff, while a poor copycat may perform worse than making random decisions. We then extend the model to a multi-player setting, in which only a single player is informed. We show that a {\em master} who controls the uninformed players can guarantee for each one of them (simultaneously) a similar performance to that of the informed player, even if the latter gets to choose the payoff matrix after the fact. Key to our analysis is the study of multi-player games,and the guarantees that a master player that plays on behalf of a set of players can offer them, without making any assumptions on the rationality of the other players.

Based on joint work with Yossi Azar, Uri Feige, Adam Kalai and Moshe Tennenholtz.

Short bio: Michal Feldman is an associate Professor at the Hebrew University of Jerusalem. She received her Ph.D in 2005 from the University of California at Berkeley. Following a postdoc at the Hebrew University and at Tel-Aviv University, she joined the faculty of the School of Business Administration at the Hebrew University (in 2007). Her research focuses on the intersection of game theory, computer science and microeconomics, a field often termed “Algorithmic Game Theory”. She has been recently awarded a Marie Curie grant, and is currently a visiting scholar at the Center for Research on Computation and Society (CRCS) at Harvard University.
Website: http://pluto.huji.ac.il/~mfeldman/