Events
Spring 2022

Learning & Games Visitor Speaker Series: Multiplayer Learning in Multi-Armed Bandits and Markets

Thursday, Feb. 17, 2022 2:00 pm3:00 pm PST

Add to Calendar

Parent Program: 
Speaker: 

Simina Brânzei (Purdue University)

Location: 

Calvin Lab Room 116 or Zoom

Title: Multiplayer learning in multi-armed bandits and markets

 Abstract: Consider a two player multi-armed bandit problem, where one arm has a known success probability, while the other arm does not. In every round, each player pulls an arm, gets the reward from the arm they pulled, and observes the action of the other player but not their reward. The model is related to the economics literature on strategic experimentation, where usually players observe each other's rewards. 

We show that two competing players explore less than a single player with an optimal strategy, while cooperating players explore more. Neutral players learn from each other, receiving strictly higher rewards than if they played by themselves. Both competing and neutral players settle on the same arm in the long term.

I will also discuss exchange and production markets with additive valuations, when players learn to bid using proportional response dynamics. In the production market, this dynamic leads to growth of the market in the long term, but also creates growing inequality between the players. In the exchange market, the proportional response dynamic converges to market equilibria. This resolves an open question about the exchange market, where tatonnement does not converge to market equilibria and no natural process leading to equilibria was known.

This is based on joint works with Peres and Devanur, Mehta, Nisan, and Rabani.

Bio: Simina Branzei is an assistant professor at Purdue University. She completed her Ph.d. at Aarhus University in Denmark and afterwards was a research fellow at Simons and postdoctoral fellow at the Hebrew University of Jerusalem. Her research interests are in algorithmic game theory, learning, and more generally artificial intelligence and theoretical computer science.