Network Games, Control, and Optimization

Inhaltsverzeichnis

1. Frontmatter

2. Pricing of Coexisting Cellular and Community Networks

   Patrick Maillé, Bruno Tuffin, Joshua Peignier, Estelle Varloot

   Abstract

   Community networks have emerged as an alternative to licensed band systems (WiMAX, 4G, etc.), providing an access to the Internet with Wi-fi technology while covering large areas. A community network is easy and cheap to deploy, as the network is using members’ access points in order to cover the area. We study the competition between a community operator and a traditional operator (using a licensed band system) through a game-theoretic model, while considering the mobility of each user in the area.

3. Achieving Arbitrary Throughput–Fairness Trade-offs in the Inter-cell Interference Coordination with Fixed Transmit Power Problem

   Vaibhav Kumar Gupta, Gaurav S. Kasbekar

   Abstract

   We study the problem of inter-cell interference coordination (ICIC) with fixed transmit power in OFDMA-based cellular networks, in which each base station (BS) needs to decide as to which subchannel, if any, to allocate to each of its associated mobile stations (MS) for data transmission. In general, there exists a trade-off between the total throughput (sum of throughputs of all the MSs) and fairness under the allocations found by resource allocation schemes. We introduce the concept of \(\tau -\alpha -\)fairness by modifying the concept of \(\alpha -\)fairness, which was earlier proposed in the context of designing fair end-to-end window-based congestion control protocols for packet-switched networks. The concept of \(\tau -\alpha -\)fairness allows us to achieve arbitrary trade-offs between the total throughput and degree of fairness by selecting an appropriate value of \(\alpha \) in \([0,\infty )\). We show that for every \(\alpha \in [0,\infty )\) and every \(\tau > 0\), the problem of finding a \(\tau -\alpha -\)fair allocation is NP-complete. Also, we propose a simple, distributed subchannel allocation algorithm for the ICIC problem, which is flexible, requires a small amount of time to operate, and requires information exchange among only neighboring BSs. We investigate via simulations as to how the algorithm parameters should be selected so as to achieve any desired trade-off between the total throughput and fairness.

4. Coexistence of LTE-Unlicensed and WiFi with Optimal Channel Aggregation

   Naveen Kolar Purushothama

   Abstract

   In this work, we investigate the problem of channel and rate allocation for LTE-Unlicensed (LTE-U) to efficiently coexist with WiFi access points (APs). Specifically, we formulate an auction mechanism where LTE-U first announces an aggregation number (number of WiFi channels that LTE-U wishes to aggregate) and a reserve rate (maximum rate that LTE-U is willing to allocate to an AP), following which the APs decide their mode of operation—cooperation or competition. In cooperation mode, an AP allows LTE-U to exclusively occupy its channel (in return for a rate) while in the competition mode both LTE-U and AP simultaneously contend for channel access. We characterize the solution to the auction problem in terms of Symmetric Bayesian Nash Equilibrium (SBNE) and prove results illustrating its structure. We then optimize the auction mechanism by evaluating the optimal aggregation number and reserve rate that maximizes the total rate achieved by LTE-U subject to a constraint on APs’ rates. Finally, through simulation experiments we demonstrate the efficacy of our algorithm in comparison with (1) the strategy of aggregating a fixed number of channels and (2) a heuristic algorithm where a random number of channels are aggregated.

5. Analysis of Sponsored Data Practices in the Case of Competing Wireless Service Providers

   Patrick Maillé, Bruno Tuffin

   Abstract

   With wireless sponsored data, a third party, content or service provider, can pay for some of your data traffic so that it is not counted in your plan’s monthly cap. This type of behavior is currently under scrutiny, with telecommunication regulators wondering if it could be applied to prevent competitors from entering the market and what the impact on all telecommunication actors can be. To answer those questions, we design and analyze in this paper a model where a content provider (CP) can choose the proportion of data to sponsor and a level of advertisement to get a return on investment, with several Internet service providers (ISPs) in competition. We distinguish three scenarios: no sponsoring, the same sponsoring to all users, and a different sponsoring depending on the ISP you have subscribed to. This last possibility may particularly be considered an infringement of the network neutrality principle. We see that sponsoring can be beneficial to users and ISPs depending on the chosen advertisement level. We also discuss the impact of zero-rating where an ISP offers free data to a CP to attract more customers, and vertical integration where a CP and an ISP are the same company.

6. Media Delivery Competition with Edge Cloud, Remote Cloud and Networking

   Xinyi Hu, George Kesidis, Behdad Heidarpour, Zbigniew Dziong

   Abstract

   We describe a marketplace for content distribution, specifically stored-video streaming, involving both edge cloud (fog) and remote cloud computing and storage resources. Three different types of participants are considered: providers that are affiliated with the remote cloud, those that are affiliated with the ISP/edge, and those affiliated with neither. For a simple model, we explore the existence of a Nash equilibrium. Furthermore, we formulate a leader-follower game involving a market regulator maximizing a social welfare and study its Stackelberg equilibrium. For a market regulator seeking to limit prices charged by an edge-cloud entrant, we show an interesting trade-off between “moderate” edge-cloud prices and existence of follower (Nash) equilibrium.

7. An Algorithmic Framework for Geo-Distributed Analytics

   Srikanth Kandula, Ishai Menache, Joseph (Seffi) Naor, Erez Timnat

   Abstract

   Large-scale cloud enterprises operate tens to hundreds of datacenters, running a variety of services that produce enormous amounts of data, such as search clicks and infrastructure operation logs. A recent research direction in both academia and industry is to attempt to process the “big data” in multiple datacenters, as the alternative of centralized processing might be too slow and costly (e.g., due to transferring all the data to a single location). Running such geo-distributed analytics jobs at scale gives rise to key resource management decisions: Where should each of the computations take place? Accordingly, which data should be moved to which location, and when? Which network paths should be used for moving the data, etc. These decisions are complicated not only because they involve the scheduling of multiple types of resources (e.g., compute and network), but also due to the complicated internal data flow of the jobs—typically structured as a DAG of tens of stages, each of which with up to thousands of tasks. Recent work [17, 22, 25] has dealt with the resource management problem by abstracting away certain aspects of the problem, such as the physical network connecting the datacenters, the DAG structure of the jobs, and/or the compute capacity constraints at the (possibly heterogeneous) datacenters. In this paper, we provide the first analytical model that includes all aspects of the problem, with the objective of minimizing the makespan of multiple geo-distributed jobs. We provide exact and approximate algorithms for certain practical scenarios and suggest principled heuristics for other scenarios of interest.

8. The Stackelberg Equilibria of the Kelly Mechanism

   Francesco De Pellegrini, Antonio Massaro, Tamer Başar

   Abstract

   The Kelly mechanism dictates that players share a resource proportionally to their bids. The corresponding game is known to have a unique Nash equilibrium. A related question arises, which is the nature of the behavior of the players for different prices imposed by the resource owner, who may be viewed as the leader in a Stackelberg game where the other players are followers. In this work, we describe the dynamics of the Nash equilibrium as a function of the price. Toward that goal, we characterize analytical properties of the Nash equilibrium by means of the implicit function theorem. With regard to the revenue generated by the resource owner, we provide a counterexample which shows that the Stackelberg equilibrium of the Kelly mechanism may not be unique. We obtain sufficient conditions which guarantee the set of Stackelberg equilibria to be finite and unique in the symmetric case. Finally, we describe the dependency between the resource’s signal and the maximum revenue that the resource owner can generate.

9. To Participate or Not in a Coalition in Adversarial Games

   Ranbir Dhounchak, Veeraruna Kavitha, Yezekael Hayel

   Abstract

   Cooperative game theory aims to study complex systems in which players have an interest to play together instead of selfishly in an interactive context. This interest may not always be true in an adversarial setting. We consider in this paper that several players have a choice to participate or not in a coalition in order to maximize their utility against an adversarial player. We observe that participating in a coalition is not always the best decision; indeed selfishness can lead to better individual utility. However, this is true under rare yet interesting scenarios. This result is quite surprising as in standard cooperative games; coalitions are formed if and only if it is profitable for players. We illustrate our results with two important resource-sharing problems: resource allocation in communication networks and visibility maximization in online social networks. We also discuss fair sharing using Shapley values, when cooperation is beneficial.

10. On the Asymptotic Content Routing Stretch in Network of Caches: Impact of Popularity Learning

    Boram Jin, Jiin Woo, Yung Yi

    Abstract

    In this paper, we study the asymptotic average routing stretch for random content requests in a general network of caches. The key factor considered in our study is the need of learning content popularity in an online manner to consider time-varying changes of content popularity, where there exists a complex inter-play among (a) how long we should learn popularity, (b) how often we should change cached contents, and (c) how we use learnt popularity in caching contents over the network. We model this inter-play in a broad class of caching policies, called Repeated Learning and Placement (RLP), and aim at quantifying the asymptotic routing stretch of content requests under various external conditions. Our derivation of this scaling law in the routing stretch is made under different dependence of the speed of popularity change, average routing stretch in the network of caches, the shape of the popularity distribution, and heterogeneous cache budget allocation based on nodes’ geometric importance. We believe that our analytical results, even if they are asymptotic, provide additional ways and implications on understanding the delay performance of large-scale content distribution network (CDN) and information-centric network (ICN).

11. Tiered Spectrum Measurement Markets for Licensed Secondary Spectrum

    Arnob Ghosh, Randall Berry, Vaneet Aggarwal

    Abstract

    The recent framework for tiered spectrum sharing in the 3.5 GHz band allows for environmental sensing capability (ESC) operators to measure spectrum occupancy so as to enable commercial use of this spectrum when incumbent users are not present. Motivated by this, we consider a scenario in which two spectrum access (SA) firms seek to access a spectrum band for secondary access and must in turn purchase spectrum measurements from one of the two ESCs. Each SA has an exclusive licensed access to a spectrum band. Given the purchased measurements, the SAs compete on price to serve customers. We study how the ESCs’ cost of obtaining the spectrum measurement, the ESC’s prices, and the quality of the spectrum measurements impact the resulting market equilibrium between the SAs. In particular, we show that when the ESCs offer different qualities, the only equilibria that can exist are when both SAs purchase measurements from the same ESC.

12. On Incremental Passivity in Network Games

    Lacra Pavel

    Abstract

    In this paper, we show how control principles and passivity properties can be used in analysing and designing learning rules/dynamics for agents playing a network game. We focus on two instances: (1) agents learning about the others’ actions and (2) agents learning about the game (reinforcement-learning). In both cases, we show the trade-off between game properties and agent learning dynamics properties, underpinned by passivity/monotonicity and the balancing principle.

13. Impact of Social Connectivity on Herding Behavior

    Deepanshu Vasal

    Abstract

    Information cascades have been studied in the literature where myopic selfish users sequentially appear and make a decision to buy a product based on their private observation about the value of the product and actions of their predecessors. Bikhchandani et. al (1992) and Banerjee (1992) introduced such a model and showed that after a finite time, almost surely, users discard their private information and herd on an action asymptotically. In this paper, we study a generalization of that model where we assume users are connected through a random tree, which locally acts as an approximation for Erdös–Rényi random graph when the degree distribution of each vertex of the tree is binomial and as the number of nodes grows large. We show that informational cascades on such tree-structured networks may be analyzed by studying the extinction probability of a certain branching process. We use the theory of multi-type Galton–Watson branching process and calculate the probability of the tree network falling into a cascade. More specifically, we find conditions when this probability is strictly smaller than 1 that are in terms of the degree distributions of the vertices in the tree. Our results indicate that groups that are less tightly knit, i.e., have lesser connection probability (and as a result have lesser diversity of thought), tend to herd more than the groups that have more social connections.

14. A Truthful Auction Mechanism for Dynamic Allocation of LSA Spectrum Blocks for 5G

    Ayman Chouayakh, Aurélien Bechler, Isabel Amigo, Loutfi Nuaymi, Patrick Maillé

    Abstract

    Licensed shared access is a new frequency sharing concept that allows mobile network operators (MNOs) to use some of the spectrum initially allocated to other incumbents, after obtaining a temporary license from the regulator. The allocation is made among groups such that two base stations in the same group can use the same spectrum simultaneously. In this context, different auction schemes were proposed; however, they consider the scenario in which the regulator has one and only one block of LSA frequency to allocate. In this paper, we remove this hypothesis: We suppose that the regulator has K identical blocks of spectrum to allocate, and we propose a truthful auction mechanism based on the Vickrey–Clarke-Groves mechanism (VCG). We evaluate the efficiency of our mechanism in terms of social welfare, which depends on the allocation rule of the mechanism. Simulations show that the efficiency of the proposed mechanism is at least 60% of that of VCG, which is known to be optimal.

15. Routing Game with Nonseparable Costs for EV Driving and Charging Incentive Design

    Benoît Sohet, Olivier Beaude, Yezekael Hayel

    Abstract

    Designing optimal incentive mechanisms for electric vehicles is an important challenge nowadays. In fact, this new type of vehicle influences several parts of society, at the transport level through congestion/pollution and at the energy level. In this paper, we consider the design of driving and charging optimal incentive through a routing game approach with multiple types of vehicles: gasoline and electric. We show that the game is not standard and needs a particular framework. We are able to prove the existence of a Wardrop equilibrium of this routing game with nonseparable costs, due to interaction through the energy cost. Our analysis is applied to a particular transportation network in which two paths are possible for vehicles, mainly one through the city center and another one outside. A fully characterization of Wardrop equilibrium is proposed, and optimal tolls are computed in order to minimize an environmental cost. Numerical results are provided on real data of electricity consumptions in France and in Texas, USA.

16. The Social Medium Selection Game

    Fabrice Lebeau, Corinne Touati, Eitan Altman, Nof Abuzainab

    Abstract

    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.

17. Public Good Provision Games on Networks with Resource Pooling

    Mohammad Mahdi Khalili, Xueru Zhang, Mingyan Liu

    Abstract

    We consider the interaction of strategic agents and their decision-making process toward the provision of a public good. In this interaction, each user exerts a certain level of effort to improve his own utility. At the same time, the agents are interdependent and the utility of each agent depends not only on his own effort but also on the other agents’ effort level. As the agents have a limited budget and can exert limited effort, question arises as to whether there is advantage to agents pooling their resources. In this study, we show that resource pooling may or may not improve the agents’ utility when they are driven by self-interest. We identify some scenarios where resource pooling does lead to social welfare improvement as compared to without resource pooling. We also propose a taxation–subsidy mechanism that can effectively incentivize the agents to exert socially optimal effort under resource pooling.