We consider a market comprising two competing service providers and a collection of users who can choose to subscribe to one provider or the other. The market is assumed to evolve over two subscription periods, while the users’ subscription decisions are based on the reviews of the earlier users, the prices set by the providers, and their own private preference parameter. In this context, we are interested in investigating the nature of the pricing policy adopted by the service providers. Towards this direction, employing the framework of stochastic games, we proceed to first solve the second-period pricing problem using information about the evolution of the market during the first-period. Specifically, given the first-period reviews about the QoS (Quality of Service) performance of the service providers, we characterize the solution to the second-period problem in terms of Nash equilibrium (NE) prices. We then derive an explicit expression for the NE prices by identifying the providers’ best-response functions. Next, using the form of the second-period NE prices we solve the overall two-period problem. In particular, for a given pair of pricing policies, we derive an integral-form expression for the expected revenue accrued by the providers over the two subscription periods. The revenue expression can be solved numerically to obtain the overall solution in terms of ($\epsilon $-approximate) NE pricing policy. Finally, we conduct a detailed numerical study to understand the performance of the market at the proposed Nash equilibrium pricing policy. Specifically, we identify two possible market scenarios (namely, true-belief and false-belief) that arise depending on whether the users’ belief about the providers’ capacity is correct. Interestingly, our results demonstrate that, under both market scenarios, a natural revenue-sharing compromise emerges between the providers across the two subscription time periods.

We propose a queueing theoretic based model to address the problem of offloading (packets or tasks) arising in multi-server systems. Using the framework of convex optimization we characterize the solution in terms of optimal offloading probabilities. We propose a low-complexity algorithm for identifying the optimal offloading probabilities; our algorithm is based on ordering the servers in terms of a proposed$\sigma- \mathbf{metric}$that takes into account the residual service as well as expected queue-lengths of the servers. Using the structure of the optimal policy as a guideline, we design multi-armed bandit based learning algorithms for offloading packets using only estimates of the service rates. Finally we conduct a detailed simulation study to understand the efficacy of the proposed learning algorithms in terms of queue-length regret metric.

In the above article[1]figures have been incorrectly numbered fromFig. 2onwards. We provide those figures here in the correct order. Readers are requested to refer to the figures in this article while reading the main manuscript[1].

In this work we consider the problem of maximizing the sum-utility of a network of 5G NR-U (New Radio - Unlicensed) base-stations operating in a common unlicensed band. The interference among the nearby base-stations in the network are modeled using clique constraints. Generalizing the framework of Network Utility Maximization (NUM), we propose a novel decentralized optimization mechanism involving clique-managers who arbitrate prices and payments with the local NR-Us. Assuming that the NR-Us possess no-information about the network structure, we first show that the proposed mechanism yields optimal sum-utility. We then model scenarios where the NR-Us possess (i) complete-information and (ii) local-information regarding the underlying network, and proceed to characterize solutions in terms of the respective equilibria. Finally, using the example of flower network, we conduct a numerical study to understand the efficacy of the proposed equilibria. We find that better efficiency is achieved when the NR-Us possess complete-information (i.e., fully-anarchic) than local-information (i.e., partially-anarchic). On the other hand, local-information scenario yields a fairer allocation of spectrum in the sense of maximizing the minimum allocation.

In this work we study the economic interactions that arise between a service provider and a collection of users in a participation-dependent social-learning market. Specifically, we consider a two-stage model of a market where the objective of the service provider is to design attractive subscription policies (i.e., subscription price-period combo) so as to maximize its overall revenue. The users on the other hand make subscription decisions based on their individual preferences (private information) as well as the feedback given by the earlier subscribers (public information). For the proposed two-stage model, taking into account the statistical differences between the users who subscribed to stage-1 (i.e., promotional period) and those who did not, we derive the optimal price for stage-2 (i.e., operational period) for each possible history of the stage-1 process. Then, employing the technique of dynamic programming we derive the Bellman’s optimality equation, solving which yields the optimal subscription policy for stage-1. Using the structure of the optimal policy as a guideline, we propose a range of heuristic policies by relaxing some key aspect(s) of the optimal policy. Finally, we conduct an extensive numerical study to benchmark the efficacy of the optimal policy (in terms of the average revenue accrued by the provider) against the proposed heuristic policies.

We study a completely uncoupled resource allocation algorithm for a heterogeneous network with the objective of maximizing the sum of the utilities (on the average pay-off) of users. We consider a state-dependent network, where the pay-off achieved by the users are a function of their actions as well as the state of the system. We consider four different scenarios depending on the state evolution and the users’ knowledge of the system state. In this context, we present completely uncoupled algorithms for utility maximization, where the users’ action is entirely a function of its past actions and its received pay-off. In particular, the user is oblivious to the actions of the other users in the network. Using the theory of perturbed Markov chains, we show the optimality of our algorithms under appropriate scenarios.

We consider a double-auction mechanism, which was recently proposed in the context of rate allocation in mobile data-offloading markets; our mechanism is also applicable to the problem of bandwidth allocation in network slicing markets. Network operators (users) derive benefit from offloading their traffic to third party WiFi or femtocell networks (link-suppliers). Link-suppliers experience costs for the additional capacity that they provide. Users and link-suppliers (collectively referred to as agents) have their pay-offs and cost functions as private knowledge. A network-manager decomposes the problem into a network problem (with surrogate pay-offs and surrogate cost functions) and agent problems (one per agent). The surrogate pay-offs and cost functions are modulated by the agents' bids. Agents' payoffs and costs are then determined by the allocations and prices set by the network-manager. Under this design, so long as the agents do not anticipate the effect of their actions on the prices set by the network-manager (i.e., price-taking agents), a competitive equilibrium exists as a solution to the network and agent problems, and this equilibrium optimizes the sum utility of all agents. However, this design fails when the agents (including the link-supplier) are all strategic (price-anticipating). Specifically, the presence of a strategic link-supplier drives the system to an undesirable equilibrium with zero participation resulting in an efficiency loss of 100%. This is in stark contrast to an earlier setting where the users alone are strategic but the link-supplier is not - the efficiency loss is known to be at most 34%. The paper then proposes the following Stackelberg game modification with asymmetric information structures for link-supplier and users in order to alleviate the efficiency-loss problem: the network-manager first announces the allocation and payment functions; he then invites the link-supplier to announce its bid, following which the users are invited to respond with their bids. The resulting Stackelberg games' efficiency losses can be characterized in terms of the link-supplier's cost function when the users' pay-off functions are linear. Specifically, when the link-supplier's cost function is quadratic, the worst case efficiency loss is 25%. Further, the loss in efficiency improves for polynomial cost functions of higher degree. For non-linear utility functions (e.g., α-fair and log utilities), we demonstrate the efficacy of the proposed mechanism via. a detailed numerical study.

We consider a wireless network comprising two types of nodes, namely, sinks and relays. The sink nodes are connected to a wireline infrastructure, while the relay nodes are used to extend the region covered by providing multi-hop paths to the sink nodes. Restricting to the one-dimensional setting, our objective is to characterize the fraction of covered region as a function of sink and relay node densities. We first compare and contrast our infrastructure-based model with the traditional setting where every node is a sink, and hence a location is covered if it simply lies within the range of some node. Then, drawing an analogy between the connected components of the network and the busy periods of an M/D/∞ queue (and using renewal theoretic arguments) we derive a closed-form expression for the average vacancy (complement of coverage). We also compute an upper bound for vacancy by introducing the notion of left-coverage (i.e., coverage by a node on the left); a lower bound is derived by coupling our model with an independent-disk model, where the sinks' coverage regions are independent and identically distributed. Through an extensive theoretical and numerical study, we investigate the problem of minimizing network deployment cost subject to a constraint on the average vacancy. We also conduct simulations to understand the properties of a general notion of coverage, obtained by introducing hop-counts into the definition. Parameterized approximations for the hop-constrained cluster lengths (around a sink) are proposed, whose efficacy is evaluated numerically. In particular, there exists a range of parameter values where our cluster-length approximation is good. Finally, hop-constrained cost optimization is conducted to demonstrate the efficacy of the infrastructure-based design.

We consider a recently proposed double-auction mechanism for mobile data-offloading. Network operators (users) derive benefit from offloading their traffic to third party WiFi or femtocell network (link-supplier). A link-supplier experiences costs for the additional capacity that he provides. Users and link-supplier (collectively referred to as agents) have their utilities and cost function as private knowledge. A system-designer decomposes the problem into a network problem (with surrogate utilities and surrogate cost functions) and agent problems (one per agent). The surrogate utilities and cost functions are modulated by the agents' bids. Agents' payoffs and costs are then determined by the allocations and prices set by the system designer. So long as the agents do not anticipate the effect of their actions, a competitive equilibrium exists as a solution to the network and agent problems, and this equilibrium optimizes the system utility. This work shows that when the agents are strategic (price-anticipating), the presence of strategic supplying agents drives the system to an undesirable equilibrium with zero participation. This is in stark contrast to the setting when link-suppliers are not strategic where the efficiency loss is at most 34%. The paper then proposes a Stackelberg game modification to alleviate the efficiency loss problem. The system designer first announces the allocation and payment functions. He then invites the supplying agents to announce their bids. He then invites the users to respond to the suppliers' bids. The resulting efficiency loss is characterized in terms of the suppliers' cost functions.

We present results from an extensive simulation study, conducted to understand the properties of coverage and percolation in infrastructure-based wireless networks that comprise sink and relay nodes. Specifically, we compute vacancy (complement of coverage) and percolation probabilities as functions of sink and relay node densities. Further, we identify that the vacancy probability in an alternate model that is motivated from traditional coverage processes, referred to as independent-disc model, constitutes a lower bound for the vacancy in the original infrastructure-based model. For the case of percolation, we identify a threshold boundary (in the space of sink-relay densities pair) where the percolation probability transits rapidly from 0 to 1 (i.e., from no-percolation to full-percolation).

In this paper we propose the Augmented-UCB (AugUCB) algorithm for a fixed-budget version of the thresholding bandit problem (TBP), where the objective is to identify a set of arms whose quality is above a threshold. A key feature of AugUCB is that it uses both mean and variance estimates to eliminate arms that have been sufficiently explored; to the best of our knowledge this is the first algorithm to employ such an approach for the considered TBP. Theoretically, we obtain an upper bound on the loss (probability of mis-classification) incurred by AugUCB. Although UCBEV in literature provides a better guarantee, it is important to emphasize that UCBEV has access to problem complexity (whose computation requires arms' mean and variances), and hence is not realistic in practice; this is in contrast to AugUCB whose implementation does not require any such complexity inputs. We conduct extensive simulation experiments to validate the performance of AugUCB. Through our simulation work, we establish that AugUCB, owing to its utilization of variance estimates, performs significantly better than the state-of-the-art APT, CSAR and other non variance-based algorithms.

We study a distributed user association algorithm for a heterogeneous wireless network with the objective of maximizing the sum of the utilities (on the received throughput)of wireless users. We consider a state-dependent wireless network where the rate achieved by the users are a function of their user associations as well as the state of the system. Also, we model the network to adapt its state based on the user associations. In this context, we present a completely uncoupled user association algorithm for utility maximization where the user's association is entirely a function of its past associations and its received throughput. In particular, the user is oblivious to the network state (and its evolution) as well as the association of the other users in the network. Using the theory of perturbed Markov chains [1], we show the optimality of our algorithm under appropriate scenarios.

We consider an opportunistic wireless communication 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 becomes available (or 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 common set of sleep-wake cycling relays. In general, our model can be considered as a game theoretic variant of the asset selling problem studied in the operations research literature. We study two variants of the generic relay selection problem, namely, the completely observable (CO) and the partially observable (PO) cases. These cases are based on whether a forwarder (in addition to observing its reward) can also observe the reward offered to the other forwarder. Formulating both problems as a two person stochastic game, we characterize the solutions 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. Through numerical work, for a one-hop forwarding example, we compare the cost performance of various NEPPs with a simple forwarding (SF) policy, which causes each forwarder to act as if the other is not present. We find that if the forwarders are not very close then the SF policy suffices. Insights gained from this numerical work are then used in an end-to-end simulation of geographical forwarding in a large network, in which we are concerned with delivery of packets from a tagged source to a sink, in the presence of competition from other packet flows destined for the same sink.

We consider an infrastructure-based wireless network comprising two types of nodes, namely, relays and sinks. The relay nodes are used to extend the network coverage by providing multi-hop paths to the sink nodes that are connected to a wireline infrastructure. Restricting to the one-dimensional case, our objective is to characterize the fraction of covered region for given densities of sink and relay nodes. We first compare and contrast our infrastructure-based model with the traditional setting, where a point is said to be covered if it simply lies within the range of some node. Then, drawing an analogy between the connected components of the network and the busy periods of an M / D /∞ queue, and using renewal theoretic arguments we obtain an explicit expression for the average vacancy (which is the complement of coverage). We also compute an upper bound for vacancy by introducing the notion of left-coverage (i.e., {coverage by a node from the left}). We prove a lower bound by coupling our model with an independent-disk model, where the sinks' coverage regions are independent and identically distributed. Through numerical work, we study the problem of minimizing network deployment cost subject to a constraint on the average vacancy. We also conduct simulations to understand the properties of a general notion of coverage, obtained by introducing hop-counts into the definition.

Understanding mobile data traffic demands is crucial to the evaluation of strategies addressing the problem of high bandwidth usage and scalability of network resources, brought by the pervasive era. In this paper, we conduct the first detailed measurement-driven modeling of smartphone subscribers' mobile traffic usage in a metropolitan scenario. We use a large-scale dataset collected inside the core of a major 3G network of Mexico's capital. We first analyse individual subscribers routine behavior and observe identical usage patterns on different days. This motivates us to choose one day for studying the subscribers' usage pattern (i.e., “when” and “how much” traffic is generated) in detail. We then classify the subscribers in four distinct profiles according to their usage pattern. We finally model the usage pattern of these four subscriber profiles according to two different journey periods: peak and non-peak hours. We show that the synthetic trace generated by our data traffic model consistently imitates different subscriber profiles in two journey periods, when compared to the original dataset.

In geographical forwarding of packets in a large wireless sensor network (WSN) with sleep-wake cycling nodes, we are interested in the local decision problem faced by a node that has “custody” of a packet and has to choose one among a set of next-hop relay nodes to forward the packet toward the sink. Each relay is associated with a “reward” that summarizes the benefit of forwarding the packet through that relay. We seek a solution to this local problem, the idea being that such a solution, if adopted by every node, could provide a reasonable heuristic for the end-to-end forwarding problem. Toward this end, we propose a local relay selection problem consisting of a forwarding node and a collection of relay nodes, with the relays waking up sequentially at random times. At each relay wake-up instant, the forwarder can choose to probe a relay to learn its reward value, based on which the forwarder can then decide whether to stop (and forward its packet to the chosen relay) or to continue to wait for further relays to wake up. The forwarder’s objective is to select a relay so as to minimize a combination of waiting delay, reward, and probing cost. The local decision problem can be considered as a variant of the asset selling problem studied in the operations research literature. We formulate the local problem as a Markov decision process (MDP) and characterize the solution in terms of stopping sets and probing sets. We provide results illustrating the structure of the stopping sets, namely, the (lower bound) threshold and the stage independence properties. Regarding the probing sets, we make an interesting conjecture that these sets are characterized by upper bounds. Through simulation experiments, we provide valuable insights into the performance of the optimal local forwarding and its use as an end-to-end forwarding heuristic.

Our work is motivated by geographical forwarding of sporadic alarm packets to a base station in a wireless sensor network (WSN), where the nodes are sleep-wake cycling periodically and asynchronously. We seek to develop local forwarding algorithms that can be tuned so as to tradeoff the end-to-end delay against a total cost, such as the hop count or total energy. Our approach is to solve, at each forwarding node enroute to the sink, the local forwarding problem of minimizing one-hop waiting delay subject to a lower bound constraint on a suitable reward offered by the next-hop relay; the constraint serves to tune the tradeoff. The reward metric used for the local problem is based on the end-to-end total cost objective (for instance, when the total cost is hop count, we choose to use the progress toward sink made by a relay as the reward). The forwarding node, to begin with, is uncertain about the number of relays, their wake-up times, and the reward values, but knows the probability distributions of these quantities. At each relay wake-up instant, when a relay reveals its reward value, the forwarding node's problem is to forward the packet or to wait for further relays to wake-up. In terms of the operations research literature, our work can be considered as a variant of the asset selling problem. We formulate our local forwarding problem as a partially observable Markov decision process (POMDP) and obtain inner and outer bounds for the optimal policy. Motivated by the computational complexity involved in the policies derived out of these bounds, we formulate an alternate simplified model, the optimal policy for which is a simple threshold rule. We provide simulation results to compare the performance of the inner and outer bound policies against the simple policy, and also against the optimal policy when the source knows the exact number of relays. Observing the good performance and the ease of implementation of the simple policy, we apply it to our motivating problem, i.e., local geographical routing of sporadic alarm packets in a large WSN. We compare the end-to-end performance (i.e., average total delay and average total cost) obtained by the simple policy, when used for local geographical forwarding, against that obtained by the globally optimal forwarding algorithm proposed by Kim et al.

We consider a wireless sensor network whose main function is to detect certain infrequent alarm events, and to forward alarm packets to a base station, using geographical forwarding. The nodes know their locations, and they sleep-wake cycle, waking up periodically but not synchronously. In this situation, when a node has a packet to forward to the sink, there is a trade-off between how long this node waits for a suitable neighbor to wake up and the progress the packet makes towards the sink once it is forwarded to this neighbor. Hence, in choosing a relay node, we consider the problem of minimizing delay subject to a constraint on the progress. By constraint relaxation, we formulate this next hop relay selection problem as a Markov decision process (MDP). The exact optimal solution (BF (Best Forward)) can be found, but is computationally intensive. Next, we consider a simplified model in which the times between the wake up instants of successive candidate relay nodes are assumed to be i.i.d. and exponentially distributed. The optimal policy (SF (Simplified Forward)) for this model is a simple one-step-look-ahead rule. Simulations show that SF is very close in performance to BF, even for a reasonably small node density. We then study the end-to-end performance of SF in comparison with two extremal policies: Max Forward (MF) and First Forward (FF), and an end-to-end delay minimizing policy proposed by Kim et al. We find that, with appropriate choice of one hop average progress constraint, SF can be tuned to provide a favorable trade-off between end-to-end packet delay and the number of hops in the forwarding path.