ER-03 (2010): Game theory for networks

du 25 au 29 janvier 2010 — ENS Lyon

Intervenants :

Location and schedule

All the lectures will take place in amphitheater B, at the 3rd floor of the GN1 building (main building of the “exact sciences” part of ENS Lyon).

Schedule:

  • Monday 25/01/2010 Morning: Eitan Altman 11:00 – 13
    Zero-sum Games: these are the most elementary game where there are two players, one playing against the other. These games are useful for modeling malicious users, denial of service attacks, jamming etc.  We introduce the notions of upper and lower values as well as the notion of value of a zero-sum game. We present some minimax theorems which are used to establish the existence of a value. We end with an LP solution for Zero sum matrix games. We present examples of games with and without a value.   Solution of 2 by 2 matrix games.
    Non-zero sum games. We present the notion of Nash equilibrium as   well as epsilon Nash equilibrium. We then introduce    Coordination Games and present their properties. We then study    Lemke’s algorithm for computing the equilibrium in non-zero sum games    with two players. We present examples of channel selection games.   We end this part with the concept of Correlated equilibrium

    Afternoon: Corinne Touati 14h30 – 17h00
    Notions from cooperative game theory: Bargaining and fairness.
    Le but de cette partie est de comprendre comment appréhender les qualités d’une allocation (équilibre de Nash ou valeur optimisant une fonction par exemple). Nous commençons par la définition de la propriété d’optimalité. Parmi l’ensemble des points optimaux, un ensemble de critères permet de choisir un point dit équitable. Nous présentons des techniques numériques permettant d’approcher la frontière de Pareto et de calculer les points équitables. Enfin, nous verrons dans une dernière partie des méthodes d’évaluations des performances d’allocations, en terme à la fois d’équité et d’optimalité.
    1. Optimalité
    a. Définition de Pareto et notions liées
    b. Propriétés des ensembles de Pareto (par ex. compacité)
    c. Epsilon-approximation et méthodes de résolutions
    d. Introduction à l’optimisation multi-critères, exemple d’un problème d’ordonnancement.

  • Tuesday 26/01/10  Morning: Corinne Touati 10:30 – 12:30
    2. Fairness and Nash bargaining.
    a. Axiomatic definitions: Thomson, Raiffa-Kalai-Smorodinsky, Nash)
    b. Equivalent optimizations and properties
    c. Alpha fairness
    d. Algorithmic solutions.
    e. Application to flow control and TCP.
    3. Performance evaluation of the resource allocation:
    a. The Gain index,
    b. Price of anarchy
    c. Selfish Degradation Factor
    d. Pareto equilibrium

    Afternoon: Eitan Altman 14:00 – 16:30
    Convex games. These are games with a convex compact space. We shall study Rosen’s theory for the existence of an equilibria,   The strict diagonal concavity property (which extends concavity    to a game context). This notion is used to establish    uniqueness of equilibrium in convex games.
    We then introduce games with coupled constraints    as in Rosen, as well as the related    notion of generalized Equilibrium. These are equilibria in which the space of actions of each player are not independent: the actions available to a player may depend on those already chosen by others (for example, if there are capacity constraints over links then the amount of flow that a player can send over a link depends on how much other players send over that link). In the presence of such constrained there is in general no uniqueness of equilibrium. We thus introduce the problem of equilibrium selection. We introduce in particular the notion of normalized Nash equilibrium which and and relate it to scalable pricing.

  • Wednesday 27/01/10Morning Rachid El-Azouzi 9h30 – 12h30
    Energy-efficient power control games Non-cooperative games where terminals want to maximize the number of information bits per joule are analyzed. The solution of this game is shown to be inefficient.
    Medium access games: the aloha game.

    Afternoon Rachid El-Azouzi 14:00 – 17:00
    Super-modular Games and Potential Games. These are two classes of games in which not only do we know that equilibria exists, but we also know that sequence of best responses of players convenrge to the equilibrium. In particular, we show how potential games can be transformed into a global optimization problem whose optimum corresponds to the equilibrium of the original game.
    Routing games Wardrop equilibrium: the players are modeled as infinitesimally small, which means that we have a continuum of players. computation of the equilibrium of the game
    Definitions. Price of anarchy, price of stability, variational inequalities. Link between Nash and Wardrop equilibria.

  • Thursday 28/01/10Morning: Corinne Touati 10:30 – 12:30
    Evolutionary game theory and population games. (games are related to infinite number of players). We introduce the concept of equilibrium is Evolutionary Stable Strategy, which is more general than a Nash equilibrium in a given sense.
    Replicator Dynamics and evolutionary dynamics: Methods for convergence to equilibria, cases of non-convergence and oscillations. Based on the idea that higher fitness will be adopted by a growing number of individuals. Other evolutionary dynamics: Brown-von Neumann-Nash, Best response dynamics, Fictitious play, Logit response dynamics. We will discuss about the main difference of those dynamics and present a generalization which is called the revision protocols.

    Afternoon: Corinne Touati 14:00 – 17:00
    Learning in games. All the previous evolutionary dynamics are related to learning process. The theory of learning in games explains the dynamic behavior of each player or agents depending on its own experience. Those learning processes related to the evolutionary dynamics, are used in order to construct distributed algorithms converging to equilibrium (Nash or ESS). We will introduce an example of distributed algorithm proposed in the literature which has been widely used in the networking community for power control, pricing, resource sharing and routing protocol. We will present other reinforcement learning algorithms: the Erev-Roth algorithm, and the Arthur algorithm for a variant of the last one with renormalization. Those distributed algorithms have interesting properties of implementation as they are totally distributed but they suffer from stability problems at the boundary of the state space. We will investigate how feedback delays and errors affect convergence

  • Friday 29/01/10Morning: Eitan Altman  11:00  – 13:00
    The Braess paradox. Routing games with finitely many users: Uniqueness of the equilibrium.  Parallel links. Load balancing problems. Relation to Ad-hoc networks.

    Afternoon: Eitan Altman 14:30 – 17:00
    Introduction to Repeated Games. Threats and punishments. Credibility of threats and refinements of equilibria. Stochastic games and Dynamic programming approach for stochastic games. The discouted cost and the average cost games. Product stochastic games. Anonymous sequential games, Markov Decision Evoluationary Games.

Correspondant local

  • Paulo Goncalves

6 comments to ER-03 (2010): Game theory for networks