%% ================================================================================
%% This LaTeX file was created by AbiWord.                                         
%% AbiWord is a free, Open Source word processor.                                  
%% More information about AbiWord is available at http://www.abisource.com/        
%% ================================================================================

\documentclass{article}\usepackage[latin1]{inputenc}
\usepackage{calc}
\usepackage{setspace}
\usepackage{graphicx}
\usepackage{multicol}
\usepackage{multirow} 
\usepackage[normalem]{ulem}
%Please set your language here
\usepackage[english]{babel}
\usepackage{color}
\usepackage{hyperref}
\usepackage{eurosym}
\usepackage{tikz}
\usepackage{colortbl}


\setlength{\oddsidemargin}{0.9840in-1in}
\setlength{\textwidth}{\paperwidth - 0.9840in-0.9840in}
\newcommand\refe{\footnote{ref?}}
\newcommand\betterrefe{\footnote{better/morerecent ref?}}
\newcommand\traduction[1]{\emph{#1}{\footnote{traduction?}}}
\newcommand\question[1]{{\footnote{#1}}}

%%%%%%%%%


\newcommand\META[1]{\textbf{#1:}}
\newcommand{\cocher}{$\fbox{x}$}
\newcommand{\noncocher}{$\fbox{\textcolor{white}{x}}$}

\newcommand\COMMENTAIRE[1]{\textbf{\textit{ #1}}}
\newcommand\COMMENTAIREFN[1]{\footnote{\textbf{\textit{ #1}}}}
\newcommand\qed{\fbox{}}
\newcommand\MISSING[1]{\textbf{\textit{ #1}}}

\begin{document}

\title{Programme BLANC \\
Document de Soumission B}
\author{Edition 2009}
\date{\today}
\maketitle

{\Large
\begin{tabular}[h]{|c|ccccccccc|}
  \hline
Acronyme & \multicolumn{9}{|c|}{$JEDY \& CO$} \\ \hline
Titre du projet & \multicolumn{9}{|c|}{\textbf{JE}ux \textbf{D}ans les s\textbf{Y}st{\`e}mes dymaniques et \textbf{CO}nvergences} \\
en fran{\c c}ais     &        &          &        &         &          &        &          &        & \\ \hline
Titre du projet & \multicolumn{9}{|c|}{Games in dynamic systems and Convergences} \\
en anglais     &        &          &        &         &          &        &          &        & \\ \hline
CSD principale & $\fbox{x}$ 1& $\noncocher$ 2& $\noncocher$ 3& $\noncocher$ 4& $\noncocher$ 5& $\noncocher$ 6& $\noncocher$ 7& $\noncocher$ 8 & $\noncocher$ 9 \\\hline
CSD secondaire & $\noncocher$ 1& $\noncocher$ 2& $\noncocher$ 3& $\noncocher$ 4& $\noncocher$ 5& $\noncocher$ 6& $\noncocher$ 7& $\noncocher$ 8 & $\noncocher$ 9 \\
(\emph{si interdisplinarit{\'e}}) &        &          &        &         &          &        &          &        & \\ \hline
\end{tabular} }

\tableofcontents
 

\newpage

\section{{Contexte et positionnement du projet / context and positionning of the proposal}}


More and more distributed systems include agents that interact in
various and varying degrees of collaboration and competition. For
example, in telecommunication protocols, inter-domain routing often
involves routes that belongs to commercial companies whose benefits
are function of the involved traffics, and hence function of a global
competition. As another example, in the computational grid tasks must
often be scheduled on machines, that may belong to several
organizations that have their own objectives. This may lead to
globally sub-optimal load balancing situations resulting of the
competition between organizations that have to optimize their own
objectives.


Most of  solutions in distributed systems have been conceived with the
classical tools of distributed algorithms. Classical distributed
algorithms consider that agents may be faulty, but that non-faulty
agents are all contributing to a common social objective. In the last
ten years, many works were devoted to reconsider several algorithms or
constructions with more realistic hypotheses upon agents, taking into
considerations that they may be independent agents with economic or
own profits, using Game theory.

Game theory is indeed a natural tool to study theses systems, as it is
a branch of mathematics that aims at predicting toward which
situation(s) should be a set of rational partners will converge in a competition
\cite{LivreGameTheory}.


Game theory introduces several notions of equilibria, that aims at
modeling situations where all individual players act in accordance
with their selfish interest. In particular, a Nash Equilibrium is a
configuration in which no rational partner has some unilateral
incentive to depart: if the choices (called strategies in this theory)
made by its opponents are kept fixed, no player has a benefit in
changing unilaterally his/her own strategy. Since the introduction of this
concept by Nash in \cite{Nash50}, many variants of this notion of
equilibrium have been proposed and studied: see for e.g. perfect
equilibria \cite{Sel75}, proper equilibria \cite{My78}, sequential
equilibria \cite{KW82}, stable equilibria \cite{Nash50} \dots etc):
see \emph{e.g. } \cite{Dam87}.


Game theory, that comes originally from Mathematics and Economics, is  distinguished from
Algorithmic Game Theory. Indeed, most historical developments of
classical theory have been obtained without any consideration of
effectiveness. Algorithmic Game Theory, which is mainly less than 10
years old, aims at revisiting constructions from a complexity and
distributed algorithmic point of view. For example, while Nash theorem
establishes that a mixed equilibrium always exist using Brouwer fix point
theorem, there is no guarantee that it can be computed, and even if it
is computable, that it may be computed efficiently or piratically by players.


Given the description of a system, the problem of \textbf{computing
  its equilibria} is the problem of determining the situations that
should be reached if all partners were rational. A lot of attention has
been put recently to this problem, by considering several situations
and several constraints, for example in the fields of networks or
scheduling \cite{bookGamesTheory}. The problem of computing equilibria
from a theoretical complexity point of view has also received much
attention in the last five years: see
e.g. surveys~\cite{ChenD06,SurveyComplexity}. However, most of these
studies \textit{require a full description of the system} in order to
compute the equilibria, and consider mostly \textit{centralized
  (i.e. non-distributed) algorithms}.
 % In particular, since definitions of notions like Nash Equilibria involve all partners and all their strategies, and hence the full description of the game, 

Now, a system may have several equilibria, but all of them are often
not equivalent for the global efficiency.

Given the description of a system, \textbf{the evaluation of
  equilibria} is the hard problem of comparing equilibria. If an
equilibrium is not Pareto optimal, meaning that the players' payoffs
can all be increased, this is clear that the equilibrium is not
desirable. But, a system may have many Pareto optimal situations -
situations that cannot be improved upon without hurting at least one
player- but with non equivalent individual or social
outcomes. Equilibria can be compared for instance according to the
fairness between partners, using measures like the Jain index \cite{Jain},
or variants of price of anarchy or of stability that are ratio
introduced to quantify the lost induced by competition with respect to
an ideal cooperation. See \emph{e.g. } \cite{Survey1,Survey2}
\betterrefe for surveys with numerous references on the subject. These
notions are often \textit{global notions}, that \textit{cannot be
  computed locally, and hence used locally in a implementation of a
  distributed system.}


The design of distributed algorithms is classically done in order to
guarantee that the final state reached by agents is the expected one,
i.e. is correct.  As we said, it has been observed in the last decade
that several applications coming from distributed systems involve
naturally competitions between agents, and hence can be modeled by
game theory. Several distributed problems have been revisited under
this aspect. But most of the attention have been put up to this day to
guarantee that final states correspond to equilibria, and hence to
rational situations, but \textit{ignoring if these situations of
  equilibria can be reached by the distributed system},
i.e. \textit{can be reached by agents using only local information}.
Indeed, in distributed systems, players generally correspond to agents,
that do not have or cannot have a global view of the system. This
means that the equilibria, and possibly the best equilibrium, must be
computed in a distributed fashion, without information that are non-local to
agents.

Since some/most notions of equilibria from game theory are global
notions, and hence can not be computed exactly with only local
information, this forces to relax the considered notion of
equilibria to more approximate notions. For example, whereas it may
be difficult to guarantee that a system is globally in an Nash
equilibrium, it may be possible to guarantee that the situation
reached is such that any agent is locally in an equilibrium with all
its neighbors. \question{ok? citer graphical games?}


This project proposes to give answers to the following  problems:
\begin{itemize}
\item In applications coming from distributed systems, chosen in the
  context of situations where some agents compete for common
  resources, determine whether some equilibrium be computed in a
  distributed fashion. This means: determine whether the agents can be
  designed such that the system evolves globally to states that
  correspond to some notion of equilibria. Describe the notions of
  equilibria that can be computed in such a way.


\item Determine whether good/expected equilibria can be computed in a
  distributed fashion. That is to say, determine whether there is a
  way to guarantee the evolution towards efficient equilibria, for
  various notions of efficiency considered in literature.


\item Discuss the quality of the obtained solutions. First, understand
  what is the complexity of solutions from a complexity point of view:
  characterize when this is possible to some polynomial time
  algorithms. Determine bounds on the time required before reaching
  some equilibria, or a situation close to equilibria.  Second,
  understand what are the guarantees given by the proposed algorithms:
  explicit the relations between reached situations, and the ones that
  would have been obtained using exact notion of equilibria and
  centralized algorithms.
\end{itemize}
 
Considered applications will be chosen among  problems coming
from scheduling  applications in the computational grid and from interdomain
routing, using the fields of expertise of involved partners.

% \MISSING{En dire plus sur les applications viseees quelque part}

% \vfill
% \COMMENTAIRE{Question: Poids des applications? On est plutot amont, ou sur des applications? }
% \vfill

%%%%%%%%%


\section{{Description scientifique et technique / scientific and technical description}}

\subsection{\textcolor[rgb]{0.000,0.502,0.502}{Etat de l'art / Background, state of the art}}

\textbf{\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize (2 pages maximum)}}}}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Presenter un }}}\textbf{\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize etat de lart national et international }}}}\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize dressant letat des connaissances sur le sujet et decrivant le }}}\textbf{\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize contexte et les enjeux scientifiques}}}}\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize  dans lequel se situe le projet}}}\textbf{\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize .}}}}\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize  Faire apparaitre deventuels resultats preliminaires.}}}





This project proposes to give answers to the following  problems:
\begin{itemize}
\item In applications coming from distributed systems, chosen in the
  context of situations where some agents compete for common
  resources, determine whether some equilibrium be computed in a
  distributed fashion. This means: determine whether the agents can be
  designed such that the system evolves globally to states that
  correspond to some notion of equilibria. Describe the notions of
  equilibria that can be computed in such a way.


\item Determine whether good/expected equilibria can be computed in a
  distributed fashion. That is to say, determine whether there is a
  way to guarantee the evolution towards efficient equilibria, for
  various notions of efficiency considered in literature.


\item Discuss the quality of the obtained solutions. First, understand
  what is the complexity of solutions from a complexity point of view:
  characterize when this is possible to some polynomial time
  algorithms. Determine bounds on the time required before reaching
  some equilibria, or a situation close to equilibria.  Second,
  understand what are the guarantees given by the proposed algorithms:
  explicit the relations between reached situations, and the ones that
  would have been obtained using exact notion of equilibria and
  centralized algorithms.
\end{itemize}







This context of game with local view (local in the sense of a
distributed system) is not so standard in literature.


\paragraph{Other game theoretic models}

These fields of applications have already been considered in game
theoretic settings for several other applications.

In particular, a general and now classical theoretical setting for load balancing has
been introduced in \cite{KP99}. Tasks or jobs (players) whose
objective is to minimize their own cost must be mapped to
servers. Such games are sometimes called the \textit{KP model}
\cite{KP99,ChapterVocking}. This model can also be formally defined as
a routing problem between two nodes connected by parallel edges with
possibly different speeds.  Each agent has an amount of traffic to map
to one of the edges such that the load on this edge is as small as
possible \cite{KP99}.  
Wardrop network\cite{Wardrop-52}\refe can be considered as a
generalization of this model.  

These models have essentially been studied from a general complexity
theoretic point of view, sometimes as toy examples.

% Similar games but with more general cost functions have also been
% considered: see
% e.g. \cite{ChapterVocking,caragiannis6tbs,czumaj2002sta,libman2001ars},
% and all references in \cite{ChapterVocking}.
% %
% Refer to \cite{Survey2,Survey1,Survey3} for surveys about results for
% selfish load balancing and selfish routing on parallel links.



% Wardrop traffic model  was conceived to represent road traffic with the idea of an infinite number of agents being responsible for an infinitesimal amount of traffic each. A network equipped with non-decreasing latency functions mapping flow on edges to latencies is given. For each of several commodities a certain amount of traffic, or flow demand, has to be routed from a given source to a given destination via a collection of paths. A flow in which for all commodities the latencies of all used paths are minimal with respect to this commodity is called a Wardrop equilibrium of the network. % Whereas this is well-known that such equilibria can % be solved by centralized algorithms in polynomial time, as in \cite{Fischer07} we are interested in % \textit{distributed} algorithms to compute Wardrop equilibria.

Some authors involved in this proposal have already considered more
specific applications related to the fields of applications proposed
here.  Works~\cite{PascualRT07,Loubna2007} consider the dual settings
where players correspond to resources (like servers, routers) in the
context of some network or computational grid
applications. In~\cite{PascualRT07} players correspond to servers and
not to tasks in a load balancing problem. In \cite{LegrandCoRR2007} the
problem is to concurrently schedule multiple applications on an
heterogeneous network of computers in a computational
grid. In~\cite{Loubna2007}, nodes are considered as players and aim at
making profits from their incoming traffic.

More generally, many game theoretic settings have been discussed in
the context of wireless networks\refe, or in network contexts. In
most of these studies, in the spirit of classical game theory, the
problem is often to model a situation as a game, and then use the
concepts of equilibria from game theory to derive what will be the
rational situations. \refe

From an abstract complexity point of view, the hardness of computing
the equilibria of a game is now rather
well understood\cite{SurveyComplexity}, and one can say that most of
the work done so far using game theory in these application domains is
about computations of equilibria of particular games, with constraints
specific to considered applications.

\paragraph{Measuring quality of equilibria} 


Various quantities have been
introduced to quantify efficiency of equilibria. For example, Price of
anarchy, introduced by \cite{KP99}, comparing cost of Nash equilibria
to cost of the optimal (social cost) has been intensively studied on
the KP model: see e.g. \cite{ChapterVocking} for a reference
introduction. This has been extended to Wardrop network games \refe,
or to above mentioned extensions of the KP model
\refe. \COMMENTAIREFN{Indices de Jains? Other things a deevelopper ici?}

\paragraph{Computing equilibria in a distributed fashion?}

However, in all above works, equilibria are not assumed to be computed
locally: from a global description of the system, using the considered
(usually global) notion of equilibria, one analytically derives  what
should be the situation(s) assuming that agents are rational. In the
spirit of most classical game theory, one does not really discuss how
agents can evolve in order to reach such a situation.

In that sense, when we said that the hardness of computing the
equilibria of a game is now rather well
understood\cite{SurveyComplexity}, the notion of computation involved
is the notion of centralized algorithm: that is to say, about
(non-distributed) algorithms which are intended to take a description of
the system and output a description of its equilibria.

When designing a distributed system, an important problem is to
understand if distributed agents can be programmed such that the
system evolves towards equilibria. Only a few works have been devoted
to this problem.

\paragraph{Computing equilibria by learning}

A first way to compute equilibria is to use the theory of the learning
of equilibria in classical game theory. In classical \textit{game
  theory}, various algorithms for learning equilibrium states have
been proposed: % centralized and decentralized (or distributed)
% algorithms,
games with perfect, complete or incomplete information,
with a restricted number of players, etc... See
e.g. \cite{LearningAutomata89} for an introduction to the learning
automata model, and the general references in
\cite{DecentralizedLearning94} for specific studies for zero-sum
games, $N$-person games with common payoff, non-cooperative games,
etc...

However, most of the previous approaches cannot be implemented in a
distributed system: for example, \emph{dummy player approaches} require to
maintain a global view of the system, as well as an full history of
the system.

 

In the KP model, it has been observed that the proof of existence of a
pure Nash equilibria can be turned into a dynamic: players play in
turn, and move to machines with a lower load. Such a strategy can be
proved to lead to a pure Nash equilibrium by use of a potential
argument. Bounds on the convergence time have been investigated in
\cite{EvenDaretal03,Even-DarKM07}. Considered algorithms are
centralized and require complete information games.  Bounds
are mostly obtained by bounding the possible variations of suitable
potential functions. Since players play in turns, this is often called
the \textit{Elementary Step System}. Other results of convergence in
this model, have been investigated in
\cite{GoldbergPODC2004,libman2001ars,orda1993crm}.

Concerning models that allow concurrent decisions, we can mention
the followings works. In \cite{Even-DarSODA2005}, tasks are allowed to
migrate in parallel from overloaded to underloaded resources. The
process is proved to terminate in expected $O(\log \log n + \log m)$
rounds. The analysis is restricted to the case of unitary weights, and
with identical machines. The considered process requires a global
knowledge: one must determine whether one load is above or under
average.


In \cite{SODA06} is considered a distributed process that avoids that
latter problem: only local knowledge is required. The process is
proved to terminate in expected $O(\log \log n + m^4)$ rounds. The
analysis is also done only for unitary weights, and for identical
machines. Techniques involved in the proof, relying on martingale
techniques,  are  somehow related to techniques for studying the
classical problem of allocating balls into bins games as evenly as
possible.


Some authors of this proposal considered in\cite{Boussaton08} a
particular learning scenario for tasks in the KP model.  This learning
algorithm, already considered in \cite{DecentralizedLearning94} for
general games, is proved to be convergent on these allocation games,
with provable error bounds on the convergence time \refe.

\paragraph{Computing equilibria by other means}

Alternatives to the theory of the learning of equilibria can also be
used to compute equilibria.

For example, some authors involved in this proposal in
~\cite{LegrandCoRR2007} a technique to compute in a distributed system
its Nash bargaining situations (NBS). The considered technique is
based on a gradient descent method, using the fact that NBS'
corresponds to the extrema of some function, not correlated to the
game.

For some other games, it is sometimes possible to use   learning
equilibria techniques but working on different games, in order to
guarantee convergence towards some equilibria. For example, 
\cite{TouatiCoRR2008} proposes a way to compute pure equilibria using
such an approach.


\paragraph{Complexity point of view} 
Observe that some, but only few, of the previous studies lead to bounds on the
convergence time: for example, \cite{Even-DarSODA2005} proves a
convergence in expected $O(\log \log n + \log m)$ rounds for the KP
model.

Notice also that distributed systems contexts sometimes lead to not
fully specified games in the spirit of game theory. For example, it is
not easy to define precise player utilities for multicriteria
scheduling. Equilibria like Pareto optimal situations can however
sometimes be computed. Discussing the complexity of these distributed
algorithms hence yields to discuss relations between optimal
situations and equilibria situations.

More generally, only a few things are also known about the relations
between the effectively computed solutions and true equilibria. For
example, when working on gradient descent based methods, what is the
relation between a situation close to a minimum and the true
equilibria corresponding to the exact minimum.


 \paragraph{Our application context}

 We propose to consider applications coming from scheduling problems
 in the context of the computational grid and from interdomain
 routing, using the fields of expertise of involved partners. In
 particular, some partners have been working on multi-objective
 scheduling problems \refe. One considers a set of machines
 (heterogeneous processor or group of homogeneous processors) that are
 independent with their own control. Some tasks are submitted locally
 in each organization, but can be executed on some other
 organizations, as soon as local efficiency of locally submitted tasks
 are not too much penalized. We also have been working on interdomain
 routing, in the presence of routers that belong to several companies
 whose aim at making profits from incoming traffic \refe.

 In these applications, the common problem is to allocate some
 resources to some agents corresponding to players. These agents are
 in a situation of competition, and are agents in a distributed
 system. As such, they can not have easily a full description of the
 game, but have only a local view of the system.


\subsection{{Objectifs et caractere ambitieux/novateur du projet /
    Rationale highlighting the originality and novelty of the
    proposal}}


\textbf{\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize (2 pages maximum)}}}}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Decrire les }}}\textbf{\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize objectifs scientifiques/techniques}}}}\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize  du projet.}}}


This project proposes to give answers to the following  problems:
\begin{itemize}
\item In applications coming from distributed systems, chosen in the
  context of situations where some agents compete for common
  resources, determine whether some equilibrium be computed in a
  distributed fashion. This means: determine whether the agents can be
  designed such that the system evolves globally to states that
  correspond to some notion of equilibria. Describe the notions of
  equilibria that can be computed in such a way.


\item Determine whether good/expected equilibria can be computed in a
  distributed fashion. That is to say, determine whether there is a
  way to guarantee the evolution towards efficient equilibria, for
  various notions of efficiency considered in literature.


\item Discuss the quality of the obtained solutions. First, understand
  what is the complexity of solutions from a complexity point of view:
  characterize when this is possible to some polynomial time
  algorithms. Determine bounds on the time required before reaching
  some equilibria, or a situation close to equilibria.  Second,
  understand what are the guarantees given by the proposed algorithms:
  explicit the relations between reached situations, and the ones that
  would have been obtained using exact notion of equilibria and
  centralized algorithms.
\end{itemize}
 

Considered applications will be chosen among  problems coming
from scheduling of applications in the computational grid and from interdomain
routing, using the fields of expertise of involved partners.


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Presenter }}}\textbf{\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize les avancees scientifiques}}}}\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize  attendues. Preciser loriginalite et le caractere ambitieux du projet.}}}

%% Relie fortement aux taches.

\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Detailler les }}}\textbf{\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize verrous scientifiques et techniques}}}}\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize  a lever par la realisation du projet.}}}

Among clear difficulties to reach these objectives are the following:
\begin{itemize}
\item Notions of equilibria from game theory are mainly global, and hence non-distributed notions, in the sense that they involve all agents. For example, in a Nash equilibrium, \textit{all} agents must be in a situation such that unilaterally they can not improve their payoff, fixing the strategies of \textit{all} other agents. When considering distributed algorithms, one need to replace these global notions by local criteria. This may lead to change the notions of equilibria considered into approximations, or approximated notions, that needs to be understood, and that are not classical.
\item Solutions from the theory of equilibria learning in games, or dynamic learning scenarios that we expect to use, often involve stochastic behaviors. This introduces clearly some difficulties. Classical notions of convergence or of termination for distributed systems need to be replaced by probabilistic notions. This involves all the subtleties behind the various notions of convergence for stochastic processes, like weak convergence, convergence in law, almost sure convergence, etc, and also behind their algorithmic study.

\item Solutions from the theory of equilibria learning in games, or dynamic learning scenarios that we expect to use, are often analyzed using continuous tools, like ordinary differential equations. These tools are used to discuss processes that are actually purely discrete. This involves all the discussions and problems behind analyzing discrete processes by continuous abstractions.
\end{itemize}




\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Decrire eventuellement }}}\textbf{\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize le ou les produits finaux developpes}}}}\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize  a lissue du projet montrant }}}\textbf{\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize le caractere innovant}}}}\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize  du projet.}}}

%% Reliefortement aux taches.


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Presenter les }}}\textbf{\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize resultats escomptes}}}}\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize  en proposant si possible des criteres de reussite et devaluation adaptes au type de projet, permettant devaluer les resultats en fin de projet.}}}


%% Relie fortement aux taches.


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Le cas
      echeant, demontrer }}}\textbf{\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize l'articulation entre les disciplines scientifiques }}}}\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize et le}}}\textbf{\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize  caractere interdisciplinaire }}}}\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize du projet.}}}



\section{{Programme scientifique et technique, organisation du projet / scientific and technical programme, project management}}

% We propose to reach our objectives  by  tacckling three main tasks: 
% \begin{enumerate}
% \item task 1: Existence of Equilibrium and Convergence
% \item task 2: Quality and Quantativity of Equilibrium
% \item task 3: Speed of convergence
% \end{enumerate}

% (Faire un dessin)
\bigskip
%
\begin{figure}
\begin{center}
\begin{tikzpicture}[thick]
\node[draw,anchor=east] (w3) {WP 3: Speed of Convergence};
\node[draw,right of=w3,anchor=west,xshift=4cm] (w2) {WP 2: Quality of Equilibria};
\node[draw,above of=w3,anchor=west,xshift=2cm] (sd) {dynamical systems};
\node[draw,above of=sd] (w1) {WP 1: Properties of Convergence};
\draw (w2) edge [->,bend left]  (w3);
\draw (w3) edge [->,bend left]  (w1);
\draw (w1.east) edge [->,bend left]  (w2);
\end{tikzpicture}
\end{center}
\label{fig:relations}
\caption{Relations between workpackages in the {JEDY\&CO} project.}
\end{figure}
%}
\bigskip

\subsection{\textcolor[rgb]{0.000,0.502,0.502}{Programme scientifique et structuration du projet / scientific programme, specific aims of the proposal}}

\textbf{\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize (2 pages maximum)}}}}


\textbf{\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Presentez le programme scientifique, la methodologie et la structuration du projet.}}}}


\textbf{\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Justifiez la decomposition en taches du programme de travail en coherence avec les objectifs poursuivis. }}}}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Les taches representent les grandes phases du projet. Elles sont en }}}\textbf{\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize nombre limite}}}}\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize .}}}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Presenter les liens entre les differentes taches (si possible, utilisez un diagramme ou un organigramme technique).}}}

The JEDY\&CO project is divided into three work packages  subdivided into three tasks. Each 
task is assigned a leader that is responsible for the on-time submission of the associated deliverables. 
More details about the organization of the JEDY\&CO   project are provided in Section \ref{sec:troisq} 


\begin{enumerate}
\item Work package 0: \textbf{Management} (Leader: Johanne  Cohen,
  PRiSM) 


\item  Work package 1: \textbf{Property of a dynamical system convergence for distributed and interactive Algorithms.}
  \begin{enumerate}
  \item Task 1.1: \emph{Distributed system with  players having local and partial
    information}  (Leader:  Denis Trystram, LIG)
  \item Task 1.2: \emph{Distributed hierarchical system with different types of players} (Leader: Corinne Touati, LIG)
  \item Task 1.3: \emph{Distributed system with dynamical interactions} (Leader: Dominique Barth, PRiSM)
  \end{enumerate}
\item  Work package 2: \textbf{Qualitative and Quantitative properties of  Equilibrium points}
 \begin{enumerate}
  \item Task 2.1: \emph{Optimality and fairness and correlation of  equilibria } (Leader: Corinne Touati, LIG)
  \item Task 2.2: \emph{Stability and Purity property} (Leader: Corinne Touati, LIG)
  \item Task 2.3: \emph{Reputation, truthful property, and robustness} (Leader: Johanne Cohen, PRiSM)
\item Task 2.4: \emph{Approximation, equity , Pareto approximation}  (Leader:  Denis Trystram, LIG)
  \end{enumerate}
\item  Work package 3: \textbf{Speed of convergence, number of iterations, and synchronization issues}
 \begin{enumerate}
  \item Task 3.1: \emph{Step size adaptation of stochastic system.}  (Leader: Johanne Cohen, PRiSM)
  \item Task 3.2: \emph{Speed of convergence of learning scenarios% multidimensional differential equations.
    } (Leader: Olivier Bournez, LIX)
  \item Task 3.3: \emph{Study of improvement given by asynchronous behavior on theoretical and
    heuristic point of view} (Leader: Bruno Gaujal, LIG)
  \end{enumerate}

\end{enumerate}

The expected schedule of the whole project (excluding the
``Management'' workpackage) over the three years life span is shown in
the Figure~\ref{fig:temporall}.
   

\begin{figure}
\begin{center}
\newcommand{\hauteur}{0.7}
\newcommand{\largeur}{2}

\begin{tikzpicture}[xscale=2,thick ]
\node[rectangle,draw,minimum width=\largeur cm,anchor = south west,minimum height=\hauteur cm] at (0*\largeur,0*\hauteur) (t11) {1.1};
\node[rectangle,draw,minimum width=\largeur  cm,anchor = south west,minimum height=\hauteur cm] at (1*\largeur,1*\hauteur) (t12) {1.2};
\node[rectangle,draw,minimum width=\largeur *1.5 cm,anchor = south west,minimum height=\hauteur cm] at (1.5*\largeur,2*\hauteur) (t13) {1.3};
\node[rectangle,draw,minimum width=\largeur cm,anchor = south west,minimum height=\hauteur cm] at (1*\largeur,3*\hauteur) (t22) {2.2};
\node[rectangle,draw,minimum width=\largeur cm,anchor = south west,minimum height=\hauteur cm] at (0.5*\largeur,4*\hauteur) (t21) {2.1};
\node[rectangle,draw,minimum width=\largeur cm,anchor = south west,minimum height=\hauteur cm] at (3*\largeur,5*\hauteur) (t23) {2.3};
\node[rectangle,draw,minimum width=\largeur cm,anchor = south west,minimum height=\hauteur cm] at (1*\largeur,6*\hauteur) (t24) {2.4};
\node[rectangle,draw,minimum width=\largeur *1.5 cm,anchor = south west,minimum height=\hauteur cm] at (0.5*\largeur,7*\hauteur) (t31) {3.1};
\node[rectangle,draw,minimum width=\largeur cm,anchor = south west,minimum height=\hauteur cm] at (1*\largeur,8*\hauteur) (t32) {3.2};
\node[rectangle,draw,minimum width=\largeur cm,anchor = south west,minimum height=\hauteur cm] at (2*\largeur,9*\hauteur) (t33) {3.3};
\draw[->] (t32) -- (t33);
\draw[->] (t32) -- (t23);
\draw [->] (t11) -- (t31);
%\draw[->] (t12) -- (t24);
\draw (t12) edge [->,bend right=15] (t24.south);
\draw[->] (t21) -- (t24);
%\draw[->] (0,0) -- (t22);
\draw[->] (0,0) -- (7,0); 
\draw[->] (0,0) -- (0,10); %% Attention c'est la qu'il faut.....

\end{tikzpicture}
\end{center}
\label{fig:temporall}
\caption{Temporal organization of the \textbf{JEDY\&CO} project.}
\end{figure}


The expected participation of the various funded partners in the
various tasks is described in Figure~\ref{fig:tasks}. The unit used in
Figure~\ref{fig:tasks} is the \emph{person-month} (abbreviated
\emph{pm}).

\begin{figure}
\centering
\begin{tabular}{|l|l|l|l|l|l|}\hline
\textbf{Task}&\textbf{PRiSM}&\textbf{LIG}&\textbf{LIX} \\ \hline
\emph{Management} & \emph{pm} & & & &\\ \hline
Task 1.1 &  pm & pm & pm & 5.4pm & 4pm \\ 
Task 1.2 &  4.14pm & 5.45pm & 0.9pm & &\\ 
Task 1.3 &  4.14pm & 8.18pm & 1.8pm & &\\ 
Task 1.4 &  8.28pm & 2.73pm & 1.8pm & &\\ 
Task 1.5 &  & 5.45pm & & & 7pm \\ \hline
\emph{Workpackage 1} & \emph{26.9pm} & \emph{17.73pm} & \emph{6.3pm} & \emph{5.4pm} & \emph{11pm} \\ \hline
Task 2.1 &  8.28pm & 2.73pm & & & 4pm \\ 
Task 2.2 &  8.28pm & & 3.6pm & &\\ 
Task 2.3 &  2.07pm & 2.73pm & 3.6pm & 2.7pm & 2pm \\ 
Task 2.4 &  2.07pm & & 1.8pm & 5.4pm & \\ \hline
\emph{Workpackage 2} & \emph{20.69pm} & \emph{5.45pm} & \emph{9pm} & \emph{8.1pm} & \emph{6pm} \\ \hline
Task 3.1 &  8.28pm & & 2.7pm & 1.35pm & 1pm \\ 
Task 3.2 &  & 1.36pm & 3.6pm & 1.35pm & 4pm \\ 
Task 3.3 &  4.14pm & & 0.9pm & 5.4pm &\\ \hline
\emph{Workpackage 3} & \emph{12.41pm} & \emph{1.36pm} & \emph{7.2pm} & \emph{8.1pm} & \emph{5pm} \\ \hline
\textbf{Total} & \textbf{60pm} & \textbf{30pm} & \textbf{22.5pm} & \textbf{21.6pm} & \textbf{22pm} \\ \hline
\textbf{Total (\%)} &  \textbf{38.44\%} & \textbf{19.22\%} & \textbf{14.41\%} & \textbf{13.84\%} & \textbf{14.09\%} \\ \hline
\end{tabular}

\caption{Funded partners commitments to tasks (excluding resources
provided by the \textbf{SHAMAN} project)}
\label{fig:tasks}
\end{figure}


\subsection{\textcolor[rgb]{0.000,0.502,0.502}{Coordination du projet / project management}}

\textbf{\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize (2 pages maximum)}}}}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Preciser les aspects organisationnels du projet et les modalites de coordination (si possible individualisation dune tache coordination : cf. tache 0 du document de soumission A).}}}


% Mise en place d'une strategie

\paragraph{Work package 0} is devoted to management of the project. 

\paragraph*{Workpackage leader} Johanne Cohen, \emph{PRiSM}

\paragraph*{Participants} \emph{all}

\paragraph*{Deliverables} At $t+2$ a a web site for the project 
will be provided, and scientific results and deliverables will be
posted on the web site as they become available. At $t+3$ a SVN server
will be set up for source file sharing among partners. At $t+3$,
$t+6$, $t+9$, $t+12$, $t+15$, $t+18$, $t+21$, $t+24$, $t+27$,  $t+30$,
$t+33$, and $t+36$ plenary meetings will be organized. It is expected that at $t+18$ and
$t+30$ those plenary meetings will be organized concurrently with an
international workshop or conference on related topics. At $t+36$ a
final report stating the main achievements of the project will be
compiled.

\paragraph{Structure and flow} Figure \ref{fig:relations} summaries
the logical dependencies between the various workpackages of the
{JEDY\&CO} project. There is a natural flow from Workpackage 1 to
Workpackage 2: whenever a convergence is observed or proved, this is
necessary to understand the quality of the involved equilibria. There
is a natural flow from Workpackage 2 to Workpackage 3: whenever the
quality of involved equilibria is attested, this is necessary to
evaluate whether this equilibria is attained in a reasonable
time. There is also a natural flow from Workpackage 3 to Workpackage
1: whenever speed of convergence is low, this is often required to
reconsider the strategy that lead to convergence.

The chronogram for the JEDY\&CO project is depicted in Figure
\ref{fig:chrono}. %blabla


%%%%%%%%%%%%%%%%%%%%

\newcommand{\formatannee}{|c|c|c|c|c|c}

%\newcommand{\formatannee}{| p{0.3cm} | p{0.3cm} | p{0.3cm}| p{0.3cm} | p{0.3cm} | p{0.3cm}}
\newcommand{\annee}{ $2$ & $4$ & $6$ & $8$ &$10$ & $12$  }
 \newcommand{\years}[1]{  \multicolumn{6}{|l||}{\textbf{Year} $\mathbf{#1}$ }    }
\newcommand{\deuxmois}{ \cellcolor[gray]{0}{4}  }
\newcommand{\dixmoisvide}{    & & & &  }
\newcommand{\huitmoisvide}{   & & &   }
\newcommand{\sixmoisvide}{    & &   }

\newcommand{\sixmoisplein}{     \multicolumn{3}{c}{ \cellcolor[gray]{0}{4}}  }
\newcommand{\anneepleine}{ \multicolumn{6}{c}{ \cellcolor[gray]{0}{4}}  }
\newcommand{\anneevide}{      &  &   &  &  &      }


 
\begin{figure}
    \begin{tabular}[h]{l|l||r|r|r|r|r|r||r|r|r|r|r|r||r|r|r|r|r|r||}
    \multicolumn{2}{l||}{  } & \years{1} & \years{2} & \years{3} \\   
  \multicolumn{2}{l||}{  } &  \annee &\annee &\annee \\\hline\hline
  \multicolumn{2}{l||}{WP 0}  &\deuxmois&  \huitmoisvide    &\deuxmois&\dixmoisvide    &\deuxmois&\dixmoisvide    &\deuxmois   \\\hline\hline
  \multirow{3}*{\rotatebox{90}{{{ WP 1}}}} & \textbf{Task 1.1}    &  \anneepleine &\anneevide          &\anneevide \\
                                           &  \textbf{Task 1.2}   &  \anneevide   &\anneepleine          &\anneevide \\
                                           &  \textbf{Task 1.3}   &  \anneevide   &   \sixmoisvide  &  \sixmoisplein        &\anneepleine \\\hline\hline
 \multirow{4}*{\rotatebox{90}{{{ WP 2}}}}  & \textbf{Task 2.1}  & \sixmoisvide  &  \sixmoisplein &  \sixmoisplein & \sixmoisvide &\anneevide \\
    &  \textbf{Task 2.2}  &  \anneevide &\anneepleine &\anneevide \\
    &  \textbf{Task 2.3} &  \anneevide &\anneevide &\anneepleine \\
    &  \textbf{Task 2.4} &  \anneevide &\anneepleine &\anneevide \\\hline\hline
 \multirow{3}*{\rotatebox{90}{{{ WP 3}}}}  & \textbf{Task 3.1}  &\sixmoisvide  &  \sixmoisplein &\anneepleine &\anneevide \\
     &  \textbf{Task 3.2}  &  \anneevide &\anneepleine &\anneevide \\
      &  \textbf{Task 3.3} &  \anneevide &\anneevide &\anneepleine \\\hline\hline
  \end{tabular}

\caption{Task chronogram summary} \label{fig:chrono} 
\end{figure} 

The summary for the list of deliverables for the JEDY\&CO project is
presented in Figure \ref{fig:deliv}. %bla

\begin{figure}
\caption{Deliverables summary}
\end{figure}

\subsection{\textcolor[rgb]{0.000,0.502,0.502}{Description des travaux par tache / detailed description of the work organised by tasks}}

\textbf{\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize (idealement  1 ou 2 pages par tache)}}}}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Pour chacune dentre elle, decrire : }}}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize son responsable et les partenaires impliques (si possible, sous forme graphique),}}}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize ses objectifs,}}}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize le programme detaille des travaux}}}\footnote{{\footnotesize  Les projets de recherche sappuyant sur les donnees reunies, par exemple, dans le cadre de la constitution dun corpus, dun suivi de cohorte, dune approche longitudinale, dun panel, doivent expliciter precisement la nouveaute du recueil de donnees envisage, la nouveaute des traitements ou des analyses proposees par rapport a ceux deja engages.}} \textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize ,}}}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize la description des methodes, des choix techniques et des solutions envisages,}}}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize les risques et les solutions de repli envisagees, les indicateurs de succes associes aux objectifs et  les livrables,}}}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize les
      contributions des partenaires (le qui fait quoi )}}}

%Work Package 0: Management 

% \begin{enumerate}
% \item property of a dynamical system convergence for distributed and interative Algorithms.
%   \begin{itemize}
%    \item  distributed system where all players have local and partial information about the system.
% (Denis, Dominique)

%    \item distributed hierachical system where different type of actors (users and providers for example) are involved in    
%  (Stackelberg equilibria). (Corinne)
%    \item distributed system with dynamical interactions (mobility,
%      discovery services, network dimensioning \COMMENTAIRE{dominique})

%       power  of the system, what kind of cooperation is possible where few  structures exist.
%   \end{itemize}
% \item Qualitative and Quantitative properties of  Equilibrium points
%   \begin{itemize}
%   \item reputation, trustfull property, and robutness (Johanne)

%   \item correlated  equilibriums  (Corinne)
%   \item Purity equilibruim, Jain indices (fairness equilibrium) (Corinne)
% \item  price of stability  (Approximation).  (Denis)
%   \end{itemize}
% \item Speed of convergence, number of iterations, and synchronisation issues
%   \begin{itemize}
%   \item Step size adaptation of stochastic system.  (Bruno et Olivier)
%   \item Speed of convergence of multidimensional differential equations.  (Olivier)
%   \item Study of improvement given by asynchronism on theoritical and
%     heuristic point of view. (Bruno)
%   \item Cornetti ??  <---> (Johanne)
%   \end{itemize}
% \end{enumerate}


% \begin{enumerate}
% \item Work package 0: \textbf{Management} (Leader: Johanne  Cohen,
%   PRiSM) 

\subsubsection{\textcolor[rgb]{0.000,0.502,0.502}{WP1: Property of a dynamical system convergence for distributed and interactive Algorithms.}}


\paragraph{ Task 1.1: \emph{Property of convergence with partial information} }

\subparagraph{Workpackage Leader:}  Denis Trystram, \emph{LIG}.

\subparagraph{Participants}: PRiSM, LIG, LIX


\subparagraph{Description}

% Task 11. Property of convergence with partial informations
% Coordinator: Denis Trystram, participants: all

The project JEDI\&Co targets on distributed systems (namely,
computational grids, telecommunication network).  We are looking for
solutions that are "good" equilibria or that optimize one (or more)
objective(s).  Such distributed systems are characterized by "agents"
that have only local information and it is hard to obtain and keep a
global view of the system. In this sense, the information are only
partial ones.  Using classical optimization, most efficient solutions
of combinatorial optimization problems (like multi-organization
scheduling or routing) are centralized.  Obtaining a good solution (an
optimal one or guaranteed a solution with a performance guaranty)
needs to have a global state.  Usually, good local solutions
(optimized locally or for selfish purpose) are not good global
solutions.

This distributed character of the systems originates from two
situations. First, the agents do not want to give or share their local
information.  Obtaining a global state in this case may be
prohibitive, and thus, it is impossible to include it into a dynamic
process.  Secondly, local information are available.  Each agent has
its own wishes or constraints, and it aims at optimizing its selfish
objective.  Thus, it is theoretically possible to construct the global
view, however, it is not tractable for realistic instances (because of
the too large number of local strategies).  In both cases, we need to
construct equilibria using iterative algorithms involving only partial
distributed information.  The purpose of Task T11 is to study the
convergence of such processes.

This task is a basic one, because it is important that all
participants study the literature related to the construction and the
analysis of global state (distributed algorithms, approximation
solutions, variants of Nash equilibria, etc.).  The goal of this task
is to master the existing methods and results for constructing a
global solutions from local partial solutions.  Such techniques are
known in the different disciplines (algorithms, operational research,
complexity), and should be shared and learned by all the participants
of different disciplines.  The output of this task will be first to
share this basic background and knowledge.  Moreover, another output
is to derive new results for the target problems: new approximation
algorithms for the multi-organization scheduling problem and new
convergence conditions for the routing problem.




\paragraph{   Task 1.2: \emph{Distributed hierarchical system with different
      types of players} }

\subparagraph{Workpackage Leader:}  Corinne Touati, \emph{LIG}.


\subparagraph{Participants}: PRiSM, LIG


%Task 1.2 Distributed hierachical system

\subparagraph{Description}

With the increasing level of interconnection and heterogeneity between
systems, different levels of optimization are generally needed. A
typical example is MPLS (Multi Protocol Label Switching) where users
optimize their individual route so as to minimize some cost function
without knowledge of the type of network their packets are actually
going through, would it be wireless, optical or Ethernet. The routes
they are aware of consist of hops between virtual nodes that do not
even necessarily coincide with physical ones. Meanwhile, the system
aims at leveraging the physical paths followed by packets so as to
guarantee good utilization of the system.

Another example can be found in wireless systems, where contention is
addressed both at the network layer (TCP window) and at the physical
layer (backoff timer of IEEE 802.11 protocol). As there is no
coordination between the two network layers, inefficiencies occur.

An even different system was studied by Legrand and al. [38] where
schedulers compete in a non-cooperative way to access the grid, while
the system ensures fair access to individual resources. They observed
that even though one can guarantee fairness and efficiency at each
local resource, this does not lead to fairness in the global system,
hence comforting the fact that optimizations achieved at independent
levels do not lead to efficient use of the global system.

In hierarchical systems, some piece of information should hence be
transferred between the different levels of optimization so as to
obtain efficient equilibria. In this task, we look for efficient
algorithms in hierarchical systems with minimal information exchange
between the layers.





\paragraph{    Task 1.3: \emph{Distributed system with dynamical interactions} }


\subparagraph{Workpackage Leader:}  Dominique Barth, \emph{PRiSM}.


\subparagraph{Participants}: PRiSM, LIX





\subsubsection{\textcolor[rgb]{0.000,0.502,0.502}{WP2: Qualitative and Quantitative properties of  Equilibrium points}}

\paragraph{  Task 2.1: \emph{Optimality and fairness and correlation
    of  equilibria }}


\subparagraph{Workpackage Leader:}  Corinne Touati, \emph{LIG}.


\subparagraph{Participants}: LIG, LIX


\subparagraph{Description}

%Optimality and fairness of equilibria

Optimality is usually defined based on the definition of Pareto
optimality. Yet, if a point is not Pareto optimal, one needs a measure
of its inefficiency. The price of anarchy and price of stability are
measures of distance between the non cooperative equilibria and a
particular point of the Pareto border, namely the social optimum. The
more recent SDF (Selfish Degradation Factor) is the distance between a
Nash equilibrium and the Pareto border. Analogously, the Jain Index
measure the distance of an equilibrium point to the (Pareto optimal)
Max-Min fair point.

This task is two-folds. First, we aim at developing tight bounds on
the efficiency of the equilibria, using one of the already defined
efficiency metrics. Indeed, as previously mentioned, these performance
measures are based on global considerations and thus can often only be
approximated in a distributed environment. Second, we aim at
developing algorithms that converge towards efficient equilibria,
with respect to these performance measures. Toward this goal, different
techniques can be used. One of them is to consider a non-cooperative
game on a modified system, for which the equilibrium is known to be
optimal \cite{pierre}. Another option is to consider a wider class of
equilibria, known as Correlated Equilibria \cite{Aumann}. In such
games, an independent agent provides some additional piece of
information. It has been shown that appropriate choice of this
information can, in a totally non-cooperative system, increase the
efficiency of the reached equilibrium. The underlying concept is that
this data acts correlates the different agents. Further, it has been
shown that this data does not need to be connected to the system state
to have an effective impact on the system's performance
\cite{bonneau}.

  

\paragraph{ Task 2.2: \emph{Stability and Purity property}}


\subparagraph{Workpackage Leader:}  Corinne Touati, \emph{LIG}.


\subparagraph{Participants}: PRiSM, LIG

 
 \paragraph{Task 2.3: \emph{Reputation, truthful property, and
     robustness}}


\subparagraph{Workpackage Leader:}  Johanne Cohen, \emph{PRiSM}.


\subparagraph{Participants}: PRiSM, LIG


 \paragraph{Task 2.4: \emph{Approximation, equity , Pareto
     approximation}}


\subparagraph{Workpackage Leader:}  Denis Trystram, \emph{LIG}.


\subparagraph{Participants}: PRiSM, LIG, LIX

\subparagraph{Description}

% Task 24. Approximation (qualitative and quantitative properties of the equilibria)
% Coordinator: Denis Trystram, participants: TO BE COMPLETED

Nash equilibria correspond to the best possible situation when no cooperation is allowed.
There are many interesting variants of this concept (that will be studied in other tasks).
Allowing cooperation among agents often leads to form coalitions: two or more agents can agree
on some common strategies for improving their own objectives, the counter-part is that the objectives of other agents are usually worsened.
In order to avoid such bad effects, we propose to add an extra global (centralized) mechanism
for controlling or optimizing the global behavior of the system.
The main difference with other existing classical approaches is that this global solution is obtained from
local partial solutions.
For instance, the multi-organization scheduling problem, this corresponds to construct a approximation of the global
optimum without deteriorating the local solutions.
ADD HERE FEW WORDS ABOUT APPROXIMATION FOR THE OTHER PROBLEM (ROUTING).

Pareto optimal solutions are defined as the best possible compromise
solutions among all the agents.  The users of such distributed systems
are interested in determining the whole set of Pareto points, one user
would put emphasize of specific compromises which are generally
different than the other users.  This usually leads to a problem for
enumerating the whole Pareto set (whose cardinality may be exponential
in the size of the problem).  Thus, approximations are needed to
reduce the search space to a polynomial number of solutions (these
solutions will not be optimal, but only approximated solutions).

This task aims at determining a framework for the study of multi-objective optimization
using the concepts of game theory. The classical approach in combinatorial optimization can only handle
efficiently few objectives. We target here on many objectives (typically, each user would have his-her own objective).
The output of this task is to establish new approximation bounds for specific objectives in the multi-organization scheduling problem (for instance, the best existing absolute bound for obtaining the global makespan using greedy algorithms is 3 and the lower bound is 2. We believe that it is possible to improve this bound, and to propose better bounds using more sophisticated algorithms).


\subsubsection{\textcolor[rgb]{0.000,0.502,0.502}{WP3: Speed of convergence, number of iterations, and synchronization issues}}


\paragraph{  Task 3.1: \emph{Step size adaptation of stochastic
    system.}}

\subparagraph{Workpackage Leader:}  Johanne Cohen, \emph{PRiSM}.


\subparagraph{Participants}: PRiSM, LIG, LIX

  
\paragraph{ Task 3.2: \emph{Speed of convergence of learning scenarios% multidimensional differential equations.
    }}

\subparagraph{Workpackage Leader:}  Olivier Bournez, \emph{LIX}.


\subparagraph{Participants}: PRiSM,  LIX

  
\paragraph{ Task 3.3: \emph{Study of improvement given by asynchronous behavior on theoretical and
    heuristic point of view}}

\subparagraph{Workpackage Leader:}  Bruno Gaujal, \emph{LIG}.


\subparagraph{Participants}:  LIG, LIX





\subsection{\textcolor[rgb]{0.000,0.502,0.502}{Calendrier des taches,
    livrables et jalons / planning of tasks, deliverables and
    milestones}}

\label{sec:troisq}
\textbf{\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize (2 pages maximum)}}}}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Presenter sous forme graphique un echeancier des differentes taches et leurs dependances (par exemple, utiliser un diagramme de Gantt).}}}



\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Presenter un tableau synthetique de l'ensemble des livrables du projet (numero de tache, date, intitule, responsable).}}}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Preciser de facon synthetique les jalons scientifiques et$/$ou techniques, les points bloquants ou aleas qui risquent de remettre en cause l'aboutissement du projet ainsi que les reunions de projet prevues.}}}


The chronogram for the JEDY\&CO project is depicted in Figure
\ref{fig:chrono}. %blabla

The summary for the list of deliverables for the JEDY\&CO project is
presented in Figure \ref{fig:deliv}. %bla



\section{{Strategie de valorisation des resultats et mode de protection et dexploitation des resultats / data management, data sharing, intellectual property and results exploitation}}

\textbf{\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize (1 a 2 pages)}}}}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Presenter les strategies de valorisation des resultats :}}}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize la communication scientifique;}}}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize la communication aupres du grand public, le cas echeant;}}}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize la valorisation des resultats attendus;}}}
\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize les retombees scientifiques et techniques, eventuellement les retombees industrielles, economiques }}}
\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize la place du projet dans la strategie industrielle des entreprises partenaires du projet}}}
\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize autres retombees (normalisation, information des pouvoirs publics, ...)}}}
\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize pour les bases de donnees, indiquer les modes de stockage et de maintenance ainsi que les communautes beneficiaires}}}
\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Presenter les grandes lignes des modes de protection et dexploitation des resultats.}}}
\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Pour les projets partenariaux organismes de recherche/entreprises, les partenaires devront conclure, sous legide du coordinateur du projet, un accord de consortium dans un delai de un an si le projet est retenu pour financement.  }}}
\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Pour les
      projets academiques, laccord de consortium nest pas obligatoire
      mais fortement conseille.}}}

\paragraph{Results sharing}
Obtained results will be submitted to high level public computer
science conferences, or to public computer science journals.

All meetings from the JEDY\&CO project will be open. Scientists
interested by the subjects of the meetings will have the opportunity
to present their results, if related, or to listen from the talks from
members of the JEDY\&CO project.

We intend to organize at $t+18$ and $t+30$ the plenary meetings
concurrently with an international workshop or conference on related
topics. This particular plenary meetings will be special occasions to
communicate wisely on the JEDY\&CO project, its thematics and
results. We will in particular invite first level speakers to present
talks at these meetings.

Some members of the JEDY\&CO project have some relationships with
industrial partners (see e.g. past projects ACTRICE, ANR CHOC). Even
if the problematics of the JEDY\&CO projects are currently at a
theoretical level, we will encourage migration of our theoretical
results towards concrete industrial problems.

\paragraph{Intellectual property and results exploitation}

Each partner keeps complete property of its previous background. No
stipulation can be interpreted as giving any property
transfer. Neither disclosure from a partner to another, nor possible
use, in the context of this project, can give the other partner the
right to make commercial usage of it without the preliminary agreement
of the owner, except for disposals from article.


%  Recherche en amount pour acquerir une expertise sur des projets
%   li és au th ématique (France Te l  ecom)%, Alcatel (en dernier ressort)
% \item construire des outils  op erationnels for manageming   for large computing infrastructure  (Bull)
%\end{itemize}

\newpage

\section{{Organisation du partenariat / consortium organisation and description}}
\label{sec:cinq}
\subsection{\textcolor[rgb]{0.000,0.502,0.502}{Description, adequation et complementarite des partenaires / relevance and complementarity of the partners within the consortium}}

\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize  }}}\textbf{\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize (maximum une demi page par partenaire)}}}}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Decrire brievement chaque partenaire et fournir ici les elements permettant dapprecier la qualification des partenaires dans le projet (le `pourquoi qui fait quoi ). Il peut sagir de realisations passees, dindicateurs (publications, brevets), de linteret du partenaire pour le projet (il ne sagit pas de fournir ici le C.V. du responsable scientifique de chaque partenaire).}}}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Fournir en annexe 7.2  une presentation plus detaillee des partenaires, de leur savoir- faire et de leurs apports et attentes dans le projet. }}}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Montrer la complementarite et la valeur ajoutee des cooperations entre les differents partenaires. Linterdisciplinarite et louverture a diverses collaborations seront a justifier en accord avec les orientations du projet.}}}\textbf{\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize  (une page maximum)}}}}

\paragraph{PRiSM Partner}
PRiSM is a French laboratory in computer science of the University of
Versailles St-Quentin created in 1994 and associated to the French
CNRS since this date. This laboratory is composed of seven research
teams in various scientific domains with 50 researchers and about 80
PhD students:
\begin{itemize}
\item  Algorithmic, Combinatorics and Applications
\item  Computer architectures and Parallelism
\item Network architectures and services
\item Evaluation of Performance of networks
\item Cryptography
\item Distributed computing and optimization
\item Data Base systems
\item information Systems and Software architectures
\end{itemize}
  
 
PRiSM is involved in RTRA DIGITEO, in the "pôles de compétitivité"
SYSTEM@TIC and MOVEO and in different European networks of
excellence. The research teams participating to the JEDY\&CO project
are the team "Algorithms, Combinatorics and Applications" (ALCAP) and
the team "Distributed computing and optimization" (CARO). The
competences of these teams brought to the project related to
distributed algorithms for networks (in particular about routing,
resource provisioning for QoS and pricing), combinatorial
optimization, graph algorithms and algorithmic theoretical game
theory.  These teams are jointly implied in various French and
European research projects in the field of telecommunications
networks. They are also involved in academic and industrial research
projects in France, with telecommunication industrial partners.

\paragraph{ LIG Partner}
\paragraph{ LIX Partner}

LIX is a French laboratory in computer science at the Ecole
Polytechnique.  It is a mixed laboratory with the CNRS, and hosts
several INRIA projects.  The researchers O. Bournez and C. D\"urr from
LIX have recently started working on algorithmic game theory.  More
precisly on the question of existance of Nash equilibria, the price of
anarchy and learning aspects of games.  The network of this project,
would able them to integrate techniques from the other groups which
they do not master yet.



\subsection{\textcolor[rgb]{0.000,0.502,0.502}{Qualification du
    coordinateur du projet / qualification of the project
    coordinator}}

\textbf{\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize (une demi page maximum)}}}}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Fournir les elements permettant de juger la capacite du coordinateur a coordonner le projet.}}}





\subsection{\textcolor[rgb]{0.000,0.502,0.502}{Qualification, role et implication des participants}\textcolor[rgb]{0.000,0.502,0.502}{ / contribution and qualification of each project particpant}}

\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Pour chaque partenaire, remplir le tableau ci-dessous qui precisera la qualification, les activites principales  et les competences propres de chaque participant :}}}

{\footnotesize * a renseigner uniquement pour les Sciences Humaines et Sociales}





\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Pour chacune des personnes dont limplication dans le projet est superieure a 25\% de son temps sur la totalite du projet, une biographie dune page }}}\textbf{\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize maximum}}}}\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize  sera placee en annexe 7.2 du present document qui comportera :}}}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Nom, prenom, age, cursus, situation actuelle}}}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Autres experiences professionnelles}}}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Liste des cinq publications (ou brevets) les plus significatives des cinq dernieres annees, nombre de publications dans les revues internationales ou actes de congres a comite de lecture.}}}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Prix, distinctions}}}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Si besoin, pour chacune des personnes, leur implication dans d'autres projets (Contrats publics et prives effectues ou en cours sur les trois dernieres annees) sera presentee selon le modele fourni en annexe 7.3. On precisera l'implication dans des projets europeens ou dans dautres types de projets nationaux ou internationaux. Expliciter larticulation entre les travaux proposes et les travaux anterieurs ou deja en cours.}}}



\section{{Justification scientifique des moyens demandes / scientific justification of requested budget}}

\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize On presentera ici pour chaque partenaire, la justification scientifique et technique des moyens demandes dans le document de soumission A. Ces moyens sont synthetises a lechelle du projet dans la fiche Tableaux recapitulatifs  dans ce document de soumission A.}}}





\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Chaque partenaire justifiera les moyens quil demande en distinguant les differents postes de depenses selon le canevas suivant :.}}}


\subsection{\textcolor[rgb]{0.000,0.502,0.502}{Partenaire 1 / partner 1 : PRiSM}}
\begin{flushleft}
{Equipement / Equipment}
\end{flushleft}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Preciser la nature des equipements* et justifier le choix des equipements}}}
\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Si necessaire, preciser la part de financement demande sur le projet et si les achats envisages doivent etre completes par dautres sources de financement. Si tel est le cas, indiquer le montant et lorigine de ces financements complementaires.}}}
\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize *Un devis sera demande si le projet est retenu pour financement.}}}


\begin{flushleft}
{Personnel / Staff}
\end{flushleft}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Le personnel non permanent (theses, post- doctorants,CDD..) finance sur le projet devra etre justifie.}}}

\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Fournir  les profils des postes a pourvoir pour les personnels a recruter (une demi page maximum par type de poste)}}}
\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Pour les theses (ne concerne ni la  biologie-sante, ni les sciences humaines et sociales), preciser si des demandes de bourse de these sont prevues ou en cours, en preciser la nature et la part de financement imputable au projet. }}}


\begin{itemize}
\item 





% A Ph.D. student will participate to Tasks 1.1, 2.3, and 2.3. The main topic of the thesis 
% concerns  . This thesis will help to de    models 
% for  in this context.  It is 
% expected that the Ph. D. student will be re cruited for 36 months, and will be hosted and supervised 
% by PRiSM  for a to tal cost of \euro. Moreover, the 
\end{itemize}
 





\begin{flushleft}
{Prestation de service externe / Subcontracting}
\end{flushleft}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Preciser :}}}
\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize la nature des prestations}}}
\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize le type de prestataire.}}}





%\begin{flushleft}
{Missions / Missions}
%\end{flushleft}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Preciser :}}}
\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize les missions liees aux travaux dacquisition sur le terrain (campagnes de mesures)}}}
\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize les missions relevant de colloques, congres}}}


\begin{flushleft}
{Depenses justifiees sur une procedure de facturation interne / Internal expenses}
\end{flushleft}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Preciser la nature des prestations}}}


\begin{flushleft}
{Autres depenses de fonctionnement / Other expenses}
\end{flushleft}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Toute depense significative relevant de ce poste devra etre justifiee.}}}
\subsection{\textcolor[rgb]{0.000,0.502,0.502}{Partenaire 2 / partner 2 : LIG}}
\begin{flushleft}
{Equipement / Equipment}
\end{flushleft}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Preciser la nature des equipements* et justifier le choix des equipements}}}
\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Si necessaire, preciser la part de financement demande sur le projet et si les achats envisages doivent etre completes par dautres sources de financement. Si tel est le cas, indiquer le montant et lorigine de ces financements complementaires.}}}
\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize *Un devis sera demande si le projet est retenu pour financement.}}}


\begin{flushleft}
{Personnel / Staff}
\end{flushleft}

\begin{itemize}
\item A postdoctoral fellow will participate to Task 3.3 and then to tasks of the WP4. This postdoc will 
be recruited for 18 months for a total amount of \euro{??}.
\end{itemize}
 






\begin{flushleft}
{Prestation de service externe / Subcontracting}
\end{flushleft}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Preciser :}}}
\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize la nature des prestations}}}
\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize le type de prestataire.}}}





%\begin{flushleft}
{Missions / Missions}
%\end{flushleft}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Preciser :}}}
\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize les missions liees aux travaux dacquisition sur le terrain (campagnes de mesures)}}}
\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize les missions relevant de colloques, congres}}}


\begin{flushleft}
{Depenses justifiees sur une procedure de facturation interne / Internal expenses}
\end{flushleft}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Preciser la nature des prestations}}}


\begin{flushleft}
{Autres depenses de fonctionnement / Other expenses}
\end{flushleft}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Toute depense significative relevant de ce poste devra etre justifiee.}}}
\subsection{\textcolor[rgb]{0.000,0.502,0.502}{Partenaire 3 / partner 3 : LIX}}




\begin{flushleft}
{Equipement / Equipment}
\end{flushleft}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Preciser la nature des equipements* et justifier le choix des equipements}}}
\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Si necessaire, preciser la part de financement demande sur le projet et si les achats envisages doivent etre completes par dautres sources de financement. Si tel est le cas, indiquer le montant et lorigine de ces financements complementaires.}}}
\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize *Un devis sera demande si le projet est retenu pour financement.}}}


\begin{flushleft}
{Personnel / Staff}
\end{flushleft}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Le personnel non permanent (theses, post- doctorants,CDD..) finance sur le projet devra etre justifie.}}}

\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Fournir  les profils des postes a pourvoir pour les personnels a recruter (une demi page maximum par type de poste)}}}
\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Pour les theses (ne concerne ni la  biologie-sante, ni les sciences humaines et sociales), preciser si des demandes de bourse de these sont prevues ou en cours, en preciser la nature et la part de financement imputable au projet. }}}









\begin{flushleft}
{Prestation de service externe / Subcontracting}
\end{flushleft}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Preciser :}}}
\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize la nature des prestations}}}
\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize le type de prestataire.}}}





%\begin{flushleft}
{Missions / Missions}
%\end{flushleft}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Preciser :}}}
\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize les missions liees aux travaux dacquisition sur le terrain (campagnes de mesures)}}}
\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize les missions relevant de colloques, congres}}}


\begin{flushleft}
{Depenses justifiees sur une procedure de facturation interne / Internal expenses}
\end{flushleft}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Preciser la nature des prestations}}}


\begin{flushleft}
{Autres depenses de fonctionnement / Other expenses}
\end{flushleft}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Toute depense significative relevant de ce poste devra etre justifiee.}}}







\newpage
  

\newpage
\section{{Annexes}{ }}

\subsection{\textcolor[rgb]{0.000,0.502,0.502}{References bibliographiques / references}}

\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Inclure la liste des references bibliographiques utilisees dans ce document et les references bibliographiques des partenaires ayant trait au projet.}}}


\bibliographystyle{plain}
\bibliography{Jeux,bibliographieMembre}



\subsection{\textcolor[rgb]{0.000,0.502,0.502}{Biographies / CV, Resume}}

\textbf{\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize (une
        page maximum par personne)}}}} 

The project partners are: three French academic partners (PRiSM, LIG,
LIX). The partners   credentials are described in more detail
below. The project is to employ (in terms of percentage of research
time) of each French permanent academic partners involved in the
project. Note that PhD students and post doctoral researches are to be
employed but are not listed.

The PRiSM partner has a strong background in distributed and graph
algorithms, with emphasis on  optimization algorithms for telecommunication network. The PRiSM
partner includes the following people:
\begin{itemize}
\item Dominique Barth (20\%) professor of Universit{\'e} de Versailles
  St Quentin
  \cite{barth04d,BaEc04,BEHa08b,BEHV05,Boussaton08,Loubna2007}.  41
  years old. Dominique Barth defended a PhD thesis in Computer Science
  (1994) in Bordeaux and defended a HDR (1999) in Orsay. He has been
  with Université Paris-Sud 11 at Orsay between 1994 and 1999, and
  currently is Professor in the PRiSM laboratory with Univeristé de
  Versailles St Quentin since 1999. He has created and leaded the
  Algortihmic, Combinatoric and Application team of PRiSM.  His main
  research interests concern graph theory and gaph algorithms with two
  application domains, telecommunication network and Computational
  Biology. Concerning telecommunication networks, he mainly focuses on
  distributed algorithms to manage QoS in a selfish interdomain
  network, using game theory concepts.  He is and has been the head of
  the participation of his team to many european and national
  research projects.


\item Johanne Cohen, (60\%) Charg{\'e}e de Recherche CNRS 
  \cite{Loubna2007,Boussaton08,Chalopin2008,UCPC2008}. Johanne Cohen
  is the principal investigator of the JEDY\&CO project. Her CV can be
  found in Section~\ref{CVJOHANNE}.  She is charg{\'e}e de recherche
  CNRS since 2001. She was an assistant professor at Nancy I
  university from 2000 to 2001, after a PhD defensed in Paris XI Orsay
  University in 1998, and a Magistere from ENS Lyon. Her research
  interests include algorithmics for telecommunication, graph theory,
  algorithmic game theory, distributed algorithmics, complexity and
  approximation theory.

\item Thierry Mautor (20\%) \cite{Mautor01,Mautor04,OSA2006,Mautor07,Mautor08} is assistant professor in the PRiSM
  laboratory of the University of Versailles-Saint Quentin en Yvelines
  since 1994. He defended a PhD thesis in 1993 and a HDR in 2001. His
  main research field is the Combinatorial Optimization and the
  determination for several optimization problems of efficient
  solution methods as well exact as heuristic. Especially, he works on
  the Quadratic Assignment Problem and the Vehicle Routing
  Problems. But, he has worked also on Parallel and Distributed
  Algorithms, on Graph Algorithms and Game Theory, specially for
  telecommunication network problems.
\end{itemize} 

The LIG partner has a strong background in complexity and scheduling algorithms, with emphasis on    network. The LIG 
partner includes the following people:



\begin{itemize}
\item Bruno Gaujal (20\%)
  \cite{ArticleAltman.AGH_ITAC00,BookAltman.AGH_03,ArticleGaujal.GJM_SJC00,Perronnin2008,Thierry08}
  is a former student of {\'E}cole Normale Sup{\'e}rieure in Lyon.  He
  received his PhD from the University of Nice in 1994.  He has held
  several positions in AT\&T Bell Labs (USA), INRIA Sophia-Antipolis,
  Loria (Nancy) and ENS-Lyon. Currently, he is a Research Director
  with INRIA Rhones-Alpes.  Since 2005, he is the leader of the
  large-scale computing group, MESCAL (30 members) (INRIA project
  team, member of the LIG laboratory).  He joins the INRIA-Alcatel
  Lucent common Laboratory in 2008 where he leads the research action
  on self optimizing networks (SelfNets, 40 members). His main
  interests are in performance evaluation, optimization and control of
  discrete event dynamic systems in a deterministic as well as a
  stochastic context.

\item Corinne Touati (20\%)
  \cite{InoieKT06,TouatiAG06,Coucheney2008,LegrandT07,LegrandCoRR2007,BrevetTouati}.
  She is charg{\'e}e de recherche INRIA and she is a member of INRIA
  projet MESCAL (Middleware Efficiently SCALable). She held a
  post-doctoral position in the OSDP (Operating Systems and
  Distributed Programming) laboratory of Tsukuba University (Japan)
  lead by Professeur Kameda from November 2003 to May 2006. She did her
  PhD studies at the University of Nice and the INRIA
  Sophia-Antipolis, under the joint supervision of Eitan Altman and of
  J{\'e}r{\^ o}me Galtier (from October 2000 to September 2003).  She
  studies optimization and performance evaluation problems in
  communication networks and distributed systems, using in particular
  tools issued from game theory. Corinne Toauti takes part in the
  Program Committee of international conferences in game theory and in
  communication networks (IEEE WCNC 2008, ValueTools 2008, NET-COOP
  2008).
 
\item Denis Trystram (40\%)
  ~\cite{DiedrichJPT07,PascualRT07,MounieRT07,JeannotST08}. He  was born in
  1958 in Paris, France.  He obtained a PhD in Applied Mathematics at
  INPG (Institut National Polytechnique de Grenoble) in 1984 and a
  second one in Computer Science in 1988 from the same institute.  He
  is Professor since 1991 at INP Grenoble and is now distingued
  professor in this Institute.  He is leading a research team on
  Scheduling and Combinatorial Optimization within the MOAIS team at
  LIG laboratory.  He is currently Regional Editor for Europe for the
  Parallel Computing Journal and serve in the board of IEEE TPDS and
  other journals.  Denis Trystram participates regularly to the
  Program Committee of major conferences of the field (EUROPAR, IPDPS,
  HiPC, PARCO, SPAA, ...).

  The main research activities of professor Trystram concern the
design of efficient approximation algorithms for multi-objective
scheduling problems.  He has published several books and more than 80
articles in international journals and as many international
conferences.
\end{itemize}



The LIX partner has a strong background in complexity and scheduling
algorithms, with emphasis on and computational aspect of dynamical
system. The LIX partner includes the following people:


\begin{itemize}  

\item Olivier Bournez (40\%)  \cite{Boussaton08,Chalopin2008,UCPC2008}


Christoph D\"urr (50\%)
\cite{Durr.Nguyen:Voronoi,chrobak.durr.jawor:maxflow,BaptisteChrobak:Preemptive-Multi-Machine}
studied computer science at the Akademie f\"ur Datenverarbeitung
in B\"oblingen, worked in the industry during 2 years, and continued
studying at the Universit\'e Paris-Sud, where he did his PhD in 1997.
After two years of postdoc at ICSI Berkeley, and later the Hebrew
University of Jerusalem, we worked as a teaching assistant at the IUT
d'Orsay, and is now a CNRS researcher at LIX, Ecole Polytechnique.  He
recieved his habilitation in 2005.  Rather than being a specialist in
a particular domain, he constributed to quite different areas of
computer science, including quantum computation, cellular automata,
discrete tomography, scheduling, online algorithms, and recently
algorithmic game theory.

\end{itemize}



\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Cf. .}}}


\subsection*{\textcolor[rgb]{0.000,0.502,0.502}{Implication des personnes dans nodautres contrats / involvement of project participants to other grants, contracts, etc }}

\textbf{\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize (un tableau par partenaire)}}}}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Cf.  }}}


\textit{\textcolor[rgb]{1.000,0.000,0.000}{{\footnotesize Mentionner ici les projets en cours devaluation  soit au sein de programmes de lANR, soit aupres dorganismes, de fondations, a lUnion Europeenne, etc. que ce soit comme coordinateur ou comme partenaire. Pour chacun, donner le nom de lappel a projets, le titre du projet et le nom du coordinateur.}}}
 

% \begin{itemize}
% \item Past ANR projects:
%   \begin{itemize}
%   \item 2005--2008, ANR \emph{blanche}. Partners (MESCAL, Prism).  The
%     main objective is to study monotonicity properties of computer
%     systems models in order to speed up the simulations and estimate
%     performance indexes more accurately.
%  \item 2006--2009, SOGEA: Dominique Barth, Olivier Bournez, Johanne Cohen, Octave
%     Boussaton were involved in ANR project SOGEA
%     http://sogea.loria.fr, that will terminate in 2008. Olivier
%     Bournez was the coordinator of this project. This project partly
%     focus on dynamical aspects of games, but focus also on their
%     relations with self-stabilization, and on complexity
%     theory. Prefered domains of applications come from sensor networks
%     and interdomain routing.
%   \end{itemize}
% \end{itemize}

\subsubsection*{Partner  PRiSM} 
 
\begin{tabular}{|c|c|c|c|c|c|c|}\hline
 \multirow{4}{*}{Part.}& Nom de la   &           & Intitul{\'e} de l'appel   &            &              &  Date    \\
                       & Personne    & Personne  & {\`a} projet              & Titre du  & Nom du       &  d\'ebut    \\
                       & participant & .Mois     & source de financement     & projet    & Coordinateur &   \&   \\
                       & au projet   &           & Montant attribu{\'e}      &           &              & date de fin     \\\hline
$N^o1$ & J. Cohen &    40\% =(4.8)      & ANR VERSO & SHAMAN & Sébastien Tixieul & 10/07-9/11 \\
       &          &                     &   Montant total         &       &  (LIP6)           &            \\
       &          &                     &    en n{\'e}gotiation        &       &          &            \\ \hline
$N^o1$ & D. Barth &   6     & RNRT  & ECOFRAME &  D.Chiaroni & 2007-2009 \\
       &          &                     &   Montant total         &       &  ALCATEL        &            \\
       &          &                     &    ????        &       &          &            \\ \hline
$N^o1$ & D. Barth &    12             & P\^ole de compt\'etivit\'e.  & CARRIOCAS &  O. Audouin & 2007-2009 \\
       &          &                   &  SYSTEM@TIC                         &           & ALCATEL        &            \\ \hline
$N^o1$ & D. Barth &                  & Digiteo  & PASAPAS  &  F. Quessette  & 2007-2010 \\
       &          &                   &  (RTRA) &           & PRiSM        &            \\ \hline
\end{tabular}
   




In particular, this partner is involved in several on-going projects. 

\begin{itemize}
\item The ANR VERSO SHAMAN projet has no deep intersection with this
  proposal. In particular, it focuses on the algorithmic foundations of
  resource-constrained autonomous large scale systems, dedicated to
  enabling the sustainability of network functions in spite of abrupt
  system evolutions, component failures, and attacks.

  \item The projet RNRT ECOFRAME (2006 - end 2009):  stands for Elements de
    COnvergence pour les Futurs Reseaux. \COMMENTAIRE{Dominique?}
  \end{itemize}


Within SYSTEM@TIC ``p\^ole de competitivite'', Dominique Barth
    is involved in projet CARRIOCAS (ending August 2009). It studies
    and implements an ultra high bit rate (up to 40Gb/s per channel)
    optical fiber core network to meet the scientific and industrial
    needs in remote usage of computing and storage resource for high
    performance interactive/collaborative simulations and virtual
    prototyping.

   
 






\subsubsection*{Partner LIG}
\begin{tabular}{|c|c|c|c|c|c|c|}\hline
 \multirow{4}{*}{Part.}& Nom de la   &           & Intitul{\'e} de l'appel   &            &              &  Date    \\
                       & Personne    & Personne  & {\`a} projet              & Titre du  & Nom du       &  d\'ebut    \\
                       & participant & .Mois     & source de financement     & projet    & Coordinateur &   \&   \\
                       & au projet   &           & Montant attribu{\'e}      &           &              & date de fin \\\hline
$N^o2$ & C. Toauti &    80\% =(9.6)      & ANR jeunes  & DOCCA & Florence PERRONNIN   & 9/07-8/10 \\
        &          &                     & Chercheurs  &       &                      &            \\
        &          &                     &   Montant total         &       &  (LIG)           &            \\
        &          &                     &    ?????        &       &          &            \\\hline
$N^o2$ & B. Gaujal &                    & ANR SETIN        &    Check-bound &   Nihal Pekergin  & 2007--2009 \\  
        &          &                     &   Montant (partner)         &       &  (Paris 1)           &            \\
        &          &                     &    50 K \euro        &       &          &            \\\hline
\hline
\end{tabular}






In particular, this partner is involved in several projects. 
\begin{itemize}
\item The ANR \emph{jeune chercheur} DOCCA project (2000--2010) aims at developing a peer-to-peer
  collaborative computing protocol with a strong emphasis on
  theoretical aspects of fairness issues and collaboration
  incentives. Our target system is a fully decentralized architecture,
  where desktops are both volunteers and clients (they can submit
  jobs).  Our objective is Design a P2P architecture based on the
  algorithms designed in the second step and to create a novel P2P
  collaborative computing system.
\item The ANR SETIN Check-bound (2007--2009) focused on
  safety-critical applications, coupled with their increasing
  complexity. The presence of systems in safety-critical applications
  makes indispensable their verification to see if they behaves as
  required.  Thus the model checking which is the automated manner of
  formal verification techniques is of particular interest. Since
  verification techniques have become more efficient and more
  prevalent, the natural extension is to extend the range of models
  and specification formalisms to which model checking can be
  applied. Indeed the behavior of many real-life processes is
  inherently stochastic, thus the formalism has been extended to
  probabilistic model checking.
\end{itemize}




Within the Minalogic ``p\^ole de competitivite'' Bruno Gaujal
    participates in the project Sceptre (2007-2010) with
    STMicroelectronics, Verimag and LIP on optimized software
    compilation for multicore embedded systems. We have started a PhD
    with STMicroelectronics on monitoring and performance measures of
    embedded systems on chips.

    A new project within the same ``p\^ole de competitivit\'e'', whose
    objective is to provide small companies with federated computing
    resources has started in 2008. It involves the Mescal and Moais
    teams of LIG.
 
\subsubsection*{Partner LIX}
\begin{tabular}{|c|c|c|c|c|c|c|}\hline
 \multirow{4}{*}{Part.}& Nom de la   &           & Intitul{\'e} de l'appel   &            &              &  Date    \\
                       & Personne    & Personne  & {\`a} projet              & Titre du  & Nom du       &  d\'ebut    \\
                       & participant & .Mois     & source de financement     & projet    & Coordinateur &   \&   \\
                       & au projet   &           & Montant attribu{\'e}      &           &              & date de fin     \\\hline
$N^o3$ & O. Bournez &    40\% =(4.8)      & ANR VERSO & SHAMAN & Sébastien Tixieul & 10/07-9/11 \\
       &            &                     &    Montant total         &      &  (LIP6)           &            \\
       &            &                     &      ??????????      &       &          &            \\\hline
$N^o3$ & C. D\"urr  &    10\% = (3.6)      & ANR jeunes             & ARS & Léo Liberti & 08/2008--07/2011\\
       &            &                     & chercheurs            &     &            & \\ 
       &            &                     &    Montant total      &      &  (LIX)           &            \\
       &            &                     &      136 K\euro            &               &          &            \\\hline


\end{tabular}


In particular, this partner is involved in several on-going projects. 

\begin{itemize}
\item The ANR VERSO SHAMAN projet  is already defined. 
\item The ANR \emph{jeune chercheur} ARS project (2008-2011) stands for
automatic reformation search.  The idea is that various optimisation
problems can be modeled as linear or quadratic programs.  Some
modelisations are better than others, in the sense, that they can be
easier approximated or that they have less variables or constraints
and therefore e solved more efficiently.  The goal of this project is
to come up with algorithms, that automatically reformulate one model
into a better model.
  \end{itemize}




%   \hline
%   & Nom de la & Personne & Intitul{\'e} &  & & \\
%  \multirow{2}{Par.} & Nom de la & Personne & Intitul{\'e} &  & &  \hline\\
% & Nom de la & Personne & Intitul{\'e} &  & & 
% & Nom de la & Personne & Intitul{\'e} &  & & 
% % $N^o$ & D. Barth &            & Personne & Intitul{\'e} &\\

% % $N^o$ & J. Cohen &           & Personne & Intitul{\'e} & 
% \hline \\

 

% \end{tabular}

 


\end{document}
