Corinne Touati

Chargée de recherche Inria au laboratoire LIG (Grenoble)

INRIA LIG
INRIALaboratoire ID English version English version

Principaux thèmes de recherche

Je m'intéresse aux divers concepts de théorie des jeux appliqués à problèmes concrets issus des réseaux de télécommunications et des grands systèmes distribués.

Niveaux d'équité

Nous travaillons sur un problème d'ordonnancement dans un système maître-esclave Le but de cette étude est de montrer que lorsque les utilisateurs ont un comportement égoïste (ou non-coopératif), il n'est pas suffisant qu'une plate-forme effectue un partage égalitaire à chaque instant pour que le partage de ressource soit équitable, ni même optimal. En d'autres termes, une équité au niveau « système » n'engendre pas une équité au niveau « utilisateur ». [Détails du système]
Références :[Legrand et al. Infocom 2007]

Equité dans les systèmes non convexes

Nous étudions un exemple de système non-convexe de partage de charge dans des systèmes distribués. Une hypothèse classique en théorie des jeux est de considérer l'ensemble des utilité des joueurs convexes. Nous montrons ici, dans un exemple simple, que cette hypothèse est particulièrement restrictive, et que la non-convexité des fonctions peut impliquer d'importantes difficultés dans la manière même de définir l'équité. [Détails du système]

Nous nous intéressons également au lien entre ces critères d'équité et les équilibres de Nash. Ces derniers sont obtenus lorsque chaque joueur (ici chaque flot de requêtes) choisit une stratégie optimale individuellement. Il a été montré que les équilibres obtenus par de telles stratégies sont généralement non-optimaux. Nous avons alors proposé un nouveau critère équité, dénommé critère de Nash Proportionnel qui est optimal tout en garantissant des performances proportionnelles à celles qui seraient obtenues par un équilibre de Nash. Nous étudions les propriétés d’un tel critère et sa relation éventuelle avec ceux précédemment étudiés. Nous avons montré que la non-convexité du système conduisaient à des résultats contre-intuitifs. Références :[Touati et al., ISDG 2004, Inoie et al., ISDG 2004, Touati et al., TR 2005].

Non-optimalité des systèmes non-coopératifs

Nous étudions un problème de contrôle de flux dans lequel nous avons exhibé un cas de paradoxe de Braess. L'étude de tels paradoxes est d'importance primordiale. En effet, lorsque les différents acteurs d'un même système ne coordonnent pas leurs actions (on parle alors de non-coopération) et optimisent individuellement leurs fonctions d'utilité, les équilibres obtenus ne sont pas optimaux. Une conséquence de cette sous-optimalité est l'apparition de paradoxes, phénomènes dans lesquels l'ajout de ressource au système provoque la dégradation des performances de tous les acteurs. [Détails du système]
Références :[Inoie et al., C&OR 2006, Inoie et al., CDC 2004, Touati et al., TR 2005].

Nous nous intéressons également au définitions de mesures d'optimalité des équilibres. En effet, nous avons mis en évidence que la très célèbre mesure du "prix de l'anarchie" (price of anarchy) ne définit pas une mesure d'efficacité mais une distance par rapport à un point (efficace) particulier. Alors, des équilibres optimaux (au sens de Pareto) ou même optimaux et équitables (comme par exemple au sens du NBS - Nash Bargaining Solution) peuvent avoir de très mauvaises valeurs de prix d'anarchie. Nous proposons donc des mesures d'efficacité basées sur la distance à la frontière de Pareto.
Références :[Legrand et al. Infocom 2007]

Systèmes de tarifications Nous travaillons, en collaboration avec Parijat Dube et Laura Wynter (IBM T.J. Watson Research Center - New York) sur un problème de tarification pour des services de commerce électronique. Nous considérons dans notre modèle deux entreprises en compétition. Plus généralement l’une d’elle peut représenter une grande entreprise et la seconde le reste du marché. Nous supposons que les clients peuvent choisir librement de joindre l’une ou l’autre des firmes. Nous caractérisons alors le comportement de chacun d’eux par un paramètre représentant son attitude face au compromis entre qualité de service et prix auquel il fait face. Le profil du marché est ainsi représenté par la distribution de ces paramètres. Nous utilisons les formulations classiques de la théorie des files d’attentes pour obtenir des relations explicites entre les qualités de services obtenues et les prix offerts.
La difficulté d’une telle étude réside alors dans le fait que la qualité de service dépend du nombre d’utilisateurs joignant l’entreprise, lui même dépendant des prix exercés. En étudiant la stratégie optimale de chaque compagnie - i.e. le prix optimal à afficher pour l'accès à son service -, nous avons montré un phénomène dit de 'tit-for-tat'.
Références :[Dube et al., Informs 2005, Touati et al., Networking 2004]
L’équité dans les réseaux de télécommunications

Il a été montré que la satisfaction relative qu'apporte une allocation à un utilisateur dépend de l’application utilisée, ce qui n’est pas pris en compte par les protocoles actuellement utilisés. Nous proposons d’adapter les critères d'équité issus de la théorie des jeux afin de prendre en compte les particularités inhérentes aux réseaux de télécommunications, et en particulier aux besoins des applications temps réel. Nous nous sommes en particulier inspiré du NBS (Nash Bargaining Solution) pour adapter une large famille de critères d’équité (couvrant entre autres les connus d’équité max-min et d’équité proportionnelle) afin de prendre en compte les fonctions d'utilités des applications. Ces dernières représentent la satisfaction relative qu'apporte l'allocation aux utilisateurs. Références :[Touati et al., NPDPA 2002, Altman et al., ISDG 2002 Touati et al., Comnet 2006, Touati et al., Inria 2001]

De plus, nous proposons des méthodes algorithmiques de résolution et adaptées à à des exemples de réseaux et basées sur une extension de la programmation linéaire : la SDP (Semi Definite Programming, ou Programmation semi-definie positive). Références :[Touati et al., GTA 2003, Touati et al., ITC 2003]

Nous nous sommes intéressés en particulier aux réseaux:
Note sur le lien scientifique et industriel.