|
Jean-Yves Le Boudec, EPFL, Switzerland
Download the slides 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 $. 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. |
|
Evripidis Bampis Abstract : Nous allons presenter quelques resultats recents dans les domaines de l'ordonnancement et des encheres en relation avec la problematique de la veracite. |
|
Stephane Le Roux, INRIA - Microsoft Research
Download the slides Download the article Abstract : I consider basic routing problems whose solutions are defined as static route choices that are optimal everywhere. I introduce dalographs to generalise these problems, which helps describe a sufficient (resp. necessary) condition so that every dalograph has a solution. Both conditions depend only on the notion of optimality, which boils down to an arbitrary binary relation. The necessary and the sufficient conditions coincide when this relation is a linear order, but not in general. As expected, this partial characterisation is easily translated back to the routing world. For more information, see Ch6, p111 of my PhD dissertation: http://perso.ens-lyon.fr/stephane.le.roux/Download/slr_thesis.pdf |
|
Tembine Hamidou, LIA (joint work with E. Altman (INRIA), R. El-Azouzi (LIA, UAPV) and W. H. Sandholm (University of Wisconsin))
Download the slides 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. |
|
Olivier Bournez, LORIA, France (joint work with Xavier Koegler, Pierre Fraigniaud and Johanne Cohen)
Download the slides Download the article 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. |
|
Yezekael Hayel, University of Avignon (joint work with E. Altman, R. El-Azouzi and T. Hamidou)
Download the slides 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. |
|
Alonso Silva, University of Nice (joint work with E. Altman and P. Bernhard)
Download the slides 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. |
|
Sylvain Sorin, Paris 6 (joint work with Josef Hofbauer and Yannick Viossat)
Abstract : Using an explicit representation in terms of the logit map we show, in a unilateral framework, that the time average of the replicator dynamics is a perturbed solution, hence an asymptotic pseudo- trajectory of the best reply dynamics. |
|
Eitan Altman, INRIA (joint work with A. Silva, P. Bernhard and M. Debbah)
Download the slides 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. |
|
Roberto Cominetti, Universidad de Chile (joint work with Emerson Melo and Sylvain Sorin)
Download the slides 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. |
|
Johanne Cohen, Loria, France
Abstract : This talk introduces the concept of selfing self-stabilization (introduced by Dasgupta and al.): how to balance competition and cooperation so as to obtain some stability of the environment. This concept will be illustrated on the problem of shortest path computation in the inter-domain routing (for instance BGP) introduced by Griffin and al. |
|
Alain Jean-Marie, INRIA (joint work with Mabel Tidball (INRA))
Download the slides Download the article Abstract : We present a learning mechanism, inspired from the concept of Conjectural Variations Equilibria in Game Theory. It consists, for each player, in formulating a "conjecture" about the behavior of the opponents, and in updating iteratively this conjecture, based on collected information. This mechanism converges to outcomes that are candidates for being Pareto optima. We discuss the local stability of this algorithm, and illustrate its behavior in the classical cases of Cournot and Bertrand duopolies. |
|
Marc Lelarge, TREC, INRIA (joint work with Jean Bolot (SPRINT))
(http://www.di.ens.fr/~lelarge/)
Download the article 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. |
|
Samson Lasaulce, Supelec (joint work with E. V. Belmega and M. Debbah)
Download the slides Download the article Abstract : We consider the uplink traffic in a wireless network that comprises a large group of mobile stations and a certain number of base stations connected between them. We assume an heterogeneous network where the base stations can differ by their reception noise levels, bandwidth or number of antennas. We introduce the problem of distributed (hard and soft) handovers in which each user is able to allocate his transmit power between the available base stations in order to selfishly maximize his individual Shannon transmission rate. In order to clearly understand the main concepts and issues related to this scenario we first analyze, for two types of receivers (namely single-user decoding and successive interference cancellation) the case of a network of single-antenna terminals and static links where the base stations only differ by their noise levels. To bridge the gap between the considered decentralized network and its virtual multiple input multiple output (MIMO) counterpart a pricing mechanism is proposed. Next, using random matrix theory, we show how this methodology extends to networks with multi-antenna terminals, time-varying channels and base stations having different bandwidth or number of antennas. Simulations are provided to illustrate our analysis. |
|
Jérôme Galtier, France Telecom R&D and INRIA
Abstract : In the context of radio distributed networks, we present a tournament-based approach for the Medium Access Control (MAC) in WiFi and WiMAX networks. Our protocol is quite simple to analyze and can be used in a lot of different situations. We give mathematical evidence showing that our performance is tight, in the sense that no protocol with fixed congestion window can do better. We also place ourselves in the 802.11b framework, and show experimental results enlightening collision reduction of 14% to 21% compared the best known methods. We show channel capacity improvement, and fairness considerations. |
|
Denis Trystram, University of Grenoble (joint work with Erik Saule)
Download the slides Abstract : Scheduling is a very old problem of combinatorial optimization. Scheduling algorithms are often centralized. This centralized character allows to design more efficient algorithms (consider for instance the PTAS of Shmoys for the basic P||cmax problem). Game theory is an old domain where the global behaviour of a system is determined by local interactions of players or agents. It allows to optimize a large number of objectives by a decentralized process. Thus, Game Theory does not seem seems to be the adequate tool for studying the scheduling problem. However, researchers of the Game Theory domain developed some concepts and properties that can be applied to scheduling, namely, fairness and trusthfulness. We will consider the problem of multi-users scheduling sharing m identical resources as a case study. We propose an algorithmic scheme with a constant performance ratio for this problem which is both fair and truthful. |
|
Arnaud Legrand, CNRS (joint work with Remi Bertin and Corinne Touati)
Download the slides Download the article Abstract : In this talk, we present a fully decentralized algorithm for fair resource sharing between multiple bag-of-tasks applications in a grid environment. This algorithm is inspired from related work on multi-path routing in communication network. An interesting feature of this algorithm is that it allows the choice of wide variety of fairness criteria and achieves both optimal path selection and flow control. In addition, this algorithm only requires local information at each slave computing tasks and at each buffer of the network links while minimal computation is done by the schedulers. A naive adaptation is unstable and inefficient though. Fortunately, a simple and effective scaling mechanism is sufficient to circumvent this issue. This scaling mechanism is motivated by a careful study of the subtle differences with the classical multi-path routing problem. We prove its efficiency through a detailed analysis of a simple simulation. |
|
Krzysztof Rzadca, Polish-Japanese Institute of Information Technology
Download the slides Abstract : In many multiobjective optimization problems, individual objectives correspond with goals of individual, independent agents. The agents cannot make any decisions, yet the decision maker should treat each agent fairly. The optimization goal is to find a set of solutions that provide a good compromise between efficiency and equity. We propose to use the axiomatic theory of equity for such problems. The theory is based on Lorenz-like analysis of fair wealth distribution. The theory defines a relation of equitable dominance based on axioms of optimality, symmetry and transfers. Equitably-optimal solutions are a subset of Pareto-optimal solutions. As an example application, we consider a scheduling problem in which two agents compete for one processor. Comparing with min-max fairness, we show that the axiomatic theory of fairness enables us to better balance the system performance with the individual equity. |
|
Fanny Pascual, University of Paris 6 (joint work with Laurent Gourves and Jerome Monnot)
Download the slides Abstract : We study a problem involving a set of organizations. Each organization has its own set of users (or clients) who either supply or demand one unit of an indivisible product. Knowing the profit induced by each buyer-seller pair, an organization wants to maximize the amount of the transactions it makes between its users. Given a set of several organizations, where transactions are allowed between users of two different organizations, our goal is to return an assignment of the users which maximizes the amount of transactions done, while no organization gets less than it could obtain by considering only its own set of users. This problem also apply when the quality of an assignment between two users is measured by the satisfaction of its users, and the aim of each organization is then to maximize the average satisfaction of its users. Complexity results, exact and approximation algorithms are given. We also study the problem where a solution is acceptable if each organization accepts to reduce its profit by a given ratio. |
|
Laurent Gourves, University of Paris-Dauphine and CNRS (joint work with Aristotelis Giannakos, Jerome Monnot and Vangelis Th. Pashos)
Download the slides Abstract : We introduce and study a congestion game having MAX SAT as an underlying structure and show that its price of anarchy is 1/2. The main result is a redesign of the game leading to an improved price of anarchy of 2/3 from which we derive a non oblivious local search algorithm for MAX SAT with locality gap 2/3. A similar congestion MIN SAT game is also studied. |
|
Hisao Kameda, University of Tsukuba, Tsukuba, Japan
Abstract : We first confirm the notions of Pareto optimality, superiority, and inefficiency. Then, we characterize Braess-like paradoxes. Furthermore, we give a definition of the measure of Pareto superiority, which has not been generally accepted yet. Based on the measure of Pareto superiority, we define a measure of the degree of a Braess-like paradox. We present some properties on Braess-like paradoxes that are described in terms of the defined measures. |
|
Amar Azad, INRIA Sophia-Antipolis (joint work with Eitan Altman)
Abstract : This work studies the routing in the network shared by several users. Each user seeks to optimize either its own performance or some combination between its own performance and that of other users, by controlling the routing of its given flow demand. We parameterize the degree of cooperation which allows to cover the fully non-cooperative behavior, the fully cooperative behavior, and even more, the fully altruistic behavior, all these as special cases of the parameter's choice. A large part of the work consists in exploring the impact of the degree of cooperation on the equilibrium. Our first finding is to identify multiple Nash equilibrium with cooperative behavior that do not occur in the non-cooperative case under the same conditions (cost, demand and topology). We then identify Braess like paradox (in which adding capacity or adding a link to a network results in worse performance to all users) and study the impact of the degree of cooperation on it. We identify situations where low cooperation results in poorer performance at equilibrium. We finally obtain some theoretical results that show that for low degree of cooperation the equilibrium is unique, confirming the results of our numerical study. |
|
Vijay Kamble,
Department of Industrial Engineering and Management, IIT-Kharagpur,
West Bengal 721302, India (joint work with Eitan Altman and Hisao
Kameda) Abstract : The original Braess paradox has been predicted in a context of Wardrop equilibrium in a road traffic context where there is a continuum of (non-atomic) players. It was shown that the performance of all users at equilibrium becomes worse when adding a route. This paradox as well as various variants were also studied in the context of computer networks and telecommunications. We identify a new type of paradox occurring in wireless communications with some unusual properties with respect to previous models in which the paradox has been identified. |
|
Eitan Altman, INRIA, joint work with Anurag Kumar, Chandramani K. Singh and Rajesh Sundaresan
Download the slides Abstract : With the rapidly developing mobile communication technology, Intelligent mobile terminals are expected to be able to decide to which access point and/or which wireless access technology to use. When dsigning and deploying wireless networks, these capabilities of the mobiles should be taken into account. We study in this paper the question of determining locations of base stations (that may belong to the same or to competing ISPs) taking into account the impact of these decisions on the behavior of intelligent mobile terminals who can connect to the service provider that offers the best utility. We first study the SINR association-game: we determine the cells corresponding to each base stations, i.e. the locations at which mobile terminals prefer to connect to a given base stations than to others. We use the Signal to Interference and Noise ratio as the metrics that determines the association problem. We obtain some surprising results: (i) displacing a base station a little in one direction may result in the boundary of the corresponding cell to move in the opposite direction; (ii) A cell corresponding to a base station may be the union of disconnected sub-cells. We then study the Stackelberg equilibrium in the combined base station location and mobile association problem: we determine where to locate the base stations so as to maximize the revenues obtained at the induced SINR mobile association game. |
|
Gaoning HE, Motorola, European Communication Research
Download the slides Abstract : In this paper, we consider the uplink of a single cell network with K users simultaneously communicating with a base station using OFDM modulation over N carriers. In such a scenario, users can decide their power allocation based on three possible Channel State Information (CSI) levels, which are called complete, partial and statistical. The optimal solutions for maximizing the average capacity with complete and statistical knowledge are known to be the water-filling game and the uniform power allocation respectively. We study the problem in the partial knowledge case. We formulate it as a strategy game, where each player (user) selfishly maximizes his own average capacity. The information structure that we consider is such that each player, at each time instant, knows his own channel state, but does not know the states of other players. We study the existence and uniqueness of Nash equilibrium. We find the optimal solution for the symmetric case considering two positive channel states, and we show the optimization problem for any L states. |