{'fraction_non_alphanumeric': 0.039042484035027344, 'fraction_numerical': 0.006997820351038201, 'mean_word_length': 4.440399417516122, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Game Theoretic Analysis for Joint Sponsored and Edge Caching Content Service Market

With a sponsored content scheme in a wireless network, a sponsored content service provider can pay to a network operator on behalf of the mobile users/subscribers to lower down the network subscription fees at the reasonable cost in terms of receiving some amount of advertisements. As such, content providers, network operators and mobile users are all actively motivated to participate in the sponsored content ecosystem. Meanwhile, in 5G cellular networks, caching technique is employed to improve content service quality, which stores potentially popular contents on edge networks nodes to serve mobile users. In this work, we propose the joint sponsored and edge caching content service market model. We investigate an interplay between the sponsored content service provider and the edge caching content service provider under the non-cooperative game framework. Furthermore, a three-stage Stackelberg game is formulated to model the interactions among the network operator, content service provider, and mobile users. Sub-game perfect equilibrium in each stage is analyzed by backward induction. The existence of Stackelberg equilibrium is validated by employing the bilevel optimization programming. Based on the game properties, we propose a sub-gradient based iterative algorithm, which ensures to converge to the Stackelberg equilibrium.


I. INTRODUCTION
Sponsored content in wireless networks has been introduced as a promising scheme to utilize a proper designed incentive mechanism to motivate mobile users to use more services and consume more contents, generating higher revenue to the mobile service ecosystem. For example, AT&T launched a sponsored data plan that allows content service providers to partly or fully pay for the data usages on behalf mobile users to the network operator, when the mobile users access the sponsored contents [1]. With the sponsored content scheme, mobile users as the end users of network content services can offload their data subscription fees to content service providers. Correspondingly, content service providers can potentially cooperate with network providers by sponsoring data usages to motivate mobile users to join the network [2]- [4].
In the meanwhile, edge caching is emerging in the context of 5G networks as a promising technique to deliver high quality content services at lower costs. The key idea is that the edge caching content service provider caches the content on edge devices of the network in advance. Mobile users who request for contents may access the contents directly at the edge devices, without costly remote content deliveries. With edge caching, mobile users may obtain content services via local connections, e.g., WiFi, such that no cellular data usage will be incurred. Therefore, edge caching can be viewed as an alternative sponsorship scheme for mobile users. Edge caching is seen as on of the most effective solutions to deal with highly explosive content traffic demands in 5G era. As a result, equipping caches at small base stations offers a promising way to exploit the potential of edge networks in addition to densifying the existing cellular networks.
In this work, we introduce the integration of the edge caching and sponsored content schemes. In particular, we investigate their interaction and their coexistence that affect the mobile user behavior, the network operator in the data/content traffic market. To sum up, the main contributions of this paper are summarized as follows: 1) We formulate a joint sponsored and edge caching content service market model to analyze the interactions among the wireless network operator, the sponsored content service provider as well as the edge caching content service provider, and mobile users. 2) We formulate a novel three-stage Stackelberg game to model their interactions to jointly maximize the payoff of the wireless network operator, the profit of each content service providers, and the utilities of mobile users. 3) Through backward induction, we analyze the sub-game perfect equilibrium in each stage analytically. Furthermore, the existence of the Stackelberg equilibrium is validated by capitalizing on the bilevel optimization technique. The rest of the paper is organized as follows. Section II presents the system description and Section III formulates a three-stage Stackelberg game to model the joint sponsored and edge caching content service market. The equilibrium analysis are shown in Section IV. Section V provides the performance evaluation. Section VI concludes the paper.

II. SYSTEM MODEL
We consider a market-oriented content delivery network consisting of four types of entities: a Wireless Network Operator (WNO), a Sponsored Content Service Provider (SCSP), an Edge Caching Content Service Provider (ECCSP), and a pool of Mobile Users (MUs). The MUs can access contents (e.g., video) from the SCSP and ECCSP. If an MU accesses contents from the SCSP, the contents can be downloaded directly through the network infrastructure provided by the WNO. In this case, the SCSP can sponsor for the data transfer from the WNO to the MU. In the mean time, the MU can also access contents stored in an edge caching device belonged to the ECCSP. The MU can download the contents from the device locally without involving the WNO. With the coexistence of both SCSP and ECCSP, the MU who requests for contents may autonomously choose the content source to lower down the content cost. The SCSP and ECCSP need to compete with each other to attract content demands from the users.
Let y denote the content (volume) demanded by MUs, and σ e f (y) denote the utility obtained from accessing and consuming the content, where the factor σ e > 0 represents the utility coefficient of MUs, e.g., a particular valuation between MUs and content. Similar to that in [5], we first define the following function: where 0 < α < 1 is a given coefficient. In particular, the function f (·) is non-decreasing and concave with decreasing marginal satisfaction, indicating the decreasing marginal preference of MUs to contents. In traditional wireless content access, the WNO charges each MU a price p for a unit volume of content downloaded. Thus, the general form of utility function of the MU with y content demand is given defined as v(y) = σ e f (y) − py.
With a sponsored content scheme, the payment from MUs to the WNO can be partly sponsored by the SCSP, as introduced in Section I. Denote θ ∈ [0, 1] as a sponsorship factor of content sponsored by the SCSP, i.e., θ units of the content is sponsored. Thus, the MU pays for the rest (1 − θ)y units of content to the WNO, with the cost (1 − θ)py incurred to the MU [2], [3]. Generally, the MUs are also affected by another variable l a which is the amount of advertisement imposed by the SCSP and ECCSP per volume of content. We assume that l a is constant for all contents. For example, Pandora Internet Radio plays advertisement at regular intervals between songs. We assume a normalized l a ∈ [0, 1] since both the ECCSP and SCSP have the amount of advertisements strictly less than that of the provided contents. For the ease of derivation later, we introduce an auxiliary variable τ defined as τ = 1 1+la , τ ∈ 1 2 , 1 . Thus, the utility of the MU which has the content demand y from the SCSP is expressed as u s (y) = τ σ e f (y) − (1 − θ)py.
An ECCSP is able to cache contents in the edge caching devices for MUs to access via a local network connection. We denote t ∈ [0, 1] as the caching effort of the ECCSP, which indicates the sponsorship from the ECCSP to MUs. When an MU access the cached content from the ECCSP, the advertisement from the ECCSP is imposed to the MU which lowers its utility. Nevertheless, accessing the cached content, the MU does not need to pay the WNO [6]. Accordingly, the utility of the MU which has demand z for the cached content from the ECCSP is expressed as u e (z) = τ σ e f (z)g(t) − cz, where c is the network handover cost. The caching effort t indicates the amount of resources (e.g., storage and bandwidth) allocated for delivering the cached content to the MUs. The function g(t) is defined as content delivery quality. In particular, g(t) is a monotonically increasing function with diminishing returns reflecting the positive influence of caching effort t on MUs' experience. Similar to (1), we adopt the a common function to capture the Quality of Service (QoS) experienced by MUs, i.e., where 0 < β < 1 is defined to be a coefficient.

III. GAME FORMULATION FOR JOINT SPONSORED AND EDGE CACHING CONTENT SERVICE MODEL
In this section, we formulate a three-stage Stackelberg game to model the interactions among the network participants (i.e., WNO, SCSP, ECCSP, and MUs). In the following Sections III-A, III-B and III-B2, we analyze the sub-game problems of each stage in the game.

A. Stage III: Mobile Users (Followers)
In the network, each MU may either choose to access the sponsored contents from the SCSP, or the cached contents provided by the ECCSP. The MU determines a fraction of the content demand to access from the SCSP denoted by x ∈ [0, 1]. The fraction of cached content demand from the ECCSP is thus 1 − x.
Each rational MU balances the content access between the SCSP and ECCSP to maximize its utility. The utility of the MU can be expressed as follows: (3) where f (x) and g(t) are defined in (1) and (2), respectively.
Each MU sub-game problem can be formulated as follows, given the volume unit price asked by the WNO, the sponsorship factor θ from the SCSP and the caching effort t from the ECCSP, the MU chooses x to maximize the utility:

B. Stage II: SCSP and ECCSP (2nd-Tier Players)
At this stage, the SCSP and ECCSP both determine their individual strategy simultaneously in a competitive manner, given the pricing strategy of the WNO.
1) Sponsored Content Service Provider: The SCSP aims to maximize the profit sponsoring, i.e., the gained advertisement revenue minus the cost of sponsorship provided for the MUs, as follows: where σ c is the advertisement revenue coefficient, and the term σ c h(x) denotes the advertisement revenue [5], in which h(x) is defined as follows: where 0 < γ < 1 which is a coefficient. Thus, the SCSP subgame is defined as follows: 2) Edge caching content service provider: As discussed in Section II, the cost incurred to the ECCSP for caching the content with caching effort t is denoted as Ct. The profit gained by the ECCSP, i.e., the advertisement revenue from content traffic minus the cost for content caching, is defined as follows: where h(·) is the same as defined in (6). We assume C to be a baseline content caching cost. The cost of the ECCSP for caching the content with caching effort t is thus Ct [6]- [8]. Accordingly, the profit maximization problem of the ECCSP is formulated as follows: C. Stage I: Wireless Network Operator (1st-Tier Player) The WNO sets the volume unit price p for data traffic. In addition to obtaining its revenue from charging the SCSP and MUs, the WNO also has the content delivery cost. Accordingly, the objective of the WNO is to maximize its payoff, expressed as follows: where wx 2 denotes the corresponding cost, and w represents the unit cost of content delivery. The quadratic sum form reflects the marginal cost increases as the total demand increases, e.g., due to congestion effects, which is a well-accepted assumption. The strategy space of the WNO is denoted as where p is the maximum price. As a result, the payoff maximization problem of the WNO is formulated as follows: Problems 1, 2-A, 2-B and 3 altogether form a three-stage Stackelberg game with the objective of finding the Stackelberg equilibrium. In the next section, the sub-game problems will be solved sequentially. The Stackelberg equilibrium will be investigated.

IV. GAME EQUILIBRIUM ANALYSIS
In this section, we sequentially solve the sub-game perfect equilibrium in each stage of Stackelberg game by employing backward induction. Specifically, we analyze the content demand of MUs in Stage III, the sponsoring strategy of the SCSP as well as the caching strategy of the ECCSP in Stage II, and the pricing strategy of the WNO in Stage I, respectively.

A. Stage III: MU's content demand
Given the unit content downloading price p charged by the WNO, sponsorship factor θ determined by the SCSP, as well as caching effort t determined by the ECCSP, respectively, the MUs determine optimal content demands for utility maximization individually in the sub-game G u . Thus, we analyze the sub-game G u by solving the Problem 1. By substituting f (·) as in (1) and g(·) as in (2) into (3), the utility of the MU with the decision variable x is obtained as follows: In the next step, the first order and second order derivatives of (16) with respect to x is taken to prove its concavity, as follows: As shown in (17), the second order derivative of u(·) is always negative. Therefore, the function u is strictly concave with respect to x. As the strategy space of x is already known to be a convex and compact subset of the Euclidean space, the following proposition can be concluded accordingly [9]. Proposition 1. The sub-game perfect equilibrium in the subgame G u is unique.
Furthermore, based on the first order derivative condition, we have and we can show that The following conclusions hold. x * = 1 given the best response of the MU is larger than 1; x * = 0 given the best response of the MU is less than 0. If the best response of the MU with respect to the content demand x * is within the strategy space [0, 1], the best response of the MU, i.e., x * , satisfies the condition in (20), i.e., B. Stage II: SCSP's sponsoring and ECCSP's caching strategy Given the sub-game equilibrium in G u obtained from the Stage III, the SCSP and ECCSP as 2nd-tier players optimize the sponsoring and caching strategies for profit maximization in a competitive manner, respectively. The optimal strategies of both the SCSP and ECCSP are obtained by solving the sub-game Problems 2-A and 2-B.
Firstly, we analyze the optimal sponsoring strategy of the SCSP. Based on (5), the profit obtained by the SCSP can be reformulated as follows: where x * is the best response of the MU. The first and second order derivatives of profit Π s (θ; p) with respect to the sponsorship factor θ are given as follows: and From the condition in (20), we obtain ∂x * ∂θ and ∂ 2 x * ∂θ 2 with simple steps, as shown in (12) and (13).
Likewise, we analyze the optimal caching strategy of the ECCSP. From (8), the profit obtained by the ECCSP can be expressed as follows: The first and second derivatives of profit Π e (t; p) with respect to caching effort t are given as follows: and From the condition in (20), we derive ∂x * ∂t and ∂ 2 x * ∂t 2 with simple steps, as shown in (14) and (15). By analyzing the profits of the SCSP and ECCSP given in (22) and (25), respectively, we have the following proposition.
Proposition 2. The existence of the Nash equilibrium in the non-cooperative sub-game G c is guaranteed if the following conditions and hold.
Proof. From (13), we can easily know that ∂ 2 x * ∂θ 2 < 0 under the condition in (29). Further, we have ∂x * ∂θ > 0 and ∂ 2 Πs(θ;p) Consequently, we can conclude that ∂ 2 Πs(θ;p) ∂θ 2 < 0 under the condition in (28). Then, we analyze the properties of ∂ 2 Πe(t;p) is negative, we need to prove that By substituting (14) and (15) into (31), and with simple steps, we have Accordingly, under the condition in (30), the inequality given in (32) is satisfied. Therefore, the negativity of ∂ 2 Πe(t;p) ∂t 2 is proven. Accordingly, the non-cooperative sub-game G c between the SCSP and ECCSP is a concave game, from which the existence of the Nash equilibrium in the sub-game G c follows.
Finally, we prove the uniqueness of the Nash equilibrium in the non-cooperative sub-game between the SCSP and ECCSP, as shown in the following proposition.

Proposition 3.
If there exists at least one Nash equilibrium in the non-cooperative sub-game G c , the Nash equilibrium is unique provided that the following condition holds.
Proof Sketch. We mainly prove that the Jacobian matrix of point-to-set mapping with respect to the profit profile of both the SCSP and ECCSP is negative definite. Consequently, ∇F is diagonally strictly concave, from which the uniqueness of the Nash equilibrium in the non-cooperative sub-game G c is guaranteed [9]. Please refer to [10] for more details.

C. Stage I: WNO's pricing strategy
In Stage I, the monopolist WNO determines the optimal price p * by solving the Problem 3 with the optimal sponsorship factor θ * as well as the optimal caching effort t * obtained at Stage II, and the optimal content demand x * obtained at Stage I. In this case, the Problem 3 can be reformulated as follows: The constraint in (35) applies for the strategy space of the WNO. The constraints in (36) and (37) indicate that θ * and t * denote the best responses of the SCSP and ECCSP, respectively, given the price p. The constraint in (38) is derived from the best response of the MU given θ, t and p, which represents the implicit function of x * (θ, t, p). The constraints in (39) and (40) ensure the existence and the uniqueness of the noncooperative sub-game G c , which are given in Proposition 3. Let X denote x * (θ, t, p) : D θ ⊗D t ⊗D p → D x , where ⊗ denotes the Cartesian product, D θ , D t and D p represent the domains of θ, t and p, respectively. Note that these domains are all close sets. Further, we define Π(θ, t, p) and g(θ, t, p) number. In addition, we define ρ = [θ; t] : D θ ⊗D t → D ρ . As a result, Problem 3 can be redefined as the bilevel programming problem, which is shown as follows: As shown in Section IV-B, we have proved the existence of a unique pair of θ * and t * for any given p as the optimal solution of Problem 2, i.e., the Nash equilibrium in non-cooperative sub-game G c . Accordingly, the optimal solution to the lowerlevel programming problem ρ * = [θ * ; t * ] exists and is unique, for any given p. Therefore, the strong sufficient optimality condition of second order (SSOSC) is satisfied for the bilevel programming problem in (41) because of the existence and the uniqueness of ρ * (Theorem 3.9 in [11]). This indicates that the optimal solution to the lower-level programming problem of the bilevel programming problem is strongly stable. Thus, our bilevel programming problem can be reduced to a single-level problem, which is expressed as follows: maximize 0<p<p P(p) = pX − wX 2 , subject to ρ = U (p).
(42) ρ = U (p) in the constraint can be obtained by using the KKT condition to the lower-level programming problem of the bilevel programming problem as follows: where λ denotes the Lagrangian multiplier vector. Moreover, the feasible domain of the single-level programming is defined as Ω(p, ρ) = { (p, ρ)| ρ = U (p), p ∈ D p }, which is a nonempty and closed set according to the Weierstrass Theorem [12]. Since we know that the optimal solution to the lower-level programming problem of the bilevel programming problem is unique, Constant Rank Constraint Qualification (CRCQ) and Mangasarian-Fromovitz Constraint Qualification (MFCQ) are satisfied by all the feasible points in Ω(p, ρ) (Theorem 3.9 in [11]). Based on Theorem 4.10 in [13], ρ = U (p) is a piecewise continuously differentiable function and (p, ρ) = (p, U (p)) is therefore continuous on p. Further, with the closed sets Ω(p, ρ) and D p , according to the well-known Closed Graph Theorem, we can conclude that ρ = U (p) being continuous implies that the mapping D p → Ω(p, ρ) is closed. Therefore, Ω(p, ρ) is non-empty and closed, and thus the bilevel programming problem admits a globally optimal solution, i.e., the Stackelberg equilibrium. Accordingly, we conclude with the following proposition.

Proposition 4.
There exists at least one Stackelberg equilibrium in the proposed three-stage Stackelberg game.
Each stage of the proposed three-stage Stackelberg game has been investigated so far. Similar to that in [14], we then present the sub-gradient based algorithm to obtain the Stackelberg equilibrium of the proposed game. The convergence property of the sub-gradient based iterative algorithm has been proved in [14].
Firstly, the impact of the price constraint on the WNO is investigated, as in Fig. 1. It is worth noting that the optimal price offered by the WNO is the same as the maximum price constraint. The intuition is that the lower price can attract the MU to consume more sponsored content from the SCSP, which may incur higher delivery cost maintained by the WNO. Thus, the WNO is reluctant to lower the offered price. In addition, we find that as the price constraint, i.e., the optimal price increases, the payoff of the WNO increases and the sponsored content demand of the MU decreases. This is because the WNO is able to set a higher price and extract more surplus from the MU, and achieves higher payoff consequently. Further, as expected, the payoff of the WNO decreases with the increase of w, i.e., the unit cost of content delivery.
We next study the impact of the utility coefficient of MUs on the players in the game model, as illustrated in Fig. 2. We find that the sponsored content demand of the MU decreases with the increase of σ e . This is because when σ e increases, the sponsorship fee from the SCSP becomes relative lower compared with the improved utility of the MU from consuming the content. Recall that the caching effort positively affects the utility of the MU from consuming the content, therefore, the sponsored content demand of the MU decreases. As a result, the SCSP wants to offer more sponsorship fee to attract the MU to consume the sponsored content, and the ECCSP has an incentive to lower its caching effort to reduce the caching cost. Once the sponsorship fee from the SCSP is large enough, the SCSP is not willing to offer more sponsorship fee to save its cost. Accordingly, the sponsorship fee from the SCSP increases first and then decreases. Therefore, the SCSP's profit decreases and the ECCSP's profit increases, which is consistent with the results in Fig. 2. Since the sponsored content demand of the MU decreases, and thus the payment from the MU to the WNO is reduced, which leads to the decrease of the WNO's payoff. As expected, we find that the sponsored content demand of the MU increases and the caching effort of the ECCSP decreases as the content caching cost C increases. This is due to the fact that, with the increase of C, the cost of the ECCSP for increasing caching effort becomes greater. In this case, the ECCSP is willing to reduce its caching effort for saving cost and thus compensate for its decreasing profit. Meanwhile, the SCSP wants to offer higher sponsorship fee to the MU for encouraging the MU's higher sponsored content demand. Consequently, both the SCSP's profit and the WNO's payoff increase. Moreover, from Fig. 2, we find that the increase of the advertisement length l a leads to the increase of the SCSP's profit and the WNO's payoff. This is because when l a increases, the utility of the MU from consuming the content decreases, and the offered sponsorship fee becomes significant for the MU. This encourages higher sponsored content demand of the MU, which benefits the SCSP and the WNO accordingly. Therefore, the profit of the ECCSP decreases because of its decreasing content traffic. Lastly, we examine the impact of the advertisement revenue coefficient σ c on the players in the game model, as illustrated in Fig. 3. We find that the profit of the SCSP, the profit of the ECCSP, and payoff of the WNO increases with the increase of σ c . This is because the advertisement revenue from increasing content traffic is improved as σ c increases. Thus, the profit of both the SCSP and ECCSP are improved. In this case, the SCSP and ECCSP are more willing to increase the sponsorship fee and caching effort, respectively, to attract more demand from the MU. Recall that the optimal price is equal to the price constraint. As the price is fixed, with the increase of σ c , the SCSP has an incentive to offer a higher sponsorship fee to the MU since its cost becomes insignificant compared with the increasing advertisement revenue coefficient. Thus, the sponsored content demand of the MU increases, which leads to the increase of the WNO's payoff consequently. By comparing curves with different value of handover cost c, we find that the decrease of c leads to the decrease of the sponsored content demand, the SCSP's profit and the WNO's payoff. This is due to the fact that the MU is reluctant to choose the cached content from the ECCSP when the handover cost is high. Consequently, the MU is more willing to access and consume the content from the SCSP using. Due to the increasing content traffic, the WNO's payoff is improved accordingly. Utilizing this fact, the SCSP also has an incentive to reduce its sponsorship fee for saving the cost and achieving higher profit. However, the ECCSP needs to increase its caching effort to compensate for the higher handover cost. Therefore, the profit of the ECCSP decreases as shown in Fig. 3.

VI. CONCLUSION
In this work, we have considered a three-stage Stackelberg game based market model for a joint sponsored and edge caching content service. The model describes the interactions among the wireless operator, the sponsored content provider, and the edge provider. The analytical form of the subgame perfect equilibrium in each stage has been analyzed by backward induction. We have also validated the existence of the Stackelberg equilibrium by capitalizing on the bilevel optimization technique. Furthermore, a sub-gradient based iterative algorithm has been proposed, which converges to the Stackelberg equilibrium with certainty. Numerical results have been proposed to evaluate the performance of all the game participants. Further studies of this work will focus on the social interactions among the users such as [15], or the dynamic pricing scheme such as [16] in the context of sponsored content.