GAmes, optimizatioN and analysis of nEtworkS tHeory and
applications: Report
for 2012-2013
Scientific Achievements
1.
Delay Tolerant Networks (DTNs).
We have pursued our
study of optimal control in delay tolerant network. We studied the trade-off between delivery delay
and energy consumption in a delay tolerant network in which a message (or a
file) has to be delivered to each of several destinations by epidemic relaying.
In addition to the destinations, there are several other nodes in the network
that can assist in relaying the message. A preliminary version of the work was
already reported last year, and it has now appeared in a journal [R2]. The analysis is based on a
mobility model in which all individuals move independently of each other. In [R4] we have studied through
simulations the multicast time in DTNs where the mobility of individuals follow dependent movement such as the one of flocking birds.
This model is typical to cooperative movement and could be useful to describe a
rescue team in an area hit by a disaster. We showed the impact of the
parameters defining the mobility on the multicast time.
In [R1] we formulate a problem where both
transmission and activation of mobile terminals are controlled as a linear
optimal control problem. We solve the problem by making use of this linearity
in order to obtain explicit expressions for the objective function as a
function of the control actions trajectories (rather than as a function of both
actions and state trajectories). This allows us to compute the optimal
strategies explicitly.
2.
Competition in Social Networks.
We
considered in [R3] a situation where
several content producers send their content to some subscriber of a social
network. These posts appear on the subscriber’s timeline which is assumed to
have finite capacity. Whenever a new post arrives to the timeline, an older
post leaves it. Therefore to be visible, a source has to keep sending from time
to time contents. Each source is modelled as a player in a non-cooperative game
in which one trades between the utility for being visible on the timeline and
the cost (or effort) for keeping sending content. We solve this game in a Markovian setting and compute the performance measures of interest.
3.
Network neutrality and collusions
Representatives
of several Internet access providers have expressed their wish to see a
substantial change in the pricing policies of the Internet. In particular, they
would like to see content providers pay for use of the network, given the large
amount of resources they use. This would be in clear violation of the
"network neutrality" principle that had characterized the development
of the wireline Internet. We proposed and studied
possible ways of implementing such payments and of regulating their amount. The
results were reported already in the previous report. We have pursued our work
on network neutrality studying various ways of collusions between an ISP and a content
provider and in particular, another form of non-neutrality in which a content provider
signals to an ISP information on the popularity of its content and hides this
information from other ISPs. We define and compute the price of collusion and
study the impact of such signalling on the ISP that is iin
collusion as well as on the other ones. The results appear in [R5].
4.
Fundamental results in Game
Networking games.
There are
very few known tools to study the following questions:
-
Uniqueness
of the equilibrium in games
-
Convergennce to the equiolibrium
-
Equilibria in presence of consntraints
A central
tool for the study of all these is an extension to the concavity notion to the
game setting which is called diagonal
strict concavity due to Rosen. This condition is however much too
restrictive. For example, in their pioneering paper on routing games, Orda, Shimkin and Rom have been
able to establish these conditions only for light traffic conditions, when
there are two players only and for the most simple
topology of two parallel links. Yet using ad-hoc techniques they showed that in
routing games one has a unique equilibrium under much more general conditions.
These conditions however are very problem specific. In our paper [R6] we managed to extend Rosen’s
property and thus obtained uniqueness under much weaker conditions than Rosen’s
condition. We call it the Generalized Diagonal Strict Concavity condition. We
then showed that it holds for many applications such as routing games with
general topology and any number of players.
Publications
[R1] Eitan Altman, Amar Prakash
Azad, Tamer Basar
and Francesco De Pellegrini, "Combined Optimal Control of
Activation and Transmission in Delay Tolerant Networks", IEEE/ACM Transactions on Networking, Vol 21 No. 2, pp 482-494, April
2013
[R2] Chandramani Singh, Eitan Altman Anurag Kumar, and Rajesh Sundaresan, Optimal forwarding in Delay Tolerant
Networks with Multiple Destinations, IEEE/ACM Transactions on Networking, IEEE early
access articles, 2013.
[R3] Eitan Altman, Anurag Kumar, and Parmod Kumar and Srinivasan Venkatramanan, "Competition over timeline in
social networks", Proceedings of the
3rd IEEE/ACM workshop on Social Networks, Analysis and Applications, August
2013.
[R4] Sushma Patil, Eitan Altman, Manjesh Kumar Hanawal, Julio Rojas-Mora, "Modeling and Simulation of Mobility of Crowds", hal-00819653, version 1 LNCS 7984, pp
352-363, Proceedings of Analytical and Stochastic Modelling
Techniques and Applications (ASMTA), Ghent, July 8-10, 2013.
[R5] Manjesh Kumar Hanawal
and Eitan Altman, "Network Non-Neutrality Through
Preferential Signaling", Proc. of the 11th Intl. Symposium on Modeling and
Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt),
May 13-17, 2013, Tsukuba Science City, Japan.
[R6] Manjesh Kumar, Eitan Altman and Rajesh Sundaresan,
“Generalizing
Diagonal Strict Concavity Property for Uniqueness of Nash Equilibria”, Submitted to IEEE Infocom 2014.
General comments
Maestro is
part of the joint Indian French laboratory of applied mathematics (IFCAM).
INRIA has been financing this year IFCAM through targeted expenses of Ganesh
such as a postdoc (Pramod Kumar) visits to and from
India and Internships (see next item).
Budget details of 2013
Internships.
1.
Sushma Patil Hanawal : 25/08/2012-25/03/2013
Topic: Evaluation of Dynamic Mobility Models in Complex Systems Background
Cost on 2013: 3578€ during 2013
Advisor:
Eitan Altman
2. KumarTeja CHIPPALA : 06/05-23/07/13 Topic:
Multi-armed Bandit Problem and Data Routing
Advisor: Konstantin Avratchenkov
Cost : 3500€
Postdoc
Pamod
Kumar, 12 months payed through IFCAM
Visits
· Visit of Prof Rajesh Sundaresan:
24 nov - 14 4 dec, 2013.
· Visit of Prof. Vivek
Borkar, nov
3 - nov 10, 2013.
· Visit of Dr. Kavitha
Veeraruna, 25 May - 1 June, 2013.
· Parmod Kumar, 16 aug - 25 sep, 2013. Visits IISc
· Parmod
Kumar, 2 nov 2013 - 31 jan
2014. Visits IISc.
Workplan for 2014
Organization of two workshops
The members of Ganesh orgqnize two Indo-French workshops
in January 2014:
1. WORKSHOP ON NEW AVENUES FOR
NETWORK MODELS (13th-15th January, 2014)
2. WORKSHOP ON SOCIAL NETWORKS (16th
January, 2014)
The workshops will include three tutorials of three hours each and twenty seminars of one hour each. Two of the three tutorials are given by
members of Ganesh: The tutorial on Competition in social networks will be
presented by Eitan Altman (INRIA), and the tutorial
about Mean Field approximations will be presented by Rajesh Sundaresan
(IISc). Two of the seminars will be presented by
members of MAESTRO. In addition, three students from MAESTRO team will attend
the workshops.
Scientific work plan:
I.
Dynamics of competition
A central research topic for the second year will be the dynamics of
competition in networks as well as learning in games based on stochastic approximations. This
will include topics such as non-equilibrium behavior. This will be applied to
1. dynamic games that occur in
social networks,
2. routing games and
3. power control in wireless networks.
We shall build on the framework which we developed and reported this year
which extends concavity to the game framework (we call this framework the
generalized diagonal strict concavity). This
line of research is particularly original since it provides new theoretical tools
for studying convergence issues in games that are applicable under much weaker
conditions than those available today. We have started working in this
direction with Prof Borkar (IIT Mumbai) during his
last visit to MAESTRO on November 2013.
II.
Timeline games
Parmod Kumar (joint postdoc of MAESTRO and IISc) will pursue his joint work with E Altman (INRIA) and A Kumar (IISc) on competition in social networks. So far we have
worked on the competition of content over visibility on the timeline of some
common destination. We plan to add to this study other features, and in
particular the possibility of sharing and embedding content. The impact of
these on the model is the addition of an epidemic routing component to the model
in which the topology of the network is expected to play an important role.
III.
Network neutrality
We plan to pursue our work on network neutrality. We shall extend our
previous work to include several ISPs and several content providers. We shall
study the price of collusion, as well as various hierarchical versions of this
game (in the sense of different order between the decision
taking by the actors).
IV.
Evolutionary games and
state dependent power control
We are working on extending the theory of evolutionary games to include
for each player a controlled Markov decision chain such that the control
actions in pairwise interactions between individuals not only impact the immediate
fitness of each involved individual, but also the state transition
probabilities. The objective of an individual is then to optimize the total
expected fitness during his lifetime rather than the immediate fitness (which
is the case in standard evolutionary games). In previous publications we have
described how to obtain the equilibrium in this game and applied it to power control
where the control actions depended on the level of remaining energy in the
battery. The objectives were to maximize the total amount of packets
transmitted in the lifetime of the battery. We now plan to study the replicator
dynamic for this new type of model. The replicator dynamic is well understood
in standard evolutionary games where it is used for describing the
non-equilibrium behavior of the system. To apply it to our new formalism, we
shall use tools from stochastic approximations theory with several time scales.
We shall be working on this topic with Prof. Vivek Borkar.
Budget request
1.
Mutual visits
In the organization of the two workshops in January, Maestro will
finance the trip of the following researchers.
-
Three permanent researchers (E Altman, and K. Avratchenkov from Maestro and L. Cocatellucci
from EURECOM),
-
Two postdocs (Parmod Kumar
and Majed Haddad from Maestro team) and
-
Three Ph.D. students (Alexandre
Reiffers, Ilaria Brunnetti and Jithin
KAZHUTHUVEETTIL SREEDHARA from the Maestro team).
One permanent member and one postdoc will be payed
by CEFIPRA who sponsors the first workshop.
In addition there will be one visit of a French scientist to India
during 2014.
We further request to finance three visits of Indians members of Ganesh
to INRIA.
We request 15 K Euros for the above and will cover the remaining from
our own resources.
2.
Internships
We request 7000 euros for Internships.
3.
Postdoc
Three remaining months for Parmod Kumar are
requested
Remark
Since the budget of Ganesh also covers the activity of Maestro in IFCAM
we request a budget larger than 10 K Euros
Changes in the participants
Prof Vivek Borkar
who a member of Ganesh has changed his affiliation during 2013 from TIFR Mumbai
to the EE department of IIT Mumbai.