Quarterly Workshop: Learning as a Solution Concept

About the Series

The Quarterly CS+Econ Workshop brings in three or four experts at the interface between computer science and economics to present their perspective and research on a common theme. Chicago area researchers with interest in economics and computer science are invited to attend. The technical program is in the morning and includes coffee and lunch. The afternoon of the workshop will allow for continued discussion between attendees and the speakers. 

The the workshop series is organized by Ronen Gradwohl (Kellogg, MEDS), Jason Hartline (Computer Science), and Marciano Siniscalchi (Economics). Funding for the series is provided by the Shaw Family Supporting Organization CS+X Fund.

Synopsis

The first edition of this workshop will be on the theme of Learning as a Solution Concept. Traditional approaches in game theory separately describe outcomes of static equilibrium concepts and conditions under which models of learning converge to the static equilibrium concepts. Recent work, however, has shown the value of understanding the outcomes of strategic interaction directly from assumptions on learning processes and regardless of whether they reach a static equilibrium. One example is “no-regret learning,” which arises from many natural algorithms. The speakers are Drew Fudenberg, Alex Peysakhovich, Vasilis Syrgkanis, and Matt Weinberg.

Logistics

  • Date: Friday, November 9, 2018.
  • Location: Kellogg Global Hub 5101 (map) and Seeley Mudd 3514 (map), Northwestern U, Evanston, IL 60208.
  • Transit: Noyes St. Purple Line (map).
  • Parking: Validation for North Campus Parking Garage (map) available at workshop.
  • Registration: None required.  Please bring your own name badge from past conference.

Schedule

Kellogg Global Hub 5101

  • 8:30-9:00: Continental Breakfast
  • 9:00-9:05: Opening Remarks
  • 9:05-9:45: Matt Weinberg (Princeton):
    Selling to a no-regret buyer
  • 9:45-9:50: Matt Weinberg Q/A
  • 9:50-10:30: Vasilis Syrgkanis (Microsoft Research):
    No-regret Learning with Recency Bias: Fast and Last-Iterate Convergence
  • 10:30-10:35: Vasilis Syrgkanis Q/A
  • 10:35-11:05: Coffee Break

Seeley Mudd 3514

  • 11:05-11:45: Drew Fudenberg (MIT):
    Player Compatible Equilibrium
  • 11:45-11:50: Drew Fudenberg Q/A
  • 11:50-12:30: Alex Peysakhovich (Facebook AI):
    Game Theory and Deep Reinforcement Learning
  • 12:30-12:35: Alex Peysakhovich Q/A
  • 12:35-1:30: Lunch

Seeley Mudd 3014

  • 2:00-4:00: Student meetings with speakers

Titles and Abstracts

Speaker: Matt Weinberg
Title: Selling to a no-regret buyer
Abstract: We consider the problem of a single seller repeatedly selling a single item to a single buyer (specifically, the buyer has a value drawn fresh from known distribution D in every round). Prior work assumes that the buyer is fully rational and will perfectly reason about how their bids today affect the seller’s decisions tomorrow. In this work we initiate a different direction: the buyer simply runs a no-regret learning algorithm over possible bids. We provide a fairly complete characterization of optimal auctions for the seller in this domain. Specifically:

  • If the buyer bids according to EXP3 (or any “mean-based” learning algorithm), then the seller can extract expected revenue arbitrarily close to the expected welfare. This auction is independent of the buyer’s valuation D, but somewhat unnatural as it is sometimes in the buyer’s interest to overbid.
  • There exists a learning algorithm A such that if the buyer bids according to A then the optimal strategy for the seller is simply to post the Myerson reserve for D every round.
  • If the buyer bids according to EXP3 (or any “mean-based” learning algorithm), but the seller is restricted to “natural” auction formats where overbidding is dominated (e.g. Generalized First-Price or Generalized Second-Price), then the optimal strategy for the seller is a pay-your-bid format with decreasing reserves over time. Moreover, the seller’s optimal achievable revenue is characterized by a linear program, and can be unboundedly better than the best truthful auction yet simultaneously unboundedly worse than the expected welfare.
Speaker: Vasilis Syrgkanis
Title: No-regret Learning with Recency Bias: Fast and Last-Iterate Convergence

Abstract: We investigate the behavior of large families of no-regret dynamics in game theoretic settings in terms of their speed of convergence to small regret solutions and in terms of last-iterate behavior. We show that natural classes of regularized learning algorithms with a form of recency bias achieve faster convergence rates to approximate efficiency and to coarse correlated equilibria in multiplayer normal form games. Our results extend those of [Rakhlin and Shridharan 2013] and [Daskalakis et al. 2014], who only analyzed two-player zero-sum games for specific algorithms. Finally, inspired by empirical findings we investigate the long-term stability properties of such dynamics and show that in a family of zero-sum games they avoid limit cycles and converge pointwise to an equilibrium. Avoiding limit cycles is desirable from both a behavioral and an algorithmic perspective and we discuss implications to the field of adversarial machine learning.

Based on joint works with: Alekh Agarwal, Haipeng Luo, Robert E. Schapire, Constantinos Daskalakis, Andrew Ilyas and Haoyang Zeng.

Speaker: Drew Fudenberg
Title: Player Compatible Equilibrium
Abstract: This talk will summarize recent work with Kevin He on the learning foundations of equilibrium refinements. I will focus on our paper “player compatible equilibrium,” which develops a trembles-based equilibrium refinement where the restrictions on the trembles correspond to the relative frequencies of various “experiments” under either Bayesian optimization or the Bayes upper confidence bounds heuristic.

Speaker: Alex Peysakhovich
Title: Game Theory and Deep Reinforcement Learning
Abstract: Modern advances in deep learning have led to agents that have superhuman performance in games like Go, chess, and poker. In this talk I will introduce the basics of deep reinforcement learning (deep RL) and discuss how to push these advances beyond two player zero sum games. I will cover recent work that combines ideas from game theory with deep RL to construct agents that can cooperate, coordinate, and communicate with others.