Search

In this paper, the worst-case probability measure over the data is introduced as a tool for characterizing the generalization capabilities of machine learning algorithms. More specifically, the worst-case probability measure is a Gibbs probability measure and the unique solution to the maximization of the expected loss under a relative entropy constraint with respect to a reference probability measure. Fundamental generalization metrics, such as the sensitivity of the expected loss, the sensitivity of the empirical risk, and the generalization gap are shown to have closed-form expressions involving the worst-case data-generating probability measure. Existing results for the Gibbs algorithm, such as characterizing the generalization gap as a sum of mutual information and lautum information, up to a constant factor, are recovered. A novel parallel is established between the worst-case data-generating probability measure and the Gibbs algorithm. Specifically, the Gibbs probability measure is identified as a fundamental commonality of the model space and the data space for machine learning algorithms., Comment: To appear in the Proceedings of the AAAI Conference on Artificial Intelligence (7 + 2 pages)

This paper introduces constrained correlated equilibrium, a solution concept combining correlation and coupled constraints in finite non-cooperative games. In the general case of an arbitrary correlation device and coupled constraints in the extended game, we study the conditions for equilibrium. In the particular case of constraints induced by a feasible set of probability distributions over action profiles, we first show that canonical correlation devices are sufficient to characterize the set of constrained correlated equilibrium distributions and provide conditions of their existence. Second, it is shown that constrained correlated equilibria of the mixed extension of the game do not lead to additional equilibrium distributions. Third, we show that the constrained correlated equilibrium distributions may not belong to the polytope of correlated equilibrium distributions. Finally, we illustrate these results through numerical examples.

Network slicing (NS) is a key technology in 5G networks that enables the customization and efficient sharing of network resources to support the diverse requirements of nextgeneration services. This paper proposes a resource allocation scheme for NS based on the Fisher-market model and the Trading-post mechanism. The scheme aims to achieve efficient resource utilization while ensuring multi-level fairness, dynamic load conditions, and the protection of service level agreements (SLAs) for slice tenants. In the proposed scheme, each service provider (SP) is allocated a budget representing its infrastructure share or purchasing power in the market. SPs acquire different resources by spending their budgets to offer services to different classes of users, classified based on their service needs and priorities. The scheme assumes that SPs employ the $\alpha$-fairness criteria to deliver services to their subscribers. The resource allocation problem is formulated as a convex optimization problem to find a market equilibrium (ME) solution that provides allocation and resource pricing. A privacy-preserving learning algorithm is developed to enable SPs to reach the ME in a decentralized manner. The performance of the proposed scheme is evaluated through theoretical analysis and extensive numerical simulations, comparing it with the Social Optimal and Static Proportional sharing schemes.

This paper characterizes an achievable information-energy region of simultaneous information and energy transmission over an additive white Gaussian noise channel. This analysis is performed in the finite block-length regime with finite constellations. More specifically, a method for constructing a family of codes is proposed and the set of achievable tuples of information rate, energy rate, decoding error probability (DEP) and energy outage probability (EOP) is characterized. Using existing converse results, it is shown that the construction is information rate, energy rate, and EOP optimal. The achieved DEP is, however, sub-optimal.

In this work, we propose a Graph Convolutional Neural Networks (GCN) based scheduling algorithm for adhoc networks. In particular, we consider a generalized interference model called the $k$-tolerant conflict graph model and design an efficient approximation for the well-known Max-Weight scheduling algorithm. A notable feature of this work is that the proposed method do not require labelled data set (NP-hard to compute) for training the neural network. Instead, we design a loss function that utilises the existing greedy approaches and trains a GCN that improves the performance of greedy approaches. Our extensive numerical experiments illustrate that using our GCN approach, we can significantly ($4$-$20$ percent) improve the performance of the conventional greedy approach., Comment: 10 pages, Accepted at EAI VALUETOOLS 2021 - 14th EAI International Conference on Performance Evaluation Methodologies and Tools

In this paper, the fundamental limits on the rates at which information and energy can be simultaneously transmitted over an additive white Gaussian noise channel are studied under the following assumptions: $(a)$ the channel is memoryless; $(b)$ the number of channel input symbols (constellation size) and block length are finite; and $(c)$ the decoding error probability (DEP) and the energy outage probability (EOP) are bounded away from zero. In particular, it is shown that the limits on the maximum information and energy transmission rates; and the minimum DEP and EOP, are essentially set by the type induced by the code used to perform the transmission. That is, the empirical frequency with which each channel input symbol appears in the codewords. Using this observation, guidelines for optimal constellation design for simultaneous energy and information transmission are presented.

We study in this paper optimal control strategy for Advanced Sleep Modes (ASM) in 5G networks. ASM correspond to different levels of sleep modes ranging from deactivation of some components of the base station for several micro-seconds to switching off of almost all of them for one second or more. ASMs are made possible in 5G networks thanks to the definition of so-called lean carrier radio access which allows for configurable signaling periodicities. We model such a system using Markov Decision Processes (MDP) and find optimal sleep policy in terms of a trade-off between saved power consumption versus additional incurred delay for user traffic which has to wait for the network components to be woken-up and serve it. Eventually, for the system not to oscillate between sleep levels, we add a switching component in the cost function and show its impact on the energy reduction versus delay trade-off., Comment: The 18th IEEE International Symposium on Network Computing and Applications (NCA 2019) 26-28 September 2019 Cambridge, MA USA

We consider an example of stochastic games with partial, asymmetric and non-classical information. We obtain relevant equilibrium policies using a new approach which allows managing the belief updates in a structured manner. Agents have access only to partial information updates, and our approach is to consider optimal open loop control until the information update. The agents continuously control the rates of their Poisson search clocks to acquire the locks, the agent to get all the locks before others would get reward one. However, the agents have no information about the acquisition status of others and will incur a cost proportional to their rate process. We solved the problem for the case with two agents and two locks and conjectured the results for $N$-agents. We showed that a pair of (partial) state-dependent time-threshold policies form a Nash equilibrium., Comment: This is long version of the paper accepted in Allerton 2019

Future electricity distribution grids will host a considerable share of the renewable energy sources needed for enforcing the energy transition. Demand side management mechanisms play a key role in the integration of such renewable energy resources by exploiting the flexibility of elastic loads, generation or electricity storage technologies. In particular, local energy markets enable households to exchange energy with each other while increasing the amount of renewable energy that is consumed locally. Nevertheless, as most ex-ante mechanisms, local market schedules rely on hour-ahead forecasts whose accuracy may be low. In this paper we cope with forecast errors by proposing a game theory approach to model the interactions among prosumers and distribution system operators for the control of electricity flows in real-time. The presented game has an aggregative equilibrium which can be attained in a semi-distributed manner, driving prosumers towards a final exchange of energy with the grid that benefits both households and operators, favoring the enforcement of prosumers' local market commitments while respecting the constraints defined by the operator. The proposed mechanism requires only one-to-all broadcast of price signals, which do not depend either on the amount of players or their local objective function and constraints, making the approach highly scalable. Its impact on distribution grid quality of supply was evaluated through load flow analysis and realistic load profiles, demonstrating the capacity of the mechanism ensure that voltage deviation and thermal limit constraints are respected.

We consider a multi-population epidemic model with one or more (almost) isolated communities and one mobile community. Each of the isolated communities has contact within itself and, in addition, contact with the outside world but only through the mobile community. The contact rate between the mobile community and the other communities is assumed to be controlled. We first derive a multidimensional ordinary differential equation (ODE) as a mean-field fluid approximation to the process of the number of infected nodes, after appropriate scaling. We show that the approximation becomes tight as the sizes of the communities grow. We then use a singular perturbation approach to reduce the dimension of the ODE and identify an optimal control policy on this system over a fixed time horizon via Pontryagin's minimum principle. We then show that this policy is close to optimal, within a certain class, on the original problem for large enough communities. From a phenomenological perspective, we show that the epidemic may sustain in time in all communities (and thus the system has a nontrivial metastable regime) even though in the absence of the mobile nodes the epidemic would die out quickly within each of the isolated communities., Comment: 16 pages (two column format), 4 figures

We propose a setting for two-phase opinion dynamics in social networks, where a node's final opinion in the first phase acts as its initial biased opinion in the second phase. In this setting, we study the problem of two camps aiming to maximize adoption of their respective opinions, by strategically investing on nodes in the two phases. A node's initial opinion in the second phase naturally plays a key role in determining the final opinion of that node, and hence also of other nodes in the network due to its influence on them. More importantly, this bias also determines the effectiveness of a camp's investment on that node in the second phase. To formalize this two-phase investment setting, we propose an extension of Friedkin-Johnsen model, and hence formulate the utility functions of the camps. There is a tradeoff while splitting the budget between the two phases. A lower investment in the first phase results in worse initial biases for the second phase, while a higher investment spares a lower available budget for the second phase. We first analyze the non-competitive case where only one camp invests, for which we present a polynomial time algorithm for determining an optimal way to split the camp's budget between the two phases. We then analyze the case of competing camps, where we show the existence of Nash equilibrium and that it can be computed in polynomial time under reasonable assumptions. We conclude our study with simulations on real-world network datasets, in order to quantify the effects of the initial biases and the weightage attributed by nodes to their initial biases, as well as that of a camp deviating from its equilibrium strategy. Our main conclusion is that, if nodes attribute high weightage to their initial biases, it is advantageous to have a high investment in the first phase, so as to effectively influence the biases to be harnessed in the second phase.

Facebook News Feed personalization algorithm has a significant impact, on a daily basis, on the lifestyle, mood and opinion of millions of Internet users. Nonetheless, the behavior of such algorithm lacks transparency, motivating measurements, modeling and analysis in order to understand and improve its properties. In this paper, we propose a reproducible methodology encompassing measurements, an analytical model and a fairness-based News Feed design. The model leverages the versatility and analytical tractability of time-to-live (TTL) counters to capture the visibility and occupancy of publishers over a News Feed. Measurements are used to parameterize and to validate the expressive power of the proposed model. Then, we conduct a what-if analysis to assess the visibility and occupancy bias incurred by users against a baseline derived from the model. Our results indicate that a significant bias exists and it is more prominent at the top position of the News Feed. In addition, we find that the bias is non-negligible even for users that are deliberately set as neutral with respect to their political views, motivating the proposal of a novel and more transparent fairness-based News Feed design., Comment: IFIP Perfomance 2018 - 36th International Symposium on Computer Performance, Modeling, Measurements and Evaluation

We study a stochastic game framework with dynamic set of players, for modeling and analyzing their computational investment strategies in distributed computing. Players obtain a certain reward for solving the problem or for providing their computational resources, while incur a certain cost based on the invested time and computational power. We first study a scenario where the reward is offered for solving the problem, such as in blockchain mining. We show that, in Markov perfect equilibrium, players with cost parameters exceeding a certain threshold, do not invest; while those with cost parameters less than this threshold, invest maximal power. Here, players need not know the system state. We then consider a scenario where the reward is offered for contributing to the computational power of a common central entity, such as in volunteer computing. Here, in Markov perfect equilibrium, only players with cost parameters in a relatively low range in a given state, invest. For the case where players are homogeneous, they invest proportionally to the 'reward to cost' ratio. For both the scenarios, we study the effects of players' arrival and departure rates on their utilities using simulations and provide additional insights.

Facebook News Feed personalization algorithm has a significant impact, on a daily basis, on the lifestyle, mood and opinion of millions of Internet users. Nonetheless, the behavior of such algorithms usually lacks transparency, motivating measurements, modeling and analysis in order to understand and improve its properties. In this paper, we propose a reproducible methodology encompassing measurements and an analytical model to capture the visibility of publishers over a News Feed. First, measurements are used to parameterize and to validate the expressive power of the proposed model. Then, we conduct a what-if analysis to assess the visibility bias incurred by the users against a baseline derived from the model. Our results indicate that a significant bias exists and it is more prominent at the top position of the News Feed. In addition, we found that the bias is non-negligible even for users that are deliberately set as neutral with respect to their political views., Comment: International Symposium on Foundations of Open Source Intelligence and Security Informatics (FOSINT-SI 2018). In conjunction with ASONAM 2018. Barcelona, Spain, August 28-31, 2018

Many systems require frequent and regular updates of a certain information. These updates have to be transferred regularly from the source to the destination. We consider scenarios in which an old packet becomes completely obsolete, in the presence of a new packet. In this context, if a new packet arrives at the source while it is transferring a packet, one needs to decide the packet to be dropped. New packet has recent information, but might require more time to transfer. Thus it is not clear as to which packet to be dis- carded, and this is the main focus of the paper. Recently introduced performance metrics, called average age of information (AAoI) and peak age of information (PAoI) of the information available at the destination, are the relevant performance measures. These type of systems do not require storage buffers, of size more than one, at the source queue. We consider single source / multiple sources regularly updating information to a single destination possibly over wireless channels to derive optimal drop policies that optimize the AAoI. We showed that the state independent (static) policies like dropping always the old packets or dropping always the new packets is optimal in many scenarios, among an appropriate set of stationary Markov policies. We consider relevant games when multiple sources compete. In many scenarios, the non-cooperative solution almost minimizes the social objective, the sum of AAoIs of all the sources., Comment: 12 pages and 3 figures

We study the problem of optimally investing in nodes of a social network in a competitive setting, where two camps aim to maximize adoption of their opinions by the population. In particular, we consider the possibility of campaigning in multiple phases, where the final opinion of a node in a phase acts as its initial biased opinion for the following phase. Using an extension of the popular DeGroot-Friedkin model, we formulate the utility functions of the camps, and show that they involve what can be interpreted as multiphase Katz centrality. Focusing on two phases, we analytically derive Nash equilibrium investment strategies, and the extent of loss that a camp would incur if it acted myopically. Our simulation study affirms that nodes attributing higher weightage to initial biases necessitate higher investment in the first phase, so as to influence these biases for the terminal phase. We then study the setting in which a camp's influence on a node depends on its initial bias. For single camp, we present a polynomial time algorithm for determining an optimal way to split the budget between the two phases. For competing camps, we show the existence of Nash equilibria under reasonable assumptions, and that they can be computed in polynomial time.

Designing an optimal network topology while balancing multiple, possibly conflicting objectives like cost, performance, and resiliency to viruses is a challenging endeavor, let alone in the case of decentralized network formation. We therefore propose a game-formation technique where each player aims to minimize its cost in installing links, the probability of being infected by a virus and the sum of hopcounts on its shortest paths to all other nodes. In this article, we (1) determine the Nash Equilibria and the Price of Anarchy for our novel network formation game, (2) demonstrate that the Price of Anarchy (PoA) is usually low, which suggests that (near-)optimal topologies can be formed in a decentralized way, and (3) give suggestions for practitioners for those cases where the PoA is high and some centralized control/incentives are advisable., Comment: accepted for publication in IEEE Transactions on Control of Network Systems

We study the problem of optimally investing in nodes of a social network in a competitive setting, wherein two camps aim to drive the average opinion of the population in their own favor. Using a well-established model of opinion dynamics, we formulate the problem as a zero-sum game with its players being the two camps. We derive optimal investment strategies for both camps, and show that a random investment strategy is optimal when the underlying network follows a popular class of weight distributions. We study a broad framework, where we consider various well-motivated settings of the problem, namely, when the influence of a camp on a node is a concave function of its investment on that node, when a camp aims at maximizing competitor's investment or deviation from its desired investment, and when one of the camps has uncertain information about the values of the model parameters. We also study a Stackelberg variant of this game under common coupled constraints on the combined investments by the camps and derive their equilibrium strategies, and hence quantify the first-mover advantage. For a quantitative and illustrative study, we conduct simulations on real-world datasets and provide results and insights., Comment: The original version of this paper is accepted for publication in IEEE Transactions on Network Science and Engineering. The copyright for this article belongs to IEEE

Bio-inspired paradigms are proving to be useful in analyzing propagation and dissemination of information in networks. In this paper we explore the use of multi-type branching processes to analyse viral properties of content in a social network, with and without competition from other sources. We derive and compute various virality measures, e.g., probability of virality, expected number of shares, or the rate of growth of expected number of shares etc. They allow one to predict the emergence of global macro properties (e.g., viral spread of a post in the entire network) from the laws and parameters that determine local interactions. The local interactions, greatly depend upon the structure of the timelines holding the content and the number of friends (i.e., connections) of users of the network. We then formulate a non-cooperative game problem and study the Nash equilibria as a function of the parameters. The branching processes modelling the social network under competition turn out to be decomposable, multi-type and continuous time variants. For such processes types belonging to different sub-classes evolve at different rates and have different probabilities of extinction etc. We compute content provider wise extinction probability, rate of growth etc. We also conjecture the content-provider wise growth rate of expected shares., Comment: 76 pages, Document has Part-1 and Part-2 of the work

We consider location-dependent opportunistic bandwidth sharing between static and mobile downlink users in a cellular network. Each cell has some fixed number of static users. Mobile users enter the cell, move inside the cell for some time and then leave the cell. In order to provide higher data rate to mobile users, we propose to provide higher bandwidth to the mobile users at favourable times and locations, and provide higher bandwidth to the static users in other times. We formulate the problem as a long run average reward Markov decision process (MDP) where the per-step reward is a linear combination of instantaneous data volumes received by static and mobile users, and find the optimal policy. The transition structure of this MDP is not known in general. To alleviate this issue, we propose a learning algorithm based on single timescale stochastic approximation. Also, noting that the unconstrained MDP can be used to solve a constrained problem, we provide a learning algorithm based on multi-timescale stochastic approximation. The results are extended to address the issue of fair bandwidth sharing between the two classes of users. Numerical results demonstrate performance improvement by our scheme, and also the trade-off between performance gain and fairness., Comment: 16 Pages, 1 Figure, 1 Table

In small cell networks, high mobility of users results in frequent handoff and thus severely restricts the data rate for mobile users. To alleviate this problem, we propose to use heterogeneous, two-tier network structure where static users are served by both macro and micro base stations, whereas the mobile (i.e., moving) users are served only by macro base stations having larger cells; the idea is to prevent frequent data outage for mobile users due to handoff. We use the classical two-tier Poisson network model with different transmit powers (cf [1]), assume independent Poisson process of static users and doubly stochastic Poisson process of mobile users moving at a constant speed along infinite straight lines generated by a Poisson line process. Using stochastic geometry, we calculate the average downlink data rate of the typical static and mobile (i.e., moving) users, the latter accounted for handoff outage periods. We consider also the average throughput of these two types of users defined as their average data rates divided by the mean total number of users co-served by the same base station. We find that if the density of a homogeneous network and/or the speed of mobile users is high, it is advantageous to let the mobile users connect only to some optimal fraction of BSs to reduce the frequency of handoffs during which the connection is not assured. If a heterogeneous structure of the network is allowed, one can further jointly optimize the mean throughput of mobile and static users by appropriately tuning the powers of micro and macro base stations subject to some aggregate power constraint ensuring unchanged mean data rates of static users via the network equivalence property (see [2])., Comment: 13 pages, 5 diagrams, 2 plots, 3 images

Although HTTP-based video streaming can easily penetrate firewalls and profit from Web caches, the underlying TCP may introduce large delays in case of a sudden capacity loss. To avoid an interruption of the video stream in such cases we propose the Backward-Shifted Coding (BSC). Based on Scalable Video Coding (SVC), BSC adds a time-shifted layer of redundancy to the video stream such that future frames are downloaded at any instant. This pre-fetched content maintains a fluent video stream even under highly variant network conditions and leads to high Quality of Experience (QoE). We characterize this QoE gain by analyzing initial buffering time, re-buffering time and content resolution using the Ballot theorem. The probability generating functions of the playback interruption and of the initial buffering latency are provided in closed form. We further compute the quasi-stationary distribution of the video quality, in order to compute the average quality, as well as temporal variability in video quality. Employing these analytic results to optimize QoE shows interesting trade-offs and video streaming at outstanding fluency., Comment: 9 pages

The price-anticipating Kelly mechanism (PAKM) is one of the most extensively used strategies to allocate divisible resources for strategic users in communication networks and computing systems. The users are deemed as selfish and also benign, each of which maximizes his individual utility of the allocated resources minus his payment to the network operator. However, in many applications a user can use his payment to reduce the utilities of his opponents, thus playing a misbehaving role. It remains mysterious to what extent the misbehaving user can damage or influence the performance of benign users and the network operator. In this work, we formulate a non-cooperative game consisting of a finite amount of benign users and one misbehaving user. The maliciousness of this misbehaving user is captured by his willingness to pay to trade for unit degradation in the utilities of benign users. The network operator allocates resources to all the users via the price-anticipating Kelly mechanism. We present six important performance metrics with regard to the total utility and the total net utility of benign users, and the revenue of network operator under three different scenarios: with and without the misbehaving user, and the maximum. We quantify the robustness of PAKM against the misbehaving actions by deriving the upper and lower bounds of these metrics. With new approaches, all the theoretical bounds are applicable to an arbitrary population of benign users. Our study reveals two important insights: i) the performance bounds are very sensitive to the misbehaving user's willingness to pay at certain ranges; ii) the network operator acquires more revenues in the presence of the misbehaving user which might disincentivize his countermeasures against the misbehaving actions., Comment: 21

We consider in this paper competition of content creators in routing their content through various media. The routing decisions may correspond to the selection of a social network (e.g. twitter versus facebook or linkedin) or of a group within a given social network. The utility for a player to send its content to some medium is given as the difference between the dissemination utility at this medium and some transmission cost. We model this game as a congestion game and compute the pure potential of the game. In contrast to the continuous case, we show that there may be various equilibria. We show that the potential is M-concave which allows us to characterize the equilibria and to propose an algorithm for computing it. We then give a learning mechanism which allow us to give an efficient algorithm to determine an equilibrium. We finally determine the asymptotic form of the equilibrium and discuss the implications on the social medium selection problem.

A central question in routing games has been to establish conditions for the uniqueness of the equilibrium, either in terms of network topology or in terms of costs. This question is well understood in two classes of routing games. The first is the non-atomic routing introduced by Wardrop on 1952 in the context of road traffic in which each player (car) is infinitesimally small; a single car has a negligible impact on the congestion. Each car wishes to minimize its expected delay. Under arbitrary topology, such games are known to have a convex potential and thus a unique equilibrium. The second framework is splitable atomic games: there are finitely many players, each controlling the route of a population of individuals (let them be cars in road traffic or packets in the communication networks). In this paper, we study two other frameworks of routing games in which each of several players has an integer number of connections (which are population of packets) to route and where there is a constraint that a connection cannot be split. Through a particular game with a simple three link topology, we identify various novel and surprising properties of games within these frameworks. We show in particular that equilibria are non unique even in the potential game setting of Rosenthal with strictly convex link costs. We further show that non-symmetric equilibria arise in symmetric networks. I. INTRODUCTION A central question in routing games has been to establish conditions for the uniqueness of the equilibria, either in terms of the network topology or in terms of the costs. A survey on these issues is given in [1]. The question of uniqueness of equilibria has been studied in two different frameworks. The first, which we call F1, is the non-atomic routing introduced by Wardrop on 1952 in the context of road traffic in which each player (car) is infinitesimally small; a single car has a negligible impact on the congestion. Each car wishes to minimize its expected delay. Under arbitrary topology, such games are known to have a convex potential and thus have a unique equilibrium [2]. The second framework, denoted by F2, is splitable atomic games. There are finitely many players, each controlling the route of a population of individuals. This type of games have already been studied in the context of road traffic by Haurie and Marcotte [3] but have become central in the telecom community to model routing decisions of Internet Service Providers that can decide how to split the traffic of their subscribers among various routes so as to minimize network congestion [4]. In this paper we study properties of equilibria in two other frameworks of routing games which exhibit surprising

We consider a setting in which two nodes (referred to as forwarders) compete to choose a relay node from a set of relays, as they ephemerally become available (e.g., wake up from a sleep state). Each relay, when it arrives, offers a (possibly different) "reward" to each forwarder. Each forwarder's objective is to minimize a combination of the delay incurred in choosing a relay and the reward offered by the chosen relay. As an example, we develop the reward structure for the specific problem of geographical forwarding over a network of sleep-wake cycling relays. We study two variants of the generic relay selection problem, namely, the completely observable (CO) case where, when a relay arrives, both forwarders get to observe both rewards, and the partially observable (PO) case where each forwarder can only observe its own reward. Formulating the problem as a two person stochastic game, we characterize solution in terms of Nash Equilibrium Policy Pairs (NEPPs). For the CO case we provide a general structure of the NEPPs. For the PO case we prove that there exists an NEPP within the class of threshold policy pairs. We then consider the particular application of geographical forwarding of packets in a shared network of sleep-wake cycling wireless relays. For this problem, for a particular reward structure, using realistic parameter values corresponding to TelosB wireless mote, we numerically compare the performance (in terms of cost to both forwarders) of the various NEPPs and draw the following key insight: even for moderate separation between the two forwarders, the performance of the various NEPPs is close to the performance of a simple strategy where each forwarder behaves as if the other forwarder is not present. We also conduct simulation experiments to study the end-to-end performance of the simple forwarding policy., Comment: 25 pages, 6 figures

Self-Organizing Network (SON) technology aims at autonomously deploying, optimizing and repairing the Radio Access Networks (RAN). SON algorithms typically use Key Performance Indicators (KPIs) from the RAN. It is shown that in certain cases, it is essential to take into account the impact of the backhaul state in the design of the SON algorithm. We revisit the Base Station (BS) load definition taking into account the backhaul state. We provide an analytical formula for the load along with a simple estimator for both elastic and guaranteed bit-rate (GBR) traffic. We incorporate the proposed load estimator in a self-optimized load balancing algorithm. Simulation results for a backhaul constrained heterogeneous network illustrate how the correct load definition can guarantee a proper operation of the SON algorithm., Comment: Wireless Communications Letters, IEEE, 2015

This paper proposes a new prediction process to explain and predict popularity evolution of YouTube videos. We exploit our recent study on the classification of YouTube videos in order to predict the evolution of videos' view-count. This classification allows to identify important factors of the observed popularity dynamics. Our experimental results show that our prediction process is able to reduce the average prediction errors compared to a state-of-the-art baseline model. We also evaluate the impact of adding popularity criteria in our classification., Comment: Paper withdrawn due to conflict of interest in conference call for paper

The Net Neutrality issue has been at the center of debate worldwide lately. Some countries have established laws so that principles of Net Neutrality are respected, the Netherlands being the latest country in Europe. Among the questions that have been discussed in these debates are whether to allow agreements between service and content providers, i.e. to allow some preferential treatment by an operator to traffic from some subset of providers. Our goal in this paper is to analyze the impact of non neutral pricing and agreements on the Internet users and on the content providers. Each one of several Internet users have to decide in which way to split their demand among several content providers. The cost for an Internet user depends on whether the content providers have an agreement with the Internet Service Provider in which the Internet user is connected to. In addition, the requests coming from users depend on the preference of the consumer in the different CP. We model the choice of how to split the demands and the pricing aspects faced by the content providers as a hierarchical game model composed of a congestion game at the lower level and a noncooperative pricing game at the upper level. We show that agreement between providers have a positive impact on the equilibrium performance of the Internet users. We further show that at equilibrium, the content provider on the contrary, does not benefit from the agreement.

Large antenna arrays can be used to generate highly focused beams that support very high data rates and reduced energy consumption. However, optimal beam focusing requires large amount of feedback from the users in order to choose the best beam, especially in Frequency Division Duplex (FDD) mode. This paper develops a methodology for designing a multilevel codebook of beams in an environment with low number of multipaths. The antenna design supporting the focused beams is formulated as an optimization problem. A multilevel codebook of beams is constructed according to the coverage requirements. An iterative beam scheduling is proposed that searches through the codebook to select the best beam for a given user. The methodology is applied to a mass event and to a rural scenario, both analyzed using an event-based network simulator. Very significant gains are obtained for both scenarios. It is shown that the more dominant the Line of Sight (LoS) component, the higher the gain achieved by the multilevel beamforming., Comment: Orange Labs Report

Virtual Sectorization (ViSn) aims at covering a confined area such as a traffic hot-spot using a narrow beam. The beam is generated by a remote antenna array located at-or close to the Base Station (BS). This paper develops the ViSn model and provides the guidelines for designing the Virtual Sector (ViS) antenna. In order to mitigate interference between the ViS and the traditional macro sector covering the rest of the area, a Dynamic Spectrum Allocation (DSA) algorithm that self-optimizes the frequency bandwidth split between the macro cell and the ViS is also proposed. The Self-Organizing Network (SON) algorithm is constructed to maximize the proportional fair utility of all the users throughputs. Numerical simulations show the interest in deploying ViSn, and the significant capacity gain brought about by the self-optimized bandwidth sharing with respect to a full reuse of the bandwidth by the ViS., Comment: VTC2015-Spring, 5th International Workshop on Self-Organizing Networks (IWSON), May 2015, Glasgow, United Kingdom

We revisit in this paper the relation between evolution of species and the mathematical tool of evolutionary games, which has been used to model and predict it. We indicate known shortcoming of this model that restricts the capacity of evolutionary games to model groups of individuals that share a common gene or a common fitness function. In this paper we provide a new concept to remedy this shortcoming in the standard evolutionary games in order to cover this kind of behavior. Further, we explore the relationship between this new concept and Nash equilibrium or ESS. We indicate through the study of some example in the biology as Hawk and Dove game, Stag Hunt Game and Prisoner Dilemma, that when taking into account a utility that is common to a group of individuals, the equilibrium structure may change dramatically. We also study the multiple access control in slotted Aloha based wireless networks. We analyze the impact of the altruism behavior on the performance at the equilibrium.

Defining an optimal protection strategy against viruses, spam propagation or any other kind of contamination process is an important feature for designing new networks and architectures. In this work, we consider decentralized optimal protection strategies when a virus is propagating over a network through a SIS epidemic process. We assume that each node in the network can fully protect itself from infection at a constant cost, or the node can use recovery software, once it is infected. We model our system using a game theoretic framework and find pure, mixed equilibria, and the Price of Anarchy (PoA) in several network topologies. Further, we propose both a decentralized algorithm and an iterative procedure to compute a pure equilibrium in the general case of a multiple communities network. Finally, we evaluate the algorithms and give numerical illustrations of all our results., Comment: accepted for publication in IEEE Transactions on Control of Network Systems

This paper addresses the mobile assignment problem in a multi-cell broadcast transmission seeking minimal total power consumption by considering both transmission and operational powers. While the large scale nature of the problem entails to find distributed solutions, game theory appears to be a natural tool. We propose a novel distributed algorithm based on group formation games, called \textit{the hedonic decision algorithm}. This formalism is constructive: a new class of group formation games is introduced where the utility of players within a group is separable and symmetric being a generalized version of parity-affiliation games. The proposed hedonic decision algorithm is also suitable for any set-covering problem. To evaluate the performance of our algorithm, we propose other approaches to which our algorithm is compared. We first develop a centralized recursive algorithm called \textit{the hold minimum} being able to find the optimal assignments. However, because of the NP-hard complexity of the mobile assignment problem, we propose a centralized polynomial-time heuristic algorithm called \textit{the column control} producing near-optimal solutions when the operational power costs of base stations are taken into account. Starting from this efficient centralized approach, a \textit{distributed column control algorithm} is also proposed and compared to \textit{the hedonic decision algorithm}. We also implement the nearest base station algorithm which is very simple and intuitive and efficiently manage fast-moving users served by macro BSs. Extensive simulation results are provided and highlight the relative performance of these algorithms. The simulated scenarios are done according to Poisson point processes for both mobiles and base stations.

The Quality of Experience (QoE) of streaming service is often degraded by frequent playback interruptions. To mitigate the interruptions, the media player prefetches streaming contents before starting playback, at a cost of delay. We study the QoE of streaming from the perspective of flow dynamics. First, a framework is developed for QoE when streaming users join the network randomly and leave after downloading completion. We compute the distribution of prefetching delay using partial differential equations (PDEs), and the probability generating function of playout buffer starvations using ordinary differential equations (ODEs) for CBR streaming. Second, we extend our framework to characterize the throughput variation caused by opportunistic scheduling at the base station, and the playback variation of VBR streaming. Our study reveals that the flow dynamics is the fundamental reason of playback starvation. The QoE of streaming service is dominated by the first moments such as the average throughput of opportunistic scheduling and the mean playback rate. While the variances of throughput and playback rate have very limited impact on starvation behavior., Comment: 14 pages

This paper studies the Nash stability in hedonic coalition formation games. We address the following issue: for a general problem formulation, is there any utility allocation method ensuring a Nash-stable partition? We propose the definition of the Nash-stable core. We study the conditions for having a non-empty Nash-stable core. More precisely, we show how relaxed efficiency in utility sharing method allows to ensure a non-empty Nash-stable core.

The goal of this paper is to study the behaviour of view-count in YouTube. We first propose several bio-inspired models for the evolution of the view-count of YouTube videos. We show, using a large set of empirical data, that the view-count for 90% of videos in YouTube can indeed be associated to at least one of these models, with a Mean Error which does not exceed 5%. We derive automatic ways of classifying the view-count curve into one of these models and of extracting the most suitable parameters of the model. We study empirically the impact of videos' popularity and category on the evolution of its view-count. We finally use the above classification along with the automatic parameters extraction in order to predict the evolution of videos' view-count., Comment: Technical report, 10 pages. Added MER definition analysis. Added interval confidence intervals. Added prediction results

Small cells have been identified as an effective solution for coping with the important traffic increase that is expected in the coming years. But this solution is accompanied by additional interference that needs to be mitigated. The enhanced Inter Cell Interference Coordination (eICIC) feature has been introduced to address the interference problem. eICIC involves two parameters which need to be optimized, namely the Cell Range Extension (CRE) of the small cells and the ABS ratio (ABSr) which defines a mute ratio for the macro cell to reduce the interference it produces. In this paper we propose self-optimizing algorithms for the eICIC. The CRE is adjusted by means of load balancing algorithm. The ABSr parameter is optimized by maximizing a proportional fair utility of user throughputs. The convergence of the algorithms is proven using stochastic approximation theorems. Numerical simulations illustrate the important performance gain brought about by the different algorithms., Comment: Submitted to WiOpt 2014

Typically the cost of a product, a good or a service has many components. Those components come from different complex steps in the supply chain of the product from sourcing to distribution. This economic point of view also takes place in the determination of goods and services in wireless networks. Indeed, before transmitting customer data, a network operator has to lease some frequency range from a spectrum owner and also has to establish agreements with electricity suppliers. The goal of this paper is to compare two pricing schemes, namely a power-based and a flat rate, and give a possible explanation why flat rate pricing schemes are more common than power based pricing ones in a deregulated wireless market. We suggest a hierarchical game-theoretical model of a three level supply chain: the end users, the service provider and the spectrum owner. The end users intend to transmit data on a wireless network. The amount of traffic sent by the end users depends on the available frequency bandwidth as well as the price they have to pay for their transmission. A natural question arises for the service provider: how to design an efficient pricing scheme in order to maximize his profit. Moreover he has to take into account the lease charge he has to pay to the spectrum owner and how many frequency bandwidth to rent. The spectrum owner itself also looks for maximizing its profit and has to determine the lease price to the service provider. The equilibrium at each level of our supply chain model are established and several properties are investigated. In particular, in the case of a power-based pricing scheme, the service provider and the spectrum owner tend to share the gross provider profit. Whereas, considering the flat rate pricing scheme, if the end users are going to exploit the network intensively, then the tariffs of the suppliers (spectrum owner and service provider) explode., Comment: This is the last draft version of the paper. Revised version of the paper accepted by ValueTools 2013 can be found in Proceedings of the 7th International Conference on Performance Evaluation Methodologies and Tools (ValueTools '13), December 10-12, 2013, Turin, Italy

Access to online contents represents a large share of the Internet traffic. Most such contents are multimedia items which are user-generated, i.e., posted online by the contents' owners. In this paper we focus on how those who provide contents can leverage online platforms in order to profit from their large base of potential viewers. Actually, platforms like Vimeo or YouTube provide tools to accelerate the dissemination of contents, i.e., recommendation lists and other re-ranking mechanisms. Hence, the popularity of a content can be increased by paying a cost for advertisement: doing so, it will appear with some priority in the recommendation lists and will be accessed more frequently by the platform users. Ultimately, such acceleration mechanism engenders a competition among online contents to gain popularity. In this context, our focus is on the structure of the acceleration strategies which a content provider should use in order to optimally promote a content given a certain daily budget. Such a best response indeed depends on the strategies adopted by competing content providers. Also, it is a function of the potential popularity of a content and the fee paid for the platform advertisement service. We formulate the problem as a differential game and we solve it for the infinite horizon case by deriving the structure of certain Nash equilibria of the game.

The fast development of the Self-Organizing Network (SON) technology in mobile networks renders the problem of coordinating SON functionalities operating simultaneously critical. SON functionalities can be viewed as control loops that may need to be coordinated to guarantee conflict free operation, to enforce stability of the network and to achieve performance gain. This paper proposes a distributed solution for coordinating SON functionalities. It uses Rosen's concave games framework in conjunction with convex optimization. The SON functionalities are modeled as linear Ordinary Differential Equation (ODE)s. The stability of the system is first evaluated using a basic control theory approach. The coordination solution consists in finding a linear map (called coordination matrix) that stabilizes the system of SON functionalities. It is proven that the solution remains valid in a noisy environment using Stochastic Approximation. A practical example involving three different SON functionalities deployed in Base Stations (BSs) of a Long Term Evolution (LTE) network demonstrates the usefulness of the proposed method., Comment: submitted to IEEE TCNS. arXiv admin note: substantial text overlap with arXiv:1209.1236

We consider wireless caches located in the plane according to general point process and specialize the results for the homogeneous Poisson process. A large data file is stored at the caches, which have limited storage capabilities. Hence, they can only store parts of the data. Clients can contact the caches to retrieve the data. We compare the expected cost of obtaining the complete data under uncoded as well as coded data allocation strategies. It is shown that for the general class of cost measures where the cost of retrieving data is increasing with the distance between client and caches, coded allocation outperforms uncoded allocation. The improvement offered by coding is quantified for two more specific classes of performance measures. Finally, our results are validated by computing the costs of the allocation strategies for the case that caches coincide with currently deployed mobile base stations.

We study the flow-level performance of random wireless networks. The locations of base stations (BSs) follow a Poisson point process. The number and positions of active users are dynamic. We associate a queue to each BS. The performance and stability of a BS depend on its load. In some cases, the full distribution of the load can be derived. Otherwise we derive formulas for the first and second moments. Networks on the line and on the plane are considered. Our model is generic enough to include features of recent wireless networks such as 4G (LTE) networks. In dense networks, we show that the inter-cell interference power becomes normally distributed, simplifying many computations. Numerical experiments demonstrate that in cases of practical interest, the loads distribution can be well approximated by a gamma distribution with known mean and variance., Comment: technical report

One of the central issues in the debate on network neutrality has been whether one should allow or prevent preferential treatment by an internet service provider (ISP) of traffic according to its origin. This raised the question of whether to allow an ISP to have exclusive agreement with a content provider (CP). In this paper we consider discrimination in the opposite direction. We study the impact that a CP can have on the benefits of several competing ISPs by sharing private information concerning the demand for its content. More precisely, we consider ISPs that compete over access to one common CP. Each ISP selects the price that it charges its subscribers for accessing the content. The CP is assumed to have private information about demand for its content, and in particular, about the inverse demand function corresponding to the content. The competing ISPs are assumed to have knowledge on only the statistical distribution of these functions. We derive in this paper models for studying the impact that the CP can have on the utilities of the ISPs by favoring one of them by exclusively revealing its private information. We also consider the case where CP can charge ISPs for providing such information. We propose two mechanisms based on {\em weighted proportional fairness} for payment between ISPs and CP. Finally, we compare the social utility resulting from these mechanisms with the optimal social utility by introducing a performance metric termed as {\em price of partial bargaining}, Comment: 10 pages, 4 figures, Accepted at WiOpt 2013

Social scientists have observed that human behavior in society can often be modeled as corresponding to a threshold type policy. A new behavior would propagate by a procedure in which an individual adopts the new behavior if the fraction of his neighbors or friends having adopted the new behavior exceeds some threshold. In this paper we study the question of whether the emergence of threshold policies may be modeled as a result of some rational process which would describe the behavior of non-cooperative rational members of some social network. We focus on situations in which individuals take the decision whether to access or not some content, based on the number of views that the content has. Our analysis aims at understanding not only the behavior of individuals, but also the way in which information about the quality of a given content can be deduced from view counts when only part of the viewers that access the content are informed about its quality. In this paper we present a game formulation for the behavior of individuals using a meanfield model: the number of individuals is approximated by a continuum of atomless players and for which the Wardrop equilibrium is the solution concept. We derive conditions on the problem's parameters that result indeed in the emergence of threshold equilibria policies. But we also identify some parameters in which other structures are obtained for the equilibrium behavior of individuals.

Future communication networks are expected to feature autonomic (or self-organizing) mechanisms to ease deployment (self-configuration), tune parameters automatically (self-optimization) and repair the network (self-healing). Self-organizing mechanisms have been designed as stand-alone entities, even though multiple mechanisms will run in parallel in operational networks. An efficient coordination mechanism will be the major enabler for large scale deployment of self-organizing networks. We model self-organizing mechanisms as control loops, and study the conditions for stability when running control loops in parallel. Based on control theory and Lyapunov stability, we propose a coordination mechanism to stabilize the system, which can be implemented in a distributed fashion. The mechanism remains valid in the presence of measurement noise via stochastic approximation. Instability and coordination in the context of wireless networks are illustrated with two examples and the influence of network geometry is investigated. We are essentially concerned with linear systems, and the applicability of our results for non-linear systems is discussed., Comment: submitted to INFOCOM 2013

In this paper, we develop a hierarchical Bayesian game framework for automated dynamic offset selection. Users compete to maximize their throughput by picking the best locally serving radio access network (RAN) with respect to their own measurement, their demand and a partial statistical channel state information (CSI) of other users. In particular, we investigate the properties of a Stackelberg game, in which the base station is a player on its own. We derive analytically the utilities related to the channel quality perceived by users to obtain the equilibria. We study the Price of Anarchy (PoA) of such system, where the PoA is the ratio of the social welfare attained when a network planner chooses policies to maximize social welfare versus the social welfare attained in Nash/Stackeleberg equilibrium when users choose their policies strategically. We show by means of a Stackelberg formulation, how the operator, by sending appropriate information about the state of the channel, can configure a dynamic offset that optimizes its global utility while users maximize their individual utilities. The proposed hierarchical decision approach for wireless networks can reach a good trade-off between the global network performance at the equilibrium and the requested amount of signaling. Typically, it is shown that when the network goal is orthogonal to user's goal, this can lead the users to a misleading association problem., Comment: 12 pages, 3 figures, technical report. arXiv admin note: text overlap with arXiv:1002.3931, arXiv:0903.2966 by other authors

This paper studies a significant problem in green networking called switching off base stations in case of cooperating service providers by means of stochastic geometric and coalitional game tools. The coalitional game herein considered is played by service providers who cooperate in switching off base stations. When they cooperate, any mobile is associated to the nearest BS of any service provider. Given a Poisson point process deployment model of nodes over an area and switching off base stations with some probability, it is proved that the distribution of signal to interference plus noise ratio remains unchanged while the transmission power is increased up to preserving the quality of service. The coalitional game behavior of a typical player is called to be \emph{hedonic} if the gain of any player depends solely on the members of the coalition to which the player belongs, thus, the coalitions form as a result of the preferences of the players over their possible coalitions' set. We also introduce a novel concept which is called the Nash-stable core containing those gain allocation methods that result in Nash-stable partitions. By this way, we always guarantee Nash stability. We study the non-emptiness of the Nash-stable core. Assuming the choice of a coalition is performed only by one player in a point of time, we prove that the Nash-stable core is non-empty when a player chooses its coalition in its turn, the player gains zero utility if the chosen coalition is visited before by itself., Comment: This paper has been withdrawn by the author since it was published partly

Representatives of several Internet service providers (ISPs) 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 (CPs) 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. Our first goal in this paper is to propose and study possible ways of implementing such payments and of regulating their amount. We introduce a model that includes the users' behavior, the utilities of the ISP and of the CPs, and the monetary flow that involves the content users, the ISP and CP, and in particular, the CP's revenues from advertisements. We consider various game models and study the resulting equilibria; they are all combinations of a noncooperative game (in which the ISPs and CPs determine how much they will charge the users) with a "cooperative" one on how the CP and the ISP share the payments. We include in our model a possible asymmetric weighting parameter (that varies between zero to one). We also study equilibria that arise when one of the CPs colludes with the ISP. We also study two dynamic game models and study the convergence of prices to the equilibrium values., Comment: 38 pages, 6 figures

This paper studies the performance of Mobile Ad hoc Networks (MANETs) when the nodes, that form a Poisson point process, selfishly choose their Medium Access Probability (MAP). We consider goodput and delay as the performance metric that each node is interested in optimizing taking into account the transmission energy costs. We introduce a pricing scheme based on the transmission energy requirements and compute the symmetric Nash equilibria of the game in closed form. It is shown that by appropriately pricing the nodes, the selfish behavior of the nodes can be used to achieve the social optimum at equilibrium. The Price of Anarchy is then analyzed for these games. For the game with delay based utility, we bound the price of anarchy and study the effect of the price factor. For the game with goodput based utility, it is shown that price of anarchy is infinite at the price factor that achieves the global optima.