Corinne Touati

Researcher at the Inria in the LIG laboratory (Grenoble, France)

INRIA LIG
INRIAID Laboratory Version francaise: Version française

Main research themes

I am interested in several game theory concepts applied to real situations in communication networks and large distributed systems.

Fairness levels

We are working on a scheduling problem on a master-slave platform. The aim of this study is to show that when users exhibit a selfish (or non cooperative) behavior, it is not sufficient for the platform to ensure a equal share of the resources at each instant for the resource sharing to be fair, or even efficient. In other words, a fairness in the system level doesn't provide with fairness at the application level . [System details]
References :[Legrand et al. Infocom 2007]

Fairness in non convex systems

We study an example of non-convex system of load balancing in distributed systems. A classical hypothesis in game theory is to consider the utility set of players as being convex. We show in this work, by using a simple system, that this hypothesis is particularly restrictive and that the non-convexity of the functions can imply some important difficulties in ways of defining fairness. [Details]

We also study the link between these fairness criteria and the Nash equilibria. The laters are obtained when each player (here each flow of requests) follows a strategy that is individually optimal. It has been shown that the equilibria obtained by such strategies are generally sub-optimal. We therefore studied a new criteria, called Nash Proportionate fairness that is optimal while guarantying performances proportional as those that would be obtained by a Nash equilibrium. We study the properties of such criteria and its eventual relationship with the ones previously studied. We showed that the non-convexity of the system lead to counter-intuitive results. References :[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.