Workshop POPEYE
Cosponsored by MMSOS (specific action of EuroFGI Network of Excellence)IMAG Grenoble, 21-22 May 2008.
Program 21 May:
Systems and the Decoupling Assumption.
Joint work with Michel Benaim
Abstract:
We consider models of N interacting objects, where the interaction is via a common resource and the distribution of states of all objects. We introduce the key scaling concept of intensity; informally, the expected number of transitions per object per time slot is of the order of the intensity. We consider the case of vanishing intensity, i.e. the expected number of object transitions per time slot is o(N). We show that, under mild assumptions and for large N, the occupancy measure converges, in mean square (and thus in probability) over any finite horizon, to a deterministic dynamical system. The mild assumption is essentially that the coefficient of variation of the number of object transitions per time slot remains bounded with $N$. No independence assumption is needed anywhere. The convergence results allow us to derive properties valid in the stationary regime. We discuss when one can assure that a stationary point of the ODE is the large N limit of the stationary probability distribution of the state of one object for the system with N objects. We use this to develop a critique of the decoupling assumption sometimes used in conjunction with a fixed point analysis.
Joint work with J. Bolot.
Abstract:
Getting agents in the Internet, and in networks in general, to invest in and deploy security features and protocols is a challenge, in particular because of economic reasons arising from the presence of network externalities. We study a network of interconnected agents, which are subject to epidemic risks such as those caused by propagating viruses and worms, and which can decide whether or not to invest some amount to self-protect and deploy security solutions. We introduce a general model which combines an epidemic propagation model with an economic model for agents which captures network effects and externalities. Borrowing ideas and techniques used in statistical physics, we introduce a Local Mean Field (LMF) model, which extends the standard mean-field approximation to take into account the correlation structure on local neighborhoods. We solve the LMF model in a network with externalities, and we identify the impact of network externalities on the decision to invest in and deploy security features.
Abstract:
We propose an evolutionary game dynamics with migration for hybrid population games with many local interactions at the same time. Each local interaction concerns a random number of interacting players. The strategies of a player have two components. Specifically, each player chooses both (i) the region or subpopulation and (ii) a strategy among a finite set of secondary pure strategies in each region. We assume that when updating a strategy, a player can change only the secondary strategies associate to the region at a time. We investigate what impact this restriction has on the population dynamics. We apply this model to the integrated power control and base station assignment problem in a multi-cell in code division multiple access(CDMA) wireless data networks with large number of mobiles. We show that global neutrally evolutionary stable strategies and choice constrained equilibria are stationary points of hybrid mean dynamics called dynamics with multicomponent strategies under the positive correlation conditions. We give some convergence results of our hybrid model in stable population games and potential population games under some particular class of dynamics.
Joint work with Xavier Koegler, Pierre Fraigniaud and Johanne Cohen
Abstract:
Les protocoles de populations ont été introduits par Angluin-Aspnes-Diamadi-Fischer-Peralta comme un modèle de réseaux de capteurs: une population d'agents, à états finis, interagissent par paires. Les interactions ont lieu avec une hypothèse de passivité mobile: chaque agent peut entrer en communication avec tout autre agent, et les interactions ne sont pas contrôlées, mais obéissent à une hypothèses d'équité, vérifiée par exemple par une hypothèse d'appariement selon une loi uniforme. On discutera de certains liens entre ce modèle et les hypothèses faites généralement dans les modèles de la théorie évolutionnaire des jeux. On présentera quelques résultats connus sur la puissance de reconnaissance et de calcul du modèle: Angluin-Aspnes-Eisenstat ont caractérisé la puissance de reconnaissance du modèle comme celle des relations définissables en arithmétique de Presburger. On présentera quelques extensions de ce résultat à des systèmes probabilistes et on discutera de ce qui peut être calculé par le modèle avec une hypothèse de grande population. Les résultats qui seront présentés correspondent au travail de stage de première année d'ENS et au stage de master en cours de Xavier Koegler. Travail de master encadré par Pierre Fraigniaud et moi-même. Travail de première année encadré par Johanne Cohen et moi-même. Les protocoles de populations ont été introduits par Angluin-Aspnes-Diamadi-Fischer-Peralta comme un modèle de réseaux de capteurs: une population d'agents, à états finis, interagissent par paires. Les interactions ont lieu avec une hypothèse de passivité mobile: chaque agent peut entrer en communication avec tout autre agent, et les interactions ne sont pas contrôlées, mais obéissent à une hypothèses d'équité, vérifiée par exemple par une hypothèse d'appariement selon une loi uniforme. On discutera de certains liens entre ce modèle et les hypothèses faites généralement dans les modèles de la théorie évolutionnaire des jeux. On présentera quelques résultats connus sur la puissance de reconnaissance et de calcul du modèle: Angluin-Aspnes-Eisenstat ont caractérisé la puissance de reconnaissance du modèle comme celle des relations définissables en arithmétique de Presburger. On présentera quelques extensions de ce résultat à des systèmes probabilistes et on discutera de ce qui peut être calculé par le modèle avec une hypothèse de grande population. Les résultats qui seront présentés correspondent au travail de stage de première année d'ENS et au stage de master en cours de Xavier Koegler. Travail de master encadré par Pierre Fraigniaud et moi-même. Travail de première année encadré par Johanne Cohen et moi-même.
Abstract:
We present a class of evolutionary games involving large populations that have many pairwise interactions between randomly selected players. The fitness of a player depends not only on the actions chosen in the interaction but also on the individual state of the players. Players have finite life time and take during which they participate in several local interactions. The actions taken by a player determine not only the immediate fitness but also the transition probabilities to its next individual state. We define and characterize the Evolutionary Stable Strategies (ESS) for these games and propose a method to compute them. We illustrate the model and results through a networking problem.
Abstract:
Computing optimal routes in massively dense adhoc networks becomes intractable as the number of nodes becomes very large. One recent approach to solve this problem is to use a fluid type approximation in which the whole network is replaced by a continuum plain. Various paradigms from physics have been used recently in order to solve the continuum model. We propose in this paper an alternative modeling and solution approach similar to a model by Beckmann developed more than fifty years ago from the area of road traffic.
Abstract:
We consider massively dense ad-hoc networks and study their continuum limits as the node density increases and as the graph providing the available routes becomes a continuous area with location and congestion dependent costs. We study both the global optimal solution as well as the non-cooperative routing problem among a large population of users where each user seeks a path from its source to its destination so as to minimize its individual cost. We seek for a (continuum version of the) Wardrop equilibrium. We first show how to derive meaningful cost models as a function of the scaling properties of the capacity of the network as a function of the density of nodes. We present various solution methodologies for the problem: (1) the viscosity solution of the Hamilton-Bellman-Jacobi equation, for the global optimization problem, (2) a method based on Green Theorem for the least cost problem of an individual, and (3) a solution of the Wardrop equilibrium problem using a transformation into an equivalent global optimization problem.
Abstract:
Traffic in congested networks is often described as an equilibrium or steady state that emerges from the adaptive behavior of drivers. While this intuitive view tends to be confirmed in experiments, traditional concepts such as Wardrop Equilibrium or Stochastic User Equilibrium are directly stated as equilibrium equations which are not tied to an underlying adaptive dynamics. The notion of Markovian equilibrium incorporates some dynamical features by assuming that passengers move towards their destination through a sequential process of arc selection based on a random discrete choice model at every intermediate node in their trip: route selection is the outcome of a sequential decision process while network flows are the invariant measures of the corresponding Markov chains. Despite a certain dynamical flavor, this notion remains essentially static and is not linked to an adaptive behavior of the players. In this talk we discuss a discrete time stochastic process that represents a plausible model for the adaptive behavior of finitely many users in a simple traffic network. The dynamics are based on a minimal piece of information: each player observes only the travel time for the specific route chosen on any given day, and future decisions depend on the history of past individual observations. Since travel times depend on the congestion conditions imposed collectively by all the player's decisions, the process progressively reveals to each player the congestion conditions in the network. In the long run, the temporal evolution of the dynamics lead the system to coordinate on a steady state that may be characterized as a Nash equilibrium for a particular steady state game, providing a unified framework where a stochastic model for user behavior gives rise to a continuous dynamical system and leads ultimately to a consistent notion of equilibrium. The approach is connected to the literature on adaptive learning in repeated games and specific tools such as fictitious play and no-regret dynamics. However it presents substantial differences in the form of the dynamics as well as in the interpretation of the state variables. In particular we observe a clear distinction between the original repeated game and the steady state game.
Coordinators:
Eitan Altman and Alain Jean Marie, MAESTRO, INRIA