# Hierarchical Combinatorial Auction in Computing Resource Allocation for Mobile Blockchain

Authors: Yuanyuan Xu; Kun Zhu; Shan Li
Journal: Wireless Communications and Mobile Computing
 (2020)

---

## Abstract

The mobile blockchain has been recognized as an emerging solution to address the security and privacy issues in a mobile application system. The mining process in mobile blockchain requires high computing resources which could overwhelm that which mobile devices can offer. In this case, mobile edge computing servers (MESs) can be involved to offer computing services to miners in mobile blockchain. Note that the resources of MESs are also limited; MESs could further request resources from the cloud computing server (CCS). Accordingly, the issue of hierarchical computing resource allocation arises. In this paper, we first consider a simple case with single-seller multiple buyers and a hierarchical single-seller multibuyer combinatorial auction model is proposed to solve this problem, based on which efficient and truthful frameworks are provided. We then extend the model to consider multiple CCSPs and propose a hierarchical multiple-seller multiple-buyer combinatorial auction model. For both models, the winner determination problems are formulated and computationally tractable algorithms are proposed. Also, pricing schemes are proposed to ensure the property of incentive compatibility and individual rationality. Finally, we evaluate the proposed schemes via simulations.


---

## Body

## 1. Introduction

With the development of mobile applications (e.g., e-commerce), the privacy and security issues have been receiving more attentions [1]. And mobile blockchain [2] has been considered a candidate solution for solving the above problems in mobile application systems. Note that in blockchain systems, an important component is the mining process which is used to verify and record transactions. However, the mining process in mobile blockchain is usually resource demanding, while the mobile devices are usually resource limited. To solve this problem, the Mobile Edge Computing Service Provider (MESP) can be introduced into the mobile blockchain application network which allows miners to offload mining computation tasks to the mobile edge computing servers [3].Note that the computing resources of MESPs could also be limited; MESPs may not satisfy the large resource requirements of various miners. In this case, the Cloud Computing Service Provider (CCSP) who usually owns a large amount of computing resources can be further considered. In this case, miners can first request computing services from the MESPs. If the resources in MESPs are insufficient, MESPs could further rent services from the CCSP. Accordingly, the issue of hierarchical computing resource allocation involving miners, MESPs, and CCSPs arises. Specifically, the miners are regarded as service buyers and the MESP and CCSP are considered service sellers.In this paper, we investigate the issue of hierarchical computing resource allocation in mobile blockchain. For simplicity, we first consider the simpler case of a single CCSP and a hierarchical single-seller multibuyer combinatorial auction model is proposed based on which an efficient and truthful framework is provided. The hierarchical combinatorial auction model can be divided into the lower level auction and the upper level auction. Specifically, miners act as buyers and MESPs act as sellers in the lower level auction, while in the upper level auction, the CCSP is both an auctioneer and seller and the MESPs act as the buyers. MESPs can be viewed as the middlemen who have no intrinsic valuations and demands, and their revenues are gained from resale. MESPs’ valuations depend on the demands from miners. We then extend the model to consider multiple CCSPs and propose a hierarchical multiple-seller multibuyer combinatorial auction model.For both the proposed hierarchical combinatorial auctions, the following three issues need to be addressed: (1) how to design the hierarchical combinatorial auction mechanism for mobile blockchain, (2) how to formulate the winner determination problems (WDPs) in both lower level auction and upper level auction and how to solve them in an efficient way, and (3) how to design incentive compatible pricing schemes. In this work, we will solve all the issues above. The main innovations and contributions of this paper can be concluded as follows:(i)
A single-seller multibuyer hierarchical combinatorial auction mechanism is proposed to address the two-level resource allocation problems for mobile blockchain. And we then extend the model to a more general multiple-seller multibuyer(ii)
WDPs are formulated for CCSP and MESPs, and corresponding solvable algorithms for WDPs are also proposed(iii)
Pricing schemes are proposed to ensure the property of incentive compatibility(iv)
Simulations show high resource utilization and efficiency of the proposed schemesThe rest of this paper is structured as follows. Related work are reviewed in Section2. Section 3 describes the system model and assumptions. In Section 4, a hierarchical single-seller multibuyer combinatorial auction model is proposed. In Section 5, an extension to the multibuyer multiseller model is provided. Simulation results are analyzed in Section 6, and Section 7 draws the conclusions.


## 2. Related Work

Recently, to address the problem on the blockchain mining, many studies have been done from the perspective of a game theory [4]. In [5], a game theory model was proposed to model the process of solving proof of work (PoW) problem. Since the expected reward of miners depends on the block size to a large extent, each miner should choose a reasonable block size to obtain the optimal expected reward. In [6], a cooperative game model is proposed to study the mining pool, in which, miners build up their computing power for a steady return. However, the studies mentioned above principally involve the block mining strategy and pay less attention to the large amount of resource required for the development of blockchain applications.The auction mechanism has been widely used in resource allocation in different fields, e.g., radio resource allocation [7], cloud resource allocation [8], wireless virtualization [9, 10], and cloud/edge computing [11, 12]. In order to address the physical machine resource management problem in the cloud environment, an optimal and approximate defense strategy mechanism is designed in [11]. In [12], a profit maximization model of hierarchical moving edge based on auction is proposed. Unfortunately, it does not take any economic characteristics into account, such as incentive compatibility. While ensuring strategic defense, the redistribution of wireless channels is studied in [13], with emphasis on the maximization of social welfare. They consider not only the correctness of the strategy but also the spatial reusability of the channel, the heterogeneity of the channel, and the diversity of the bidding. Nevertheless, the bidder’s request for the spectrum bundle is always considered true in the auction model. In reality, all of these cannot be used for the allocation of computing resource in the blockchain in a direct way, principally because of the uniqueness of the mobile blockchain network. In the mobile blockchain network, special consideration should be given to external factors [14, 15] of distribution. For example, in addition to the computing resources they receive, each miner is very concerned about the computing power of other miners.In addition, deep learning method is used in [16] to recover the traditional revenue maximization optimal auction to solve resource allocation for mobile blockchain. Nevertheless, just one resource unit is considered in the model. [3] only considers the miners with constant demand and no real experiments are conducted. In [17], multidemand bidding scheme has been proposed to obtain the optimization of social welfare. They only consider MESPs to allocate computing services to miners. While in our work, we consider both the MESPs and CCSPs. In our previous work, we investigate the single-seller multibuyer case, while in this work, we extend the model to a multiseller multibuyer one. Furthermore, we add more theoretical analysis including proof of several favorable economic properties of the proposed models. Also, more numerical results are provided and analyzed.


## 3. System Model and Assumptions

### 3.1. Mining Process in Mobile Blockchain

The mining process in blockchain networks is shown in Figure1. Blockchain owners build blockchain applications and design protocols for blockchain networks. Each mobile user applies for a block from the blockchain owner, and then she will do a mining task. The mining task is actually to solve a PoW problem. After the problem is solved, the solutions must be promoted in order to reach consensus. After successfully completing all of these processes, the transactions completed by the miners are added to the blockchain. Only the miner who is the first to get the solution and reach a consensus can be rewarded.Figure 1
The process of mining in blockchain networks.


### 3.2. The Probability of Successfully Mining with Edge Computing Services

Mineri’s hash power ωi which is related to other miners’ allocated resources can be formulated as follows:
(1)ωic,x=cixij∑i=1Ncixij,which is a fraction function and the sum of all the miners’ hash power is equal to one. ci represents computing resources required by mobile user i. xij is a binary variable and if the value of it is equal to one that dedicating mobile user i will be allocated the required resources by MESP j. Otherwise, she will get nothing.During the mining process, the miners are competing with each other to become the first to solve the PoW problem and broadcast to reach an agreement. The generation of new blocks obeys the Poisson distribution which holds a constant rate1/λ in the mobile blockchain network [18]. Before the mining race begins, the miners keep unverified transaction information into their blocks. We use t=t1,⋯,tN to represent the size of the transaction in each miner’s block. Miners need to broadcast their blocks to mobile blockchain networks to gain consensus. The first miner to win this consensus will be rewarded. Rewards consist of fixed rewards and random rewards and can be formulated as follows:
(2)Ri=T+r·tiℙωic,x,ti,where T is the fixed reward and r·ti is the random reward which is related to the size of transaction ti and r is always positive. Also, ℙωic,x,ti is the probability of getting a reward.Judging from the above mining process, getting rewards successfully needs two steps. The first is successfully mining, and the second is timely propagation certification. The success rate of mining is directly proportional to the hash power. So, we use the hash power to represent the probability of successfully mining which is formulated as follows:(3)Pi=ωi.The time of propagation is related to the size of the transaction. Here, we useτi=ς⋅ti to represent the time of propagation. ς is a constant which reflects the impact of Si on τi. Since the new blocks generate following the Poisson distribution, the probability of miner propagation failure can be formulated as follows:
(4)Pi0=1−exp−1λτi.In this case,,ℙωic,x,ti can be formulated as follows:
(5)ℙiωic,x,ti=Pi1−Pi0.After substitutingPi and Pi0, Pi can be formulated as follows:
(6)ℙiωic,x,ti=ωie−1/λς·ti.


### 3.3. Blockchain Management

The blockchain mining protocol is maintained by the blockchain owner, which includes a fixed bonusT and transaction rate r for miners contributing to mining. In addition, the security of a blockchain depends only on the amount of computing power used to solve it in a PoW problem [19]. This has a positive network effect: as more miners take part in mining and more computing resources put into mining, rewards for miners will increase as the blockchain network becomes more secure and stable. Based on existing research [20], we use a common sshaped utility function to define network effects:
(7)γdN=1−e−νdN1+μe−νdN,where dN=∑i∈Ncixij is the total amount of computing resources allocated and μ, ν are two positive parameters. The network effect function starts slowly from 0, then accelerates, and then eventually slows down and converges to 1 asymptotically.


## 3.1. Mining Process in Mobile Blockchain

The mining process in blockchain networks is shown in Figure1. Blockchain owners build blockchain applications and design protocols for blockchain networks. Each mobile user applies for a block from the blockchain owner, and then she will do a mining task. The mining task is actually to solve a PoW problem. After the problem is solved, the solutions must be promoted in order to reach consensus. After successfully completing all of these processes, the transactions completed by the miners are added to the blockchain. Only the miner who is the first to get the solution and reach a consensus can be rewarded.Figure 1
The process of mining in blockchain networks.


## 3.2. The Probability of Successfully Mining with Edge Computing Services

Mineri’s hash power ωi which is related to other miners’ allocated resources can be formulated as follows:
(1)ωic,x=cixij∑i=1Ncixij,which is a fraction function and the sum of all the miners’ hash power is equal to one. ci represents computing resources required by mobile user i. xij is a binary variable and if the value of it is equal to one that dedicating mobile user i will be allocated the required resources by MESP j. Otherwise, she will get nothing.During the mining process, the miners are competing with each other to become the first to solve the PoW problem and broadcast to reach an agreement. The generation of new blocks obeys the Poisson distribution which holds a constant rate1/λ in the mobile blockchain network [18]. Before the mining race begins, the miners keep unverified transaction information into their blocks. We use t=t1,⋯,tN to represent the size of the transaction in each miner’s block. Miners need to broadcast their blocks to mobile blockchain networks to gain consensus. The first miner to win this consensus will be rewarded. Rewards consist of fixed rewards and random rewards and can be formulated as follows:
(2)Ri=T+r·tiℙωic,x,ti,where T is the fixed reward and r·ti is the random reward which is related to the size of transaction ti and r is always positive. Also, ℙωic,x,ti is the probability of getting a reward.Judging from the above mining process, getting rewards successfully needs two steps. The first is successfully mining, and the second is timely propagation certification. The success rate of mining is directly proportional to the hash power. So, we use the hash power to represent the probability of successfully mining which is formulated as follows:(3)Pi=ωi.The time of propagation is related to the size of the transaction. Here, we useτi=ς⋅ti to represent the time of propagation. ς is a constant which reflects the impact of Si on τi. Since the new blocks generate following the Poisson distribution, the probability of miner propagation failure can be formulated as follows:
(4)Pi0=1−exp−1λτi.In this case,,ℙωic,x,ti can be formulated as follows:
(5)ℙiωic,x,ti=Pi1−Pi0.After substitutingPi and Pi0, Pi can be formulated as follows:
(6)ℙiωic,x,ti=ωie−1/λς·ti.


## 3.3. Blockchain Management

The blockchain mining protocol is maintained by the blockchain owner, which includes a fixed bonusT and transaction rate r for miners contributing to mining. In addition, the security of a blockchain depends only on the amount of computing power used to solve it in a PoW problem [19]. This has a positive network effect: as more miners take part in mining and more computing resources put into mining, rewards for miners will increase as the blockchain network becomes more secure and stable. Based on existing research [20], we use a common sshaped utility function to define network effects:
(7)γdN=1−e−νdN1+μe−νdN,where dN=∑i∈Ncixij is the total amount of computing resources allocated and μ, ν are two positive parameters. The network effect function starts slowly from 0, then accelerates, and then eventually slows down and converges to 1 asymptotically.


## 4. Resource Allocation as a Single-Seller Multibuyer Hierarchical Combinatorial Auction

In this section, we firstly propose a single-seller multibuyer hierarchical combinatorial double auction model for the hierarchical resource allocation in mobile blockchain considering only one CCSP as the single seller in the upper layer auction. Then, we describe how to place the bid in this auction model. After receiving all the bids, the auctioneer needs to determine the winning bids, which is then formulated as the winner determination problem (WDP). Then, the algorithms for solving the WDP are provided. Finally, the price charged for the winning bidders are calculated.


### 4.1. Hierarchical Combinatorial Auction Model

We first consider the scenario where there is a single CCSP,M MESPs, and N mobile users as shown in Figure 2. In this model, the CCSP provides services to MESPs and then each MESP provides services to mobile users, and naturally the problem of resource allocation is a hierarchical one. Specifically, we assume that the CCSP owns C units of million instructions per seconds (MIPS) computing resources. And each MESP j owns Cjown computing resources. Besides, each MESP can further reserve Cjres amount of resource from CCSP. In addition, we consider that mobile devices’ own computing resources are small enough to be ignored when compared to the computing resources of demand.Figure 2
System model of hierarchical resource allocation for blockchain mining.To jointly solve the issue of two-level resource allocation, a two-level hierarchical auction mechanism is designed as shown in Figure3. In the lower level, a combinatorial double auction is performed where miners and MESPs are considered resource buyers and sellers, respectively. While in the upper level, a one-sided combinatorial auction is considered, where the CCSP is considered the seller and the MESPs are considered buyers. Specifically, in the lower level, each miner i submits a bid including resource demand di=ci and corresponding bidding price. In the upper level, each MESP first reserves certain computing resources Cjres from cup=∑j=iMcjres computing resources owned by the CCSP are to be auctioned among the MESPs. We denote Cj>0 as the computing resources obtained by MESP j from the CCSP in the upper level auction. In this case, for each MESP j in the lower level, the available computing resources are Cjlow=Cjown+Cjres+Cj. Note that the bids in both the lower and upper levels are combinatorial, which means multiple combinations of resource demands and corresponding bidding prices can be provided simultaneously which on the one hand increases the flexibility and on the other hand significantly increases the complexity.Figure 3
The model of a single-seller multibuyer hierarchical auction.


### 4.2. How to Place a Bid?

Each mobile blockchain miner needs to place a bid for requested resources which reflects her valuation in the lower level auction. Since mobile blockchain users cannot know the winners’ number and the total resources’ number available until the auction is over, mobile useri’s bid bi is represented by the expected reward Ri which is equal to valuation vi which is called ex ante valuation shown as follows:
(8)vi′=Ri.After submitting (1), (2), and (6), we can get the specific expression of the mobile user i’s valuation:
(9)vi′=vi′T+r·ticixij∑i=1Ncixije−1/λς·ti.After the auction result is released, useri has an ex post valuation vi of the edge computing service considering network effects, which is defined by
(10)vi=γRi,where γ is the network effect mentioned in (7).After submitting (1), (2), (6), and (7), we can get the mobile user i’s specific valuation:
(11)vi′′=1−e−νdN1+μe−νdNT+r·ticixij∑i=1Ncixije−1/λς·ti.For MESPs, bidding expressions differ from that of mobile users, because MESPs as the middlemen have no intrinsic demands and valuations. In the lower level auction, each MESPj needs to submit asking bids aj for all possible resource bundle sets. Similarly, each MESP needs to submit bid vj for all possible resources bundles sets to CCSP in the upper level auction.


### 4.3. How to Determine the Winning Bids?

After receiving all bids from bidders, which group of bids to be accepted needs to be decided by the auctioneer. For the proposed model in this paper, the WDPs for MESPs and CCSP need to be formulated. Specifically, the WDP for MESPs is shown as follows:(12)Maximize∑i=1Nvi′′xij+∑j=1Majyj,SubjecttoC1:∑i=1Nxijci≤Cjres+Cj,C2:∑i=1Mxij≤1,∀i∈1,N,C3:xij∈0.1,∀i∈N,C4:yj∈0,1,∀i∈M,where the object function is to maximize the sum of both sides’ valuation. Constraint C1 indicates that the amount of computing resources required should receive a maximum limit. Constraint C2 makes sure that a mobile user can get resources from only one MESP. xij in constraint C3 is a binary variable and if the value of it is equal to one that dedicating mobile user i is accepted and will be allocated the required resources. Otherwise she will get nothing. yj in constraint C4 is also a binary variable and if the value of it is equal to one that dedicating MESP j is accepted and will allocate resources to the corresponding mobile users. Otherwise she will be the loser.Specifically, the WDP for the CCSP is formulated as follows:(13)Maximize∑j=1Mvjyj,SubjecttoC1:∑jMyjCj≤C−∑jMCjres,C2:yj∈0,1,∀j∈M,where the object function is to maximize the sum of bidders’ valuation. Constraint C1 indicates that the amount of computing resources required should receive a maximum limit. Constraint C2 ensure that yj is a binary variable. yj is a binary variable and if the value of it is equal to one that dedicating MESP j is accepted and will be allocated required resources from CCSP. Otherwise she will be the loser.


### 4.4. How to Solve the WDPs in the Hierarchical Auction?

Backward induction is used to solve the winner determination problems in the hierarchical auction. Specifically, we first consider the lower level auction. Deliberately stated here, as a hierarchical optimization problem, how to jointly solve WDP for each layer is of key importance.


#### 4.4.1. Solving the WDP in the Lower Level Auction

In the lower level, multiple miners and multiple MESPs exist. And the corresponding WDP is an integer programming problem which is NP-hard. For achieving a satisfying approximate optimal solution with low complexity, we propose a greedy algorithm motivated by [8] which takes “bid density” into account as shown in Algorithm 1:Algorithm 1: A greedy algorithm for solving the WDP for MESPs.
1. Initialization: Setxij=0 for each miner i and yj=0 for each MESP j2. For submitted bidvi for each miner i and submitted ask aj for each MESP j, calculate the “bid density.” Reorder the miners’ bid in a descending order and the MESPs’ ask in an ascending order:v1c1≥v2c2≥⋯≥vNcN,a1C1low≤a2C2low≤⋯≤aNCNlow3. Match up one by one according to corresponding order until MESPs do not have enough resources to allocate and set relativexij=1, yj=1.Similar to previousM approximation for combinatorial auctions in which M is defined as the total number of items allocated. We redefine M to be the required calculating capacity c.


#### 4.4.2. Solving the WDP in the Upper Level Auction

There is a single CCSP as a seller and multiple MESPs as buyers in the upper level. The WDP problem in the upper level is also an integer programming problem. In this part, we propose two schemes to solve the WDP. Firstly, for a small-scale problem, a dynamic programming-based algorithm motivated by [21] is proposed for obtaining the exact solution. The main idea is to decompose the original WDP into similar subproblems that can be solved recursively. Specifically, the service allocation is divided into Km stages, which is denoted by the subproblem considering the service allocation to k users who have required resources ek=eckT, where eck denotes the required computing resources. In each stage k, the service provider with resources can be denoted by uk=uck. Therefore, the state transition can be formulated as
(14)ek+1=ek−uk.Accordingly, we can havefk,ek=maxfk−1,ek,fk−1,ek−uk+vk. The details are shown in Algorithm 2:Considering the auctioneer’s computing power and the scale of the problem, a greedy algorithm which takes “bid density” into account is also proposed to obtain an approximate optimal solution as shown in Algorithm3:Algorithm 2: A dynamic programming algorithm for solving the winning determination problem.
1. Collect bidsBk (Sk) from each user k, and initial the condition f1,e1.2. Calculate the optimal value functionfk,ek for each state.3. Output: usingxk∗=argmaxxkfk,ek to get the optimal allocation in each state.Algorithm 3: A greedy algorithm for solving the WDP for CCSP.
1.Initialization: setyj=0 for each MESP j2. For submitted bidvj for each MESP j, calculate “bid density”. Reorder the MESPs’ bid in a descending order:v1C1≥v2C2≥⋯≥vNCN3. Allocate computing resources to corresponding MESPs until the CCSP do not have enough resources and set relativeyj=1.


### 4.5. How to Price the Winning Bidders?

#### 4.5.1. Pricing Scheme for Lower Level Auction

The design of pricing scheme is important for achieving incentive compatibility in the auction with which each bidder will always bid truthfully. The VCG [22] scheme achieves the incentive compatibility which have been proved which is only compatible with exact algorithms.In this case, we design a VCG-like pricing scheme which can be adapted to approximate algorithms, in which a base price is introduced. Specifically, each type of resources has a base price, and a user who is the winner will pay the larger one between the base price and the VCG price. The charged price can be formulated as follows:(15)Pki=maxPkbasei,Pkvcgi,where
(16)Pkbasei=bi,Pkvcgi=vkckci,where Pkbasei represents the base price of user i, and Pkvcgi is the VCG price. We will choose Pkbasei as the final payment price in the case that the VCG price is smaller, or else, the VCG price will be chosen.


#### 4.5.2. Pricing Scheme for Upper Level Auction

For solving the WDP for CCSP, we propose two algorithms which are an exact algorithm based on dynamic programming algorithm and an approximate algorithm based on greedy algorithm, and the pricing scheme for them should be different. Specifically, for dynamic programming-based algorithm, we use VCG pricing. The VCG price of bidderi can be shown as follows:
(17)Pki=∑j≠ivjB∗−∑j≠ivjB,B∗and B denote the resources obtained by bidder j without bidder i and with bidder i, respectively.The pricing scheme in the greedy algorithm is similar to that in the lower level auction.


#### 4.5.3. Analysis of Economic Properties

In this part, we will make an analysis on the properties of the proposed single-seller multibuyer hierarchical auction mechanism.Theorem 1.
The hierarchical single-seller multibuyer auction mechanism proposed in this paper is individually rational for all truthful bidders in both two levels.Proof of Theorem 1.
The VCG solution and the precise WDP solution algorithm proved to be individually rational [23]. For greedy algorithm with corresponding pricing scheme, two cases are considered by us. The first case is that if no bidder is blocked by the winning bidder k, then Pk=Pbase,0,. Then, bk≥Pbase and accordingly ui≥0. Hence, the user i’s utility is nonnegative. Therefore, each participant is individually rational.Theorem 2.
The hierarchical single-seller multibuyer auction mechanism proposed in this paper is incentively compatible for all truthful bidders in both two levels.Proof of Theorem 2.
To prove incentive compatibility, we have to prove monotonicity and critical payment property. Monotonicity can be proved immediately. Specifically, a bidder can increase its ranking order by increasing the bid value, as the bidder’s surplus at each level increases.Then, we will prove critical payment property. If we can find the critical value that a bidder must bid to win the auction, the critical payment property can be proved. Donate userj with the highest valuation wins the auction and user k does not participate in the auction. Therefore, the minimum bid which the user k needs to place is vi/cick, which is bidder k’s payment in the pricing scheme in each level. Accordingly, incentive compatibility can be proved.Theorem 3.
The hierarchical single-seller multibuyer auction mechanism proposed in this paper achieves allocation efficiency with truthful bidding in both two levels.This result can be easily proved from the winner determination problem formulation for which the sum of accepted bids is maximized.


## 4.1. Hierarchical Combinatorial Auction Model

We first consider the scenario where there is a single CCSP,M MESPs, and N mobile users as shown in Figure 2. In this model, the CCSP provides services to MESPs and then each MESP provides services to mobile users, and naturally the problem of resource allocation is a hierarchical one. Specifically, we assume that the CCSP owns C units of million instructions per seconds (MIPS) computing resources. And each MESP j owns Cjown computing resources. Besides, each MESP can further reserve Cjres amount of resource from CCSP. In addition, we consider that mobile devices’ own computing resources are small enough to be ignored when compared to the computing resources of demand.Figure 2
System model of hierarchical resource allocation for blockchain mining.To jointly solve the issue of two-level resource allocation, a two-level hierarchical auction mechanism is designed as shown in Figure3. In the lower level, a combinatorial double auction is performed where miners and MESPs are considered resource buyers and sellers, respectively. While in the upper level, a one-sided combinatorial auction is considered, where the CCSP is considered the seller and the MESPs are considered buyers. Specifically, in the lower level, each miner i submits a bid including resource demand di=ci and corresponding bidding price. In the upper level, each MESP first reserves certain computing resources Cjres from cup=∑j=iMcjres computing resources owned by the CCSP are to be auctioned among the MESPs. We denote Cj>0 as the computing resources obtained by MESP j from the CCSP in the upper level auction. In this case, for each MESP j in the lower level, the available computing resources are Cjlow=Cjown+Cjres+Cj. Note that the bids in both the lower and upper levels are combinatorial, which means multiple combinations of resource demands and corresponding bidding prices can be provided simultaneously which on the one hand increases the flexibility and on the other hand significantly increases the complexity.Figure 3
The model of a single-seller multibuyer hierarchical auction.


## 4.2. How to Place a Bid?

Each mobile blockchain miner needs to place a bid for requested resources which reflects her valuation in the lower level auction. Since mobile blockchain users cannot know the winners’ number and the total resources’ number available until the auction is over, mobile useri’s bid bi is represented by the expected reward Ri which is equal to valuation vi which is called ex ante valuation shown as follows:
(8)vi′=Ri.After submitting (1), (2), and (6), we can get the specific expression of the mobile user i’s valuation:
(9)vi′=vi′T+r·ticixij∑i=1Ncixije−1/λς·ti.After the auction result is released, useri has an ex post valuation vi of the edge computing service considering network effects, which is defined by
(10)vi=γRi,where γ is the network effect mentioned in (7).After submitting (1), (2), (6), and (7), we can get the mobile user i’s specific valuation:
(11)vi′′=1−e−νdN1+μe−νdNT+r·ticixij∑i=1Ncixije−1/λς·ti.For MESPs, bidding expressions differ from that of mobile users, because MESPs as the middlemen have no intrinsic demands and valuations. In the lower level auction, each MESPj needs to submit asking bids aj for all possible resource bundle sets. Similarly, each MESP needs to submit bid vj for all possible resources bundles sets to CCSP in the upper level auction.


## 4.3. How to Determine the Winning Bids?

After receiving all bids from bidders, which group of bids to be accepted needs to be decided by the auctioneer. For the proposed model in this paper, the WDPs for MESPs and CCSP need to be formulated. Specifically, the WDP for MESPs is shown as follows:(12)Maximize∑i=1Nvi′′xij+∑j=1Majyj,SubjecttoC1:∑i=1Nxijci≤Cjres+Cj,C2:∑i=1Mxij≤1,∀i∈1,N,C3:xij∈0.1,∀i∈N,C4:yj∈0,1,∀i∈M,where the object function is to maximize the sum of both sides’ valuation. Constraint C1 indicates that the amount of computing resources required should receive a maximum limit. Constraint C2 makes sure that a mobile user can get resources from only one MESP. xij in constraint C3 is a binary variable and if the value of it is equal to one that dedicating mobile user i is accepted and will be allocated the required resources. Otherwise she will get nothing. yj in constraint C4 is also a binary variable and if the value of it is equal to one that dedicating MESP j is accepted and will allocate resources to the corresponding mobile users. Otherwise she will be the loser.Specifically, the WDP for the CCSP is formulated as follows:(13)Maximize∑j=1Mvjyj,SubjecttoC1:∑jMyjCj≤C−∑jMCjres,C2:yj∈0,1,∀j∈M,where the object function is to maximize the sum of bidders’ valuation. Constraint C1 indicates that the amount of computing resources required should receive a maximum limit. Constraint C2 ensure that yj is a binary variable. yj is a binary variable and if the value of it is equal to one that dedicating MESP j is accepted and will be allocated required resources from CCSP. Otherwise she will be the loser.


## 4.4. How to Solve the WDPs in the Hierarchical Auction?

Backward induction is used to solve the winner determination problems in the hierarchical auction. Specifically, we first consider the lower level auction. Deliberately stated here, as a hierarchical optimization problem, how to jointly solve WDP for each layer is of key importance.


### 4.4.1. Solving the WDP in the Lower Level Auction

In the lower level, multiple miners and multiple MESPs exist. And the corresponding WDP is an integer programming problem which is NP-hard. For achieving a satisfying approximate optimal solution with low complexity, we propose a greedy algorithm motivated by [8] which takes “bid density” into account as shown in Algorithm 1:Algorithm 1: A greedy algorithm for solving the WDP for MESPs.
1. Initialization: Setxij=0 for each miner i and yj=0 for each MESP j2. For submitted bidvi for each miner i and submitted ask aj for each MESP j, calculate the “bid density.” Reorder the miners’ bid in a descending order and the MESPs’ ask in an ascending order:v1c1≥v2c2≥⋯≥vNcN,a1C1low≤a2C2low≤⋯≤aNCNlow3. Match up one by one according to corresponding order until MESPs do not have enough resources to allocate and set relativexij=1, yj=1.Similar to previousM approximation for combinatorial auctions in which M is defined as the total number of items allocated. We redefine M to be the required calculating capacity c.


### 4.4.2. Solving the WDP in the Upper Level Auction

There is a single CCSP as a seller and multiple MESPs as buyers in the upper level. The WDP problem in the upper level is also an integer programming problem. In this part, we propose two schemes to solve the WDP. Firstly, for a small-scale problem, a dynamic programming-based algorithm motivated by [21] is proposed for obtaining the exact solution. The main idea is to decompose the original WDP into similar subproblems that can be solved recursively. Specifically, the service allocation is divided into Km stages, which is denoted by the subproblem considering the service allocation to k users who have required resources ek=eckT, where eck denotes the required computing resources. In each stage k, the service provider with resources can be denoted by uk=uck. Therefore, the state transition can be formulated as
(14)ek+1=ek−uk.Accordingly, we can havefk,ek=maxfk−1,ek,fk−1,ek−uk+vk. The details are shown in Algorithm 2:Considering the auctioneer’s computing power and the scale of the problem, a greedy algorithm which takes “bid density” into account is also proposed to obtain an approximate optimal solution as shown in Algorithm3:Algorithm 2: A dynamic programming algorithm for solving the winning determination problem.
1. Collect bidsBk (Sk) from each user k, and initial the condition f1,e1.2. Calculate the optimal value functionfk,ek for each state.3. Output: usingxk∗=argmaxxkfk,ek to get the optimal allocation in each state.Algorithm 3: A greedy algorithm for solving the WDP for CCSP.
1.Initialization: setyj=0 for each MESP j2. For submitted bidvj for each MESP j, calculate “bid density”. Reorder the MESPs’ bid in a descending order:v1C1≥v2C2≥⋯≥vNCN3. Allocate computing resources to corresponding MESPs until the CCSP do not have enough resources and set relativeyj=1.


## 4.4.1. Solving the WDP in the Lower Level Auction

In the lower level, multiple miners and multiple MESPs exist. And the corresponding WDP is an integer programming problem which is NP-hard. For achieving a satisfying approximate optimal solution with low complexity, we propose a greedy algorithm motivated by [8] which takes “bid density” into account as shown in Algorithm 1:Algorithm 1: A greedy algorithm for solving the WDP for MESPs.
1. Initialization: Setxij=0 for each miner i and yj=0 for each MESP j2. For submitted bidvi for each miner i and submitted ask aj for each MESP j, calculate the “bid density.” Reorder the miners’ bid in a descending order and the MESPs’ ask in an ascending order:v1c1≥v2c2≥⋯≥vNcN,a1C1low≤a2C2low≤⋯≤aNCNlow3. Match up one by one according to corresponding order until MESPs do not have enough resources to allocate and set relativexij=1, yj=1.Similar to previousM approximation for combinatorial auctions in which M is defined as the total number of items allocated. We redefine M to be the required calculating capacity c.


## 4.4.2. Solving the WDP in the Upper Level Auction

There is a single CCSP as a seller and multiple MESPs as buyers in the upper level. The WDP problem in the upper level is also an integer programming problem. In this part, we propose two schemes to solve the WDP. Firstly, for a small-scale problem, a dynamic programming-based algorithm motivated by [21] is proposed for obtaining the exact solution. The main idea is to decompose the original WDP into similar subproblems that can be solved recursively. Specifically, the service allocation is divided into Km stages, which is denoted by the subproblem considering the service allocation to k users who have required resources ek=eckT, where eck denotes the required computing resources. In each stage k, the service provider with resources can be denoted by uk=uck. Therefore, the state transition can be formulated as
(14)ek+1=ek−uk.Accordingly, we can havefk,ek=maxfk−1,ek,fk−1,ek−uk+vk. The details are shown in Algorithm 2:Considering the auctioneer’s computing power and the scale of the problem, a greedy algorithm which takes “bid density” into account is also proposed to obtain an approximate optimal solution as shown in Algorithm3:Algorithm 2: A dynamic programming algorithm for solving the winning determination problem.
1. Collect bidsBk (Sk) from each user k, and initial the condition f1,e1.2. Calculate the optimal value functionfk,ek for each state.3. Output: usingxk∗=argmaxxkfk,ek to get the optimal allocation in each state.Algorithm 3: A greedy algorithm for solving the WDP for CCSP.
1.Initialization: setyj=0 for each MESP j2. For submitted bidvj for each MESP j, calculate “bid density”. Reorder the MESPs’ bid in a descending order:v1C1≥v2C2≥⋯≥vNCN3. Allocate computing resources to corresponding MESPs until the CCSP do not have enough resources and set relativeyj=1.


## 4.5. How to Price the Winning Bidders?

### 4.5.1. Pricing Scheme for Lower Level Auction

The design of pricing scheme is important for achieving incentive compatibility in the auction with which each bidder will always bid truthfully. The VCG [22] scheme achieves the incentive compatibility which have been proved which is only compatible with exact algorithms.In this case, we design a VCG-like pricing scheme which can be adapted to approximate algorithms, in which a base price is introduced. Specifically, each type of resources has a base price, and a user who is the winner will pay the larger one between the base price and the VCG price. The charged price can be formulated as follows:(15)Pki=maxPkbasei,Pkvcgi,where
(16)Pkbasei=bi,Pkvcgi=vkckci,where Pkbasei represents the base price of user i, and Pkvcgi is the VCG price. We will choose Pkbasei as the final payment price in the case that the VCG price is smaller, or else, the VCG price will be chosen.


### 4.5.2. Pricing Scheme for Upper Level Auction

For solving the WDP for CCSP, we propose two algorithms which are an exact algorithm based on dynamic programming algorithm and an approximate algorithm based on greedy algorithm, and the pricing scheme for them should be different. Specifically, for dynamic programming-based algorithm, we use VCG pricing. The VCG price of bidderi can be shown as follows:
(17)Pki=∑j≠ivjB∗−∑j≠ivjB,B∗and B denote the resources obtained by bidder j without bidder i and with bidder i, respectively.The pricing scheme in the greedy algorithm is similar to that in the lower level auction.


### 4.5.3. Analysis of Economic Properties

In this part, we will make an analysis on the properties of the proposed single-seller multibuyer hierarchical auction mechanism.Theorem 1.
The hierarchical single-seller multibuyer auction mechanism proposed in this paper is individually rational for all truthful bidders in both two levels.Proof of Theorem 1.
The VCG solution and the precise WDP solution algorithm proved to be individually rational [23]. For greedy algorithm with corresponding pricing scheme, two cases are considered by us. The first case is that if no bidder is blocked by the winning bidder k, then Pk=Pbase,0,. Then, bk≥Pbase and accordingly ui≥0. Hence, the user i’s utility is nonnegative. Therefore, each participant is individually rational.Theorem 2.
The hierarchical single-seller multibuyer auction mechanism proposed in this paper is incentively compatible for all truthful bidders in both two levels.Proof of Theorem 2.
To prove incentive compatibility, we have to prove monotonicity and critical payment property. Monotonicity can be proved immediately. Specifically, a bidder can increase its ranking order by increasing the bid value, as the bidder’s surplus at each level increases.Then, we will prove critical payment property. If we can find the critical value that a bidder must bid to win the auction, the critical payment property can be proved. Donate userj with the highest valuation wins the auction and user k does not participate in the auction. Therefore, the minimum bid which the user k needs to place is vi/cick, which is bidder k’s payment in the pricing scheme in each level. Accordingly, incentive compatibility can be proved.Theorem 3.
The hierarchical single-seller multibuyer auction mechanism proposed in this paper achieves allocation efficiency with truthful bidding in both two levels.This result can be easily proved from the winner determination problem formulation for which the sum of accepted bids is maximized.


## 4.5.1. Pricing Scheme for Lower Level Auction

The design of pricing scheme is important for achieving incentive compatibility in the auction with which each bidder will always bid truthfully. The VCG [22] scheme achieves the incentive compatibility which have been proved which is only compatible with exact algorithms.In this case, we design a VCG-like pricing scheme which can be adapted to approximate algorithms, in which a base price is introduced. Specifically, each type of resources has a base price, and a user who is the winner will pay the larger one between the base price and the VCG price. The charged price can be formulated as follows:(15)Pki=maxPkbasei,Pkvcgi,where
(16)Pkbasei=bi,Pkvcgi=vkckci,where Pkbasei represents the base price of user i, and Pkvcgi is the VCG price. We will choose Pkbasei as the final payment price in the case that the VCG price is smaller, or else, the VCG price will be chosen.


## 4.5.2. Pricing Scheme for Upper Level Auction

For solving the WDP for CCSP, we propose two algorithms which are an exact algorithm based on dynamic programming algorithm and an approximate algorithm based on greedy algorithm, and the pricing scheme for them should be different. Specifically, for dynamic programming-based algorithm, we use VCG pricing. The VCG price of bidderi can be shown as follows:
(17)Pki=∑j≠ivjB∗−∑j≠ivjB,B∗and B denote the resources obtained by bidder j without bidder i and with bidder i, respectively.The pricing scheme in the greedy algorithm is similar to that in the lower level auction.


## 4.5.3. Analysis of Economic Properties

In this part, we will make an analysis on the properties of the proposed single-seller multibuyer hierarchical auction mechanism.Theorem 1.
The hierarchical single-seller multibuyer auction mechanism proposed in this paper is individually rational for all truthful bidders in both two levels.Proof of Theorem 1.
The VCG solution and the precise WDP solution algorithm proved to be individually rational [23]. For greedy algorithm with corresponding pricing scheme, two cases are considered by us. The first case is that if no bidder is blocked by the winning bidder k, then Pk=Pbase,0,. Then, bk≥Pbase and accordingly ui≥0. Hence, the user i’s utility is nonnegative. Therefore, each participant is individually rational.Theorem 2.
The hierarchical single-seller multibuyer auction mechanism proposed in this paper is incentively compatible for all truthful bidders in both two levels.Proof of Theorem 2.
To prove incentive compatibility, we have to prove monotonicity and critical payment property. Monotonicity can be proved immediately. Specifically, a bidder can increase its ranking order by increasing the bid value, as the bidder’s surplus at each level increases.Then, we will prove critical payment property. If we can find the critical value that a bidder must bid to win the auction, the critical payment property can be proved. Donate userj with the highest valuation wins the auction and user k does not participate in the auction. Therefore, the minimum bid which the user k needs to place is vi/cick, which is bidder k’s payment in the pricing scheme in each level. Accordingly, incentive compatibility can be proved.Theorem 3.
The hierarchical single-seller multibuyer auction mechanism proposed in this paper achieves allocation efficiency with truthful bidding in both two levels.This result can be easily proved from the winner determination problem formulation for which the sum of accepted bids is maximized.


## 5. Resource Allocation as a Multiple-Seller Multibuyer Hierarchical Combinatorial Double Auction

We now extend the single-seller multibuyer hierarchical auction to a multiple-seller multibuyer one. Specifically, a set ofQ=1,⋯,Q CCSPs are considered sellers as shown in Figure 4. And a multiple-seller multibuyer hierarchical combinatorial double auction is designed as shown in Figure 5. Note that in this model, both lower and upper level are double auctions. In the upper level, each MESP submits bid vj and each CCSP submits asking bids ai for all possible resource bundle sets, respectively. The lower level auction is similar to that in previous single-seller multibuyer auction model.Figure 4
Proposed combinatorial double auction model.Figure 5
Proposed combinatorial double auction model.


### 5.1. WDP Problem Formulation

With submitted asks and bids, the winnerdetermination problem can be formulated to determine the winning bidders. In the lower level double auction, the WDP is formulated as follows:(18)Maximize∑i=1Nvixi−∑j=1Majyj,SubjecttoC1:∑i=1Nxici≤Cjres+Cj,C2:∑i=1Nvixi≥,C3:xi∈0,1,∀i∈N,C4:yj∈0,1,∀j∈M,where the objective is to maximize the surplus between the buyers’ valuations and the sellers’ asks. C1 is the resource cap constraint. Constraint C2 ensures that a miner can get resources from only one MESP. Constraint C3 ensures that a MESP can offer resources to only one mobile user. Similarly, the WDP in the upper level is formulated as follows:
(19)Maximize∑i=1Nvixi−∑j=1Majyj,SubjecttoC1:∑i=1MxiCi≤Cjup,C2:∑i=1Mvixi≥∑j=1Qajyj,C3:xi∈0,1,∀i∈M,C4:yj∈0,1,∀j∈Q.


### 5.2. Solving the WDPs in the Hierarchical Double Auction?

For solving the multiple-seller multibuyer hierarchical double auction, backward induction is also used. For the lower level auction, similar schemes in the previous section can be applied. And for solving the WDP in the upper level, we propose a Lagrange multiplier algorithm.In computer science, we often use “divide-and-conquer” to reduce computational complexity to solve the complex problems [24]. In this case, we consider the Lagrange multiplier algorithm to solve the WDP problem to get an approximate optimal solution which can be divided into two steps (including problem decomposition and determining the allocation).


### 5.3. Problem Decomposition

The algorithm solves the problem by the way of decomposing the problem into two or more subproblems, which are easily solved directly. The solution then combines these subproblems to construct a solution to the original problem. Lagrangian relaxation is used to provide a technique to decompose the problem into several subproblems. One way to reduce the burden of solving WDP calculations is to use Lagrangian relaxation to establish a fictitious market to determine allocation.The basic idea of Lagrangian relaxation is to relax some of the constraints of the original problem on the objective function with a penalty term. That is, infeasible solutions to the original problem are allowed, but they are penalized in the objective function in proportion to the number of infeasibility. Under the condition of relaxed constraints selected, the constraint conditions are selected so that the optimization problem under the remaining constraints is easy in a certain sense. In the above WDP problem in the lower level, we observe that the coupling between different operations is caused by C1 and C2 constraints.Letλ denotes the Lagrange multiplier for the computing resource constraint. In addition, let π denote the Lagrange multiplier for the budget balance constraint. We define Llowλ,π=maxclowx,y,λ,π, where clowx,y,λ,π can be denoted as
(20)Clowx,y,λ,π=∑i=1Nvixi−∑j=1Majyj−λ∑i=1Nxici−Cjres−Cj.−π∑j=1Majyj−∑i=1Mvixi,Then, we depose the Lagrangian relaxation problem into two subproblems shown as follows:21Llowλ,π=max∑i=1NLilowλ,π+max∑j=1MLjlowλ,π+λCjres+Cj,where
(22)Lilowλ,π=∑i=1Nxivi−λci+πvi,Ljlowλ,π=∑j=1Myj−aj−πaj,whereLilowλ,π defines a buyer’s subproblem (BS) while Ljlowλ,π defines a seller’s subproblem (SS). Interactions among subproblems are reflected through Lagrange multipliers. Note that for given λ,π, the optimal solution to BS Lilowλ,π and SS Ljlowλ,π can be solved as follows:
(23)xi=0,ifvi−λci+πvi<0,1,otherwise,yj=1,ifaj+πaj<0,0,otherwise,Although the combinatorial double auctions can be decomposed into a number of SS and BS which can be easily solved for given Lagrangian multipliersλ, π, mu, and β. However, it must be emphasized that it is not easy to find the optimal Lagrangian multipliers. Instead of directly solving the original optimization problem, the following dual problem is solved to determine the optimal Lagrangian multipliers:
(24)minλ≥0,π≥0−Llowλ,π.


### 5.4. Determining the Allocation

A key issue of the Lagrangian relaxation method is how to determine the value of the Lagrangian multipliers. We use a subgradient method to determine Lagrange multipliers by iteratively adjusting their values according to methods that violate the corresponding constraints. The value of the Lagrangian multipliers will increase and its value will decrease if the corresponding constraint is violated.Our approach to finding solutions to dual problems is based on the iterative scheme by adjusting Lagrange multipliers based on the solution of SS and BS. Letl be an iterative index. Let xl and yl denote the optimal solution for SS and BS, respectively. The subgradients of Lagrange multipliers λ and π are shown as follows:
(25)g1l=∑i=1Nxici−Cjres−Cjg2l=∑j=1Maiyi−∑i=1NvixiLagrangian multipliers are adjusted according to the subgra- dients defined above. If subgradientg1lj, g2lj, g3lj or g4lj is greater than zero, it means that the corresponding constraint is violated. In this case, the corresponding Lagrangian multiplier λjl+1, πjl+1, μjl+1, or β will be increased shown as follows:
(26)λl+1=λl+α1lg1lj,ifλl+α1lg1l≥0,0,otherwise,πl+1=πl+α2lg2l,ifπl+α2lg2l≥0,0,otherwise,where α1l=α2l is set as a suitable step size.In our algorithm, donateλ0 and π0 as the Lagrangian multipliers λl and πl initialized value, respectively, for the first iteration. Our algorithm then finds xil and yjl for λl and πl. It then calculates λl and πl and adjust λl and πl to obtain λl+1 and πl+1 iteratively until the algorithm converges.


### 5.5. How to Price the Winning Bidders?

For pricing the winning bidders for ensuring the incentive compatibility, we also design a VCG-like scheme which can suit approximate algorithms, in which we introduce a base price. Each type of resources has a base price, and a user who is the winner will pay the larger one between the base price and the VCG price. The charged price can be formulated as follows:(27)Pki=maxPkbasei,Pkvcgi,where
(28)Pkbase=bi,Pkvcgi=vkckci,where Pkbasei represents the base price of user i, and Pkvcgi is the VCG price. We will choose Pkbasei as the final payment price in the case that the VCG price is smaller, or else, the VCG price will be chosen.For solving the WDP for CCSPs in the upper level auction, we propose two algorithms which are all approximate algorithms, the pricing scheme of which is similar to that in lower level auction. In this case, the description of the pricing scheme will be omitted here.


#### 5.5.1. Analysis of Economic Properties

In this part, we will make an analysis on the properties of the proposed multiple-seller multibuyer hierarchical auction mechanism.Theorem 4.
The hierarchical multiple-seller multibuyer auction mechanism proposed in this paper is individually rational for all truthful bidders in both two levels.Proof of Theorem 4.
The VCG solution and the precise WDP solution algorithm proved to be individually rational [23], for greedy algorithm with corresponding pricing scheme have been proved individually above. In addition, for Lagrange multiplier algorithm with corresponding pricing scheme, two cases are also considered by us. The proof process is similar to the above one and is omitted here.Theorem 5.
The hierarchical multiple-seller multibuyer auction mechanism proposed in this paper is incentively compatible for all truthful bidders in both two levels. The proof process is similar to the previous section and is omitted here.Theorem 6.
The hierarchical multiple-seller multibuyer auction mechanism proposed in this paper achieves allocation efficiency with truthful bidding in both two levels.This result can be easily proved from the winner determination problem formulation for which the sum of accepted bids is maximized.


## 5.1. WDP Problem Formulation

With submitted asks and bids, the winnerdetermination problem can be formulated to determine the winning bidders. In the lower level double auction, the WDP is formulated as follows:(18)Maximize∑i=1Nvixi−∑j=1Majyj,SubjecttoC1:∑i=1Nxici≤Cjres+Cj,C2:∑i=1Nvixi≥,C3:xi∈0,1,∀i∈N,C4:yj∈0,1,∀j∈M,where the objective is to maximize the surplus between the buyers’ valuations and the sellers’ asks. C1 is the resource cap constraint. Constraint C2 ensures that a miner can get resources from only one MESP. Constraint C3 ensures that a MESP can offer resources to only one mobile user. Similarly, the WDP in the upper level is formulated as follows:
(19)Maximize∑i=1Nvixi−∑j=1Majyj,SubjecttoC1:∑i=1MxiCi≤Cjup,C2:∑i=1Mvixi≥∑j=1Qajyj,C3:xi∈0,1,∀i∈M,C4:yj∈0,1,∀j∈Q.


## 5.2. Solving the WDPs in the Hierarchical Double Auction?

For solving the multiple-seller multibuyer hierarchical double auction, backward induction is also used. For the lower level auction, similar schemes in the previous section can be applied. And for solving the WDP in the upper level, we propose a Lagrange multiplier algorithm.In computer science, we often use “divide-and-conquer” to reduce computational complexity to solve the complex problems [24]. In this case, we consider the Lagrange multiplier algorithm to solve the WDP problem to get an approximate optimal solution which can be divided into two steps (including problem decomposition and determining the allocation).


## 5.3. Problem Decomposition

The algorithm solves the problem by the way of decomposing the problem into two or more subproblems, which are easily solved directly. The solution then combines these subproblems to construct a solution to the original problem. Lagrangian relaxation is used to provide a technique to decompose the problem into several subproblems. One way to reduce the burden of solving WDP calculations is to use Lagrangian relaxation to establish a fictitious market to determine allocation.The basic idea of Lagrangian relaxation is to relax some of the constraints of the original problem on the objective function with a penalty term. That is, infeasible solutions to the original problem are allowed, but they are penalized in the objective function in proportion to the number of infeasibility. Under the condition of relaxed constraints selected, the constraint conditions are selected so that the optimization problem under the remaining constraints is easy in a certain sense. In the above WDP problem in the lower level, we observe that the coupling between different operations is caused by C1 and C2 constraints.Letλ denotes the Lagrange multiplier for the computing resource constraint. In addition, let π denote the Lagrange multiplier for the budget balance constraint. We define Llowλ,π=maxclowx,y,λ,π, where clowx,y,λ,π can be denoted as
(20)Clowx,y,λ,π=∑i=1Nvixi−∑j=1Majyj−λ∑i=1Nxici−Cjres−Cj.−π∑j=1Majyj−∑i=1Mvixi,Then, we depose the Lagrangian relaxation problem into two subproblems shown as follows:21Llowλ,π=max∑i=1NLilowλ,π+max∑j=1MLjlowλ,π+λCjres+Cj,where
(22)Lilowλ,π=∑i=1Nxivi−λci+πvi,Ljlowλ,π=∑j=1Myj−aj−πaj,whereLilowλ,π defines a buyer’s subproblem (BS) while Ljlowλ,π defines a seller’s subproblem (SS). Interactions among subproblems are reflected through Lagrange multipliers. Note that for given λ,π, the optimal solution to BS Lilowλ,π and SS Ljlowλ,π can be solved as follows:
(23)xi=0,ifvi−λci+πvi<0,1,otherwise,yj=1,ifaj+πaj<0,0,otherwise,Although the combinatorial double auctions can be decomposed into a number of SS and BS which can be easily solved for given Lagrangian multipliersλ, π, mu, and β. However, it must be emphasized that it is not easy to find the optimal Lagrangian multipliers. Instead of directly solving the original optimization problem, the following dual problem is solved to determine the optimal Lagrangian multipliers:
(24)minλ≥0,π≥0−Llowλ,π.


## 5.4. Determining the Allocation

A key issue of the Lagrangian relaxation method is how to determine the value of the Lagrangian multipliers. We use a subgradient method to determine Lagrange multipliers by iteratively adjusting their values according to methods that violate the corresponding constraints. The value of the Lagrangian multipliers will increase and its value will decrease if the corresponding constraint is violated.Our approach to finding solutions to dual problems is based on the iterative scheme by adjusting Lagrange multipliers based on the solution of SS and BS. Letl be an iterative index. Let xl and yl denote the optimal solution for SS and BS, respectively. The subgradients of Lagrange multipliers λ and π are shown as follows:
(25)g1l=∑i=1Nxici−Cjres−Cjg2l=∑j=1Maiyi−∑i=1NvixiLagrangian multipliers are adjusted according to the subgra- dients defined above. If subgradientg1lj, g2lj, g3lj or g4lj is greater than zero, it means that the corresponding constraint is violated. In this case, the corresponding Lagrangian multiplier λjl+1, πjl+1, μjl+1, or β will be increased shown as follows:
(26)λl+1=λl+α1lg1lj,ifλl+α1lg1l≥0,0,otherwise,πl+1=πl+α2lg2l,ifπl+α2lg2l≥0,0,otherwise,where α1l=α2l is set as a suitable step size.In our algorithm, donateλ0 and π0 as the Lagrangian multipliers λl and πl initialized value, respectively, for the first iteration. Our algorithm then finds xil and yjl for λl and πl. It then calculates λl and πl and adjust λl and πl to obtain λl+1 and πl+1 iteratively until the algorithm converges.


## 5.5. How to Price the Winning Bidders?

For pricing the winning bidders for ensuring the incentive compatibility, we also design a VCG-like scheme which can suit approximate algorithms, in which we introduce a base price. Each type of resources has a base price, and a user who is the winner will pay the larger one between the base price and the VCG price. The charged price can be formulated as follows:(27)Pki=maxPkbasei,Pkvcgi,where
(28)Pkbase=bi,Pkvcgi=vkckci,where Pkbasei represents the base price of user i, and Pkvcgi is the VCG price. We will choose Pkbasei as the final payment price in the case that the VCG price is smaller, or else, the VCG price will be chosen.For solving the WDP for CCSPs in the upper level auction, we propose two algorithms which are all approximate algorithms, the pricing scheme of which is similar to that in lower level auction. In this case, the description of the pricing scheme will be omitted here.


### 5.5.1. Analysis of Economic Properties

In this part, we will make an analysis on the properties of the proposed multiple-seller multibuyer hierarchical auction mechanism.Theorem 4.
The hierarchical multiple-seller multibuyer auction mechanism proposed in this paper is individually rational for all truthful bidders in both two levels.Proof of Theorem 4.
The VCG solution and the precise WDP solution algorithm proved to be individually rational [23], for greedy algorithm with corresponding pricing scheme have been proved individually above. In addition, for Lagrange multiplier algorithm with corresponding pricing scheme, two cases are also considered by us. The proof process is similar to the above one and is omitted here.Theorem 5.
The hierarchical multiple-seller multibuyer auction mechanism proposed in this paper is incentively compatible for all truthful bidders in both two levels. The proof process is similar to the previous section and is omitted here.Theorem 6.
The hierarchical multiple-seller multibuyer auction mechanism proposed in this paper achieves allocation efficiency with truthful bidding in both two levels.This result can be easily proved from the winner determination problem formulation for which the sum of accepted bids is maximized.


## 5.5.1. Analysis of Economic Properties

In this part, we will make an analysis on the properties of the proposed multiple-seller multibuyer hierarchical auction mechanism.Theorem 4.
The hierarchical multiple-seller multibuyer auction mechanism proposed in this paper is individually rational for all truthful bidders in both two levels.Proof of Theorem 4.
The VCG solution and the precise WDP solution algorithm proved to be individually rational [23], for greedy algorithm with corresponding pricing scheme have been proved individually above. In addition, for Lagrange multiplier algorithm with corresponding pricing scheme, two cases are also considered by us. The proof process is similar to the above one and is omitted here.Theorem 5.
The hierarchical multiple-seller multibuyer auction mechanism proposed in this paper is incentively compatible for all truthful bidders in both two levels. The proof process is similar to the previous section and is omitted here.Theorem 6.
The hierarchical multiple-seller multibuyer auction mechanism proposed in this paper achieves allocation efficiency with truthful bidding in both two levels.This result can be easily proved from the winner determination problem formulation for which the sum of accepted bids is maximized.


## 6. Performance Evaluation

For numerical analysis, we consider a CCSP with 10000 MIPS computing capacity. There are two MESPs each of which reserves 3000 MIPS computing capacity, and the leftover 4000 MIPS computing capacity are available for the upper level. There are 20 miners who want to be miners to solve the PoW problem considered in this paper. Each mobile user requestsc computing capacity. c is a uniformly distributed integer random variable within the interval [100, 1000]. The bandwidth is set as 200 kHz. The mining bonus T is varied from 0 to 6, and the transaction fee rate r is varied from 0.002 to 0.01. We set ς=0.6, λ=0.006, and τ=1. In addition, μ, ν is set as 1 and 0.5. The transaction size t of each miner is within the interval [100, 1000].For comparison, a fixed sharing scheme is considered, where each MESP reserves 4000 MIPS computing capacity in the upper level. Besides, a rand allocation scheme is considered in the upper level auction in which each MESP reserves computing capacity ranging from 3000 to 4000 MIPS. For the hierarchical combination auction problem, the upper level auction adopts Algorithm2 and Algorithm 3, fixed sharing and rand scheme, and the lower level auction adopts Algorithm 1.In order to investigate the results, Figure6 shows the average social welfare of these four algorithms. It can be seen that the average social welfare by using the DP algorithm can obtain the best social welfare. This indicates that the exact solutions can perform better than the approximate solutions do. We can also see that greedy algorithm can obtain better social welfare than both fixed and rand algorithms. This is because that the fixed algorithm and rand algorithm cannot consider the requirements of buyers, both of which lose the significance of the auction. The average resource utilization achieved by different algorithms is also investigated as shown in Figure 7. The results are consistent with those of social welfare. In addition, the effects of different number of miners on the average utilization are studied in Figure 8. According to the picture, we can see that the resource utilization obtained by the DP algorithm can do the best as the increasing number of miners. However, the DP algorithm is only suitable for the case of few users. When the number of users is relatively large, the greedy algorithm is more applicable. Because the time complexity of the DP algorithm is exponentially increasing and that of greedy algorithm increases linearly. Considering the efficiency requirements in real-world applications, the greedy algorithm will still be used in the case of large users.Figure 6
The average social welfare achieved by different algorithms.Figure 7
The average resource utilization achieved by different algorithms.Figure 8
Average resource utilization achieved by different algorithms with different numbers of miners.In addition, we compare the scheme which only considers edge computing with our proposed scheme which jointly considers edge computing and cloud computing in a satisfaction ratio with increasing number of mobile users as shown in Figure9. It can be seen that the satisfaction ratio is becoming lower with the increasing number of mobile users. This may be due to the number of mobile users growing, and competition among them becomes intense. In this case, the possibility of users gaining requested resources decreases, and naturally the satisfaction ratio becomes lower. We also can observe that joint consideration can achieve better satisfaction ratio than a uniform one. This is due to the fact that our proposed scheme which jointly considers edge computing can provide much more resources than the scheme which only considers edge computing.Figure 9
The comparison in satisfaction ratio with increasing number of mobile users.Also, we compare different algorithms using the multiple-seller multibuyer hierarchical auction. For comparison, we use the greedy algorithm termed as GA in the lower level auction and use both the greedy algorithm and the Lagrange multiplier algorithm termed as LA to resolve resource allocation problem in the upper level auction. We compare the average resource utilization achieved by different algorithms with increasing number of mobile users shown in Figure10. It can be seen that the Lagrange multiplier algorithm can do better than the greedy algorithm. The Lagrange multiplier algorithm may be more exact than the greedy algorithm. Moreover, we compare the total utility achieved by different algorithms with increasing number of mobile users shown in Figure 11. We can see that the Lagrange multiplier algorithm can do better than the greedy algorithm. The increasing ratio in Figure 11 gets bigger at first and then it flattens out. The reason may be that at first as the number of mobile users increases, the competition becomes more and more fierce. However, when the number of mobile users increases to a certain level, the resource volume reaches a bottleneck, which makes the total utility flatten out.Figure 10
The average resource utilization achieved by different algorithms with increasing number of mobile users.Figure 11
The total utility achieved by different algorithms with increasing number of mobile users.


## 7. Conclusion

In this paper, a hierarchical combinatorial auction model has been proposed to solve the problem of resource allocation for mobile blockchain. Specifically, we have formulated winner determination problems (WDPs) for mobile edge computing providers and the cloud computing provider, and relevant computationally tractable algorithms to solve these problems have also been proposed. Besides, different pricing schemes have been designed to determine the final prices. The properties of the proposed schemes have also been proved theoretically. We then extend a single-seller multibuyer hierarchical auction to a multiple-seller multibuyer hierarchical auction, for which corresponding WDPs, tractable algorithms, and pricing scheme are also designed. Finally, the effectiveness of the schemes are verified by simulation and comparison.



---

*Source: 8874862-2020-08-14.xml*