Dagstuhl Seminar 17251
Game Theory Meets Computational Learning Theory
( Jun 18 – Jun 23, 2017 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/17251
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)
Coordinator
- Paul Dütting (London School of Economics, GB)
Contact
- Andreas Dolzmann (for scientific matters)
- Simone Schilke (for administrative matters)
Schedule
There is already a rich history of interaction between machine learning and game theory and economics. At present, there is increasing activity at this intersection, due to the emergence of novel and interesting theory challenges, often coupled with compelling practical motivations. Of course, this activity is motivated by the increasing quantity of data arising from various economic and social interactions. A rigorous theoretical understanding of the interplay of game theory and learning theory is a key requirement for mastering this wealth of data.
This Dagstuhl Seminar will bring together leading researchers from computer science and economics, with expertise in (algorithmic) game theory and computational learning theory. The expected outcome of the seminar is a coordinated effort to
- explore and formulate key questions and open problems at the intersection of the two fields,
- identify concrete approaches and techniques from the two fields that bear the potential to advance the state of the art in the other field, and
- combine tools from both fields to provide the necessary theoretical tools to study learning in strategic environments.
Illustrative research challenges include (but are not restricted to) the following:
- sample complexity for revenue maximization in various settings including (Bayesian) mechanism design,
- preference elicitation from economic behavior,
- complexity of equilibria, such as query complexity,
- models and algorithms for coordinated learning, and
- dynamics of multiple agents, for example in social networks.
Besides short technical presentations, we envisage a small number of keynote talks, and discussion groups on more specific subtopics, leading to a panel discussion towards the end of the seminar.
Creative Commons BY 3.0 DE
Paul W. Goldberg
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.
Paul W. Goldberg, Yishay Mansour, and Paul Dütting
- Yakov Babichenko (Technion - Haifa, IL) [dblp]
- Amir Ban (Tel Aviv University, IL) [dblp]
- Siddharth Barman (Indian Institute of Science - Bangalore, IN) [dblp]
- Peter L. Bartlett (University of California - Berkeley, US) [dblp]
- Gianluca Brero (Universität Zürich, CH) [dblp]
- Rachel Cummings (California Institute of Technology - Pasadena, US) [dblp]
- Argyris Deligkas (Technion - Haifa, IL) [dblp]
- Paul Dütting (London School of Economics, GB) [dblp]
- John Fearnley (University of Liverpool, GB) [dblp]
- Felix Fischer (University of Glasgow, GB) [dblp]
- Hu Fu (University of British Columbia - Vancouver, CA) [dblp]
- Claudio Gentile (University of Insubria - Varese, IT) [dblp]
- Paul W. Goldberg (University of Oxford, GB) [dblp]
- Jason Hartline (Northwestern University - Evanston, US) [dblp]
- Martin Hoefer (Goethe-Universität - Frankfurt a. M., DE) [dblp]
- Aleck Johnsen (Northwestern University - Evanston, US)
- Thomas Kesselheim (TU Dortmund, DE) [dblp]
- Max Klimm (HU Berlin, DE) [dblp]
- Sébastien Lahaie (Google - New York, US) [dblp]
- Yishay Mansour (Tel Aviv University, IL) [dblp]
- Jamie Morgenstern (University of Pennsylvania - Philadelphia, US) [dblp]
- Andrés Muñoz Medina (Google - New York, US) [dblp]
- Paresh Nakhe (Goethe-Universität - Frankfurt a. M., DE) [dblp]
- Denis Nekipelov (University of Virginia - Charlottesville, US) [dblp]
- Ariel Procaccia (Carnegie Mellon University - Pittsburgh, US) [dblp]
- Rahul Savani (University of Liverpool, GB) [dblp]
- Sven Seuken (Universität Zürich, CH) [dblp]
- Yaron Singer (Harvard University - Cambridge, US) [dblp]
- Alexander Skopalik (Universität Paderborn, DE) [dblp]
- Gregory Valiant (Stanford University, US) [dblp]
- Ellen Vitercik (Carnegie Mellon University - Pittsburgh, US) [dblp]
- Bernhard von Stengel (London School of Economics, GB) [dblp]
- Jens Witkowski (ETH Zürich, CH) [dblp]
- Yair Zick (National University of Singapore, SG) [dblp]
Classification
- data structures / algorithms / complexity
Keywords
- Theory
- Algorithms and complexity
- Computational learning
- Game theory
