GAMES est un groupe de travail bi-mensuel réunissant des chercheurs en théorie des jeux et optimisation multi-critères pour les réseaux et systèmes distribués. Chaque réunion se déroule sous la forme d'un exposé de l'un des membre et suivi de discussions constructives avec les intervenants. Les transparents utilisés au cours des réunions sont disponibles publiquement à partir de cette page.
Pour plus d'information et participer à nos activités, merci de contacter Corinne Touati à l'adresse corinne.touati[at]inria.fr
Lieu des réunions: Bureau 209, LIG-Montbonnot, 53 av. J. Kuntzmann, 38330 Montbonnot-Saint-Martin
Heures: Un vendredi sur deux à 2 heures.
GameNets: International Conference on Game Theory for Networks: http://www.gamenets.org/
May 13-15, 2009, Istanbul
GameComp: Workshop on Game Theory for Analysis and Optimization of Computer Systems: http://www-id.imag.fr/~touati/events/index-EN.php
22 - 23 Mai 2008, Grenoble
ISDG 2008 (International Symposium on Dynamic Games and Applications) :
http://www.im.pwr.wroc.pl/~isdg08/
30 juin- 3 juillet 2008, Wroclaw, Pologne
SAGT 2008 (International Symposium on Algorithmic Game Theory) :
http://sagt08.upb.de/,
30 avril - 2 mai 2008, Paderborn, Allemagne
Date |
Day |
Title |
Speaker |
08/04/2009 | Friday | Fair and Efficient User-Network Association Algorithm for Multi-Technology Wireless Networks | Pierre Coucheney |
20/06/2008 | Friday | Efficient Vertical Handover Mechanisms in Wireless Networks | Pierre Coucheney |
21-23/05/2008 | Friday | GameComp: Workshop on Game Theory for Analysis and Optimization of Computer Systems | GameComp |
23/05/2008 | Friday | What contribution can we expect from Game Theory for scheduling? | Denis Trystram |
01/02/2008 | Friday | How to measure efficiency? | Arnaud Legrand |
11/01/2008 | Friday | Kick-off meeting: an introduction to game theory and its application to communication networks and distributed systems | Corinne Touati |
Pierre Coucheney
Abstract : Recent mobile equipment (as well as the norm IEEE 802.21) offers the possibility for users to switch from one technology to another (vertical handover). This allows flexibility in resource assignments and, consequently, increases the potential throughput allocated to each user. In this paper, we design a fully distributed algorithm based on trial and error mechanisms that exploits the benefits of vertical handover by finding fair and efficient assignment schemes. On the one hand, mobiles gradually update the fraction of data packets they send to each network based on the rewards they receive from the stations. On the other hand, network stations send rewards to each mobile that represent the impact each mobile has on the cell throughput. This reward function is closely related to the concept of marginal cost in the pricing literature. Both the station and the mobile algorithms are simple enough to be implemented in current standard equipment. Based on tools from evolutionary games, potential games and replicator dynamics, we analytically show the convergence of the algorithm to fair and efficient solutions. Moreover, we show that after convergence, each user is connected to a single network cell which avoids costly repeated vertical handovers. To achieve fast convergence, several simple heuristics based on this algorithm are proposed and tested. Indeed, for implementation purposes, the number of iterations should remain in the order of a few tens.. |
Pierre Coucheney
Abstract : To address the challenges raised by the increasingly demanding wireless urban network users, different technologies and networks have to be used altogether. We consider network nodes in a geographical area covered by a UMTS network (administrated by a local operator). In addition, each node has the option of connecting to a local IEEE 802.11 access point (AP). We consider that users can multihome, i.e. split their traffic between their Wi-Fi AP, and the global UMTS network so as to make better use of the global resource. In this talk, we present a fully distributed algorithm based on trial and error mechanisms, where mobiles gradually update the fraction of packets they sent to each network based on rewards they receive from the stations, so as to converge towards efficient (in terms of throughput) equilibria. More precisely, we show that the distribution of users converges to the solution of replicator dynamics. Using simple properties of potential games, we design fitness functions and the corresponding individual rewards to individual users so as to obtain globally efficient equilibria. |
Denis Trystram
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
(http://www-id.imag.fr/Laboratoire/Membres/Legrand_Touati/perso.php)
Télécharger les transparents Abstract : In the context of game theory applied to communication networks, many concepts have been proposed in order to measure the efficiency and optimality of resource allocation mecanism, the most famous ones being the price of anarchy and the Jain index. In this talk, I will try to present a general framework for such a study and some concepts that have been proposed. I will try to exhibit the similarities and differences between them as well as their advantages and drawbacks. |
Corinne Touati
(http://www-id.imag.fr/Laboratoire/Membres/Touati_Corinne/perso-EN.php)
Télécharger les transparents Abstract : In this talk we review some classical concepts of game theory: Pareto optimization, Nash equilibria, Wardrop equilibria, Evolutionary games, Stochastic games, Potential games, Stackelberg equilibria, correlated equilibria, pricing mechanisms, Bargaining solutions, mechanism design, auction mechanisms, impact of non-cooperative players in cooperative environments and cake-cutting problem. For each of them we mention some examples taken from the networking or distributed system litterature. |