https://www.dagstuhl.de/17251

### 18. – 23. Juni 2017, Dagstuhl-Seminar 17251

# Game Theory Meets Computational Learning Theory

## Organisatoren

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)

## Koordinatoren

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

## Auskunft zu diesem Dagstuhl-Seminar erteilt

## Dokumente

Dagstuhl Report, Volume 7, Issue 6

Motivationstext

Teilnehmerliste

Gemeinsame Dokumente

Programm des Dagstuhl-Seminars [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