| Home | Info. for Authors | Program | Plenary Talks | Venue | Registration |
|
|
|
| |
 |
 |
Prashant G. Mehta, Tao Yang and Sean P. Meyn. Feedback Particle Filter: A New Formulation for Nonlinear Filtering based on Mean-field Games
A new formulation of the particle filter for nonlinear
filtering is presented, based on concepts from optimal control, and from
mean-field game theory. The feedback particle filter admits an innovations
error-based feedback control structure: The control is chosen so that the
posterior distribution of any particle matches the posterior distribution of
the true state given the observations.
The feedback particle filter is shown to have significant advantages over
the conventional particle filter in the numerical examples considered.
Application to Bayesian inference in neural circuits is briefly discussed
with the aid of coupled oscillator models.
Raffaele Pesenti and Dario Bauso. Mean field linear quadratic games with set up costs
This paper studies linear quadratic games with set
up costs monotonic on the number of active players, namely,
players whose action is non zero. Such games arise naturally in
joint replenishment inventory systems. Building upon a preliminary
analysis of the properties of the best response strategies and
Nash equilibria for the given game, the main contribution is the
study of the same game under large population. An introductory
discussion on fixed point methods to find mean field equilibria
is provided.
Quanyan Zhu and Tamer Başar. A Multi-Resolution Large Population Game Framework for Smart Grid Demand Response Management
Dynamic demand response (DR) management is becoming an integral part of the power system and market operational practice. Motivated by the smart grid DR management problem, we propose a multi-resolution stochastic differential game-theoretic framework to model the players' intra-group and inter-group interactions in a large population regime. We provide closed-form solutions for symmetric mean-field responses in the case of homogenous group population, and characterize the symmetric mean-field Nash equilibrium using the Hamilton-Jacobi-Bellman (HJB) equation together with the Fokker-Planck-Kolmogorov (FPK) equation. Finally, we apply the framework to the smart grid DR management problem and illustrate with numerical examples.
Sergio Pequito, A. Pedro Aguiar, Bruno Sinopoli and Diogo Gomes. Nonlinear Estimation using Mean Field Games
In this paper we introduce the Mean Field Games (MFG) as a framework to develop an estimator, that can be
viewed as an extension of the particle filters, but where now each particle is equipped with a control and acts as a rational player.
To this effect, all the players are associated with a cost function whose minimizer is the estimate. The main results presented in the papers are twofold: the formulation of the state estimation problem as a MFG and the derivation of explicit Kalman-like formulas. Computer simulations are performed to illustrate the method. In particular we provide an example where our estimator converges whereas both extended Kalman filter and particle filter diverge.
Ilan Lobel, Asuman Ozdaglar, and Diego Feijer. Distributed Multi-Agent Optimization with State-Dependent Communication
We study distributed algorithms for solving global optimization problems in which the
objective function is the sum of local objective functions of agents and the constraint
set is given by the intersection of local constraint sets of agents. We assume that each
agent knows only his own local objective function
and constraint set, and exchanges information
with the other agents over a randomly
varying network topology to update his
information state. We assume a state-dependent
communication model over this topology:
communication is Markovian with respect to the
states of the agents and the probability with
which the links are available depends on
the states of the agents.
We study a projected multi-agent subgradient
algorithm under state-dependent communication.
The state-dependence of the communication
introduces significant challenges and couples the
study of information exchange with the analysis of subgradient steps and
projection errors. We first show that the
multi-agent subgradient algorithm when used with
a constant stepsize may result in the agent
estimates to diverge with probability one. Under
some assumptions on the stepsize sequence, we
provide convergence rate bounds on a
"disagreement metric" between the agent
estimates. We show that agent estimates reach an
almost sure consensus and converge to the same
optimal solution of the global optimization
problem with probability one under different
assumptions on the local constraint sets and the stepsize sequence.
Grit Classen, Arie M.C.A. Koster and Anke Schmeink. Robust Planning of Green Wireless Networks
Current methods dealing with the energy efficient wireless network planning problem require a static model. However, bit rate requirements vary and rise over time, users move around and path gain fluctuates. In this paper, a robust optimization model is presented to deal with demand uncertainty. We apply cutting planes to reduce the complexity of the model. Furthermore, a case study is performed to compare the robust formulation to its deterministic counterpart and to conventional network planning.
Francois Meriaux and Samson Lasaulce. Mean-Field Games and Green Power Control
In this work, we consider a distributed wireless network where many transmitters communicate with a common receiver. Having the choice of their power control policy, transmitters are concerned with energy constraints : instantaneous energy-efficiency and long-term energy consumption. The individual optimization of the average energy-efficient utility over a finite horizon is studied by using control theory and a coupled system of Hamilton-Jacobi-Bellman-Fleming equations is obtained. As the corresponding stochastic differential game is difficult to analyze when the number of transmitters is large (in particular, the Nash equilibrium analysis becomes hard and even impossible), the problem is approximated by a mean-field game. The complete mean-field equilibrium analysis is then conducted (existence, uniqueness, and determination) and the efficiency of the corresponding power control policies is assessed numerically.
El-Azouzi Rachid, Francesco De Pellegrini, Habib Sidi and Yezekael Hayel. Markov Decision Evolutionary Game for Energy Management in Delay Tolerant Networks
In this paper, we apply the concepts of Markov decision evolutionary games to non-cooperative forwarding
control of Delay Tolerant Networks (DTN). Specifically, we rely on the design of mechanisms at the source node to study forwarding probability of the message in a DTN using the two-hop routing. We study the forwarding probability as a function of the competition within a large population of mobiles which need
occasionally to make some action. In particular, for each message generated
by a source, each mobile may take a decision that concerns the strategy
by which the mobile participates to the relaying of the message from
source to destination. A mobile that participates receives a unit of reward if it is
the first to deliver a copy of the packet to the destination. The action taken by a mobile determine not only the immediate reward but also the transition probability to its next battery energy state. We characterize the Evolutionary Stable
Strategies (ESS) for these games and propose a method to compute them. We also propose a mechanism design at the source in order to maximize the message delivery probability to the destination, given the equilibrium behavior (called Evolutionary Stable Strategy - ESS).
Lazaros Gkatzikis, Georgios S. Paschos and Iordanis Koutsopoulos. Medium Access Games: The Impact of Energy Constraints
In this paper we consider random medium access schemes for devices that support sleep modes, i.e. turning off electronic compartments for energy saving. Due to hardware limitations, sleep mode transitions cannot occur at the medium access timescale. Thus, we develop a two level model, consisting of a fast timescale for transmission scheduling and a slower timescale for the sleep mode transitions.We take a game theoretic approach to model the user interactions and show that the energy constraints modify the medium access problem significantly, decreasing the price of anarchy. Our results give valuable insights on the energy?throughput tradeoff for contention based systems.
Yezekael Hayel, Veronica Belmega and Eitan Altman. Hawks and Doves in a Dynamic Framework
We revisit in this paper the well-studied Hawk
and Dove game within a dynamic framework. A non-standard
evolutionary game approach is taken, in which the starting point
of the modelling is the dynamic evolution of the populations as a
function of the strategies used, instead of a fitness based model (in
which the fitness functions determine the evolution). This work
is motivated by the discussion in the book of Thomas L. Vincent
co-authored with J. Brown [4] in which they raise (on page 73)
the puzzling question of whom should one consider to be the
players: the individuals or the populations?
Ragavendran Gopalakrishnan, Jason R. Marden and Adam Wierman. Characterizing distribution rules for cost sharing games
We consider the problem of designing the distribution rule used to share "welfare" (cost or revenue) among individually strategic agents. There are many distribution rules known to guarantee the existence of a (pure Nash) equilibrium in this setting, e.g., the Shapley value and its weighted variants; however a characterization of the space of distribution rules that yield the existence of a Nash equilibrium is unknown. Our work provides a step towards such a characterization. We prove that when the welfare function is strictly submodular, a budget-balanced distribution rule guarantees equilibrium existence for all games (i.e., all possible sets of resources, agent action sets, etc.) if and only if it is a weighted Shapley value.
Piotr Wiecek and Eitan Altman. Stationary anonymous sequential games
Stationary anonymous sequential games with undiscounted
rewards are a special class of games that combines
features from both population games (infinitely many players)
with stochastic games. We extend the theory for these games to
the cases of total expected cost as well as to the expected average
cost. We show that equilibria in the anonymous sequential game
correspond to the limit of equilibria of related finite population
games as the number of players grow to infinity. We provide
many examples to illustrate our results.
Eitan Altman, Alesandra Estanislao and Manoj Panda. Routing Games on a Circle
Rings are quite common in both road traffic networks as well as in telecommunication networks. In the road traffic context, we often find rings surrounding towns and cities. Traffic over these rings is either bidirectional or we may find two rings that surround the town carrying traffic in opposite directions (clockwise and anti-clockwise). Telecommunication networks based on rings have been often used both as local area networks as well as in metropolitan area networks and here too we find both bidirectional networks as well as networks consisting of two rings carrying traffic in opposite directions. Each decision maker (e.g. the drivers, in the case of road traffic, and perhaps Internet access providers, in the case of telecommunication) is faced with a simple routing decision: whether to go clockwise or anti-clockwise. Assuming a simple source-destination demand matrix, we analyze this problem as a non-cooperative game and derive several interesting characteristics of the equilibria.
Nicolas Vieille. Convergence of Behavior in Social Networks
The dissemination of private information, or knowledge, in a population has attracted much interest, first among sociologists and geographers, and more recently among economists and computer scientists. A question that has attracted a lot of attention is whether as time passes, information spreads through the entire population, and beliefs become more precise, consensus of some sort eventually arises.
Plenary Talk: Anna Nagurney. Grand Challenges and Opportunities in Supply Chain Network Analysis and Design
Supply chain networks provide the backbones for our economies since they involve the production, storage, and distribution of products as varied as vaccines and medicines, food, high tech products, automobiles, clothing, and even energy. Many of the supply chains today are global in nature and time-sensitive and present challenging aspects for modeling and analysis. In this talk, I will discuss different perspectives for supply chain modeling, analysis, and computation based on centralized vs. decentralized decision-making behavior, along with suitable methodological frameworks. I will also highlight applications of our research to empirical electric power supply chains, to mergers and acquisitions, to supply chains in nature, and even to humanitarian logistics and health care applications from blood supply chains to medical nuclear ones. Such timely issues as risk management, demand uncertainty, outsourcing, and disruption management in the context of our recent research on supply chain network design and redesign will also be discussed. Suggestions for new directions and opportunities will conclude this talk.
Igal Milchtaich. Presentation of Finite Games as Network Congestion Games
Every finite noncooperative game can be presented as a weighted network congestion game and also as a network congestion game with player-specific costs. In the first presentation, different players may contribute differently to congestion, and in the second, they may be differently (negatively) affected by it. A game has a presentation as a network congestion game with identical weights and cost functions for all players if and only if it is an exact potential game.
Luca Carlone, Vaibhav Srivastava, Francesco Bullo and Giuseppe Calafiore. Distributed Random Convex Programming via Constraints Consensus
We study the distributed solution of random convex programs (RCP). We consider the setup in which the constraints of the RCP are not known by a central computational unit, but each node in a networked system knows a subset of constraints and the network has to exploit local computation and intra-agent communication for computing the solution of the global RCP. We propose the use of a constraint consensus algorithm
that allows each node to compute a solution of the random convex program. Then, we show that such solution converges in finite time to the centralized solution of the RCP and that it still assures the probabilistic guarantees of RoCP theory. We further present a distributed constraint removal strategy, for the case in which the network is required to remove a subset of constraints for the purpose of improving the objective value. The distributed scenario solution is demonstrated in classification and estimation problems.
Tinnirello Ilenia, Giarrè Laura, Romina Badalamenti and Fabio Giuseppe La Rosa. Distributed Resource Allocations in Ad hoc Wireless Networks
It is well known that CSMA (Carrier Sense Multiple
Access) protocols exhibit very poor performance in case of
multi-hop transmissions, because of inter-link interference due
to imperfect carrier sensing. Since ad-hoc networks based on
multi-hop packet deliveries are becoming more and more common
in different application and networking scenarios, different
medium access control extensions are currently considered for
improving the channel utilization efficiency.
In this paper, we propose a simple approach based on preallocating
temporal slots in which different sets of nodes are allowed
to contend for the channel access, which can significantly
improve CSMA performance with limited signaling overhead.
Since the approach is based on distributed coloring algorithms based
on cooperation mechanisms among the nodes, a game-theoretical analysis of
node selfish behaviors is currently under investigation.
Ehud Lehrer, Eilon Solan and Dario Bauso. Repeated games over networks with vector payoffs: the notion of attainability
We introduce the concept of strongly attainable sets of payoffs in two-player repeated games with vector payoffs in continuous time. A set of payoffs is called strongly attainable if player 1 has a strategy guaranteeing, even in the worst case, that the distance between the set and the cumulative payoff shrinks with time to zero. We characterize when any vector is strongly attainable and illustrate the motivation of our study on a multi-inventory application.
Danielle C. Tarraf and Dario Bauso. Robust Control of Networks Under Discrete Disturbances and Controls
This paper contributes to the analysis of necessary and sufficient conditions for the existence of robustly control invariant sets, as well as their properties when they do exist, in networks where the disturbances and control actions are discrete in nature.
Special emphasis is given to establishing connections with existing conditions in the literature where the inputs are assumed to be analog.
David Leslie and Jason Marden. Equilibrium selection in potential games with noisy rewards
Game theoretical learning in potential games is a highly active research area stemming from the connection between potential games and distributed optimisation. In many settings an optimisation problem can be represented by a potential game where the optimal solution corresponds to the potential function maximizer. Accordingly, significant research attention has focused on the design of distributed learning algorithms that guarantee convergence to the potential maximizer in potential games. However, there are currently no existing algorithms that provide convergence to the potential function maximiser when utility functions are corrupted by noise. In this paper we rectify this issue by demonstrating that a version of payoff-based log-linear learning guarantees that the only stochastically stable states are potential function maximisers even in noisy settings.
Patrick Loiseau, Galina Schwartz, John Musacchio and Saurabh Amin. Decongesting a Shared Resource by Means of Lotteries
We propose a raffle-based scheme for the decongestion of a shared resource. Our scheme uses ideas from the economics literature on the use of lotteries to incentivize contributions to a public good. We formulate a discrete game-theoretic model for the decongestion problem, as well as a continuous model with non-atomic users. We analyze the continuous model and we show that the discrete model converges toward the continuous model when the number of users goes to infinity. We compare our results to existing results for the public good provision problem. Overall, our results establish that the raffle-based scheme permits to achieve an optimal level of decongestion.
Karla Kvaternik and Lacra Pavel. Lyapunov Analysis of a Distributed Optimization Scheme
We analyze the convergence of the distributed multi-agent optimization scheme originally proposed in [1]. In this scheme, a number of agents cooperate to estimate the minimum of the sum of their locally-known cost functions. We consider a special case for which the collective cost function is strongly convex and where the agent communication graph is fixed. Whereas the analysis in [1] focuses on the suboptimality of the Cesaro averages of the agents' sequences, we establish explicit ultimate bounds on the agents' estimation errors themselves. We demonstrate that the collective optimum is practically asymptotically stable for this algorithm.
Saswati Sarkar. Pricing under uncertainty: Synergy between spectrum and energy
~
Peter Reichl, Ivan Gojmerac, Dominique Barth, Mariem Krichen, Johanne Cohen, Olivier Marcé. Techno-Economics of Small Cell Networks: The AWARE Project
The rapidly growing bandwidth demand for mobile
internet and mobile broadband applications is currently triggering
the development of novel approaches to increase the capacity
of the macro infrastructure of current mobile networks. Among
the available options, increasing the spatial density of mobile sites
is of specific interest, while at the same time the resulting new
paradigm of user-provided small cell networks requires to redefine
the traditional roles and relationships of network operators
and end customers to a large extent. In the framework of the
COMET/CELTIC project AWARE (Aggregation of Wireless
Access Resources), we address corresponding open issues from a
dedicated techno-economic perspective. This invited paper outlines
the basic approach taken by AWARE, describes the resulting
?prosumer? model and surveys the results of related gametheoretic
analysis.
Pierre Coucheney and Bruno Gaujal. Gibbs sampling with memory: Application to self-optimizing mobile association to base stations
Gibbs sampling techniques can be used to design self optimizing
algorithms in a distributed system made of many agents, each of them taking actions to optimize a global cost function.
If each agent updates its action according to a Gibbs sampling law, then the whole system is known to converge to a global optimal state with probability one.
However this convergence only occurs under strigent conditions on the behavior of the system:
Agent updates must happen one at a time and the valuation of the cost function
must be exact. If one of these two conditions is not satisfied (for example two agents modify their action at the same time, or the cost function valuation is noisy) then convergence may not hold or may not reach the global optimal point.
We propose a new algorithm where the previous actions of the agents are taken into account. This variant of Gibbs sampling is robust to both noisy measurements of the cost function and to any revision process (provided it has no starvation).
The dynamics induced by this algorithm is no longer Markovian. Instead, it is a stochastic approximation of the ordinary
differential equation that converges to the optimal point.
This technique is applied to self-optimizing mobile association to base stations
where its robustness is tested. Also, its speed of convergence compares well with the classical Gibbs sampling algorithm.
Ana Galindo-Serrano and Lorenza Giupponi. Femtocell Systems with Self Organization Capabilities
In this paper we present a self-organization technique to manage interference in femtocell networks. We model femtocells as a multiagent system implementing a form of Reinforcement Learning (RL) known as Q-Learning (QL) to solve the aggregated interference problem originated due to the macro-femtocell systems coexistence. We discuss this approach and propose a modification in order to solve some of the potential implementation limits of the QL algorithm. In order to achieve a more accurate environment representation and therefore a more appropriate femtocell system behavior, we combine Fuzzy logic with QL, in the form of Fuzzy Q-Learning (FQL), which allows agents to represent continuously the state and action spaces. Results are presented for the proposed QL and FQL algorithms as well as for two other FQL approaches with less complex perceptions of the surrounding environment and targets and a smart power control proposed by the 3GPP standardization body.
Gesualdo Scutari, Daniel P. Palomar, Francisco Facchinei and Jong-Shi Pang. Distributed Dynamic Pricing for MIMO Interfering Multiuser Systems: A Unified Approach
Wireless networks are composed of many users that usually have conflicting objectives and generate interference to each other. The system design is typically formulated as the optimization of the weighted sum of the users? utility functions. In an attempt to obtain distributed algorithms in the case this sum is nonconvex, researchers have proposed pricing mechanisms which however are based on heuristics and valid only for a restricted class of problems. In this paper we propose a general framework for the distributed optimization of the nonconvex sum-utility function. Our main contributions are: i) the derivation for the first time of a general dynamic pricing mechanism, ii) a framework that can be easily particularized to well-known applications, giving rise to very efficient practical algorithms that outperform existing methods; and iii) the solution to the currently open problem of social optimization for MIMO multiuser systems.
Bartek Blaszczyszyn and M.K. Karray. How the Path-Loss with Log-Normal Shadowing Impacts the Quality of Service in Cellular Networks and Why Blocking Probability is Not Always Increasing in the Shadowing Variance
Using a spatial version of the Erlang's loss formula
and the Kaufman-Roberts algorithm we show how the blocking probability of a constant bit-rate traffic depends on
the variance of the log-normal
shadowing and on the path-loss exponent in regular, hexagonal networks. Both functions exhibit a lack of
monotonicity.
In order to explain these observations, we study the mean path-loss with respect to the serving base station (BS)
and the mean interference factor,
defined as the ratio of the sum of the path-gains form interfering BS to the path-gain from the serving BS. We also
compare them to those obtained for irregular (Poisson) networks. We observe, as commonly expected, that a strong
variance of the shadowing increases the mean path-loss with respect to the serving BS, which in consequence
increases the blocking probability. However, we also obtain a more surprising result
saying that in some cases an increase of the variance of the shadowing
can significantly reduce the mean interference factor and,
in consequence, also the blocking probability. We confirm our findings by a mathematical analysis of the respective
models. We also obtain fully explicit, analytical results for the mean path-loss and interference factors in the
case of the infinite Poisson network with an arbitrary distribution of the shadowing.
Plenary Talk: Onno Boxma. Polling - analysis, optimization and control
A polling model is a queueing model consisting of several queues, which are cyclically visited by a server.
The server visits the queues according to some discipline, like $1$-limited (serve at most one customer in a visit)
or exhaustive (serve a queue until it has become empty).
Polling models find many applications in computer-communications, and also in other areas like
maintenance, production-inventory systems, and signallized traffic intersections.
The first part of the talk contains a global introduction to polling systems, and a review of some of their key properties.
In the second part of the talk I'd like to describe some recent and ongoing work with
Kamil Kosi\'nski and Offer Kella (on joint queue length and joint workload distributions)
and with Ivo Adan, Urtzi Ayesta, Josine Bruin, Brian Fralix, Vidyadhar Kulkarni, Maaike Verloop, Adam Wierman and Erik Winands
(on various scheduling and optimization problems in polling systems).
Roberto Cominetti and Cristobal Guzman. Network Congestion Control with Markovian Multipath Routing
In this paper we consider an integrated model
for TCP/IP protocols with multipath routing. The model
combines a Network Utility Maximization for rate control,
with a Markovian Traffic Equilibrium for routing, where
these layers measure congestion prices by queueing delay
and total delay respectively. This yields a cross-layer design
in which sources minimize the expected cost of sending
flows, while routers distribute the incoming flow among the
outgoing links according to a discrete choice model. We
prove the existence of a unique equilibrium state, which is
characterized as the solution of an unconstrained strictly
convex program of low dimension. A distributed algorithm
for solving this optimization problem is proposed.
Mael Le Treust and Samson Lasaulce. Resilient Source Coding
This paper provides a source coding theorem for multi-dimension information signals when the distribution associated with one of the components of the signal to be compressed is not known and a side information is available at the destination.
This new framework appears to be both of informationtheoretical and game-theoretical interest: it provides a new type of constraints to compress an information source; it is useful for designing certain types of mediators in games and characterize
utility regions for games with signals. Regarding the latter aspect, we apply the derived source coding theorem to the prisoner?s dilemma and the battle of the sexes.
Eitan Altman, Odile Pourtallier, Tania Jimenez and Hisao Kameda. Symmetric Games with networking applications
In their seminal paper,
Orda, Rom and Shimkin have already studied fully symmetric
routing games, i.e. games in which all players have the same
sources, destinations, demands and costs. They established
the uniqueness of an equilibrium in thsese games.
We extend their result to weaker
forms of symmetry, which does not require a common source
or destination.
Considering routing games,
we provide conditions under which
whenever there is some symmetry between some players,
then any equilibrium necessarily has these symmetry
property as well.
We then extend the symmetry result to
general games.
Emilie Coupechoux and Marc Lelarge. Impact of Clustering on Diffusions and Contagions in Random Networks
Motivated by the analysis of social networks, we study a model of
network that has both a tunable degree distribution and a tunable clustering coefficient.
We compute the asymptotic (as the size of the population tends to
infinity) for the number of acquaintances and the clustering for this
model. We analyze a contagion model with threshold effects and
obtain conditions for the existence of large cascade. We also analyze
a diffusion process with a given probability of contagion.
In both cases, we characterize conditions under which a global cascade
is possible.
Udi Ben-Porat, Anat Bremler-Barr and Hanoch Levy. Network and Computer Performance in Malicious Environments: The Good, the Bad and the Ugly
Performance analysis and the design of
computer and networking systems have traditionally accounted
for the stochastic nature of the problem addressed and been
based on stochastic type analysis, mainly expected value (``the
good?). In some related disciplines, mainly computer science
and algorithmic design, worst-case analysis (``the bad?) has
been popular. In recent years we have experienced a wave of
DDoS and Cyber attacks threatening the welfare of the internet.
These are launched by malicious users whose only incentive is
to degrade the performance of other, innocent, users. This has
triggered a new direction of research aiming at evaluating system
performance while accounting for the malicious behavior of the
attackers (``the ugly?). The performance metrics in this case
differs from both the average-case and the worst-case and can
affect system design considerably.
The purpose of this work is to expose and discuss this new
analysis approach as well as to distinguish it from the traditional
approaches. We use a wide array of cases and results derived in
the literature to demonstrate how such analysis can be carried
out. We further use them to show what kind of metrics can be
used to evaluate the effect of malicious behavior and the resilience
of the system against them.
Robert van der Mei. New Results on Waiting Time in Polling Systems
Polling systems are multi-queue systems where a single server visits queues in order
to serve customers present at these queues. Polling systems find a wealth of applications
in areas like computer-communications, manufacturing, maintenance, and therefore, have been
subject to extensive research over the last couple of decades.
In this talk I will give a brief overview of the state-of-the-art in the analysis of polling models
and will discuss a variety of new and promising results on waiting-time distributions in several
variants of polling models, including those with customer routing and non-Poisson arrival streams.
The talk is based on joint work with Marko Boon, Jan-Pieter Dorsman and Erik Winands
Jose Nino-Mora and Sofia S. Villar. Sensor Scheduling for Hunting Elusive Hiding Targets: a Restless Bandit Index Policy
We consider a sensor scheduling problem involving multiple sites, each containing an elusive hiding target, and a misdetection-prone sensor network capable of simultaneously sensing only a subset of those sites. Sensors must be dynamically allocated to sites based on partial information of target's visibility status. At each time slot a target's visibility evolves as a two-state Markov chain whose transition probabilities depend on sensing actions taken on
the target's site. We introduce a priority-index sensing policy for hunting smart targets, which aims to be close to optimal under a discounted or total net rewards performance criteria. The policy is designed by exploiting a real-state restless bandit formulation of the model and drawing on the indexation approach introduced by Whittle (1988) and in recent developments by Ni\~no-Mora, to address the challenging issues of indexability (existence of the index) and index evaluation.
Preliminary computational results are reported showing that the Whittle index policy can substantially outperform the conventional myopic policy as well as other simple
heuristics.
Tejas Bodas and D. Manjunath. On Load Balancing Equilibria in Multiqueue Systems with Multiclass Traffic
We consider a queueing system with two non identical FCFS servers together serving two classes of customers. All customers have i.i.d service requirements. One of the queues may charge an admission price, say $c.$ Arrivals are randomly routed to one of the servers and the routing probabilities are determined centrally to optimise a global objective, or from a local mechanism minimising a local---class or individual---objective. Our interest is to analyse the use of $c$ to achieve a target distribution of loads among the servers. We first analyse the structure of the optimal allocation and then consider (1) a system with a dispatcher for each class, (2) a non atomic system, and (3) a system where one of the classes has a dispatcher.
Dieter Fiems. Queues with M/G/[infinity] input: a survey and some new results
As input traffic at various nodes in packet switched telecommunication networks typically exhibits considerable correlation, there is a continuing interest in queuing systems with correlated arrivals. The class of M/G/[infinity] arrival models can account for various types of arrival correlation, has a two-level structure which is appealing in the context of network protocol stacks, and is characterised by only few parameters. Moreover, queues with M/G/[infinity] input prove to be amenable for a classic queueing analysis. In view of these characteristics, it is not surprising that these models have attracted considerable attention in the past. In this paper, we survey the literature on M/G/[infinity] type queueing systems, present some new results on these systems, and extend the class of M/G/[infinity] input models, while retaining the analytic tractability of the corresponding queueing systems.
Eitan Altman, Yezekael Hayel and Hisao Kameda. Revisiting Collusion in Routing Games: a Load Balancing Problem
Is it profitable for players to unite and merge to a single player?
Obviously, the sum of utilities at an equilibrium cannot exceed
the sum obtained if all players join together. But what happens
if only a subset of players join together? Previous work
on collusion have already shown that
the society may either gain or loose from collusion
of a subset of players.
In this paper we show for a simple load balancing example
that not only the society may loose, but also the subset of
players that collude may end up with a worse performance than
without collusion. In doing so, we introduce new concepts that
measure the price of collusion.
Majed Haddad and Eitan Altman. The Interplay Between Caching and Popularity
Caching should improve the performance and scalability
of multimedia streaming (e.g., YouTube). However, enabling
anyone to publish content means growth in content will not
only be larger than for traditional media, but sustainable.
This will place greater strain on centralized resources, and
require decentralized approaches such as caching and CDNs. In
particular, the increased availability of meta-data in Web 2.0 (as
opposed to traditional Web) can and should be exploited to make
such techniques more effective. We introduce new directions and
considerations in the analysis of caching popular content in the
Web which allows us to gain insight on deriving more informative
indications for quality of service development. In this work,
we provide a dynamic model for the impact of popularity on
the access speed due to caching policies of a service provider.
More specifically, we assume that caches are spatially deployed
as a Poisson distribution and that users are distributed over
the geographical area is Poissonian. Our model is formulated as
epidemic type process of file dissemination. We then study the
transient behavior of caches where information is replicated and
disseminated according to an epidemic type dynamics based on
the popularity of the content. Simulation results show that the
proposed scheme provides significant improvement in terms of
the system throughput.
Eitan Altman, Cengis Hasan, Jean-Marie Gorce and Laurent Roullet. Green Networking: Downlink Considerations
In this work, we consider downlink transmission
in cellular networks where we target to reduce the energy
consumption by switching off some base stations by such a
way that the distribution of SINR remains unchanged. This is
a mean of green networking in cellular networks in downlink
consideration. This paper analyzes for line and plane cases,
the gain in power consumption obtained after switching off
base stations. By computations we observe that the more the
operational cost the less the gain in power consumption.
Dominique Barth, Johanne Cohen, Patrick Maillé and Hélia Pouyllau. Competition among Online-Gaming Service Providers
Game as a Service (GaaS) has recently been deployed to cope with the limitations of user devices (storage, computing power, energy). The pricing schemes ?essentially flat-rate? implemented by providers are simple, but the consequences of the price levels and the offer contents on demand repartition are involved. In this paper, we introduce a model for the interactions among competing network providers offering GaaS solutions, in order to study their competition in terms of prices and selection of games to propose. We illustrate some trade-offs that network provider face, between the attractiveness of a game and its incurred costs.
Amar Prakash Azad and John Musacchio. Unilateral Altruism in Network Routing Games with Atomic Players
We study a routing game in which one of the players unilaterally acts altruistically by taking into consideration the latency cost of other players as well as his own. By not playing selfishly, a player can not only improve the other players? equilibrium utility but also improve his own equilibrium utility. To quantify the effect, we define a metric called the Value of Unilateral Altruism (VoU) to be the ratio of the equilibrium utility of the altruistic user to the equilibrium utility he would have received in Nash equilibrium if he were selfish. We show by example that the VoU, in a game with nonlinear latency functions and atomic players, can be arbitrarily large. Since the Nash equilibrium social welfare of this example is arbitrarily far from social optimum, this example also has a Price of Anarchy (PoA) that is unbounded. The example is driven by there being a small number of players since the same example with non-atomic players yields a Nash equilibrium that is fully efficient.
Mohammed Baslam, El-Azouzi Rachid, Essaid Sabir and Loubna Echabbi. Market Share Game with adversarial Access providers : A Neutral and a Non-neutral Network Analysis
Internet pricing schemes have not been concerned in the network-neutrality research. In this paper, we study the implication of non-neutrality on the competition between Internet Access Providers. We interpret non-neutral network when a service provider privileges a Content Provider (CP) in order to propose a high quality of service for this content like time-sensitive applications (voice over Internet protocol, live video streaming, online gaming). We present a competitive model that describes the interaction between several competing telecommunications Access Providers (APs), their subscribers, and a network owner. Competition between the access providers is assumed to take place in their pricing decisions as well as in terms of the Quality of Service (QoS) they offer. Furthermore, our work focuses on the analysis of games between APs under two cases : case of neutral network and case of non-neutral network. After having discussed the existence and uniqueness of equilibrium, we analyzed the impact non-neutrality versus neutrality. In particular, we showed that non-neutrality has a significant effect on the charged tariffs and the perceived quality of services in case where exist restrictions on the available bandwidth at the AP-CP link.
Yousuke Takahashi and Keisuke Ishibashi. Incentive mechanism for prompting ISPs to implement outbound filtering of unwanted traffic
Methods of filtering unwanted traffic in ISPs are categorized into
inbound filtering at receiver ISPs and outbound filtering at sender
ISPs. Outbound filtering is effective because it can directly utilize
sender information such as dynamic IP address information, but not
widely used in the current Internet. This is because outbound filtering
does not benefit the ISP that installs it and pays the cost, but
benefits ISPs that receive unwanted traffic from the installing ISP. The
objective of our study is to solve this incentive problem. We propose an
incentive mechanism where ISPs pay penalties for sending unwanted
traffic to peering ISPs. This payment is combined with payments of
transit fees so that the mechanism will be deployed through the current
ISP relationship. The key question here is whether the mechanism will be
deployed or not, and we confirmed through simulations that the mechanism
is spontaneously adopted by a sufficient number of ISPs who behave in a
selfish manner. Accordingly, outbound filtering was also widely
installed. In our simulation scenario, there are some ISPs who send
little unwanted traffic and should not install the outbound filtering
due to its cost. Our simulation showed that with an appropriate penalty
charge parameter setting, our proposed mechanism can achieve the state
that almost all ISPs who should install the outbound filtering install
the filtering, and otherwise not.
Stefano Paris, Fabio Martignon, Ilario Filippini and Antonio Capone. A Bandwidth Marketplace for Heterogeneous Mobile Networks
In recent years, with the evolution of new and content-rich Internet services, mobile network operators face the challenging task to guarantee ubiquitous and seamless access to their customers, while minimizing the installation and operating costs of their network. On the other hand, in residential areas most of the network capacity that residential users lease from ISP for Internet access remains unexploited.
Mobile network operators can therefore rent the unexploited capacity of residential user access devices (e.g., wireless access points or femtocells) when the traffic demand of their mobile customers exceeds the operator's network capacity.
To minimize the leasing costs for the use of the capacity made available by residential users and prevent market manipulation, we formulate the allocation mechanism as a combinatorial reverse auction, which guarantees that all users reveal their real price for the utilization of their wireless access points.