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.