<figure><img src="image_1.png" /></figure>

HAL
open science

# Strategic Resource Pricing and Allocation in a 5G Network Slicing Stackelberg Game

Mandar Datar, Eitan Altman, Hélène Le Cadre

► To cite this version:

Mandar Datar, Eitan Altman, Hélène Le Cadre. Strategic Resource Pricing and Allocation in a 5G Network Slicing Stackelberg Game. IEEE Transactions on Network and Service Management, 2023, 20 (1), pp.1932–4537. 10.1109/TNSM.2022.3216588. hal-03824540v3

HAL Id: hal-03824540

https://inria.hal.science/hal-03824540v3

Submitted on 21 Oct 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Strategic Resource Pricing and Allocation in a 5G Network Slicing Stackelberg Game

Mandar Datar*†, Eitan Altman*†§, Hélène Le Cadre¶

*Inria Sophia Antipolis - Méditerranée †CERI/LIA, University of Avignon, Avignon, France

§LINCS Lab, Paris ¶Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189 - CRISTAL, F-59000 Lille, France

**Abstract**—We consider a marketplace in the context of 5G network slicing, where Application Service Providers (ASP), i.e., slice tenants, providing heterogeneous services, are in competition for the access to the virtualized network resource owned by a Network Slice Provider (NSP), who relies on network slicing. We model the interactions between the end users (followers) and the ASPs (leaders) as a Stackelberg game. We prove that the competition between the ASPs results in a multi-resource Tullock rent-seeking game. To determine resource pricing and allocation, we devise two innovative market mechanisms. First, we assume that the ASPs are pre-assigned with fixed shares (budgets) of infrastructure, and rely on a trading post mechanism to allocate the resource. Under this mechanism, the ASPs can redistribute their budgets in bids and customise their allocations to maximize their profits. In case a single resource is considered, we prove that the ASPs' coupled decision problems give rise to a unique Nash equilibrium. Second, when ASPs have no bound on their budget, we formulate the problem as a pricing game with coupling constraints capturing the shared resource finite capacities, and derive the market prices as the duals of the coupling constraints. In addition, we prove that the pricing game admits a unique variational equilibrium. We implement two online learning algorithms to compute solutions of the market mechanisms. A third fully distributed algorithm based on a proximal method is proposed to compute the Variational equilibrium solution of the pricing game. Finally, we run numerical simulations to analyse the market mechanism's economic properties and the convergence rates of the algorithms.

**Index Terms**—Communication service market, Game theory, Trading post mechanism, Pricing, 5G network slicing, Resource allocation.

## I. INTRODUCTION

Next-generation wireless network is expected to deliver support to emerging sectors like Virtual Reality (VR) live broadcast, automotive, healthcare, manufacturing, etc. Critical challenges in mobile network applicability to the sectors mentioned above are their heterogeneity and conflicting communications needs, the current monolithic network is insufficient to meet. Several new concepts have been proposed for the upcoming 5G network design to satisfy these critical needs. Probably one of the most important one is “network slicing”.

Network slicing is the concept of running multiple independent logical networks (slices) on top of a common shared physical infrastructure. Each independent logical network (slice)

is then explicitly dedicated to meeting each slice tenant's needs, contrary to the “one-size-fits-all” approach that was the mainstream allocation method in the previous mobile generations [2]. Network slicing brings a paradigm shift towards a multi-tenancy ecosystem where multiple tenants, owning individual slices, negotiate with multiple virtualized infrastructure network providers, i.e., NSPs, to request resources for service provision. In this competitive multi-agent setting, the Application Service Providers (ASPs), also called slice tenants, generally express a demand for a dedicated virtual network with full ownership of their Service Level Agreement (SLA). On the contrary, NSPs aim to maximize their return on investment by enabling the dynamic sharing of the infrastructure, as this lowers their operational and capital costs and allows them to monetize their infrastructure to its fullest potential. However, the infrastructure sharing may expose the tenants to the risk of violating their SLAs. Hence, one of the fundamental issues in network slicing is an efficient sharing of the network resources, which arbitrages between two conflicting interests, i.e., inter-slice isolation and efficient network resource utilization. In order to balance the inter-slice isolation and efficient resource utilization, Caballero et al. in [3] proposed the “Share-Constrained Proportional Allocation” (SCPA) scheme where each slice is pre-assigned with a fixed share (budget) of infrastructure. Slices are then allowed to redistribute their shares and customize their allocation according to the load dynamics. In turn, NSP allocates each resource to slices in proportion to their shares on that resource. This approach allows a dynamic sharing, where tenants can redistribute their network share based on the load dynamics. At the same time, it provides the slice tenants a degree of protection by keeping the pre-assigned share intact.

Game-theoretic models have been employed for strategic resource allocation in communication networks, power systems, and more generally, a large number of deregulated industries. When dealing with strategic resource allocation, each player's utility function depends on its own decision variables, and on that of the other players. The players' feasibility sets can also be coupled through some global and local coupling constraints, capturing the laws of physics or, simply, shared capacity constraints. Extending duality results from standard continuous optimization to non-cooperative games, the dual variables of the coupling constraints can be interpreted as market prices, also called shadow prices or locational marginal prices, capturing the state of the network, e.g., congestion. Applying a similar model to dynamic resource trading in a
5G network, we design a new communication service market where the NSP charges dynamically the ASPs, depending on how much they contribute to the infrastructure utilization. The market prices are locational, being differentiated by cell and resource. From this literature, this approach seems promising regarding ASPs' cost reduction, as analysed in [4] that considers a service market where dynamic market prices are adjusted according to supply and demand (im)balances.

Relying on network slicing, we consider a market design where a set of ASPs lease their respective networks from a NSP and employ a network slicing mechanism to request resources required for their service provision. Network Slice Providers (NSPs) can be either Mobile Network Operators (MNOs), owning their own spectrum, or Mobile Virtual Network Operators (MVNOs). They rely on network slicing to allocate resources based on priorities (Quality of Services). We assume that the ASPs offer dedicated services to their users, and the resource inventory available with ASPs characterizes their service performance. The users are free to choose their ASPs. Their decisions are made based on the service satisfaction attained from ASPs. Furthermore, the ASPs collect revenue by providing services to their customers. Assuming a dynamic resource sharing mechanism and that ASPs maximize their utilities, it is highly expected that selfish ASPs may exhibit strategic behaviour. For example, they might strategically distribute their shares on the resources conditioned on the trade-off between the Quality of Service (QoS) they want to offer and the congestion perceived by the users. In this work, we focus on: 1) building a game-theoretic model of the communication service market where ASPs negotiate with NSP to request resources and compete with one another to serve a pool of end users; 2) developing a dynamic resource allocation and pricing mechanism under a competitive environment.

## A. Related Work

There is a large part of the literature dedicated to the design of communication service markets. Broadly, communication service markets have been studied as a two-stage non-cooperative game involving four categories of agents: Infrastructure network Provider (InP), Network Slice Providers (NSP)<fnref n="1" />, Application Service Provider (ASP) and End Users (EU). We focus on ASPs who allow the EUs to access applications (identically called services in the rest of the paper) by connecting to slices which are built on top of the resources bought from an NSP [5]. At the upper level of the game, ASPs (buyers) lease the resources from the NSPs (sellers), negotiating for resource prices and quantities. At the lower level, ASPs (buyers) use the acquired resources from NSPs to offer a certain service to their EUs (buyers). At this level, ASPs decide on their service price and their resource schedule, while EUs make their subscription decisions. In [6], ASPs' strategic service pricing has been analyzed as a Cournot game.

In [7], Korcak et al. considered that the Quality of Service (QoS) achieved by the ASP's users depends on the number

of subscribers of that ASP, and users' choice behaviour can be analyzed relying on Evolutionary Game Theory (EGT). Li et al. in [8] integrated both the users' choice evolution and the ASPs pricing scheme. They formulated the resulting problem as a Stackelberg game. The ASPs, interpreted as leaders, strategically decide the price to attract the users, and the users, seen as followers choose the ASPs to maximize their service satisfaction level. Also, the number of subscribers of the ASPs depends on the perceived QoS and, consequently, on their resources availability. Focusing on competitive aspects, the ASPs can act strategically when computing their resource demand, giving rise to a simultaneous non-cooperative game [9]. In [10], D'Oro et al. used a similar Stackelberg game formulation for resource allocation and scheduling in the network functions virtualization scenario. In [11], Azouzi et al. considered that the competition between ASPs takes place both in prices and in QoS. In practice, ASPs may not have complete information about the other ASPs' resources. Dealing with such an incomplete information setting, Li et al. in [12] studied ASPs' pricing strategies relying on a Bayesian game formulation, where ASPs compute their prices based on their beliefs about the resource availability. Li et al. also considered the possibility that the ASPs can coordinate and analysed the impact of ASPs coordination on the pricing scheme.

In [13], Xi et al. proposed a dynamic resource polling and trading mechanism for network virtualization relying on Stackelberg game, where the carrier is considered as the leader while the users are the followers. The techno-economic interaction of NSPs and ASPs is modelled as a multi-leader multi-follower Stackelberg game in [14] in their proposed model, NSPs act as leaders who decide the price per unit of cell capacity, while ASPs act as followers who select an NSP which maximizes its profit. In [15], Ho et al. proposed a two-stage Stackelberg game based dynamic pricing for resource allocation in wireless network virtualization, where the NSP aims to maximize its revenue by leasing the bandwidth to the Mobile Virtual Network Operator (MVNO); on the contrary, MVNOs want to minimize their costs while serving their users at the best performance. In [16], Hu et al. considered an Orthogonal Frequency Division Multiple Access (OFDMA) system consisting of an NSP, multiple MVNOs and downlink users. They formulated the resource allocation in a radio access network slicing as a tri-level Stackelberg game. In [17], Tran et al. discussed the resource allocation and pricing problem for network slicing as a multi-leader multi-follower Stackelberg game that captures the interactions among access and backhaul ASPs, and their end users.

In [18], Kazmi et, al. modelled the service selection and resource purchasing problem as a two-stage combinatorial optimization problem and solved it using a hierarchical matching game-based scheme, where matching between user and ASPs is performed at the low level, while matching between ASPs and NSP takes place at the upper level. In [19], Raveendran et al. proposed a cyclic three-sided matching game-based wireless resource allocation mechanism for slicing. In their proposed mechanism, allocation is performed by matching between radio resources, physical infrastructure, and mobile users. In [20], Lotfi et al. studied the economics of competition

<footnote n="1">¹In many articles, the terms Mobile Network Operators (MNOs), Mobile Service Providers (MSPs) and slice providers are used synonymously.</footnote>
and cooperation between NSPs and ASPs using a sequential game that they solve by computing a Subgame Perfect Nash Equilibrium (SPNE).

On the contrary, the literature devoted to multi-resource allocation with finite budget agents is rather limited, to the extent of our knowledge. In [21], Nguyen et al. modeled edge computing resource allocation problem for service as a Fisher market. In the same vein, Moro et al. in [22] formulated a resource allocation problem for 5G network slicing as Fisher market, wherein apart from edge resources like computation and memory, authors also included radio resource. Although [21], [22] deal with multi-resource service provisioning with budget constraints similarly to us, their utility functions do not describe economic quantities such as profits and costs.

<table><caption>TABLE I
LITERATURE REVIEW AND RESEARCH CONTRIBUTION POSITIONING.</caption><thead><tr><th>Article</th><th>Network Share (Budget)</th><th>Resources</th><th>Model</th></tr></thead><tbody><tr><td>[13], [14], [15], [16], [17]<br>This Work</td><td>Non-Fixed</td><td>Single type</td><td>Stackelberg game</td></tr><tr><td></td><td>Fixed and Non-Fixed</td><td>Multi-type</td><td>Coupled constraint<br>Stackelberg game</td></tr><tr><td>[4]</td><td>Non-Fixed</td><td>Single type</td><td>Potential game</td></tr><tr><td>[23][18][19]</td><td>Non-Fixed</td><td>Single type</td><td>Matching game</td></tr><tr><td>[24]</td><td>Fixed</td><td>Single type</td><td>Orthogonal<br>constraint game</td></tr></tbody></table>

In all the above works, the ASPs lease the resources from the NSP and compete to serve EUs, which is also the case in our work. However, our work innovates in that the resources are shared using a slice-based dynamic sharing mechanism. Moreover, in our case, resources are spatially distributed, and service offered in a particular cell can only be supported by the resources available within that cell. In communication networks, one of the well-known scheme for resource allocation is the auction-based allocation [25], e.g., Kelly's mechanism. Datar et al. in [26], as well as Tun et al. in [27], proposed multi-bidding Kelly's mechanism-based resource allocation for 5G slicing. They showed that Kelly's mechanism leads to a fair and efficient resource allocation both at slices and EUs levels. Our work departs from the auction-based mechanism like [26]–[27], where agents' bids are unbounded.

In follow up work to [3], Zheng et al. in [28] studied network slicing under stochastic loads and applied SCPA. They modeled the resource sharing scheme as a non-cooperative game and proved that slices achieve efficient statistical multiplexing at Nash equilibrium. Guijarro et al. in [24] designed a communication service market where ASPs employ the SCPA mechanism to request resources from NSP. They analyzed the economic impact of network slicing on the market. In [4], an automated negotiation mechanism is defined relying on an aggregative game that enables the slice tenants to dynamically trade radio resources and customize their slices on instantaneous demands, which help tenants achieve higher profits. Our paper is closely related to [24]. The main novelty of our work lies in the fact that we consider multi-resource service provisioning, contrary to most articles dealing with communication service market design, which, to the best of our knowledge, only deals

with radio resources. Moreover, in this work, we consider a more realistic scenario where the service providers own finite budgets to procure their resources. This makes resource allocation and pricing more challenging than most work in the literature, where resource distribution and pricing depend on the agents' marginal utilities. The positioning of our work contribution is described in Table I.

In our paper, we leveraged the Tullock Contest (TC) framework [29] to model the competition between slices. This framework has been extensively used in the communication network literature, to model the interactions between competitive agents. To mention a few, in [30], the competition between social media users for visibility over the timeline was modeled as a TC. Luo et al. in [31] proposed a TC based incentive mechanism for crowdsourcing. The TC framework has been applied to the multipath TCP network utility maximization problem [32]. In [33], Altman et al. studied the multi-cryptocurrency blockchain from a game-theoretic perspective, where the competition between the miners is framed as a TC. To the best of our knowledge, the theoretical results on the TC framework and its applications in literature only deal with a single resource case. We extend the TC framework to a multi-resource scenario, and thus our results also contribute to the theoretical literature on the TC framework.

We list below the key contributions of our article.

## B. Main Contributions

1) We model the interactions between the ASPs and the EUs as a Stackelberg game, where the ASPs act as leaders and the EUs as followers. Besides, we rely on replicator dynamics to model the latter's supplier choice and determine the ASP's market shares in closed form expression relying on EGT.

2) We extend the study on Tullock-rent seeking games by showing that the non-cooperative game induced by the competition between ASPs admits a unique Nash equilibrium (NE).

3) We design an innovative communication service market relying on the solving of a generalized Nash equilibrium problem, where ASPs are charged depending on how much they contribute to the infrastructure utilization. The economic performance of this innovative market is compared to benchmark post trading mechanisms with finite budget constraints.

4) Finally, we provide two online learning algorithms and a fully distributed proximal based algorithm, new to our application field, to reach the NE and the Variational equilibrium solutions of the post trading mechanism and generalized Nash equilibrium problem respectively. Numerically, we observe that the proximal method significantly outperforms the online learning benchmark algorithms in terms of scalability and convergence rates.

The rest of the paper is organised as follows: Section II introduces the system model. Section III details the game-theoretic model of competition between the ASPs. In Section IV, we describe the Stackelberg game between the ASPs and the EUs. In Section V, we analyse the existence and uniqueness
<figure><img src="image_3.png" /><figcaption>Fig. 1. The ASPs lease the resources from a NSP at different locations and compete to offer heterogeneous services to the end users.</figcaption></figure>

of the NE. Section VI introduces the resource pricing and market equilibrium. In Section VII, we provide two (semi-decentralized) online learning algorithms and a fully distributed algorithm to compute market equilibria. In Section VII, we report on numerical results. A concluding section ends the paper.

## II. SYSTEM MODEL

We consider a market design, where at the upper level, a set of ASPs, $S$, leases some resources from a NSP to create one or more slices to provide different heterogeneous vertical applications (services). The NSPs lease the physical resources from Infrastructure network Providers (InPs) to form their own softwareized network, which can then be used to tailor slices to a host of application services (vertical services) demanded by the ASPs. For example, an ASP can lease some resources from NSP in the form of two slices, one for ultra-reliable low latency communications applications and another for enhanced mobile broadband applications. Each slice created by NSPs can be either managed by themselves or through third-party application service providers (ASP). If NSPs manage some of their own created slices and provide direct service to end users, they act as both NSPs and ASPs simultaneously. At the lower level, the ASPs (sellers) use the leased resources and compete to attract the maximum number of end-users (buyers). Specifically, we assume that the NSP owns a network that consists of a set of base stations or cells, $C$. Each base station at different locations accommodates multiple types of resources such as bandwidth, CPU, memory, etc. Users are spread across the network. Let $N^c$ be the number of users present in cell $c$. We assume that the service offered by the ASP in a particular cell can only be supported by the resources available within that cell. The system model is depicted in Fig. 1.

**Notation:** Let $\mathbb{R}^n$ indicate the set of $n$ dimension real vectors, and $\mathbb{R}^n_+$ its nonnegative orthant. $\|\cdot\|$ represents the Euclidean norm. Given a vector $x$, $x^T$ denotes its transpose. Let $\text{col}(x_1, ..., x_N) := [x_1^T, ..., x_N^T]$. For a closed set $\mathcal{F} \subseteq \mathbb{R}^n$, the mapping $\text{proj}_{\mathcal{F}} : \mathbb{R}^n \to \mathcal{F}$ denotes the projection onto

<table><caption>TABLE II
MAIN NOTATIONS USED THROUGHOUT THE PAPER</caption><tr><td>C := {1, ..., C}</td><td>≡</td><td>Set of base stations or cells</td></tr><tr><td>S := {1, ..., S}</td><td>≡</td><td>Set of ASPs</td></tr><tr><td>K := {1, ..., K}</td><td>≡</td><td>Set of services available</td></tr><tr><td>M<sup>c</sup></td><td>≡</td><td>Set of resources at base station c</td></tr><tr><td>N<sub>k</sub><sup>c</sup></td><td>≡</td><td>Number of users demanding service k in cell c</td></tr><tr><td>ν<sub>sk</sub><sup>c</sup></td><td>≡</td><td>Utility of service type k user associated with ASP s in cell c</td></tr><tr><td>q<sub>sk</sub><sup>c</sup></td><td>≡</td><td>Quality of service k offered by ASP s in cell c</td></tr><tr><td>n<sub>sk</sub><sup>c</sup></td><td>≡</td><td>Number (subscribers) users form service k associated with ASP s in cell c</td></tr><tr><td>d<sub>s</sub><sup>c</sup> := (d<sub>sm</sub><sup>c</sup>)<sub>m∈M<sup>c</sup></sub></td><td>≡</td><td>Bundle of resources available with ASP s in cell c</td></tr><tr><td>d<sub>sm</sub><sup>c</sup></td><td>≡</td><td>Amount of resource type m available with ASP s in cell c</td></tr><tr><td>D<sub>m</sub><sup>c</sup></td><td>≡</td><td>Capacity of resource type m at base station c</td></tr><tr><td>ω<sub>m</sub><sup>c</sup></td><td>≡</td><td>Price per unit resource of type m at base station c</td></tr><tr><td>p<sub>sk</sub></td><td>≡</td><td>Service fees charge by ASP s for service k to users</td></tr><tr><td>R<sub>s</sub>(.)</td><td>≡</td><td>ASP s expected revenue</td></tr><tr><td>U<sub>s</sub>(.)</td><td>≡</td><td>ASP s profit</td></tr><tr><td>B<sub>s</sub></td><td>≡</td><td>Budget available with ASP s</td></tr><tr><td>I</td><td>≡</td><td>Set of coupling constraints</td></tr><tr><td>(g<sub>i</sub>(.))<sub>i∈I</sub></td><td>≡</td><td>Coupling constraint functions</td></tr><tr><td>τ<sub>s,s'</sub><sup>c</sup> (n<sup>c</sup>, U<sup>c</sup>)</td><td>≡</td><td>Revision protocol which defines the switching rate at which users in cell c switch their choice from ASP s to ASP s'</td></tr><tr><td>A<sub>s</sub></td><td>≡</td><td>Slice association probability function</td></tr><tr><td>f<sub>s</sub><sup>c</sup>(.)</td><td>≡</td><td>term in A<sub>s</sub> signifying total utility experience by the potential subscribers of ASP s</td></tr><tr><td>b<sub>sm</sub><sup>c</sup></td><td>≡</td><td>Bid of ASP s to resource m at cell c</td></tr><tr><td>λ<sub>sm</sub><sup>c</sup></td><td>≡</td><td>Lagrange multipliers of the capacity based coupling constraints</td></tr><tr><td>r<sub>s</sub></td><td>≡</td><td>Ratio of the coupling constraint dual variable at r-normalized Nash equilibrium (λ<sub>nr</sub><sup>c</sup>) over dual variable evaluated by ASP s (λ<sub>sm</sub><sup>c</sup>)</td></tr><tr><td>y<sub>s</sub></td><td>≡</td><td>Auxiliary variable which accumulates discounted gradient for ASP s</td></tr><tr><td>α<sub>n</sub></td><td>≡</td><td>Discounting factor or step size</td></tr><tr><td>h<sub>s</sub>(.)</td><td>≡</td><td>Regularization function or a penalty function</td></tr><tr><td>ζ</td><td>≡</td><td>Vanilla ADMM penalty term</td></tr><tr><td>β</td><td>≡</td><td>Proximal approximation penalty term</td></tr></table>

$\mathcal{F}$, i.e., $\text{proj}_{\mathcal{F}}(x) := \arg \min_{y \in \mathcal{F}} \|y - x\|$. Depending on the context, $|\cdot|$ will denote the absolute value of a scalar or the cardinal of a set. Table II summarizes the main notation used in the paper.

### A. User Model

We assume that the users might need different categories of services, e.g., Virtual Reality (VR) service, online gaming, autonomous driving, etc. To balance their demand, they have to subscribe to one of the ASPs. Let $\mathcal{K}$ denote the set of all the services that are available to the users. $N_k^c$ represents the number of users who need service type k in cell c; vector
$[N_1^c...N_K^c]$ denotes the distribution of users in cell $c$ for each of the $K$ services.

We consider that each user is opportunistic and free to switch from one ASP to another, which is equivalent to choosing one slice among the set of available slices providing the same application at its base station. The user chooses the slice (or, equivalently, the ASP) that offers the better trade-off, i.e., the higher QoS at the lowest price. We model the utility of each user of service type $k$ served by ASP $s \in S$ in cell $c$ as [12]

$$ \nu_{sk}^c(n_{sk}^c, q_{sk}^c, p_{sk}) = \log \left( \frac{q_{sk}^c}{n_{sk}^c} \right) - p_{sk}, \quad (1) $$

where $q_{sk}^c$ is the QoS for service type $k$ provided by ASP $s$ in cell $c$, $n_{sk}^c$ is number of service type $k$ users connected to ASP $s$, while $p_{sk}$ is the subscription fees charged by ASP $s$ for its service $k$. We assume that the service fees charged by each ASP is the same across all cells. The use of a logarithmic$^2$ (concave) function in QoS to model the user's utility means that the users' satisfaction level saturates as the QoS increases, which is coherent with the economic principle of diminishing marginal returns. In turn, the ASP QoS depends on its resources inventory availability. We assume that each ASP applies a scheduling policy to distribute its resources among the users, in order to achieve equal QoS among them, in the long run.

**Remark 1.** In the user's utility function (1), $p_{sk}$ can be broadly interpreted as the service fee charged by any ASP $s \in S$, for any service $k \in K$. This constant term might also cover other costs, like the entry cost or the switching cost that the ASPs might charge the users for churning from one supplier to another. In sophisticated formulations, the service price could be non linear and defined through some convex functions.

## B. Application Service Provider Model

We suppose that the ASPs offer different types of services to the users and let $K_s$ denote the set of the services provided by each ASP $s$ to the users, and for each service type, ASPs operate through a separate slice. The ASPs aim to maximize their number of subscriber $n_s^c = [n_{s1}^c...n_{sK}^c]$, by attracting users with a better QoS and lower price. We assume that the QoS provided by each ASPs depends on the resource inventory available at the slice and is defined according to the relationship $q_{sk}^c \triangleq q_{sk}^c(d_{sk}^c)$. Let $d_{ks}^c \triangleq (d_{sm}^c)_{m \in M^c}$ denote a bundle of resources available with ASPs $s$. $d_{skm}^c$ captures the amount of resource type $m$ acquired by ASP $s$ for slice $k$ at cell $c$. We assume that for all $c \in C$, $k \in K$ and $s \in S$, the function $q_{sk}^c(d_{sk}^c)$ is concave non decreasing in $d_{sk}^c$. This assumption is classical in economics, reflecting the principle of diminishing marginal returns.

Each ASP $s \in S$ collects revenue from the fees paid by its subscribers. The expected revenue of ASP $s$ over the network

is defined as

$$ R_s = \left( \sum_{c \in C} \sum_{k \in K} p_{sk} n_{sk}^c \right). \quad (2) $$

Each ASP needs to pay for the resources it leases from the NSP. Let $\omega_m^c$ be the price per unit of resource of type $m$ charged by the NSP, at base station $c$. Let $d_{s,m}^c = \sum_{k \in K} d_{skm}^c$ denotes total amount of resource of type $m$ allocated to ASPs $s$ at cell $c$

The total cost each ASP $s$ needs to pay to the NSP for resource activation is therefore $\sum_{c \in C} \sum_{m \in M^c} \omega_m^c d_{s,m}^c$. We define the profit gained by ASPs as a quasi linear utility function

$$ U_s = R_s - \sum_{c \in C} \sum_{m \in M^c} \omega_m^c d_{s,m}^c. \quad (3) $$

Depending on the ASPs's budgets, we consider two possible cases in the following.

**In Case I**, we assume that each ASP $s$ has a finite budget $B_s$, which captures the market (purchasing) power of the ASP. Another relevant interpretation in the context of network slicing is that it represents the ASP's priority or a fixed share of the available resource pool, such that $\sum_{s \in S} B_s = 1$. In this case, each ASP $s$ must satisfy $\sum_{c \in C} \sum_{m \in M^c} \omega_m^c d_{s,m}^c = B_s$. This budget constraint makes ASP $s$'s decision variables coupled over the cells $c \in C$. As a result, **Case I** can not be decomposed over each cell.

**In Case II**, we assume that ASP $s$ has no bound over its budget. Its strategy set is defined as the set of vectors $d_s$ such that $d_{s,m}^c \ge 0, \forall m \in M^c, \forall c \in C$. A set $\mathcal{I}$ of additional linear coupling constraints can be included in the form $g_i(d) \le 0, \forall i \in \mathcal{I}$. Note that contrary to **Case I**, **Case II** can be decomposed over each cell.

## C. Resource Allocation and Pricing Problem

In this section, we discuss the central problem that we address in this paper. We observe from equation (2) that if an ASP wants to increase its market share, it needs to propose to EUs the best QoS at the lowest price. Indeed, at the lower level, EUs will choose to subscribe to the ASP that provides the best QoS and lowest price. The resource inventory available with the ASP characterizes their service performance: larger resources availability with the ASP guarantees a better QoS. However, the resources available with the NSP are limited, resulting in double-sided competitive interactions between the ASPs: one side of the interactions captures the competition for service provision, while the other side represents the competition for resource procurement. Undoubtedly, allocating and pricing resources in such a double-sided competitive environment is a significantly challenging task. In this work, our primary focus is on designing a resource pricing and allocation mechanism for the communication marketplace, which maximizes the network resources utilization and assigns slice tenants with their favourite bundle. In the next section, we model the interactions between users, ASPs and NSP as a generalized Stackelberg game involving coupling constraints at the lower level.

<footnote>$^2$The choice of a logarithm function captures the fact that the ASPs achieve a proportional fair allocation between the users in the long run.</footnote>
### III. GAME THEORETIC MODEL

We assume that each user is utility-maximizer and selfish, and takes decisions to maximize its profit. From (1), we observe that the utility of each user depends on the total number of users of the ASP. On the one hand, as the number of users connected to the ASP increases, the utility of the user decreases. Therefore, the decision made by each user is also influenced by decisions taken by the other users. On the other hand, ASPs maximize their revenues by attracting the maximum number of users. Naturally, each ASP anticipates the users' behaviour while computing their strategy. Therefore, it is highly expected that users and ASPs exhibit strategic behaviors. In our work, the ASPs take selfish decisions while anticipating the rational reactions of the users. We model the interactions between the users and the ASPs as a generalized Stackelberg game, where the ASPs act as leaders while users react rationally as followers, computing their best responses to the signal sent by the ASPs. In the first stage, ASPs compete in terms of QoS to attract the maximum number of users. In the second stage, users optimally select their ASPs to maximize their utility given prices and QoS offered by ASPs.

In classical game theory, Nash equilibrium is the most popular solution concept to analyze non-cooperative game solutions. This concept is based on the assumptions that each player has an exact knowledge about all other players' strategies at the equilibrium, and no player has an incentive to deviate from its own strategy at equilibrium. In many cases, knowing the exact information about all other players equilibrium strategies is a strong assumption, particularly when there are many users, and information about the strategy profile of all opponents is rarely perfectly known. In light of these limitations, we model the interactions between the users as a population game that extends the formulation of a non-cooperative game by incorporating the notion of population.

#### A. Multi-Population Game $\mathcal{E}$ Among Users

The population game provides an alternative to the classical equilibrium approach by involving a dynamic model. Unlike a single-play game or repeated games where all agents take their decisions simultaneously and repetitions occur at regular time periods, in a population game, each agent revises its decision sporadically, and the decision made by the revising agent only depends on the current system state and available payoff opportunities. Now for each cell $c$, and each service type $k$ we define the population game $\mathcal{E}_k^c$ as presented in the Fig. 2

* Population: set of users requesting service type $k$, $N_k^c := \{1...N_k^c\}$ in cell $c$.

* Strategy: it is the choice of ASP $s \in S$ that each user in cell $c$ opts to join.

* Utility: the utility achieved by each user of ASP $s \in S$ with service type $k$ is equal to $\nu_{sk}^c$.

**Remark 2.** To simplify the notation and because the problem is decomposable over the set of services, we remove the subscript

$k$, used for denoting service type $k$, from the mathematical analyses in the rest of the paper (unless explicitly specified).

In a population game, each agent revises its decision occasionally after some random duration of time. Whenever an agent reconsiders its decision, it depends on the system state and payoff opportunity available at that time. A general model of decision of the game is based on the concept of revision protocol. It is a mapping that translates the current population state (i.e., distribution of user) and available payoff (i.e., utilities (1)) into a switching rate which determines when users might update their choice of provider. Let $\tau_{s,s'}^c(n^c, U^c)$ be the revision protocol which defines the switching rate at which users switch their choice from ASP $s$ to ASP $s'$, given population state $n^c = [n_1^c...n_S^c]$ and utility vector $\nu^c = [\nu_1^c...\nu_S^c]$. Let $\mathbb{N}^c = \{n^c | \sum_{s \in S} n_s^c = N^c\}$ define the set of all possible population states. Population game $\mathcal{E}$ with revision protocol $\tau$ generates a continuous time evolutionary process on set $\mathbb{N}^c$ defined as

$$ \dot{n}_s^c = \sum_{s'} n_{s'}^c \tau_{s',s}^c - n_s^c \sum_{s'} \tau_{s,s'}^c. \quad (4) $$

The first-term in the right-hand side of equation (4) measures the rate at which users connect to ASP $s$. The second term measures the rate at which the portion of the population connected to ASP $s$ disconnects. A different choice of revision protocol results in a different dynamics. In this work, we assume that the users follow the pairwise proportional imitation behavior, e.g., after every random interval of time, each user interacts with its opponents (i.e., other users), and only if users meet an opponent with a higher utility than its own, it imitates the opponent with a probability proportional to the utility difference. The switching rate at which users in cell $c$ switch from ASP $s$ to ASP $s'$ takes the form

$$ \tau_{s,s'}^c = \frac{n_{s'}^c}{N^c} [\nu_{s'}^c - \nu_s^c]_+. \quad (5) $$

After replacing $\tau_{s,s'}^c$ in (4) with (5) and after some analytical calculations detailed in Appendix C we get the replicator dynamics

$$ \dot{n}_s^c = n_s^c \left[ \nu_s^c - \frac{1}{N^c} \sum_{s'} n_{s'}^c \nu_{s'}^c \right]. \quad (6) $$

An Evolutionarily Stable Strategy (ESS) characterizes the equilibrium solution concept for population games. Once the evolutionary process reaches an ESS, the population state will not change. It is defined as the fixed point of the dynamical system defined through equation (4).

**Proposition 1.** For all $c \in C$ and for any bundle of resources available with ASP $s$, the replicator equation (6) admits a unique evolutionary equilibrium $\hat{n}_s$. Moreover, the number of users $\hat{n}_s^c$ in cell $c$ associated with ASP $s$ at the equilibrium point can be defined as

$$ \hat{n}_s^c = \frac{N^c q_s^c e^{-p_s}}{\sum_{s' \in S} q_{s'}^c e^{-p_{s'}}}. \quad (7) $$

*Proof.* The replicator equation (6) is nothing but a set of
<figure><img src="image_4.png" /><figcaption>Fig. 2. Application service providers and end users interactions as a generalized Stackelberg game.</figcaption></figure>

ordinary differential equations (ODE). The equilibrium is the stationary point of ODE. Hence, to show that the replicator dynamics admits a unique equilibrium point, it is sufficient to show that the right-hand side of (6) is continuously differentiable and that it admits a unique stationary point [34]. Replacing $\nu_s^c, \nu_{s'}^c$ from (1) in (6), we derive analytically the equilibrium point expression (7). A detailed proof is provided in Appendix A. □

## IV. STACKELBERG GAME BETWEEN SERVICE PROVIDERS AND USERS

In our game-theoretic formulation of the communication service market, the ASPs are the leaders, and the users are the followers as described in Fig. 2. We have proved in Section III that the equilibrium of the population game $\mathcal{E}_c$ between the users admits a unique solution, and the distribution of users at the equilibrium point is derived relying on the closed form expression (7). In this section, we model the interactions between the ASPs as a non-cooperative game.

We note that the analytical expression of the number of users $\hat{n}_s^c$ in cell c of ASP s at equilibrium is very similar to a contest success function from the well known TC framework [35]. The TC framework is commonly used in the economics literature to model strategic interactions between two or more competing agents. The basic contest framework consists of competing agents who expend costly resources to win a prize (a contest). Given the efforts exerted by all the agents, the probability of an agent i winning a prize is defined by the contest success function (CSF). Typically, the CSF function is defined as $\rho_i(x) = \frac{(x_i)^r}{\sum_{i'} (x_{i'})^r}$ where $x_i$ is the effort made by an agent i and r is a parameter. For example, r = 1 is the well known lottery and r $\to \infty$ defines the all-pay auction.

In the communication market context, the ASPs compete to attract users to their services by exerting effort on costly resources. The resources acquired by ASPs further reflect their service quality (a higher QoS is seen as a desirable attribute in the process of ASP selection). Thus, in our case, the CSF can be interpreted as the probability that any ASP successfully attracts an end-user. We call it the *slice association probability function* $A_s$. It is the probability that given resources expended

by all ASPs, a user will associate with ASP s. For our model, we rely on a more general and multi-resource CSF function or slice association probability function

$$A_{sk}^{c}(d^{c}, p) = \frac{f_{s}^{c}(d_{sk}^{c}, p_{sk})}{\sum_{s' \in S} f_{s'k}^{c}(d_{s'k}^{c}, p_{s'k})}, \forall s \in S, \forall c \in C, \forall k \in K. \quad (8)$$

**Remark 3.** Bernstein and Federgruen proposed a very well known general equilibrium model, named as attraction model, for industries with price and service competition in [36]. It is very similar to our slice association probability function.

In (8), the number of potential users in each cell as well as the slice association probability for each slice, might vary from cell to cell. The expected number of users choosing ASP s is defined as

$$\sum_{c \in C} \sum_{k \in K} N_k^c A_{sk}^c(d^c, p) = \sum_{c \in C} \sum_{k \in K} \frac{N_k^c f_s^c(d_{sk}^c, p_{sk})}{\sum_{s' \in S} f_{s'k}^c(d_{s'k}^c, p_{s'k})}. \quad (9)$$

Incorporating (7) and (2) in (3), we get

$$U_s(d_s, d_{-s}) = \sum_{c \in C, K \in \mathcal{K}} p_{sk} \frac{N_k^c f_{sk}^c(d_{sk}^c, p_{sk})}{\sum_{s' \in S} f_{s'k}^c(d_{s'k}^c, p_{s'k})} - \sum_{m \in \mathcal{M}^c} \omega_m^c d_{s,m}^c. \quad (10)$$

In this work, we set

$$f_{sk}^{c}(d_{sk}^{c}, p_{sk}) = q_{sk}^{c}(d_{sk}^{c})e^{-p_{sk}}. \quad (11)$$

We assume that $f_{ck}^s(d_{sk}^c, p_{sk})$ is an increasing concave function in $d_{sk}^c$ for a fix value of $p_{sk}$, while it is a convex decreasing function in $p_{sk}$ given fix value of $d_{sk}^c$. The function translates the effort exerted by ASP in terms of resource and prices charged by them to the total utility experienced by its potential subscribers. We assume that ASPs are selfish, and that each ASP aims at maximizing its profit. They take into account the decisions of the other ASPs when computing their own decision. To theoretically analyze the outcome of these strategic interactions, we define the non-cooperative game $\mathcal{G} \triangleq \langle S, (\mathcal{F}_s)_{s \in S}, (U_s)_{s \in S} \rangle$ as follows:

* Player set: the set of application service providers $S$.

* Strategy: the vector of resource demand $d_s = (d_s^1, \dots, d_s^C)$ where $d_s^i$ is the amount of resource to be requested by each base station c. The strategy set for each ASP s is $\mathcal{F}_s$.

* Utility: the utility of each ASP s is defined as $U_s$.

We study the competition between ASPs in terms of QoS, i.e., how ASPs strategically spend their budget on the resources to attract the maximum number of users and, in turn, maximize their profits. The ASPs' profit depends on both their individual decision and the decision taken by the other ASPs. Let $d_s$ be the vector of strategy of ASP s, $d_{-s} \triangleq \text{col}((d_{s'})_{s' \neq s})$ is the stack vector which contains the vector of strategies of all the ASPs in $S$ except s. The decision problem of each ASP s is
defined as

$$Q_s \quad \underset{d_s \in \mathcal{F}_s}{\text{maximize}} \quad U_s(d_s, d_{-s}).$$

To study the outcome of the non-cooperative game $\mathcal{G}$, we recall the solution concept of Nash equilibrium (NE)

**Definition 1.** [37] A strategy profile $d^* = (d_1^*, \dots, d_S^*)$ is a Nash equilibrium of the game $\mathcal{G}$ if

$$\forall s \in \mathcal{S}, U_s(d_s^*, d_{-s}^*) \geq U_s(d_s, d_{-s}^*), \forall d_s \in \mathcal{F}_s. \quad (12)$$

Here, $(d_s, d_{-s}^*)$ denotes the strategy profile with $s^{th}$ element equals $d_s$ and all other elements equal $d_{s'}^*$ (for any $s' \neq s$).

In the next section, we analyze the existence and uniqueness of the Nash equilibrium (NE) solution of the non-cooperative game $\mathcal{G}$.

## V. EXISTENCE AND UNIQUENESS OF THE NASH EQUILIBRIUM

In this section, we establish the existence and uniqueness of the NE of game $\mathcal{G}$. To prove the uniqueness of the NE, we rely on the concept of diagonally strict concavity (DSC) introduced by Rosen [38]. Intuitively, DSC is a generalization of the idea of convexity to a non-cooperative game setting.

**Definition 2** (Diagonal Strict Concavity [38]). A game with profiles of strategies $d$ and profiles of utility functions $U$ is called diagonally strict concave (DSC) for a given vector $r$ if for every distinct $\bar{d}$ and $d$,

$$[g(\bar{d}, r) - g(d, r)] (\bar{d} - d)' < 0, \quad (13)$$

with $g$ the concatenation of the weighted gradients of the players' utility functions

$$g(d, r) = [r_1 \nabla_1 U_1(d), r_2 \nabla_2 U_2(d), \dots, r_S \nabla_S U_S(d)], \quad (14)$$

where $\nabla_s U_s(d)$ denotes the gradient of utility of player $s$ with respect to his own strategy $d_s$.

**Theorem 1.** The game $\mathcal{G}$ admits a unique NE.

*Proof.* The utility of each ASP in game $\mathcal{G}$ is continuous, increasing, and concave, while the strategy space for each ASP is convex and compact. Therefore, the existence of an equilibrium for the game follows from [38], Thm.1. To prove the NE uniqueness, we note that if the players' utilities in the game $\mathcal{G}$ satisfy the DSC property, then $\mathcal{G}$ admits a unique NE (see [38], Thm.2).

Let $G(d, r)$ be the Jacobian of $g(d, r)$ with respect to $d$, where $d$ is any profile of strategies. In order to prove the strict DSC of $g(d, r)$, from [38], Thm.6, we note that it is sufficient to prove that the symmetrized version of the pseudo-Jacobian, i.e., $\hat{G}(d, r) \triangleq G(d, r) + G(d, r)'$, is negative definite over the domain of interest. To show that $\hat{G}(d, r)$ is negative definite, we must prove that the following three conditions hold simultaneously:

**C 1.** each $U_s(d)$ is a regular strictly concave function of $d_s$ (i.e., its Hessian is negative definite).

**C 2.** each $U_s(d)$ is convex in $d_{-s}$.

**C 3.** there is some $r > 0$ such that function $\sigma(d, r) = \sum_s r_s U_s(d)$ is concave in $d$.

The negative definiteness of $[G(d, r) + G'(d, r)]$ follows from [39], Lem.1. We first consider the case of a single base station $c$ with a single population demanding service $k$ and show that $\hat{G}_k^c(d, r)$ is negative definite for this case. We compute the Hessian $(H_s U_{sk}^c)$ of utility of any ASP $s$ with respect to ASP $s$ owns strategy

$$H_s U_{sk}^c = -2 \frac{p_{sk} \sum_{s' \in \mathcal{S}, s' \neq s} f_{s'k}^c}{\left( \sum_{s' \in \mathcal{S}} f_{s'k}^c \right)^3} \times \left[ (\nabla_s f_{sk}^c)^T \nabla_s f_{sk}^c - H_s(f_{sk}^c) \sum_{s' \in \mathcal{S}} f_{s'k}^c \right]. \quad (15)$$

On the right hand side of (15), matrix $(\nabla_s f_{sk}^c)^T \nabla_s f_{sk}^c$ is positive semi-definite, where $\nabla_s f_{sk}^c$ is the gradient row vector of $f_{sk}^c$ with respect to ASP $s$'s own strategy $d_{sk}^c$, $H_s(f_{sk}^c)$ is the Hessian of $f_{sk}^c$ with respect to $d_{sk}^c$ and it is negative definite as $f_{sk}^c$ is concave. Thus, the Hessian of utility $H_s U_{sk}^c$ is negative definite and satisfies the first condition **C1**.

We still need to show that the utility of each ASP $s$ is convex in the strategy of all other ASPs. For that purpose, consider the Hessian of utility of ASP $s$ with respect to strategy of all other ASPs

$$H_{-s} U_s = 2 \frac{f_{sk}^c}{\left( \sum_{s' \in \mathcal{S}} f_{s'k}^c \right)^3} [M_{sk}^c - \text{diag}_{-s} \{H(f_{uk}^c)\}], \quad (16)$$

where is $M_{sk}^c$ block matrix and $uv^{th}$ block is defined as

$$M_{skuv}^c = (\nabla_u f_{uk}^c)^T \nabla_v f_{kv}^c \text{ where } u, v \neq s, u, v, s \in \mathcal{S}. \quad (17)$$

$\nabla_u f_{uk}^c$ is the gradient row vector of $f_{uk}^c$ with respect to ASP $s$'s own strategy and $\text{diag}_{-s} \{H(f_{uk}^c)\}$ is the block diagonal matrix with block $u$ where $H(f_{uk}^c)$ is the Hessian of $f_{uk}^c$ with respect strategy vector of $u$ itself $\forall u, u \neq s, u \in \mathcal{S}$. In right hand side of equation (16) matrix $M_{sk}^c$ is positive definite and the block diagonal matrix $\text{diag}_{-s} \{H(f_{uk}^c)\}$ is negative definite as the each diagonal matrix element. $H(f_{uk}^c)$ is negative definite, thus $H_{-s} U_s$ is positive definite, which satisfies the condition **C2**.

Finally, by choosing $r_s = \frac{1}{p_{sk}} \forall s \in \mathcal{S}$ we check that $\sigma(d, r) \triangleq \sum_s r_s U_s(d)$ is concave in $d$, therefore satisfying the condition **C3**.

We now want to extend the previous proof to the multi-service case. We have already shown that $\hat{G}_k^c$ is negative definite for any single service $k$. For $K$ service types consider a $\hat{G}^c$ symmetrized version of the pseudo Jacobian, after arranging columns and rows we get (see [40], Cor.2)

$$(\hat{G}^c) = \text{diag} \{ \hat{G}_1^c, \dots, \hat{G}_k^c, \dots, \hat{G}_K^c \}.$$
The above $\hat{G}^c$ matrix is negative definite as each diagonal matrix is negative definite. Similarly extending results to multi-cell scenario we show that $\hat{G}$ matrix is negative definite

$$ (\hat{G}) = \mathrm{diag} \{ \hat{G}^1, \dots, \hat{G}^c, \dots, \hat{G}^C \}. $$

which proves the DSC property holds for the multi-cell-multi-service setting. By applying [38], Thm.2, we prove that the NE $d^*$ solution of the game $\mathcal{G}$ is unique. □

## VI. RESOURCE PRICING AND EQUILIBRIUM

We have shown in the previous section that there exists a unique NE solution of the non-cooperative game $\mathcal{G}$. We assume that the capacity of the resource released by the NSP in each cell is finite. Given the per-unit prices for resources decided by the NSP, the total resource requested by the ASPs at the NE of $\mathcal{G}$ may violate the infrastructure capacity. Thus, the NSP's primary concern is how to efficiently allocate the finite capacity constrained resources to competing ASPs. The desired allocation must satisfy all the ASPs' constraints and simultaneously maintain high resource utilization. In this regard, we assume that the NSP optimizes the unit price of each resource such that at the NE of the game $\mathcal{G}$ each ASP utilizes its entire budget and no resource remains leftover, i.e, the total demand of resources matches the available infrastructure capacity. In market economics, this pricing problem is formulated as a market clearing problem, e.g, a Fisher market, where the market prices are settled in such a way that the amount of resources requested by the buyers is equal to the amount of resources supplied by the sellers. We propose two approaches, introduced in Section II B, to deal with this challenge depending on whether the ASPs' budget is binding.

One way to compute the market equilibrium is through Walras' "tâtonnement" process, i.e., if the demand exceeds the resource capacity, the market operator increases the resource's price. Conversely, the market operator decreases the resource's price when the demand is smaller than the resource capacity. The process is repeated until demand equals supply (resource capacity). The disadvantage of this approach is that its outcome (known as a general equilibrium) relies on the strong assumption of perfect competition, which in practice does not hold. To overcome this limitation, we use the approach introduced by Shapley and Shubik in their pioneering work [41], also known as Trading post or share constrained proportional allocation (SCPA) scheme[3]. Now we formally define the trading post mechanism.

### A. Trading Post Mechanism

In the trading-post mechanism, each player (i.e, ASP) places a bid on each type of resource. Once all ASPs have placed their bids, each resource type's price is determined by the total bids placed for that resource. Precisely, let ASP $s$ submits a bid $b_{sm}^c$ to resource $m$ at cell $c$. The price per unit of resource $m$ at cell $c$ is then set to $\frac{\sum_{s \in S} b_{sm}^c}{D_m^c}$. Accordingly, ASP $s$ receives

a fraction of $d_{sm}^c$ in return to his spending of $b_{sm}^c$

$$ d_{sm}^c = \begin{cases} \frac{b_{sm}^c D_m^c}{\sum_{u \in S} b_{um}^c} & \text{if } b_{sm}^c > 0, \\ 0 & \text{otherwise.} \end{cases} \quad (18) $$

After replacing $d_{sm}^c$ in (3) and ($Q_s$) in terms of bids, the decision problem of each ASP $s$ can be written as follows

$$ \begin{array}{ll} \hat{Q}_s & \text{maximize} \quad U_s(b_s, b_{-s}), \\ & \text{subject to} \quad \sum_{c \in \mathcal{C}} \sum_{m \in \mathcal{M}^c} b_{s,m}^c \le B_s, b_{s,m}^c \ge 0. \end{array} $$

We may consider two possible behaviours for the ASPs. First, they are *price takers*, i.e., they accept the prices decided by the price setter (market operator), and they only act strategically in terms of QoS by optimizing their demand in the bundle resources. Second, ASPs are *price makers*, i.e., they anticipate the effect of their demand on the price of the bundle of resources. The trading post mechanism induces a new non-cooperative game $\hat{G}$ defined as follows:

* Player set: the set of ASPs $\mathcal{S}$.

* Strategy: the vector of bids $b_s = [b_s^1, \dots, b_s^C]$ where $b_s^c$ is the bid to be submitted to cell $c$. ASP $s$ strategy set is $\mathcal{F}_s \triangleq \{b_s | b_{sm}^c \ge 0, \forall m \in \mathcal{M}^c, c \in \mathcal{C}, \sum_{c \in \mathcal{C}} \sum_{m \in \mathcal{M}^c} b_{s,m}^c = B_s\}$.

* Utility: The utility of each ASP $s$ is $U_s$.

To study the outcome of the mechanism, we consider the standard notion of NE, applied to the trading post mechanism

**Definition 3.** A multi-bid strategy $b^* = (b_1^*, \dots, b_S^*)$ is called a NE of the game $\hat{G}$ if

$$ \forall s \in \mathcal{S}, U_s(b_s^*, b_{-s}^*) \ge U_s(b_s, b_{-s}^*), b_s \in \mathcal{F}_s. \quad (19) $$

Here, $(b_s, b_{-s}^*)$ denotes the strategy vector with $s^{th}$ element equal $b_s$ and all other elements equal $b_v^*$ (for any $v \neq s$).

For the proposed mechanism, a NE solution of game $\hat{G}$ constitutes a stable bidding policy where each ASP maximizes its utility and the NSP implements the resource allocation mechanism (18). We investigate conditions for the existence and uniqueness of the NE solution of the game $\hat{G}$. This requires complex calculations. Thus, to keep the analysis tractable, we restrict the problem to a single resource (radio resource). We assume that the QoS provided by ASP $s$ in cell $c$ is given by $q_s^c \triangleq (d_s^c)^{\rho_s^c}$ where $\rho_s^c$ is the sensitivity parameter and $0 < \rho_s^c \le 1$. Such a type of function has been used in [24] to model the effect of users sensitivity towards their service provider selection. We replace $q_s^c = (d_s^c)^{\rho_s^c}$ in (11) and from (8) we get

$$ A_s^c(d^c, p) = \frac{(d_s^c)^{\rho_s^c} e^{-p_s}}{\sum_{s' \in S} (d_{s'}^c)^{\rho_{s'}^c} e^{-p_{s'}}}. \quad (20) $$

**Proposition 2.** If for a single resource, the QoS provided by ASP $s$ in cell $c$ is defined by $q_s^c = (d_s^c)^{\rho_s^c}$ and $0 < \rho_s^c \le 1$, then the game $\hat{G}$ admits unique NE.

*Proof.* If the QoS provided by ASP $s$ in cell $c$ is defined by $q_s^c = (d_s^c)^{\rho_s^c}$ and $0 < \rho_s^c \le 1$, then the ASPs' utility functions
satisfy the three conditions C1,C2 and C3. The rest of the proof is the same as the proof of Theorem 1. □

Moving ahead, we compare the profit gained by ASPs at the NE of the game with the baseline static proportional allocation scheme (SS), i.e., the allocation where each resource is allocated to an ASP s in proportion to its budget, e.g., $\frac{B_s}{\sum_{s' \in S} B_{s'}}$.

**Proposition 3.** For two application service providers, the revenue gained under a dynamic resource sharing scheme is at least equal to the revenue gained under a proportional allocation scheme

*Proof.* The proof is provided in Appendix B. □

We have seen in the first part of this section, that when ASPs are constrained by budgets, the resource pricing can be implemented by a trading post mechanism. However, this mechanism requires a third-party player (market operator) to centralize the bids made by all the ASPs, and thus can only lead to semi-decentralized implementations. Furthermore, the network capacity constraints are only implicitly taken into account through the budget constraint.

In the next section, we design a pricing and resource allocation scheme for **Case II** introduced in Section II B, that explicitly takes into account network capacity constraints and can be implemented in a fully distributed way. **Case II** gives rise to a generalized Nash equilibrium problem (GNEP) involving global coupling constraints, which take into account the network finite capacities. To solve the GNEP, we rely on a variational reformulation of the non-cooperative game, which leads to a unique variational equilibrium (VE). Using that property, we implement two algorithms to compute the VE: the first one requires an extended game reformulation of the GNEP and is based on asymmetric projected gradient descent methods; the second one relies on an extension of the alternating direction method of multipliers (ADMM).

## B. Pricing Game

We consider a non-cooperative game where, similar to game $G$, each ASP aims at maximizing its profit by requesting resources under a set of local constraints that are not bined by a finite budget. However, we now assume that the ASPs take into account the infrastructure capacity while requesting resources, therefore giving rise to a global coupling constraint for each cell and each resource available within that cell

$$ \sum_{s \in S} d_{sm}^{c} \leq D_{m}^{c}, \forall c \in C, m \in \mathcal{M}. \quad (21) $$

Let $\tilde{\mathcal{F}}_s \triangleq \{d_s | d_{sm}^c \geq 0, \forall m \in \mathcal{M}^c, c \in C, K_s(d_s) \leq 0\}$. The decision problem faced by each ASP in this new non-cooperative game can be formulated as a parametrized optimization problem with local and global coupling constraints

$$ \begin{array}{ll} Q_s & \underset{d_s \in \tilde{\mathcal{F}}_s}{\text{maximize}} \quad R_s(d_s, d_{-s}), \\ & \text{subject to} \quad \sum_{s \in S} d_{sm}^c \leq D_m^c, \forall c \in C, m \in \mathcal{M}, (\lambda_{sm}^c) \end{array} \quad (22) $$

where $\lambda_{sm}^c$ at the right of (22) and between brackets, is the Lagrange multiplier (shadow price) of the coupling constraint (22).

We define a new non-cooperative game $\mathcal{G}_p \triangleq \langle S, (\tilde{\mathcal{F}}_s)_{s \in S}, (R_s)_{s \in S} \rangle$, where the set of players and utility is the same as in game $\mathcal{G}$. However, the strategy set of the players are coupled through the capacity constraint (22), giving rise to a GNEP. Consider the generalized Nash equilibrium (GNE) as the solution to this game.

**Definition 4.** [42] A strategy profile $d^* = (d_1^*, \dots, d_S^*)$ is called a GNE of the game $\mathcal{G}_p$ if

$$ \forall s \in S, R_s(d_s^*, d_{-s}^*) \geq R_s(d_s, d_{-s}^*), \quad (23) $$

$d_s \in \tilde{\mathcal{F}}_s, d_{sm}^c \geq 0, \forall m, c \text{ and } \sum_{s \in S} d_{sm}^c \leq D_m^c, \forall c \in C, m \in \mathcal{M}$.

Due to coupling, solving directly $\mathcal{G}_p$ requires coordination among possibly all ASPs, which might be hard to enforce in practice. To solve $\mathcal{G}_p$, we will make use of the duality approach as a natural way to obtain a hierarchical decomposition of the GNEP. To that purpose, we start by characterizing the GNE solutions of game $\mathcal{G}_p$ in terms of KKTs [42]: any strategy profile $\bar{d}$ is a GNE of the game $\mathcal{G}_p$ if and only if it satisfies the KKT conditions, which are: $\forall s \in S, \forall c \in C, \forall m \in \mathcal{M}^c$,

$$ \left\{ \begin{array}{l} \frac{\partial R_s}{\partial d_{sm}^c}(\bar{d}) = \lambda_{sm}^c, \\ \lambda_{sm}^c \left( \sum_{s \in S} d_{sm}^c - D_m^c \right) = 0, \\ \text{with } \lambda_{sm}^c \geq 0, \bar{d}_s \in \tilde{\mathcal{F}}_s. \end{array} \right. \quad (24) $$

In the above KKT conditions, we are primarily interested in $\lambda_{sm}^c$, the Lagrange multipliers of (22), as these Lagrange multipliers can be interpreted as shadow prices for the resource allocation and can be used in the game $\mathcal{G}_p$ as the evaluations by the ASPs of the prices charged by the NSP per resource unit. However, notice that if implemented without coordination, the Lagrange multipliers for each ASP are different, resulting in possibly discriminatory pricing. Moreover, there can be multiple possible GNEs. In fact, there are infinite GNEs solutions of $\mathcal{G}_p$ in this case. Nevertheless, in the following discussion, we show that there exists an equilibrium solution to $\mathcal{G}_p$ with a special characteristic: it is unique and gives rise to the same valuation among the players. Rosen [38] has introduced concept of such equilibrium in his seminal work and called it as normalized Nash equilibrium

**Definition 5.** A $r$-normalized equilibrium point is such that there exists a $\lambda_m^c > 0$ associated to each resource at each cell so that for all end users $\lambda_{sm}^c = \lambda_m^c/r_s$, for a suitable vector of nonnegative coefficients vector $r$.

It is very common in the literature, to relate normalized Nash equilibrium to the concept of variational equilibrium (VE) [42]. We will use both concepts without distinction in the following. The parameters $\{r_1 \dots r_S\}$ intuitively show the proportion of a burden on ASP s for satisfying the coupling constraints among all other application service providers in the set. Notice, $\lambda_m^c$ is
the same for all the ASP and thus can be treated as the base price. Next, we prove that such r-normalized Nash equilibrium (variational equilibrium), is unique for game $G_p$.

**Corollary 1.** *The Pricing Game* $G_p$ admits a unique normalized equilibrium for $r_s = \frac{1}{p_s}$.

*Proof.* In the proof of Theorem 1, we have shown that the Game $G$ has the DSC property $\forall c \in C$ and $\forall c \in \mathcal{M}$ and any $\omega_m^c \ge 0$. The utilities of players in the Game $G_p$ (i.e. revenues) are the same as in $G$ with $\omega_m^c = 0$. Hence, the Pricing Game $G_p$ also satisfies the DSC property. The proof is a consequence of [38], Thm.4. $\square$

**Theorem 2.** *Every r-normalized Nash equilibrium of the Pricing Game* $G_p$ with shadow prices $\lambda_{sm}^c = \frac{\lambda_m^c}{r_s}$ for all $s \in S, m \in \mathcal{M}^c, c \in C$ is a NE for the corresponding Game $G$ with $\omega_m^c = \lambda_m^c, \forall m \in \mathcal{M}^c, \forall c \in C$.

*Proof.* We reformulate $G_p$ using an augmented system-like utility function, that we call the Nash game (NG)-game utility function [43]. The NG utility function is defined as a two argument function

$$ \tilde{R}(d; x) \triangleq \sum_{s=1}^{S} r_s R_s(d_{-s}, x_s), \forall x \in \tilde{\mathcal{F}} \triangleq \prod_{s} \tilde{\mathcal{F}}_s, \quad (25) $$

where $x \triangleq (x_s)_s$ and $d_{-s}$ defined as before. We note that Definition 5 can be equivalently formulated with respect to the NG utility function. A vector $d^* \in \tilde{\mathcal{F}}$ is called a NE solution of this game if its NG utility function $\tilde{R}$ satisfies

$$ \tilde{R}(d^*; d^*) \geq \tilde{R}(d^*; x) \quad \forall x \in \tilde{\mathcal{F}}. \quad (26) $$

The above condition can equivalently be written as follows, for given $d_{-s}^*$

$$ \sum_{s=1}^{S} r_s R_s(d_{-s}^*; d_s^*) \geq \sum_{s=1}^{S} r_s R_s(d_{-s}^*; x_s), \forall x \in \tilde{\mathcal{F}}. \quad (27) $$

Note that the NG utility function $\tilde{R}$ is separable in the second argument $x$ for any given first argument $d^*$. The existence of NE is guaranteed by Theorem 2 [43]. Now to extend the NG utility function formulation to coupled constrained game, i.e., pricing game, we use the fact that the pricing game is related to a constrained maximization of NG utility function with respect to the second argument keeping the first argument as a fixed point solution. Consider that the ASPs maximize their revenue subject to coupled constraints $g_i(d) \le 0, i \in \mathcal{I} \triangleq C \times \mathcal{M}$ where $g_i(d) \triangleq D_m^c - \sum_{s'} d_{s'm}^c$. Then

$$ \tilde{R}(d^*; d^*) \geq \tilde{R}(d^*; x) \quad \forall x \in \mathcal{F}, \tilde{g}(d_{-s}^*, x_s) \leq 0, \quad (28) $$

where $\tilde{g}(d^*; x) = \sum_{s=1}^S g(d_{-s}^*, x_s)$. We introduce the augmented Lagrangian function of the constrained NG utility maximization problem, with $\lambda$ a Lagrange multiplier vector

$$ \tilde{L}(d; x; \lambda) \triangleq \tilde{R}(d; x) + \lambda^T \tilde{g}(d; x). \quad (29) $$

In our case $\forall s \in S, R_s$ is increasing concave and continuously differential, and $g$ is affine. Thus, all the constraints are active at the equilibrium. If $d^*$ is an equilibrium solution of the

pricing game $G_p$, then by [43], Lem.2, there exists a unique $\lambda^* > 0$ such that $\nabla_d \tilde{L}(d; x, \lambda^*) = 0$ and $d^*$ maximizes the Lagrangian $\tilde{L}$, over $x \in \tilde{\mathcal{F}}$ as a fixed point.

Relying on the duality framework, we prove that we can decompose the coupled constrained game $G_p$ into the equivalent game with no coupled constraints, and indeed the equivalent game coincides with the non-cooperative game $G$ with $\omega_m^c = \lambda_m^c$. To that purpose, we consider the dual cost function $D(\lambda)$ defined as

$$ D(\lambda) \triangleq \tilde{L}(d^*; d^*; \lambda). \quad (30) $$

Equivalently, relying on the notion of fixed point, the dual cost can be written as

$$ D(\lambda) \triangleq \left[ \max_{x \in \Omega} \tilde{L}(d; x; \lambda) \right] \Big|_{x=d}. \quad (31) $$

The dual NG can then be defined as the minimization of the dual cost function

$$ D^* = \min_{\lambda \ge 0} D(\lambda). \quad (32) $$

The Lagrangian function $\tilde{L}$ is separable over each ASP. Thus, the dual function can be separately written for each player as

$$ D(\lambda) \triangleq \sum_{s \in S} \left[ \max_{x_s \in \Omega_s} L_s(d_{-s}; x_s; \lambda) \right] \Big|_{x_s=d_s} \quad (33) $$

$$ = \sum_{s \in S} L_s(u_{-s}^*(\lambda), u_s^*(\lambda), \lambda), \quad (34) $$

where

$$ L_s(d_{-s}; x_s; \lambda) = r_s R_s(d_{-s}; x_s) + \lambda^T g(d_{-s}; x_s). \quad (35) $$

From [43], Thm.3, we prove that $D(\lambda)$ can be obtained by solving the relaxed game with utility function $L_s$ and no coupled constrains. Indeed, that relaxed game is the game $G$ with $\omega = \lambda$, which concludes the proof. $\square$

This approach enables us to reformulate the GNEP $G_p$, as a lower-level non-cooperative Nash game with utility function $L_s$ ($U_s$) and a higher-level optimization problem for coordination.

### C. Extended Pricing Game

Paccagnan et al. addressed decentralized computation of variational equilibrium (VE) for aggregative games with quadratic utility functions [44], [45]. They relaxed the coupling constraints of the generalized Nash equilibrium problem by including a penalty term in the original utility functions. A VE is then computed applying asymmetric gradient algorithms with constant step size. The purpose of the penalty term is to assign large penalties to deviations from the constraints. The penalty reformulation helps avoid the high computational complexity of conventional optimization reformulations or the requirement of projection steps. Traditionally, drawbacks is that penalty method convergence might be quite sensitive on selecting penalty parameters. To overcome this issue, we follow the formulation proposed in the [46]. We consider a game with $S+1$ players, where the first $S$ players are the ASPs and the
$(S + 1)^{\text{th}}$ player is the NSP, who controls the $\lambda$ price vector. We define the decision problem of the NSP, $Q_{S+1}$ as below

$$Q_{S+1} \quad \underset{\lambda \ge 0}{\text{maximize}} \quad \sum_c \sum_m \lambda_m^c \left( \sum_s d_{sm}^c - D_m^c \right). \quad (36)$$

The idea behind using $\sum_c \sum_m \lambda_m^c (\sum_s d_{sm}^c - D_m^c)$ as the utility for NSP in the above decision problem, is that it solves complementary condition from KKT (24). For the remaining $S$ players the decision problem is

$$Q_s \underset{d_s \ge 0}{\text{maximize}} \quad R_s(d_s, d_{-s}) - \frac{1}{r_s} \sum_c \sum_m \lambda_m^c d_{sm}^c \quad \forall s \in S.$$

We call $Q_+ \triangleq \{Q_1, \dots, Q_{S+1}\}$ the extended pricing game. The difference between the extended pricing game and the pricing game $G_p$ is that in the former, there are no coupled constraints – complementary conditions are treated as the utility of an additional player (NSP).

**Proposition 4.** If $\bar{d}$ is a $r$-normalized equilibrium of the pricing game, then there exists $\bar{\lambda} \ge 0$ such that $(\bar{d}, \bar{\lambda})$ is an equilibrium of the extended pricing game.

*Proof.* We have already proved that the pricing game $G_p$ is monotone on $\hat{\mathcal{F}}$, which implies that the extended pricing game is also monotone on $\hat{\mathcal{F}} \times \mathbb{R}$, the proof follows from [46], Prop.4. $\square$

## VII. ALGORITHMS TO COMPUTE MARKET EQUILIBRIA

In this section, we introduce two semi-decentralized algorithms to compute the equilibria solutions of the trading post mechanism and extended pricing game, respectively. Computational and privacy issues might limit the implementation of such algorithms on medium to large-scale problems. To mitigate these issues, we propose a fully distributed proximal algorithm, inspired from the inexact-ADMM, to compute the VE of the pricing game $G_p$.

### A. Semi-Decentralized Learning Algorithms

We have proved in Section V that $G$ admits a unique equilibrium for any price vector decided by the NSP. A similar result also holds for VI-A when dealing with a single resource. However, we still need to check whether ASPs can reach this equilibrium in a decentralized fashion. In this regard, we propose the use of the dual averaging or mirror-descent method suggested for continuous action convex games [47]. We proceed by describing the dual averaging method. In the dual averaging method, each player, i.e., ASP $s$ estimates its marginal utility or utility gradient with respect to its own strategy. To increase their utilities, the players need to take action along the direction of their utility gradient while maintaining their action in the feasible action space. In order to achieve this, each player $s$ at each time step $n$ accumulates its discounted utility gradient in some auxiliary variable $y_s$

$$y_s(n+1) = [y_s(n) + \alpha_n \nabla_{b_s} U_s(b_s(n), b_{-s}(n))] . \quad (A1)$$

In the above equation $\alpha_n$ denotes the discount factor or step size. Once the discounted gradient has been accumulated, every ASP $s$ uses its own updated value of the auxiliary variable, $y_s$, to take the next feasible action

$$b_s(n+1) = Q_s(y_s). \quad (37)$$

In turn, each ASP $s$ maps the recent value of auxiliary variable $y_s$ to its decision space $\mathcal{F}_s$ using the mapping $Q_s(y_s)$, e.g., $Q_s$ can be interpreted as a projection map. The map $Q_s(y_s)$ is defined more generically as

$$Q_s(y_s) = \underset{b_s \in \mathcal{F}_s}{\operatorname{argmax}} \{\langle y_s(n), b_s \rangle - h_s(b_s)\}, \quad (A2)$$

where $h_s(b)$ is a regularization function, also called penalty function, over the feasible action set $\mathcal{F}_s$. The penalty $h_s(b)$ aims to force the algorithm to converge within the interior of the feasible domain set. Different definitions of the regularization functions induce different maps. For instance, the use of $l_2$ norm $h_s(\cdot) = \|\cdot\|$ as a regularizer, results in the well-known Euclidean projection map.

For the game $G$, where application service providers actions are bounded by their budgets, we use the Gibbs entropy function as a regularization function

$$h_s(b_s) \triangleq \sum_{c \in \mathcal{C}} \sum_{m \in \mathcal{M}} b_{sm}^c \log(b_{sm}^c). \quad (38)$$

We replace $h_s(b_s)$ in equation (A2) by the entropic regularization function and after some calculation we get the exponential mapping

$$b_{sm}^c = \frac{B_s \exp(y_{sm}^c)}{\sum_{c \in \mathcal{C}} \sum_{k \in \mathcal{M}} \exp(y_{sk}^c)}. \quad (39)$$

The induced map $Q_s(y_s)$ is similar to the well-known Logit map, where each player distributes its budget (weights) to different resources depending on exponential of accumulated discounted gradients.

**Algorithm 1 Online Learning Algorithm for $\hat{\mathcal{G}}$**

**Require:** $\sum_{n=0}^{+\infty} \alpha_n = +\infty, \alpha_n \to 0$ as $n \to +\infty$
1: **repeat** $n = 1, 2, \dots$,
2: &nbsp;&nbsp;&nbsp;&nbsp;**for each** ASP $s \in S$
3: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Observe gradient of utility and update
4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$y_s = [y_s + \alpha_n \nabla_{b_s} U_s(b_s, b_{-s})]$
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**end for**
6: &nbsp;&nbsp;&nbsp;&nbsp;**for each** ASP $s \in S$
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**for each** cell $x \in \mathcal{C}$ and resource $m \in \mathcal{M}^c$
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Play $b_{sm}^c \leftarrow \frac{B_s \exp(y_{sm}^c)}{\sum_{c \in \mathcal{C}} \sum_{k \in \mathcal{M}} \exp(y_{sk}^c)}$.
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**end for**
10: **end for**
11: **until** $\| (b(n) - b(n-1)) \| \le \epsilon$

**Theorem 3.** If Algorithm 1 satisfies the required conditions for step size sequence, e.g., $\sum_{n=0}^{\infty} \alpha_n = +\infty, \alpha_n \to 0$ as $n \to +\infty$, then it converges to the unique NE of the Game $G$.

*Proof.* The proposed exponential algorithm is the special case of the dual averaging algorithm. If the NE of any continuous
action convex game is strictly r-variationally stable, then the converges of the dual averaging algorithm to a unique NE of the game is guaranteed by [47], Thm. 4.6. Hence to prove the convergence of the proposed algorithm, it is sufficient to show that the unique NE of game $\mathcal{G}$ is strictly r-variationally stable. The unique NE $\hat{b}$ of any convex game is strictly r-variationally stable if $\forall b_s \in \mathcal{F}_s$

$$ \sum_{s \in \mathcal{S}} r_s \nabla_s U_s(b)(b_s - \hat{b}_s) < 0. \quad (40) $$

As we have already shown in section V, the ASPs' utility functions in game $\mathcal{G}$ satisfy the DSC for $r_s = \frac{1}{p_s}$, $\forall s \in \mathcal{S}$

$$ \sum_{s \in \mathcal{S}} r_s \left[ \nabla_s U_s(b) - \nabla_s U_s(\hat{b}) \right] (b_s - \hat{b}_s) < 0. \quad (41) $$

We know that for any continuous action convex game, a feasible point $\hat{b}$ is a NE of the game if and only if

$$ \sum_{s \in \mathcal{S}} r_s \nabla_s U_s(\hat{b})(b_s - \hat{b}_s) \le 0. \quad (42) $$

Inequalities (42) and (41) imply (40), which proves that the unique NE of game $\mathcal{G}$ is strictly r-variationally stable and then by [47], Thm. 4.6, Algorithm 1 converges to the unique NE of game $\mathcal{G}$. $\square$

For Case II when the ASPs have no bound on their budgets, we have proved in Section VI B that the resource pricing scheme can be set up by solving the GNEP $\mathcal{G}_p$. Furthermore, we have also shown that the VE solution to $\mathcal{G}_p$ can be computed as the solution of an extended pricing game $\mathcal{Q}_+$. Now, we provide an online semi-decentralized learning algorithm that enables the ASPs and the NSP to reach the VE of $\mathcal{G}_p$. In the proposed semi-decentralized algorithm, we leverage on the framework from [48]: the first $S$ players, i.e., the ASPs, follow similar steps as in Algorithm 1. However, an $(S+1)^{th}$ player, i.e., the NSP, accumulates the augmented discounted gradients of its utility in the auxiliary variable $y_{S+1}$

$$ y_{S+1} = \lambda_m^c + \alpha_n \left[ \left( \sum_{s \in \mathcal{S}} d_{sm}^c - C_m^c \right) - \theta_n \lambda_n \right]. \quad (43) $$

Here rationale behind adding an extra term is that the original game is strictly monotone, and thus convergence is guaranteed in that case. However, the extended pricing game is just monotone and therefore, to make the algorithm converge to an equilibrium point, an additional term must be included [48]. NSP updates the market price by projecting the stored auxiliary variable on the positive orthant

$$ \lambda_m^c \leftarrow \text{proj}_{\mathbb{R} \ge 0} \left( \lambda_m^c + \alpha_n \left[ \left( \sum_{s \in \mathcal{S}} d_{sm}^c - C_m^c \right) - \theta_n \lambda_n \right] \right). \quad (44) $$

**Theorem 4.** [48] If Algorithm 2 satisfies the required conditions for step size sequence, e.g., $\sum_{n=0}^{+\infty} \alpha_n = +\infty$, $\alpha_n \to 0$ as $n \to +\infty$ and for an augmented sequence $\theta_n$, $\sum_{n=1}^{N} \frac{\alpha_n \theta_n}{\sum_{n=1}^{N} \alpha_n} \to 0$, $N \to 0$, then it converges to the unique equilibrium of the extended pricing game.

**Algorithm 2 Online Learning Algorithm for $\mathcal{Q}_+$**

**Require:** $\sum_{n=0}^{+\infty} \alpha_n = +\infty$, $\alpha_n \to 0$ as $n \to +\infty$

1. repeat $n = 1, 2, \dots,$

2. for each ASP $s \in \mathcal{S}$

3. Observe gradient of utility and update

4. $y_s \leftarrow [y_s + \alpha_n \nabla_{d_s} U_s(d_s, d_{-s}, \omega_s)]$

5. end for

6. for each ASP $s \in \mathcal{S}$

7. $d_s \leftarrow \text{proj}_{\mathcal{D}_s} [y_s]$

8. end for

9. NSP update the resource prices

10. for each Cell $c \in \mathcal{C}$

11. for each Resource $m \in \mathcal{M}$ update the base price

12. $\lambda_m^c \leftarrow \max [0, \lambda_m^c + \alpha_n (\sum_{s \in \mathcal{S}} d_{sm}^c - C_m^c)]$

13. end for

14. end for

15. until $\|(d(n), \omega(n)) - (d(n-1), \omega(n-1))\| \le \epsilon$

## B. A Distributed Proximal Algorithm

We assume a fully connected communication graph between the ASPs, e.g., $\Gamma_s \triangleq S \setminus \{s\}$, $\forall s \in S$. We want to compute the r-normalized Nash equilibrium solution of $\mathcal{G}_p$ relying on a fully distributed algorithm. To that purpose, we set $x_s^s \triangleq d_s$ as ASP $s$'s own action, $x_{-s}^s$ as ASP $s$'s estimate of the other ASPs' actions, and $x^s \triangleq \text{col}(x_s^s, x_{-s}^s)$ as the concatenation of ASP $s$'s own action and estimate of the others' actions. Let $\tilde{\mathcal{F}}_s \triangleq \{x_s^s | x_s^s \ge 0, \omega^T x_s^s = B_s\}$ be the strategy set of ASP $s$. Following [49], [50], we decompose the pricing game $\mathcal{G}_p$ per agent. Some slack variables $(v^{ss'})_{s,s'}$ and $(w_{ss'})_{s,s'}$ are introduced to guarantee the coincidence of the local copies. Let $M_{S-1}$ be the matrix made of $S-1$ blocks, each one of them containing the Identity matrix of size $\sum_c |\mathcal{M}^c| \times \sum_c |\mathcal{M}^c|$. Each ASP $s$ solves the local optimization problem

$$ \min_{\lambda_s \ge 0, (w_{ss'})_{s'} \in \tilde{\mathcal{F}}_{s'}(v^{ss'})_{s'}} \max_{x_s^s \in \tilde{\mathcal{F}}_{s'}(v^{ss'})_{s'}} [\mathcal{R}_s(x_s^s, x_{-s}^s) - \lambda_s^T(x_s^s + M_{S-1}x_{-s}^s - D)], \quad (45a) $$

$$ \text{s.t.} \quad x^{s'} = v^{s's''}, \forall s' \in S, \forall s'' \in \Gamma_{s'}, \quad (\alpha^{s's''}) \quad (45b) $$

$$ x^{s''} = v^{s's''}, \forall s' \in S, \forall s'' \in \Gamma_{s'}, \quad (\beta^{s's''}) \quad (45c) $$

$$ \lambda_{s'} = r_{s'} w_{s's''}, \forall s' \in S, \forall s'' \in \Gamma_{s'}, \quad (\gamma_{s's''}) \quad (45d) $$

$$ \lambda_{s''} = r_{s''} w_{s's''}, \forall s' \in S, \forall s'' \in \Gamma_{s'}. \quad (\delta_{s's''}) \quad (45e) $$

where $r_{s'} = \frac{1}{p_{s'}}$ and $r_{s''} = \frac{1}{p_{s''}}$, $\forall s' \in S$, $s'' \in \Gamma_{s'}$. Note that we use the convention to have superscript indices for primal variables, and lowerscript indices for duals of $\mathcal{G}_p$. A solution of $\mathcal{G}_p$ is obtained by assuming that each ASP $s$ solves the partial dual optimization problem (45) and by identifying $x_s^s = d_s$ and $\lambda_s = \frac{1}{r_s} \lambda$. Let $\zeta > 0$ be a scalar coefficient. We follow the alternating direction method of multipliers (ADMM). To that purpose, we explicit the Lagrangian function associated
with (45)

$$
\begin{align*}
& L_s(x^s, \{v, \alpha, \beta\}, \lambda_s, \{w, \gamma, \delta\}) \\
:= & \mathcal{R}_s(x^s) - \lambda_s^T (x_s^s + M_{S-1} x_{-s}^s - D) \\
& - \sum_{s'} \sum_{s'' \in \Gamma_{s'}} \left[ (\alpha^{s's''})^T (x^{s'} - v^{s's''}) + (\beta^{s's''})^T (x^{s''} - v^{s's''}) \right] \\
& + \sum_{s'} \sum_{s'' \in \Gamma_{s'}} \left[ \gamma_{s's''} (\lambda_{s'} - r_{s'} w_{s's''}) + \delta_{s's''} (\lambda_{s''} - r_{s''} w_{s's''}) \right],
\end{align*}
$$

and associated KKTs, which give rise to the following relationships: $\alpha^{ss'} + \beta^{ss'} = 0$ and $\gamma_{ss'} + \delta_{ss'} = 0, \forall s' \in \Gamma_s$.

To update the ASPs' strategies, we rely on the augmented Lagrangian associated with (45): $\tilde{L}_s(x^s, \{v, \alpha, \beta\}, \lambda_s, \{w, \gamma, \delta\}) \triangleq L_s(x^s, \{v, \alpha, \beta\}, \lambda_s, \{w, \gamma, \delta\}) - \frac{\zeta}{2} (\sum_{s'} \sum_{s'' \in \Gamma_{s'}} (\|x^{s'} - v^{s's''}\|^2 + \|x^{s''} - v^{s's''}\|^2)) + \frac{\zeta}{2} (\sum_{s'} \sum_{s'' \in \Gamma_{s'}} ((\lambda_{s'} - r_{s'} w_{s's''})^2 + (\lambda_{s''} - r_{s''} w_{s's''})^2)).$ Following vanilla ADMM, the duals in (45) are updated according to the rules

$$
\alpha^{s's''}(t) = \alpha^{s's''}(t-1) + \frac{\zeta}{2}(x^{s'}(t-1) - x^{s''}(t-1)), \quad (46a)
$$

$$
\beta^{s's''}(t) = \beta^{s's''}(t-1) + \frac{\zeta}{2}(x^{s''}(t-1) - x^{s'}(t-1)), \quad (46b)
$$

$$
\gamma_{s's''}(t) = \gamma_{s's''}(t-1) + \frac{\zeta}{2} \left( \frac{\lambda_{s'}(t-1)}{r_{s'}} - \frac{\lambda_{s''}(t-1)}{r_{s''}} \right), \quad (46c)
$$

$$
\delta_{s's''}(t) = \delta_{s's''}(t-1) + \frac{\zeta}{2} \left( \frac{\lambda_{s''}(t-1)}{r_{s''}} - \frac{\lambda_{s'}(t-1)}{r_{s'}} \right). \quad (46d)
$$

We update the slacks $v, w$ by solving the following optimization problems

$$
v^{ss'}(t) = \arg \max_{v^{ss'}} \tilde{L}_s \left( x^s(t-1), \{v, \alpha(t), \beta(t)\}, \lambda_s(t-1), \{w(t-1), \gamma(t), \delta(t)\} \right), \quad (47a)
$$

$$
w_{ss'}(t) = \arg \min_{w_{ss'}} \tilde{L}_s \left( x^s(t-1), \{v(t), \alpha(t), \beta(t)\}, \lambda_s(t-1), \{w, \gamma(t), \delta(t)\} \right). \quad (47b)
$$

Assuming that $\alpha^{ss'}(0) = \beta^{ss'}(0) = 0$ and $\gamma_{ss'}(0) = \delta_{ss'}(0) = 0$ and relying on (46a)-(46d), the slack update rules (47a)-(47b) give rise to the following closed form expressions

$$
v^{s's''}(t) = \frac{1}{2}(x^{s'}(t-1) + x^{s''}(t-1)), \quad (48a)
$$

$$
w_{s's''}(t) = \frac{1}{2} \left( \frac{\lambda_{s'}(t-1)}{r_{s'}} + \frac{\lambda_{s''}(t-1)}{r_{s''}} \right). \quad (48b)
$$

Set $\Phi^s \triangleq \sum_{s' \in \Gamma_s} (\alpha^{ss'} + \beta^{s's})$ and $\Psi_s \triangleq \sum_{s' \in \Gamma_s} (\gamma_{s's} + \delta_{s's})$. From (46a)-(46b) and (46c)-(46d), we get that $\Phi$ and $\Psi$ are updated according to the rules

$$
\Phi^s(t) = \Phi^s(t-1) + \zeta \sum_{s' \in \Gamma_s} (x^s(t-1) - x^{s'}(t-1)), \quad (49a)
$$

$$
\Psi_s(t) = \Psi_s(t-1) + \zeta \sum_{s' \in \Gamma_s} \left( \frac{\lambda_s(t-1)}{r_s} - \frac{\lambda_{s'}(t-1)}{r_{s'}} \right). \quad (49b)
$$

Let $\tilde{\beta}_s > 0$ be a penalty factor for the proximal first-order approximation for $s \in S$.

Following [50], from (48a)-(48b), the primal update rule for

**Algorithm 3 Distributed Proximal Algorithm for G<sub>p</sub>**

Require: $\zeta > 0, \tilde{\beta}_s > 0, \forall s \in S, \epsilon_{stop}^{primal}, \epsilon_{stop}^{dual}, t_{max}$

1: $\# \text{ Initialization Step}$

2: Each ASP *s* builds initial estimate *x*^s(0) ∈ **F̃** and λ_s(0) ≥ 0

3: Set α^{ss'} = β^{ss'} = 0 and γ_{ss'} = δ_{ss'} = 0, ∀s ∈ S, ∀s' ∈ Γ_s

4: **while** $\epsilon^{primal}(t) \ge \epsilon^{primal}_{stop} \lor \epsilon^{dual}(t) \ge \epsilon^{dual}_{stop} \land t \le t_{max}$

5: $\# \text{ Communication Step}$

6: Each ASP *s* exchanges his previous estimate *x*^s(*t*−1) and his dual Lagrange multiplier λ_s(*t* − 1) with his neighbors *s*′ ∈ Γ_s

7: $\# \text{ Action Step Update}$

8: **for each** ASP *s* ∈ *S*

9: $\Phi^s(t)$ is updated according to (49a)

10: $\Psi^s(t)$ is updated according to (49b)

11: $x_s^s(t)$ is updated by solving (50)

12: $\lambda_s(t)$ is updated according to (51)

13: $x_{-s}^{s}(t)$ is updated according to (52)

14: **end for**

$t = t + 1$

15: **end while**

ASP *s* is obtained by solving a local optimization problem

$$
x_s^s(t) = \arg \max_{x_s^s \in \tilde{\mathcal{F}}_s} \left\{ \nabla_{x_s^s} \mathcal{R}_s (x^s(t-1))^T (x_s^s - x_s^s(t-1)) - \frac{1}{2\zeta|\Gamma_s^s|} \left[ 2\zeta r_s \sum_{s' \in \Gamma_s} \frac{\lambda_s(t-1) + \lambda_{s'}(t-1)}{r_s + r_{s'}} - \Psi_s(t) + x_s^s(t-1) + M_{S-1}x_{-s}^s(t-1) - D \right]^T (x_s^s - x_s^s(t-1)) - \frac{\tilde{\beta}_s}{2} \|x_s^s - x_s^s(t-1)\|^2 - \Phi_s^s(t)^T x_s^s - \zeta \sum_{s' \in \Gamma_s} \|x_s^s - \frac{x_s^s(t-1) + x_{s'}^s(t-1)}{2}\|^2 \right\}. \quad (50)
$$

Dual update rule takes the form

$$
\lambda_s(t) = \text{proj}_{\mathbb{R}_{+}^{\sum_c |\mathcal{M}^c|}} \left( \frac{1}{2\zeta|\Gamma_s|} (x_s^s(t) + M_{S-1}x_{-s}^s(t-1) - D - \Psi_s(t) + 2\zeta r_s \sum_{s' \in \Gamma_s} \frac{\lambda_s(t-1) + \lambda_{s'}(t-1)}{r_s + r_{s'}}) \right). \quad (51)
$$

Let $\tilde{\mathcal{F}}_{-s} \triangleq \prod_{s' \neq s} \tilde{\mathcal{F}}_{s'} \subseteq \mathbb{R}_+^{(S-1)\sum_c |\mathcal{M}^c|}$. It is a closed set as the product of closed sets. The mapping $\text{proj}_{\tilde{\mathcal{F}}_{-s}} : \mathbb{R}_+^{(S-1)\sum_c |\mathcal{M}^c|} \to \tilde{\mathcal{F}}_{-s}$ denotes the projection onto $\tilde{\mathcal{F}}_{-s}$. Update of ASP $s$'s estimates can be obtained as

$$
x_{-s}^{s}(t) = \text{proj}_{\tilde{\mathcal{F}}_{-s}} \left( \frac{1}{2} (x_{-s}^{s}(t-1) + \frac{1}{|\Gamma_s|} \sum_{s' \in \Gamma_s} x_{-s}^{s'}(t-1)) - \frac{1}{2\zeta|\Gamma_s|} \Phi_{-s}^{s}(t) \right). \quad (52)
$$

**Theorem 5.** If $f_s^c(\cdot)$ is $K_s^c$ Lipschitz continuous for all $s \in S$, $c \in C$, Algorithm 3 converges to the r-normalized Nash equilibrium solution to $\mathcal{G}_p$.
<table><caption>TABLE III
DESCRIPTION OF THE PARAMETERS ($v_{s,r}$) IN THE ASPS' QoS FUNCTION.</caption><thead><tr><th rowspan="2"></th><th colspan="2">ASP 1</th><th colspan="2">ASP 2</th></tr><tr><th>ASP<sub>11</sub></th><th>ASP<sub>12</sub></th><th>ASP<sub>21</sub></th><th>ASP<sub>22</sub></th></tr></thead><tbody><tr><th>Bandwidth ($v_{BW}$)</th><td>10</td><td>5</td><td>10</td><td>5</td></tr><tr><th>VCPU($v_{vCPU}$)</th><td>32</td><td>20</td><td>40</td><td>36</td></tr><tr><th>Memory ($v_{MEM}$)</th><td>244</td><td>80</td><td>160</td><td>70</td></tr></tbody></table>

*Proof.* See Appendix D. □

<figure><img src="image_5.png" /></figure>

## VIII. NUMERICAL EXPERIMENTS

In this section, we consider two numerical experiments to validate the proposed pricing and the multi-resource allocation schemes. In the first experiment, described in Section VIII.A, we consider the first case when application service providers own the finite budgets to procure the resources. In the second experiment, illustrated in Section VIII.B, we consider the second case where ASPs are not limited by their budgets.

### A. Numerical Experiment 1

In this experiment we consider a more general setting where ASPs can support multiple services; one service being defined per slice. For each type of service provisioning, ASPs require various kinds of resources. In this scenario, particularly to define the QoS as a function of multi resources, we consider a general class of utility function known as CES (constant elasticity of substitution), mathematically defined as

$$q_s(d_s) = \left( \sum_r v_{skr} (d_{skr})^\rho \right)^{1/\rho},$$

where $\rho \in (-\infty, 0) \cup (0, 1]$ can be used to parametrize the whole family of utility functions. For example $\rho = 1$ corresponds to linear (additive) valuations $q_s(d_s) = \sum_r v_{sr}d_{sr}$, $\rho \to 0$ corresponds to Cobb Douglas function $q_s(d_s) = \Pi_r(d_{sr})^{v_{sr}}$, $\rho \to -\infty$ correspond to Leontief utility functions $q_s(d_s) = \min_r \{\frac{d_{sr}}{v_{sr}}\}$, and $D_s = (v_{s1}...v_{sr})$, where $v_{sr}$ is the amount of resource type $r$ needed by ASP $s$ to support one unit of QoS. Linear valuation signifies the perfect substitutes, representing a scenario where the resources can replace each other in utilization. On the contrary, Leontief utility functions represent the perfect complement scenario where one resource may have no value without the other. For instance, the CPU and computer memory are both essential for completing a computing task. CSE utility function interpolate between perfect substitutes and the perfect complement through the parameter $\rho$. We consider that application service providers ASP 1 and ASP 2 support two types of services. ASP 1 and ASP 2 provide the service type 1 through slice $ASP_{11}$ and slice $ASP_{21}$, while they provide service type 2 through slice $ASP_{12}$ and $ASP_{22}$ respectively. We consider the number of end-users demanding service type 1 and service type 2 at cell $C_1$ are 120 and 180, while their numbers at cell $C_2$ are 130 and 170, respectively.

For numerical experiments, we consider that each service needs three types of resources, namely, Bandwidth (Gbps), vCPU, Memory (GB). We consider that the total available capacity of bandwidth and vCPU memory is fixed at 40 Mhz, 60 units and 400 GB respectively. The values of parameters $v_{sr}$ for the application service providers and their respective services (slices) are as described in the table.

We apply our online learning algorithm to compute a NE. To evaluate the performance of the proposed allocation mechanism, we compare the revenue gained through the proposed resource allocation with three different baseline allocation schemes; first, with the static proportional resource allocation scheme (SS), where each resource required by the application service providers are allocated in proportion to their budgets; second, with the Fisher market equilibrium based resource allocation scheme (FM) proposed in [21] and [22]. We calculate the market equilibrium as a solution to the Eisenberg-Gale optimization problem, where the objective is to maximize the weighted proportional quality of service provided by ASPs

$$\text{maximize} \quad \sum_{s} \sum_{c} \sum_{k} B_s N_{ck} \log (q_{ck}^{s}(d_{ck}^{s})), \quad (53a)$$

$$\text{subject to} \quad \sum_{s} \sum_{k} d_{ckm}^{c} \leq D_{m}^{c} \quad \forall c \in C, m \in \mathcal{M}. \quad (53b)$$

Third, we compare our proposed allocation scheme with the well-known socially optimal resource allocation scheme (SO), where resources are allocated to ASPs such that the weighted sum of the QoS provided by the ASPs is maximized [51]

$$\text{maximize} \quad \sum_{s} \sum_{c} \sum_{k} B_s N_k^c q_{sk}^c (d_{sk}^c), \quad (54a)$$

$$\text{subject to} \quad \sum_{s} \sum_{k} d_{ckm}^{c} \leq D_{m}^{c} \quad \forall c \in C, m \in \mathcal{M}. \quad (54b)$$

For numerical simulations, we consider different values of parameter $\rho = 0.5, -5$ and budget $B_1 = 0.5$ and $B_1 = 0.7$. The bar graphs in Fig. 3 describe the respective revenue obtained by the ASPs under NE, SS, FM, and SO based resource allocations. We observe from the bar graphs that the revenues gained by ASPs for different values of parameters under NE and SS are almost equal and are in proportion to the budgets owned by the ASPs. We can observe that ASP with high marginal quality of service and high budget gains the maximum revenue under SO allocation. Thus, even if SO-based distribution maximizes the total system performance, it is at the cost of poor fairness in allocation. For the FM-based scheme, in Fig. 3(c), we observe that even though ASP 1 has a higher budget than ASP 2, ASP 1 gains less revenue than ASP 2; again, this is also not fair from a business point of view. The bar graphs in Fig. 3(e) describe the distribution of revenue gained by the ASPs from their different slices.

### B. Numerical Experiment 2

We consider that application service providers ASP 1 and ASP 2 offer a service type 1 from the previous experiment.
<figure><img src="image_6.png" /><figcaption>Fig. 3. ASPs' revenues at the NE of game *G* vs ASPs' revenues under static proportional allocation scheme (SS), Fisher market based resource allocation (FM), Socially optimal resource allocation (SO) a) for ρ = 0.5, B₁ = 0.5 and B₂ = 0.5; b) for ρ = -5, B₁ = 0.5 and B₂ = 0.5; c) for ρ = 0.5, B₁ = 0.7 and B₂ = 0.3; d) for ρ = -5, B₁ = 0.7 and B₂ = 0.3. ASPs' revenues for ρ = 0.5, B₁ = 0.5 and B₂ = 0.5 from e) service type 1; f) service type 2; and comparison of the ASPs' revenues for ρ = -5, B₁ = 0.7, B₂ = 0.3 from g) service type 1; h) service type 2.</figcaption></figure>

For the bandwidth and vCPU, we keep their total availability fixed. At the same time, for the memory, we vary the available capacity from 100 GB to 400 GB, and we examine the its effects on the resources' prices. First, we consider the case where the QoS provided by ASPs follows a substitutable relationship between resources, e.g., we rely on the CSE function with ρ = 0.1. Fig. 4(a) illustrates the effect of available capacity of resources on the resources price. As the total availability of memory increases. In this case, the cost of memory decreases. However, as the relationship between the resources is substitutable, we observe from the figure that a change in memory availability does not affect the price of the other resources.

Next, we consider the scenario where the ASPs' QoS is
defined by the CSE function with ρ = -1.5. In this case, the
relationship between the resources is more complementary than
the previous one. Fig. 4(b) illustrates the effect of available
capacity of resources on the resources price. As the availability
of memory increases, the cost of memory decreases. However,
in this case, we observe that a change in memory availability
also affects the price of the other resources. The cost of
bandwidth and VCPU also increases with a rise in memory's
availability. An increase in the capacity of memory gives ASPs
room to improve their QoS, but at the cost of increasing the
other related resources, Bandwidth and VCPU. Thus, it causes
congestion at Bandwidth and VCPU hence resulting in a rise in
their prices. Similarly, Fig. 4(d) presents a change in the prices
of the resources with respect to the capacity of the memory

where QoS is considered a CSE function with ρ = -2.5. In
Fig. 4(d) we demonstrate the fast convergence of Algorithm
3. For simulation purposes, we consider the availability of
Bandwidth, VCPU and Memory as 40 Gbps 60 units and
100 GB, respectively. The plot in the figure shows the exact
convergence of total demand for all three resources to their
available capacity. Fig. 4(e) shows the convergence of error
in decision variable (resources' demand) by the ASPs and the
convergence of error in price λ.

IX. CONCLUSION

In this work, we have considered a setting where application
service providers lease resources from an network slice provider
through a network slicing mechanism and compete with one
another to serve a large pool of end-users. We have shown
that the interactions between the end-users and application
service providers can be modelled as a Stackelberg game,
where the ASPs act as leaders and the end-users as followers.
In addition, we have proved that the competition between
the ASPs results in a multi-resource Tullock rent-seeking
game, which admits a unique Nash equilibrium. The market
price is computed by the NSP for each resource, taking into
account the finite capacity of the network. To compute the
market price and resource allocation, we have proposed two
innovative market mechanisms. First, we have implemented a
trading post mechanism taking into account the fact that the
ASPs have bounds on their budgets. We have proved that the
non-cooperative game induced by the trading post mechanism
<figure><img src="image_7.png" /><figcaption>Fig. 4. Changes in the price (λ) with respect to the available memory capacity, with a) ρ = 0.1, b) ρ = -1.5, and c) ρ = -2.5. d) Convergence of Algorithm 3, convergence of total resources' demand to the available capacity. e) Convergence of the primal and dual errors in Algorithm 3.</figcaption></figure>

admits a unique Nash equilibrium in case a single resource is considered. We have implemented a semi-decentralized exponential learning algorithm to compute the unique Nash equilibrium of this game. However, this mechanism does not enable an explicit incorporation of the network finite capacity constraints. To overcome that limitation, in a second design, when ASPs have no bound on their budgets but take into account the network finite capacity as a global coupling constraint, we have shown that the market equilibrium can be obtained by solving a generalized Nash equilibrium problem. We have provided a dual averaging-based semi-decentralized algorithm to compute solution of the extended game reformulation of the pricing game, and a proximal inexact- ADMM based distributed algorithm that provably converges to the Variational equilibrium of the pricing game. Finally, we have provided numerical results to analyse the economic properties of the two market designs, and confirm the fast convergence rate of the inexact-ADMM highlighting its practical applicability.

# APPENDIX

## A. Proof of Proposition 1

To find the equilibrium of the replicator dynamics defined in (6) consider $\log(\frac{q_s^c}{n_s^c}) - p_s = \log(\frac{q_{s'}^c}{n_{s'}^c}) - p_{s'}$. Taking the exponential of both sides, we obtain $\frac{q_s^c}{n_s^c} \frac{n_{s'}^c}{q_{s'}^c} = e^{p_s - p_{s'}} \Leftrightarrow \frac{q_s^c}{n_s^c} n_{s'}^c = q_{s'}^c e^{p_s - p_{s'}}$. Summing over all $s' \in S$ gives us $\sum_{s'} \frac{q_s^c}{n_s^c} n_{s'}^c = \sum_{s'} q_{s'}^c e^{p_s - p_{s'}}$, which can be rewritten as

$$n_s^c = \frac{N^c q_s^c e^{-p_s}}{\sum_{s'} q_{s'}^c e^{-p_{s'}}}, \text{ i.e., } n_s^c = \frac{N^c \int_{s}^{c} f_s^c(d_s^c) e^{-p_s}}{\sum_{s'} \int_{s'}^{c} f_{s'}^c(d_{s'}^c) e^{-p_{s'}}}.$$

## B. Proof of Proposition 3

Consider that for any bid $b_2^c > 0$ submitted by ASP 2 at cell c, ASP 1 places a bid of $b_1^c = B_1 \frac{b_2^c}{B_2}$ at cell c. Then, the quantity of resource received by ASP 1 at cell c is $d_1^c = \frac{B_1 \frac{b_2^c}{B_2}}{B_1 \frac{b_2^c}{B_2} + b_2^c} = \frac{B_1}{B_1+B_2}$. This proves that for any strategy played by ASP there exists a strategy for the other ASP such that he receives the resource in proportion to his budget.

## C. Revision Protocol

Let recall the revision protocol, which defines the switching rate at which users switch their choice from ASP s to ASP s' given population state $n \tau_{s,s'} = n_{s'}[\nu_{s'} - \nu_s]_+$. Note that for the sake of simplicity, we omit the cell dependence (c).

Relying on the evolutionary process (4) and by substitution of the revision protocol, we get

$$\begin{align*}
\dot{n}_s &= \sum_{s'} n_{s'} \tau_{s',s} - n_s \sum_{s'} \tau_{s,s'}, \\
\dot{n}_s &= \sum_{s'} n_{s'} n_s [\nu_s - \nu_{s'}]_+ - n_s \sum_{s'} n_{s'} [\nu_{s'} - \nu_s]_+, \\
\dot{n}_s &= n_s \sum_{s'} n_{s'} [\nu_s - \nu_{s'}], \\
\dot{n}_s &= n_s \left[ \nu_s - \sum_{s'} n_{s'} \nu_{s'} \right].
\end{align*}$$
Similarly, considering the revision protocol $\tau_{s,s'} = \frac{n_{s'}}{N}[U_s^c - U_s]_+$, we get

$$ \dot{n}_s = \sum_{s'} n_{s'} \tau_{s',s} - n_s \sum_{s'} \tau_{s,s'}, $$

$$ \dot{n}_s = \sum_{s'} n_{s'} \frac{n_s}{N} [\nu_s^c - \nu_{s'}^c]_+ - n_s \sum_{s'} \frac{n_{s'}}{N} [\nu_{s'}^c - \nu_s^c]_+ $$

$$ \dot{n}_s = n_s \sum_{s'} \frac{n_{s'}}{N} [\nu_s - \nu_{s'}], $$

$$ \dot{n}_s^c = n_s^c \left[ \nu_s^c - \frac{1}{N} \sum_{s'} n_{s'}^c \nu_{s'}^c \right]. $$

### D. Proof of Theorem 5

Taking the gradient of $R_s(.)$ with respect to $x_s^c := d_s$, we obtain:

$$ \nabla_{x_s^c} R_s(d) = \sum_c p_s N^c \frac{\nabla_{x_s^c} f_c^c(d_s^c) e^{-p_s}}{\left(\sum_{s'} f_{s'}^c(d_{s'}^c) e^{-p_{s'}}\right)^2} \sum_{s' \neq s} f_{s'}^c(d_{s'}^c) e^{-p_{s'}} $$

$$ \text{For any } d, \tilde{d} \in \mathcal{F}, \quad \|\nabla_{x_s^c} R_s(d) - \nabla_{x_s^c} R_s(\tilde{d})\| \le \sum_c p_s N^c \max \left\{ \frac{\nabla_{x_s^c} f_c^c(d_s^c) e^{-p_s}}{\left(\sum_{s'} f_{s'}^c(d_{s'}^c) e^{-p_{s'}}\right)^2}, \frac{\nabla_{x_s^c} f_c^c(\tilde{d}_s^c) e^{-p_s}}{\left(\sum_{s'} f_{s'}^c(\tilde{d}_{s'}^c) e^{-p_{s'}}\right)^2} \right\}. $$

$$ \|\sum_{s' \neq s} f_{s'}^c(\tilde{d}_{s'}^c) e^{-p_{s'}} - \sum_{s'} f_{s'}^c(\tilde{d}_{s'}^c) e^{-p_{s'}}\| \text{ by Hölder inequality. Then, applying Jensen's inequality, we obtain that } \|\nabla_{x_s^c} R_s(d) - \nabla_{x_s^c} R_s(\tilde{d})\| \le $$

$$ \sum_c p_s N^c \max \left\{ \frac{\nabla_{x_s^c} f_c^c(d_s^c) e^{-p_s}}{\left(\sum_{s'} f_{s'}^c(d_{s'}^c) e^{-p_{s'}}\right)^2}, \frac{\nabla_{x_s^c} f_c^c(\tilde{d}_s^c) e^{-p_s}}{\left(\sum_{s'} f_{s'}^c(\tilde{d}_{s'}^c) e^{-p_{s'}}\right)^2} \right\}. $$

$$ \sum_{s' \neq s} \|f_{s'}^c(d_{s'}^c) - f_s^c(\tilde{d}_s^c)\|. \quad \text{If } f_{s'}^c(\cdot) \text{ is } K_s^c \text{ Lipschitz continuous then by setting } L_s := $$

$$ \sum_c p_s N^c \max \left\{ \frac{\nabla_{x_s^c} f_c^c(d_s^c) e^{-p_s}}{\left(\sum_{s'} f_{s'}^c(d_{s'}^c) e^{-p_{s'}}\right)^2}, \frac{\nabla_{x_s^c} f_c^c(\tilde{d}_s^c) e^{-p_s}}{\left(\sum_{s'} f_{s'}^c(\tilde{d}_{s'}^c) e^{-p_{s'}}\right)^2} \right\} $$

then for any $d, \tilde{d} \in \mathcal{F}$, $\|\nabla_{x_s^c} R_s(d) - \nabla_{x_s^c} R_s(\tilde{d})\| \le L_s \|d - \tilde{d}\|_1 \le L_s \sqrt{S \cdot \sum_c |M^c|} \|d - \tilde{d}\|_2$. This proves that $\nabla_{x_s^c} R_s(.)$ is $L_s \sqrt{S \cdot \sum_c |M^c|}$ Lipschitz continuous. In addition, the coupling constraints in the pricing game $G_p$ are linear in the ASPs' decision variables. Though we introduce projection operators in (51), (52), Cauchy-Schwarz inequality implies that the norm of the projection matrix can be upper bounded by 1. This enables us to derive the same upper bound and statement as in [50], Thm.1.

### REFERENCES

[1] M. Datar and E. Altman, “Strategic Resource Management in 5G Network Slicing. (Invited paper),” in *ITC 33 - Networked Systems and Services*, Avignon, France, Aug. 2021. [Online]. Available: https://hal.inria.fr/hal-03333659

[2] “GSMA-An-Introduction-to-Network-Slicing,” Tech. Rep. [Online]. Available: https://www.gsma.com/futurenetworks/wp-content/uploads/2017/11/GSMA-An-Introduction-to-Network-Slicing.pdf

[3] P. Caballero, A. Banchs, G. de Veciana, and X. Costa-Pérez, “Network slicing games: Enabling customization in multi-tenant networks,” in *IEEE INFOCOM 2017 - IEEE Conference on Computer Communications*, 2017, pp. 1–9.

[4] A. Lieto, I. Malanchini, S. Mandelli, E. Moro, and A. Capone, “Strategic network slicing management in radio access networks,” *IEEE Transactions on Mobile Computing*, doi: 10.1109/TMC.2020.3025027.

[5] J. Ordonez-Lucena, P. Ameigeiras, D. Lopez, and J. J. Ramos-Munoz, “Network Slicing for 5G with SDN/NFV: concepts, Architectures, and Challenges,” *IEEE communications Magazine*, vol. 55, no. 5, pp. 80–87, 2017.

[6] L. Duan, J. Huang, and B. Shou, “Duopoly competition in dynamic spectrum leasing and pricing,” *IEEE Transactions on Mobile Computing*, vol. 11, no. 11, pp. 1706–1719, 2012.

[7] O. Korcak, G. Iosifidis, T. Alpcan, and I. Koutsopoulos, “Operator collusion and market regulation policies for wireless spectrum management,” *IEEE Transactions on Mobile Computing*, vol. 15, no. 10, pp. 2537–2549, 2016.

[8] X. Li, B. Gu, C. Zhang, Z. Liu, K. Yamori, and Y. Tanaka, “Duopoly price competition in secondary spectrum markets,” in *2017 13th International Conference on Network and Service Management (CNSM)*, 2017, pp. 1–5.

[9] F. Sun, F. Hou, H. Zhou, B. Liu, J. Chen, and L. Gui, “Equilibriums in the mobile-virtual-network-operator-oriented data offloading,” *IEEE Transactions on Vehicular Technology*, vol. 67, no. 2, pp. 1622–1634, 2018.

[10] S. D’Oro, L. Galluccio, S. Palazzo, and G. Schembra, “A game theoretic approach for distributed resource allocation and orchestration of software networks,” *IEEE Journal on Selected Areas in Communications*, vol. 35, no. 3, pp. 721–735, 2017.

[11] R. E. Azouzi, E. Altman, and L. Wynter, “Telecommunications network equilibrium with price and quality-of-service characteristics,” in *Providing Quality of Service in Heterogeneous Environments*, ser. Teletraffic Science and Engineering, J. Charzinski, R. Lehnert, and P. Tran-Gia, Eds. Elsevier, 2003, vol. 5, pp. 369–378. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S138834730801828

[12] C. Li, J. Li, Y. Li, and Z. Han, “Pricing game with complete or incomplete information about spectrum inventories for mobile virtual network operators,” *IEEE Transactions on Vehicular Technology*, vol. 68, no. 11, pp. 11 118–11 131, 2019.

[13] W. Xie, J. Zhu, C. Huang, M. Luo, and W. Chou, “Network virtualization with dynamic resource pooling and trading mechanism,” in *2014 IEEE Global Communications Conference*. IEEE, 2014, pp. 1829–1835.

[14] L. Cano, G. Carello, M. Cesana, M. Passacantando, and B. Sansò, “Modeling the techno-economic interactions of infrastructure and service providers in 5G networks with a multi-leader-follower game,” *IEEE Access*, vol. 7, pp. 162 913–162 940, 2019.

[15] T. M. Ho, N. H. Tran, S. A. Kazmi, and C. S. Hong, “Dynamic pricing for resource allocation in wireless network virtualization: A Stackelberg game approach,” in *2017 International Conference on Information Networking (ICOIN)*. IEEE, 2017, pp. 429–434.

[16] J. Hu, Z. Zheng, B. Di, and L. Song, “Tri-level Stackelberg game for resource allocation in radio access network slicing,” in *2018 IEEE Global Communications Conference (GLOBECOM)*. IEEE, 2018, pp. 1–6.

[17] T. D. Tran and L. B. Le, “Resource allocation for multi-tenant network slicing: A multi-leader multi-follower stackelberg game approach,” *IEEE Transactions on Vehicular Technology*, vol. 69, no. 8, pp. 8886–8899, 2020.

[18] S. A. Kazmi, N. H. Tran, T. M. Ho, and C. S. Hong, “Hierarchical matching game for service selection and resource purchasing in wireless network virtualization,” *IEEE Communications Letters*, vol. 22, no. 1, pp. 121–124, 2017.

[19] N. Raveendran, Y. Gu, C. Jiang, N. H. Tran, M. Pan, L. Song, and Z. Han, “Cyclic three-sided matching game inspired wireless network virtualization,” *IEEE Transactions on Mobile Computing*, vol. 20, no. 2, pp. 416–428, 2019.

[20] M. H. Lotfi and S. Sarkar, “The economics of competition and cooperation between MNOs and MVNOs,” in *2017 51st Annual Conference on Information Sciences and Systems (CISS)*. IEEE, 2017, pp. 1–6.

[21] D. T. Nguyen, L. Le, and V. Bhargava, “A Market-Based Framework for Multi-Resource Allocation in Fog Computing,” *IEEE/ACM Transactions on Networking*, vol. 27, pp. 1151–1164, 2019.

[22] E. Moro and I. Filippini, “Joint Management of Compute and Radio Resources in Mobile Edge Computing: a Market Equilibrium Approach,” *ArXiv*, vol. abs/1011.05950, 2020.

[23] S. A. Kazmi, A. Ndikumana, A. Manzoor, W. Saad, C. S. Hong et al., “Distributed radio slice allocation in wireless network virtualization: Matching theory meets auctions,” *IEEE Access*, vol. 8, pp. 73 494–73 507, 2020.

[24] L. Guijarro, J. R. Vidal, and V. Pla, “Competition in service provision between slice operators in 5g networks,” *Electronics*, vol. 7, no. 11, 2018. [Online]. Available: https://www.mdpi.com/2079-9292/7/11/315

[25] S. D’Oro, L. Galluccio, P. Mertikopoulos, G. Morabito, and S. Palazzo, “Auction-based resource allocation in openflow multi-tenant networks,” *Computer Networks*, vol. 115, pp. 29–41, 2017.

[26] M. Datar, E. Altman, F. D. Pellegrini, R. E. Azouzi, and C. Touati, “A mechanism for price differentiation and slicing in wireless networks,” in *18th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, WiOPT 2020, Volos, spectrum leasing and pricing,” IEEE Transactions on Mobile Computing, vol. 11, no. 11, pp. 1706–1719, 2012.
*Greece, June 15-19, 2020.* IEEE, 2020, pp. 1–8. [Online]. Available: https://ieeexplore.ieee.org/document/9155243

[27] Y. K. Tun, N. H. Tran, D. Ngo, S. R. Pandey, Z. Han, and C. Hong, "Wireless network slicing: Generalized kelly mechanism-based resource allocation," *IEEE Journal on Selected Areas in Communications*, vol. 37, pp. 1794–1807, 2019.

[28] J. Zheng, P. Caballero, G. de Veciana, S. J. Baek, and A. Banchs, "Statistical multiplexing and traffic shaping games for network slicing," *IEEE/ACM Trans. Netw.*, vol. 26, no. 6, pp. 2528–2541, Dec. 2018.

[29] E. Altman, M. Datar, G. Burnside, and C. Touati, "Normalized equilibrium in tullock rent seeking game," in *Game Theory for Networks - 8th International EAI Conference, GameNets 2019, Paris, France, April 25-26, 2019, Proceedings*, K. Avrachenkov, L. Huang, J. R. Marden, M. Coupechoux, and A. Giovanidis, Eds. [Online]. Available: https://doi.org/10.1007/978-3-030-16989-3_8

[30] A. Reiffers-Masson, Y. Hayel, and E. Altman, "Game theory approach for modeling competition over visibility on social networks," in *Sixth International Conference on Communication Systems and Networks, COMSNETS 2014, Bangalore, India, January 6-10, 2014*. IEEE, 2014, pp. 1–6. [Online]. Available: https://doi.org/10.1109/COMSNETS.2014.6734939

[31] T. Luo, S. S. Kanhere, H. Tan, F. Wu, and H. Wu, "Crowdsourcing with tullock contests: A new perspective," in *2015 IEEE Conference on Computer Communications (INFOCOM)*, 2015, pp. 2515–2523.

[32] S. Raj Pokhrel and C. Williamson, "A rent-seeking framework for multipath tcp," *SIGMETRICS Perform. Eval. Rev.*, vol. 48, no. 3, p. 63–70, Mar. 2021. [Online]. Available: https://doi.org/10.1145/3453953.3453968

[33] E. Altman, D. Menasché, A. Reiffers-Masson, M. Datar, S. Dhamal, C. Touati, and R. El-Azouzi, "Blockchain competition between miners: A game theoretic perspective," *Frontiers in Blockchain*, vol. 2, p. 26, 2020. [Online]. Available: https://www.frontiersin.org/article/10.3389/fbloc.2019.00026

[34] W. H. Sandholm, *Population Games and Evolutionary Dynamics*. MIT Press, 2010.

[35] G. Tullock, *Rent Seeking*, ser. Books. Edward Elgar Publishing, March undated, no. 383. [Online]. Available: https://ideas.repec.org/b/elg/eebook/383.html

[36] F. Bernstein and A. Federgruen, "A general equilibrium model for industries with price and service competition," *Operations Research*, vol. 52, no. 6, pp. 868–886, 2004. [Online]. Available: https://doi.org/10.1287/opre.1040.0149

[37] M. J. Osborne, *An Introduction to Game Theory*. Oxford University Press, New York, 2004, vol. 3, no. 3.

[38] J. B. Rosen, "Existence and uniqueness of equilibrium points for concave n-person games," *Econometrica*, vol. 33, no. 3, pp. 520–534, 1965. [Online]. Available: http://www.jstor.org/stable/1911749

[39] J. C. Goodman, "Note on existence and uniqueness of equilibrium points for concave n-person games," *Econometrica*, vol. 48, no. 1, p. 180. [Online]. Available: https://EconPapers.repec.org/RePEc:ecm:emetrp:v:48:y:1980:i:1:p:251

[40] A. Orda, R. Rom, and N. Shimkin, "Competitive routing in multiuser communication networks," *IEEE/ACM Transactions on Networking*, vol. 1, no. 5, pp. 510–521, 1993.

[41] L. Shapley and M. Shubik, "Trade using one commodity as a means of payment," *Journal of Political Economy*, vol. 85, no. 5, pp. 937–968, 1977. [Online]. Available: http://www.jstor.org/stable/1830340

[42] A. A. Kulkarni and U. V. Shanbhag, "On the variational equilibrium as a refinement of the generalized nash equilibrium," *Automatica*, vol. 48, no. 1, pp. 45–55, 2012.

[43] L. Pavel, "An extension of duality to a game-theoretic framework," *Automatica*, vol. 43, no. 2, p. 226–237, Feb. 2007. [Online]. Available: https://doi.org/10.1016/j.automatica.2006.08.027

[44] D. Paccagnan, B. Gentile, F. Parise, M. Kamgarpour, and J. Lygeros, "Distributed computation of generalized nash equilibria in quadratic aggregative games with affine coupling constraints." *IEEE* 55th Conference on Decision and Control (CDC), 2016.

[45] ——, "Nash and warddrop equilibria in aggregative games with coupling constraints," *IEEE Transactions on Automatic Control*, vol. 64, no. 4, pp. 1376–1388, 2019.

[46] G. Scutari, F. Facchinei, J. Pang, and D. P. Palomar, "Real and complex monotone communication games," *IEEE Transactions on Information Theory*, vol. 60, no. 7, pp. 4197–4231, 2014.

[47] P. Mertikopoulos and Z. Zhou, "Learning in games with continuous action sets and unknown payoff functions," *Mathematical Programming*, vol. 173, no. 1, pp. 465–507, Jan 2019.

[48] E. Tampubolon and H. Boche, "Semi-decentralized coordinated online learning for continuous games with coupled constraints via augmented lagrangian," *arXiv preprint arXiv:1910.09276*, 2019.

[49] F. Salehisadaghiani, W. Shi, and L. Pavel, "Distributed nash equilibrium seeking under partial-decision information via the alternating direction method of multipliers," *Automatica*, vol. 103, pp. 27–35, 2019.

[50] H. Le Cadre, Y. Mou, and H. Höschle, "Parametrized inexact-admm based coordination games: A normalized nash equilibrium approach," *European Journal of Operational Research*, vol. 296, no. 2, pp. 696–716, 2022.

[51] R. Mahindra, M. A. Khojastepour, H. Zhang, and S. Rangarajan, "Radio access network sharing in cellular networks," in *2013 21st IEEE International Conference on Network Protocols (ICNP)*. IEEE, 2013, pp. 1–10.

<figure><img src="image_8.png" /></figure>

**Mandar Datar** received the M.Tech. degree in electrical engineering with a specialization in control systems from the University of Mumbai, India, and a PhD in computer science from INRIA, Sophia Antipolis, France, and the University of Avignon, Avignon, France. He is currently a Postdoctoral Researcher at INRIA. Previously, he worked as an assistant professor at VJTI, Mumbai, India and as a Research Assistant at the Indian institute of technology (IIT) Bombay, Mumbai, India. His area of interest includes game theory, optimization, and

learning in games, MDP with applications in the wireless communication network.

<figure><img src="image_9.png" /></figure>

**Eitan Altman** received a B.Sc. degree in electrical engineering, B.A. in physics, and PhD in electrical engineering from Technion–Israel Institute of Technology, Haifa, 1984, 1984, and 1990, respectively, and B.Mus. in music composition from Tel-Aviv University, Israel, in 1990. Since 1990, he has been a Researcher with INRIA, France. His areas of interests include network engineering games, social networks, and the analysis through game theoretical models of network neutrality issues. He has received the Grand Prix de France Telecom, the

ISAACS Award, and the Distinguished Technical Achievement Recognition Award (IEEE TCBD). His detailed information can be found at http://www.sop.inria.fr/members/Eitan.Altman/.

<figure><img src="image_10.png" /></figure>

**Hélène Le Cadre** received the M.Sc.A. degree from the ENS and University of Rennes, Dipl.Ing. in information science and control theory from Institut Mines-Télécom Atlantique, and Ph.D. degree in applied mathematics from the University of Rennes. She is currently an Inria Researcher, in France. Previously, she worked as a Research Fellow and Assistant Professor with Ecole des Mines de Paris, Sophia-Antipolis, France, as a Visiting Researcher with the Center for Operations Research and econometrics, University catholique of Louvain, Belgium. Her

current research interests revolve around game theory, optimization, learning in games, with applications in energy, networks, and societal-scale system problems.