Institute for Mathematical Sciences Event Archive
Online registration form
Enquiries |
|
Stochastic Methods in Game Theory
(16 November - 25 December 2015)
Organizing Committee · Visitors and Participants · Overview · Activities · Venue
Â
With partial support from the GDR Jeux.
Â
Chair
- Satoru Takahashi (National University of Singapore)
Co-chairs
- Marco Scarsini (Libera Università Internazionale degli Studi Sociali Guido Carli)
- Tristan Tomala (HEC Paris)
Members
- Shie Mannor (Technion - Israel Institute of Technology)
- Vianney Perchet (Université Paris Diderot)
- Philippe Rigollet (Massachusetts Institute of Technology)
- Yeneng Sun (National University of Singapore)
- Nicolas Vieille (HEC Paris)
The program aims at showing the role of stochastic methods in strategic situations. Three workshops will focus on some aspects of the interaction between strategy and stochastics and its interest from a mathematical viewpoint.
The first workshop will focus on learning. There are strong connections between online learning (and online convex optimization) and game theory. The former can indeed be described as a game where one player (the decision maker) is facing the environment. On each period of time, either discrete or continuous, they both take some decisions and this process results in some overall payoff that the player aims to maximize. The nature of this payoff depends strongly on the hypothesis made on the environment. The fundamental question is not really whether learning occurs or not (as it is implicitly assumed that it will, if there is enough time) but rather at which speed. This is striking in a stochastic world, since concentration of measures ensure that the fixed distribution can always be discovered. Key challenges are to exhibit lower bounds (that depend on the number of repetitions, the dimensions of actions spaces, the ranges of payoffs, etc) as well as to construct algorithms that match them.
The second workshop will be about stochastic games and their applications. A stochastic game is a dynamic game where players play time-varying stage games (Shapley, 1953). Stochastic games include both Markov decision processes (single player) and repeated games (single state) as special cases, and have many applications, in particular in economics and computer science. It should come with no surprise that recursive structures and stationary strategies play important roles in analyzing stochastic games. Nevertheless basic mathematical properties such as existence and characterization of equilibrium are significantly more difficult to establish in stochastic games than in Markov decision processes and in repeated games. For instance, while it is well known that any finite stochastic game with discounting admits at least one stationary equilibrium, extensions of this result to games with no discounting or with in finite action and state spaces are often non-trivial and some of them still remain unsolved.
The third workshop will deal with congestion games. Congestion games model situations where players use facilities whose cost is an increasing function of the number of players who use them. Prominent examples of congestion games are routing games where players drive in a network of roads, trying to minimize their transportation cost. It is well known that in general a Nash equilibrium is not efficient, that is, there may exist profiles of strategies that are not equilibria and are Pareto-superior to the Nash equilibrium. In congestion games the inefficiency of equilibria is usually measured by the price of anarchy. Most of the models of congestion games are static, but recently some papers started considering the dynamic aspect of network games. Issues of efficiency of equilibria appear also in stochastic congestion frameworks, like queues. This workshop aims at bringing together scholars from various communities who deal with related topics from different viewpoints.
1. Tutorial on Learning: 16 November 2015
2. Workshop on Learning: 17 - 20 November 2015
(organized by S. Mannor, V. Perchet, and P. Rigollet)
3. Public Lecture
|
|
|
|
||
|
|
4. Tutorial on Stochastic Games: 30 November - 3 December 2015
5. Workshop on Stochastic Games: 30 November - 4 December 2015
(organized by S. Takahashi, Y. Sun, and N. Vieille)
6. Tutorial on Congestion Games: 14 December 2015
7. Workshop on Congestion Games: 15 - 18 December 2015
(organized by M. Scarsini and T. Tomala)
Please note that our office will be closed on the following public holiday.
- 25 Dec 2015, Christmas Day
Organizing Committee · Visitors and Participants · Overview · Activities · Venue
