https://www.dagstuhl.de/17251

June 18 – 23 , 2017, Dagstuhl Seminar 17251

Game Theory Meets Computational Learning Theory

Organizers

Maria-Florina Balcan (Carnegie Mellon University – Pittsburgh, US)
Paul W. Goldberg (University of Oxford, GB)
Michael J. Kearns (University of Pennsylvania – Philadelphia, US)
Yishay Mansour (Tel Aviv University, IL)

Coordinators

Paul Dütting (London School of Economics, GB)

For support, please contact

Dagstuhl Service Team

Documents

Dagstuhl Report, Volume 7, Issue 6 Dagstuhl Report
Aims & Scope
List of Participants
Shared Documents
Dagstuhl Seminar Schedule [pdf]

Summary

Algorithmic Game Theory (AGT) has been an identifiable research field for about 20 years by now. It emerged as an important research community in the 1990s, with the ACM-EC conference starting in 1999, and the conferences WINE and SAGT also support this community; in addition, the field is also represented in the main CS theory and AI conferences. Among former Dagstuhl seminars on topics in AGT, there have been a sequence of Dagstuhl seminars on Equilibrium Computation, and another sequence of seminars on Computational Social Choice, and also on Electronic Markets and Auctions.

Machine learning has of course become very pervasive, with the vast accessibility of "big data" and has the motivation to develop new methodologies for harvesting the vast amounts of data, improve our ability to automatically carry out many tasks, from classifying documents and pictures, to identifying normal trends and anomalies.

It is perhaps not surprising that it is timely to investigate the connections between economics and big data, more specifically the interface between game theory and machine learning. Much of econometrics is about handing data and deriving understanding from data.

In the AGT context, this would seem to apply most readily to data emanating from "economic" sources, and of course there are plenty of examples. The most notable of these is learning user preferences from examples.

There have been workshops at the AGT/Machine Learning interface in the ACM-EC conference (the 2017 EC held the 3rd workshop on Algorithmic Game Theory and Data Science) but there is clearly space for more meetings on this topic, and this is the first one to take place at Dagstuhl. As such, it contributed to the development of the European community in this research area (noting that ACM-EC is usually held in the USA).

It was pleasing that the seminar attracted quite a high proportion of participants who were visiting Dagstuhl for this first time, alongside others who have made multiple visits. There was a good balance amongst representatives of Algorithmic Game Theory, Machine Learning, and Economics.

One can classify the AGT/Machine Learning topics as follows.

  • Usage of ML ideas (reinforcement learning, multi-arm bandits, etc.) into decision making under uncertainty (and the search for game-theoretic solution notions such as equilibria)
  • usage of game-theoretic tools into machine learning approaches (as in Generative Adversarial Nets).
  • A basic test case is learning user valuations from historical data. For example, given the outcome of previous auctions to learn the distribution of the users' valuations and the goal is to define near optimal mechanisms. (This is also an aspect in learning "revealed preferences".)
  • Query complexity of solution concepts of games, aspects of which are applicable to learning adversary preferences in the context of security/patrolling games.

The seminar was structured around longer invited/tutorial talks (typically lasting 1.5-2 hours), one or two such talks taking place each day. These were followed by shorter contributed talks.

We thank Argy Deligkas for serving as collector of the abstracts.

Keynote/tutorial talks

  • Monday Sven Seuken, University of Zurich Design of Machine Learning-Based Mechanisms; Yaron Singer, Harvard University: Learning, Optimization, and Noise
  • Tuesday Claudio Gentile, Universita dell’Insubria: No Regret and Sequential Prediction
  • Wednesday Denis Nekipelov, University of Virginia: Robust Inference for Non-Robust Models
  • Thursday Jamie Morgenstern, University of Pennsylvania: The Sample Complexity of Single-Parameter Auction Design
  • Friday Yakov Babichenko, Technion: Informational Bounds on Equilibria, and its Relation to Learning

Related topics not covered

There is ongoing work at the intersection of macroeconomics and machine-learning techniques, that was out of scope of this meeting but may be of interest later. For example, ongoing work on Vector Autoregressive models in the context of multivariate time series modelling, which may later lead to interesting problem in computational learning theory. Another topic that was only touched-on is agent-based models of macroeconomics.

License
  Creative Commons BY 3.0 Unported license
  Paul W. Goldberg, Yishay Mansour, and Paul Dütting

Classification

  • Data Structures / Algorithms / Complexity

Keywords

  • Theory
  • Algorithms and complexity
  • Computational learning
  • Game theory

Book exhibition

Books from the participants of the current Seminar 

Book exhibition in the library, ground floor, during the seminar week.

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.

NSF young researcher support