GAMES is a bi-monthly event that aims at discussing multi-criteria optimization and game theoretic frameworks for networks and distributed systems. Each meeting is led by one of the members, on a specific topic. Slides used in each meeting are freely available on this web page.


For further information, please contact Corinne Touati at corinne.touati[at]inria.fr

Location: Room 209, LIG-Montbonnot, 53 av. J. Kuntzmann, 38330 Montbonnot-Saint-Martin
Meeting schedule: Every other Fridays at 2PM.

Upcoming events

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
May 22-23, 2008, Grenoble

ISDG 2008 (International Symposium on Dynamic Games and Applications) : http://neyman.im.pwr.wroc.pl/isdg08/
June 30 - July 3, 2008, Wroclaw, Poland

SAGT 2008 (International Symposium on Algorithmic Game Theory) : http://sagt08.upb.de/,
April 30 - May 2nd, 2008, Paderborn, Germany

Meetings (click on their title to get details)

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

Abstracts

08/04/2009 : Pierre Coucheney : Fair and Efficient User-Network Association Algorithm for Multi-Technology Wireless Networks

Pierre Coucheney

Abstracts :
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..

20/06/2008 : Pierre Coucheney : Efficient Vertical Handover Mechanisms in Wireless Networks

Pierre Coucheney

Abstracts :
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.

23/05/2008 : Denis Trystram : What contribution can we expect from Game Theory for scheduling?

Denis Trystram

Abstracts :
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.

01/02/2008 : Arnaud Legrand : How to measure efficiency?

Arnaud Legrand (http://www-id.imag.fr/Laboratoire/Membres/Legrand_Touati/perso.php)
Get the slides

Abstracts :
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.

11/01/2008 : Corinne Touati : Kick-off meeting: an introduction to game theory and its application to communication networks and distributed systems

Corinne Touati (http://www-id.imag.fr/Laboratoire/Membres/Touati_Corinne/perso-EN.php)
Get the slides

Abstracts :
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.


Links

Publications