Game Theory & Computation Seminar Series

The Game Theory and Computation Seminar is a weekly theory seminar series, highlighting recent advances in economic theory and computer science.  The range of topics includes algorithmic game theory, market design, microeconomic theory, social network theory, and other topics related to game theory and computation.

The agenda typically consists of a prepared presentation, followed by a period of questions and discussion. The seminar is aimed at an audience of theory researchers and students. We welcome members of the local academic community to attend.

The seminar's location alternates weekly between the MSR conference center at One Memorial Drive and the Littauer Center at Harvard University.  Please check the location information listed for upcoming talks.

Upcoming Talks

Monday, September 22 -- **CANCELLED -- NO SEMINAR THIS WEEK**
4:00 PM – 5:30 PM
Harvard University, Littauer Center

Risk Dynamics in Trade Networks

Rafael Frongillo, Harvard
Monday, September 29
4:00 PM – 5:30 PM
Microsoft Research, One Memorial Drive (1st Floor)

Description
We present a new framework to model interactions among agents which seek to negotiate to minimize their risk with respect to some future outcome. We quantify this risk using the concept of risk measures from finance, and introduce a class of trade dynamics which allow agents to trade contracts contingent upon the future outcome. We then show that these trade dynamics exactly correspond to a variant of randomized coordinate descent. By extending the analysis of these coordinate descent methods to account for our more organic setting, we are able to show convergence rates for very general trade dynamics, showing that the market or network converges to a unique steady state. Applying these results to prediction markets, we expand on recent results by adding convergence rates and general aggregation properties.

Joint work with Mark Reid (ANU & NICTA)

Biography
Rafael Frongillo is a computer scientist working on theoretical problems at the interface between machine learning and economics, primarily focusing on problems such as crowdsourcing or prediction markets which involve the exchange of information for money. Before coming to Harvard, he was a postdoc at Microsoft Research in New York City, and he received his Ph.D. at UC Berkeley, advised by Christos Papadimitriou and supported by the NDSEG Fellowship.

Back to top

Mallesh Pai, University of Pennsylvania
Monday, October 6
4:00 PM – 5:30 PM
Harvard University, Littauer Center

Monday, October 13 - No Seminar (Columbus Day)

Bobby Kleinberg, Cornell University
Monday, November 3
4:00 PM – 5:30 PM
Harvard University, Littauer Center

Shaddin Dughmi, University of Southern California
Monday, November 10
4:00 PM – 5:30 PM
Microsoft Research, One Memorial Drive (1st Floor)

Giorgos Zervas, Boston University
Monday, November 24
4:00 PM – 5:30 PM
Microsoft Research, One Memorial Drive (1st Floor)

Back to top

Past Speakers

On the Efficiency of the Walrasian Mechanism

Moshe Babaioff, Microsoft Research
Monday, September 15
4:00 PM – 5:30 PM
Microsoft Research, One Memorial Drive (1st Floor)

Description
Central results in economics guarantee the existence of efficient equilibria for various classes of markets. An underlying assumption in early work is that agents are price-takers, i.e., agents honestly report their true demand in response to prices. A line of research initiated by Hurwicz (1972) is devoted to studying market performance when agents are strategic about their demands. This is captured by the Walrasian Mechanism that proceeds by collecting reported demands, then finding clearing prices for the reported market.

In practice, agents commonly reduce their demand, leading to inefficient outcomes. We ask how inefficient the equilibria can be. We show that the welfare of every pure Nash equilibrium of the Walrasian mechanism is at least one quarter of the optimal welfare, when players have gross substitute valuations and do not overbid. Our result shows that approximate efficiency is guaranteed regardless of the size of the market.

Our results extend to Bayes-Nash equilibria and outcomes of no regret learning via the smooth mechanism framework. We also extend our bounds to any mechanism that maximizes welfare with respect to the declared valuations and never charges agents more than their bids. We also relax the no-overbidding assumption, and present bounds that are parameterized by the extent to which agents are willing to overbid.

Joint work with Brendan Lucier, Noam Nisan and Renato Paes Leme

Biography
Moshe Babaioff is a Researcher at Microsoft Research. His research interests lie in the intersection of Computer Science and Economics and he studies problems on the border of Computer Science Theory, Game Theory, and Microeconomic Theory. Much of his research focuses on the theoretical foundations of electronic markets. Prior to joining Microsoft Research at 2007, he spent two years as a post-doctoral scholar at the University of California, Berkeley. He received his PhD in Computer Science from the Hebrew University in Jerusalem at 2005, where he was advised by Professor Noam Nisan. He holds a M.Sc. in Computer Science and a B.A. in Mathematics and Computer Science, also from the Hebrew University.

Back to top

Where

Microsoft Research New England
First Floor Conference Center
One Memorial Drive, Cambridge, MA

Harvard University
Littauer Center, 3rd Floor Lounge
1805 Cambridge Street, Cambridge, MA

Arrival Guidance

Upon arrival at MSR, be prepared to show a picture ID and sign the Building Visitor Log when approaching the Lobby Floor Security Desk. Alert them to the name of the event you are attending and ask them to direct you to the appropriate floor. Typically the talks are located in the First Floor Conference Center, however sometimes the location may change.

If you have any questions or concerns, please send us an email.

Mailing List

To subscribe to the mailing list, send a blank message to this email address.

To unsubscribe, send a blank message to this email address.