A rotor walk in a directed graph can be thought of as a deterministic version of a Markov Chain, where a pebble moves from vertex to vertex following a simple rule until a terminal vertex, or sink, has been reached. The ARRIVAL problem, as defined by Dohrau et al. [Dohrau et al., 2017], consists in determining which sink will be reached. While the walk itself can take an exponential number of steps, this problem belongs to the complexity class NP ∩ co-NP without being known to be in P. In this work, we define a class of directed graphs, namely tree-like multigraphs, which are multigraphs having the global shape of an undirected tree. We prove that in this class, ARRIVAL can be solved in almost linear time, while the number of steps of a rotor walk can still be exponential. Then, we give an application of this result to solve some deterministic analogs of stochastic models (e.g., Markovian decision processes, Stochastic Games).

We propose a distributed learning algorithm for the resource allocation problem in Device-to-Device (D2D) wireless networks that takes into account the throughput estimation noise. We first formulate a stochastic optimization problem with the objective of maximizing the generalized alpha-fair function of the network. In order to solve it distributively, we then define and use the framework of noisy-potential games. In this context, we propose a Binary Log-linear Learning Algorithm (BLLA), which is distributed across cells and converges to a Nash equilibrium of the resource allocation game. This equilibrium is also an optimal for the resource allocation optimization problem. A key enabler for the analysis of the convergence are the proposed rules for computation of resistance of trees of perturbed Markov chains. The convergence of BLLA is proved for bounded and unbounded noise, with fixed and decreasing temperature parameter. A sufficient number of estimation samples is also provided that guarantees the convergence to an optimal state in a single cell scenario and close to an optimal state in a multi-cell scenario. We assess the performance of BLLA by extensive simulations by considering both bounded and unbounded noise cases and show that BLLA achieves higher sum data rate compared to the state-of-the-art.

The best algorithm so far for solving Simple Stochastic Games is Ludwig's randomized algorithm which works in expected $2^{O(\sqrt{n})}$ time. We first give a simpler iterative variant of this algorithm, using Bland's rule from the simplex algorithm, which uses exponentially less random bits than Ludwig's version. Then, we show how to adapt this method to the algorithm of Gimbert and Horn whose worst case complexity is $O(k!)$, where $k$ is the number of random nodes. Our algorithm has an expected running time of $2^{O(k)}$, and works for general random nodes with arbitrary outdegree and probability distribution on outgoing arcs.

We present a novel approach for distributed load balancing in heterogeneous networks that use cell range expansion (CRE) for user association and almost blank subframe (ABS) for interference management. First, we formulate the problem as a minimization of an α-fairness objective function with load and outage constraints. Depending on α, different objectives in terms of network performance or fairness can be achieved. Next, we model the interactions among the base stations for load balancing as a near-potential game, in which the potential function is the α-fairness function. The optimal pure Nash equilibrium (PNE) of the game is found by using distributed learning algorithms. We propose log-linear and binary log-linear learning algorithms for complete and partial information settings, respectively. We give a detailed proof of convergence of learning algorithms for a near-potential game. We provide sufficient conditions under which the learning algorithms converge to the optimal PNE. By running extensive simulations, we show that the proposed algorithms converge within few hundreds of iterations. The convergence speed in the case of partial information setting is comparable to that of the complete information setting. Finally, we show that outage can be controlled and a better load balancing can be achieved by introducing ABS.

In order to achieve high data rates in future wireless packet switched cellular networks, aggressive frequency reuse is inevitable due to the scarcity of the radio resources. While intra-cell interference is mostly mitigated and can be ignored, inter-cell interference can severely degrade performances of end-users. Hence, Inter-Cell Interference Coordination is commonly identified as a key radio resource management mechanism to enhance system performance of 4G networks. This paper addresses the problem of ICIC in the downlink of Long Term Evolution (LTE) systems where the Resource Blocks (RB) selection process is inspired from the reinforcement learning theory targeted to address the adversarial Multi-Armed Bandit problem. We resort to the popular EXP3 algorithm whose goal is to steer autonomously the decision of each Base Station (BS) towards the least interfered RBs while ensuring reactivity to the possible changes that can occur in the common resource usage and radio channel quality. However, the EXP3 algorithm is computationally heavy as its strategy set grows exponentially with the number of needed RBs and the total amount of available RBs. Therefore, we propose an efficient adaptation of the EXP3 algorithm, deemed Q-EXP3, where the needed RBs are selected one by one requiring only polynomial time computation.

We present a novel approach for distributive load balancing in heterogeneous networks that use cell range expansion (CRE) for user association. First, we formulate the problem as a minimisation of an α-fairness objective function. Depending on α, different objectives in terms of network performance or fairness can be achieved. Next, we model the interactions among the base stations for load balancing as a potential game, in which the potential function is the α-fairness function. The optimal Nash equilibrium of the game is found by using distributed learning algorithms. We use log-linear and binary log-linear learning algorithms for complete and partial information settings, respectively. By running extensive simulations, we show that the proposed algorithms converge within a few tens of iterations. The convergence speed in the case of partial information setting is comparable to that of the complete information setting. We also show that the best response algorithm does not necessarily converge to the optimal Nash equilibrium.

In this paper, we analyze the problem of signal covariance optimization in Gaussian multiple-input, multiple-output (MIMO) channels under imperfect (and possibly delayed) channel state information. Starting from the continuous-time dynamics of matrix exponential learning, we develop a distributed optimization algorithm driven by a damping term which ensures the method's stability under stochastic perturbations and asynchronicities of arbitrary magnitude. As opposed to traditional water-filling methods, the algorithm's convergence properties (speed and accuracy) can be controlled by tuning the users' learning rate and/or the damping parameter. Accordingly, the algorithm converges arbitrarily close to an optimum signal covariance profile within a few iterations, even for large numbers of users and/or antennas per user; furthermore, the quality of the solution obtained remains robust in the presence of imperfect (or delayed) measurements and asynchronous user updates.

The search neutrality debate questions the ranking methods of search engines. We analyze the issue when content providers offer content for free, but get revenues from advertising. We investigate the noncooperative game among competing content providers under different ranking policies. When the search engine is not involved with high-quality content providers, it should adopt neutral ranking, also maximizing user quality-of-experience. If the search engine controls high-quality content, favoring its ranking and adding advertisement yield a larger revenue. Though user perceived quality may not be impaired, the advertising revenues of the other content providers drastically decrease.

In this paper, we deal with a dynamic and stochastic admission control and mobile association problem in an heterogeneous wireless network. We extend the usual problem by adding mobility features described by a Markov Modulated Poisson Process. The aim is to optimize the average performance of the system. This dynamic control problem is modeled and solved using a Semi Markov Decision Process (SMDP) framework. We then assess the impact of the mobility and show that (i) our network centric approach outperforms a simple user centric algorithm and (ii) mobility improves the performance of the system when optimal policy of the problem is used.

Network neutrality is the topic of a vivid and very sensitive debate, in both the telecommunication and political worlds, because of its potential impact in everyday life. That debate has been raised by Internet Service Providers (ISPs), complaining that content providers (CPs) congest the network with insufficient monetary compensation, and threatening to impose side payments to CPs in order to support their infrastructure costs. While there have been many studies discussing the advantages and drawbacks of neutrality, there is no game-theoretical work dealing with the observable situation of competitive ISPs in front of a (quasi-)monopolistic CP. Though, this is a typical situation that is condemned by ISPs, and, according to them, another reason of the non-neutrality need. We develop and analyze here a model describing the relations between two competitive ISPs and a single CP, played as a three-level game corresponding to three different time scales. At the largest time scale, side payments (if any) are determined. At a smaller time scale, ISPs decide their (flat-rate) subscription fee (toward users), then the CP chooses the (flat-rate) price to charge users. Users finally select their ISP (if any) using a price-based discrete choice model, and decide whether to also subscribe to the CP service. The game is analyzed by backward induction. As a conclusion, we obtain among other things that non-neutrality may be beneficial to the CP, and not necessarily to ISPs, unless the side payments are decided by ISPs.

Current multi-core machines feature a complex and hierarchical core topology, multiple levels of cache and memory subsystem with NUMA design. Although this design provides high processing power to parallel machines, it comes with the cost of asymmetric memory access latencies. Depending on the parallel application communication patterns, this asymmetry may reduce the overall performance of the system. Therefore, to achieve scalable performance in this environment, it becomes crucial to exploit the machine architecture while taking into account the application communication patterns. In this paper, we introduce a topology-aware load balancing algorithm named HWTOPOLB. It combines the machine topology characteristics with the communication patterns of the application to equalize the application load on the available cores while reducing latencies. We also present the proof that the algorithm is asymptotically optimal (Theorem 1). We have implemented our load balancing algorithm using the CHARM++ Parallel System and analyzed its performance using three different benchmarks. Our experimental results show that the HWTOPOLB can achieve average performance improvements of 24% when compared to existing load balancing strategies on three different multi-core machines.

In this paper, we deal with a control problem for a new joint admission and resource allocation controller taking into account vertical handover in a heterogeneous wireless network. The controller is dynamic: it uses statistical information on the arrival and sojourn rates of the mobiles to optimize the average performance of the system. To account for multi-objective optimization, we consider the maximization of an objective subject to a set of constraints. We turn this constrained problem into an unconstrained one that we numerically solve using the Semi-Markovian Decision Process (SMDP) framework. We compare the optimal policy to some heuristics for different parameter values.

In this paper we show how game theory and Gibbs sampling techniques can be used to design a self-optimizing algorithm for minimizing end-to-end delays for all flows in a multi-class mobile ad hoc network (MANET). This is an improvement over the famed Ad-Hoc On-demand Distance Vector (AODV) protocol, that computes the routes with minimal number of hops for each flow in a multi-flow ad-hoc network. Here, the load of each flow is taken into account to choose the best route (in terms of delays) among a fixed number of routes. The algorithm can be implemented in a fully distributed and asynchronous way and is guaranteed to converge to the global optimal configuration. Numerous numerical experiments show that the gain over AODV, computed over a large number of networks, is quite substantial.

Recent mobile equipment (as well as the norm IEEE 802.21) offers the possibility for users to switch from one technology to another (vertical handover). This allows flexibility in resource assignments and, consequently, increases the potential throughput allocated to each user. In this paper, we design a fully distributed algorithm based on trial and error mechanisms that exploits the benefits of vertical handover by finding fair and efficient assignment schemes. On the one hand, mobiles gradually update the fraction of data packets they send to each network based on the rewards they receive from the stations. On the other hand, network stations send rewards to each mobile that represent the impact each mobile has on the cell throughput. This reward function is closely related to the concept of marginal cost in the pricing literature. Both the station and the mobile algorithms are simple enough to be implemented in current standard equipment. Based on tools from evolutionary games, potential games and replicator dynamics, we analytically show the convergence of the algorithm to fair and efficient solutions. Moreover, we show that after convergence, each user is connected to a single network cell which avoids costly repeated vertical handovers. To achieve fast convergence, several simple heuristics based on this algorithm are proposed and tested. Indeed, for implementation purposes, the number of iterations should remain in the order of a few tens.

Most of recent mobile equipment now supports different network technologies (WiFi, WiMax, LTE, Bluetooth and such like). Meanwhile, network operators offer services through these different technologies. The superposition of the different technologies (using different frequency band) increases the potential throughput of the system and hence global performance.