EAI - Reinventing the governance and economy of research and innovation
The leading professional community for research career enhancement in the digital age

Invited Talks

Prof. Eitan Altman

Routing Games and Potential

We present in this talk different modeling frameworks for studying routing games. These include the frameworks of road traffic assignment with the related Wardrop equilbrium and Rosental’s congestion games. Both frameworks are of potential games. We focus on two example of games: the Kameda load balancing game and variants of the the rent seeking game of Tullok. Through these examples we study conditions for uniqueness of equilibrium and relate it to properties of the potential such as multimodularity and discrete concavity.

Bio of Eitan Altman:

Research director at Inria, France.  His main areas of research include the performance evaluation and control of telecommunication networks, optimal control, and stochastic games. 
He is the recipient of numerous awards and distinctions, in particular he received the Distinguished Technical Achievement Recognition Award awarded by IEEE TC on Big Data conference (TCBD), for « his outstanding technical leadership and achievement in stochastic modeling and big data analysis » in 2017, the 2014  Isaacs Award granted by the society of dynamic games for in recognition for his research on dynamic game theory and the Grand prix of France Telecom, granted by the French Academy of Science in 2012.

Giacomo Como

Learning, Multi-scale Dynamics, and Heterogeneities in Network Congestion Game

Motivated by transportation systems control problems, this talk discusses multi-scale dynamical network flow models whereby the dynamics of traffic flows are intertwined with those of the drivers’ route choices. The latter are influenced by the current congestion through the network as well as decentralized congestion-dependent tolls set by the system planner. Our main result proves that a class of decentralized monotone congestion-dependent tolls allow for globally stabilising the transportation network around a generalized Wardrop equilibrium. In particular, our results imply that using decentralized marginal cost tolls, stability of the dynamic transportation network is guaranteed to be around the social optimum traffic assignment. This is particularly remarkable as such feedback tolls can be computed in a fully local way without the need for any global information about the network structure, its state, or the exogenous network loads.

Finally, the impact of heterogeneities in the drivers’ behaviours is addressed by considering a model where different classes of users perceive different congestion costs (which may correspond to different available information). In this case, the game is no longer potential. Results on existence and uniqueness of user equilibria and convergence of (noisy) best response dynamics are presented for certain classes of network topologies.

Bio of Giacomo Como:

He is an international expert in dynamical systems in networks and game theory. He holds two positions: associated professor in Politecnico di Torini and in the department of Automatic control in Lund University and has held visiting positions in MIT (Boston)  and CNR (Italy).

 

 

 

 


Stephane Durand

Distributed Best Response dynamics with high playing rates in potential games

In this presentation, we present and analyze distributed best re- sponse dynamics to compute Nash equilibria in potential games. This algorithm uses local Poisson clocks for each player, and does not rely on the usual but un- realistic assumption that players take no time to compute their best response. If this time (d) is taken into account, distributed best response dynamics may suffer from overlaps: one player starts to play while another player has not changed its strategy yet. Overlaps may lead to drops of the potential but we can show that they do not jeopardize eventual convergence to a Nash equilibrium. We show that the average execution time of the algorithm can be bounded from above by C d n log n (1 + o(1)) and from below by C’ n log n (1 + o(1)), where C and C’ are constants, n is the number of players and d is the time taken by one player to compute its best response. These bounds are obtained by using an asymptotically optimal playing rate. Our analytic bounds show that this rate is high (order of log log n). This induces a large probability of overlap (p = 1 log log n/ log n). In practice, numerical simulations also show that using high playing rates is efficient, with an optimal probability of overlap equal to 0.78 for any number of players smaller than 250. This implies that best response dynamics are unexpectedly efficient to compute Nash equilibria, even in a distributed setting.

Bio of Stephane Durand:

Research director at Inria, France.  His main areas of research include the performance evaluation and control of telecommunication networks, optimal control, and stochastic games. 
He is the recipient of numerous awards and distinctions, in particular he received the Distinguished Technical Achievement Recognition Award awarded by IEEE TC on Big Data conference (TCBD), for « his outstanding technical leadership and achievement in stochastic modeling and big data analysis » in 2017, the 2014  Isaacs Award granted by the society of dynamic games for in recognition for his research on dynamic game theory and the Grand prix of France Telecom, granted by the French Academy of Science in 2012.

Bruno Gaujal

An Efficient Distributed Algorithm for Optimal Routing in Networks

The problem of finding optimal routes in networks that adapt to the state of the network has been addressed in several contexts including transportation networks, roads, communication networks (wired and wireless) as well as electric networks. The most celebrated results in this area pertain to algorithmic graph theory with the celebrated max-flow, min-cut theorem of Fulkerson and to algorithmic game theory with the work of Tardos and Roughgarden. A noteworthy class of routing algorithms bases its routing decisions on dynamic properties of the network, including real time link load and end-to-end latency. This class of strategies is known as adaptive routing. Such solutions are attractive because they typically enable more efficient usage of network resources. In contrast, traditional load-oblivious routing algorithm may blindly over-utilize some links, leading to congestion, while other links have unused capacity. In this work, we present a novel algorithm for adaptive routing in sta- tionary packet-switched networks, mapping source-destination flows to paths. We find that it provides a viable and stable solution to adapt to traffic condi- tions. Our algorithm is based on game theory and is endowed with the following desirable properties that make it a good candidate for efficient implementation in real-world networks:

– It is fully distributed: only local information is needed, and it requires no explicit coordination between routers;
– It is oblivious to the network topology: it will work in all networks provided that paths are available for all flows (source- destination);

– It is based on a bandit information model: The delay over each link is only available under a black box function: only the delay over the utilized links can be estimated, up to some un-biased noise.
– It scales with the number of flows and with the size of the network (conver- gence to optimal solutions takes a polynomial time in the size of the network and in the number of flows).

Bio of Bruno Gaujal:

Bruno Gaujal is an Inria researcher.  Till Dec. 2015,  he has been  the head of the large-scale computing group, MESCAL, of Inria. He has held several positions in AT&T Bell Labs, INRIA,  Loria and École Normale Supérieure of Lyon.  He is the author of more than 100 scientific publications in journals and international conferences. He is a founding partner and a scientific advisor of a start-up company, RTaW, since 2007.  His main interests are in performance evaluation, optimization and control of large discrete event dynamic systems with applications to telecommunication networks and large computing infrastructures.

Marco Scarsini

The Buck-Passing Game

We consider a model where agents want to transfer the responsibility of doing a job to one of their neighbors in a social network. This can be considered a network variation of the public good model. The goal of the agents is to see the buck coming back to them as rarely as possible. We frame this situation as a game, called the Buck-Passing Game, where players are the vertices of a directed graph and the strategy space of each player is the set of her out-neighbors. The cost that a player incurs is the expected long term frequency of times she gets the buck. We consider two versions of the game. In the deterministic one the players choose one of their out-neighbors. In the stochastic version they choose a probability vector that determines who of their out-neighbors is chosen. We use the theory of potential games to show that both the deterministic and stochastic Buck-Passing Game admit a pure equilibrium, even if the strategy set of each player is uncountable. These equilibria are prior-free, that is, they do not depend on the initial distribution according to which the first player having the buck is chosen.

Joint work with Roberto Cominetti and Matteo Quattropani

Bio of Marco Scarsini:

Marco Scarsini is a full professor in the dept. of economics and finance of LUISS University (Rome). He is held several professor positions in the mathematical department of University of Parma, La Sapienza  in Roma, and the university of Torino. His main research interests are applied probability, Game Theory, and the Mathematics of gambling.

Marc Schröder

Price-of-Anarchy in Stochastic Atomic Congestion Games with Affine Costs

We consider an atomic congestion game with stochastic demand in which each player participates in the game with probability p, and incurs no cost with probability 1-p. We assume that p is common knowledge among all players, but the outcome of the random variable is private information. We investigate how the price of anarchy of this incomplete information game depends on the probability p. We provide tight bounds on both the price of anarchy as well as on the price of stability for all values of p. This is joint work with Roberto Cominetti, Marco Scarsini and Nicolas Stier-Moses.

Bio of Marc Schröder:

Marc Schröder is a postdoctoral researcher in the School of Business and Economics at RWTH Aachen University. After completing his PhD at Maastricht University and doing a postdoc at Universidad de Chile, he is now working in the group of Britta Peis. His research interests are various aspects of (algorithmic) game theory with a current focus on congestion games.

EAI Institutional Members