{'fraction_non_alphanumeric': 0.029671801741460148, 'fraction_numerical': 0.007702612190221032, 'mean_word_length': 4.425923682616596, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Privacy-Preserving Strategyproof Auction Mechanisms for Resource Allocation

: In recent years, auction theory has been extensively studied and many state-of-the-art solutions have been proposed aiming at allocating scarce resources. However, most of these studies assume that the auctioneer is always trustworthy in the sealed-bid auctions, which is not always true in a more realistic scenario. Besides the privacy-preserving issue, the performance guarantee of social efﬁciency maximization is also crucial for auction mechanism design. In this paper, we study the auction mechanisms that consider the above two aspects. We discuss two multi-unit auction models: the identical multiple-items auction and the distinct multiple-items auction. Since the problem of determining a multi-unit auction mechanism that can maximize its social efﬁciency is NP-hard, we design a series of nearly optimal multi-unit auction mechanisms for the proposed models. We prove that the proposed auction mechanisms are strategyproof. Moreover, we also prove that the privacy of bid value from each bidder can be preserved in the auction mechanisms. To the best of our knowledge, this is the ﬁrst work on the strategyproof multi-unit auction mechanisms that simultaneously consider privacy preservation and social efﬁciency maximization. The extensive simulations show that the proposed mechanisms have low computation and communication overheads.


Introduction
Resource allocation is one of the most important issues in many areas. Typical examples include the virtual machine resource allocation in cloud computing, spectrum resource allocation in wireless communications, and so on. Since an auction is a fair and efficient resource allocation in the real world, it has also been introduced into the networking area, especially for scarce resource allocations. By far, many auction mechanisms have been designed for different resource allocation problems, such as the computing resources in the cloud [1] , spectrum licenses [2][3][4] , cellular networks [5] , and CRNs [6] .
Strategyproofness (a.k.a., truthfulness) is regarded as one of the key objectives in the auction mechanism design, which means that the optimal strategy for bidders is to bid their true valuations of the items for sale. Most of the auction mechanisms are designed to charge each winner a minimum bid value, by which she can win the auction, to ensure the strategyproofness of the bidders [7] . Unfortunately, the auctioneer may not always be trustworthy. Once the true valuation of each bidder is revealed to an untrustworthy auctioneer, he may take advantage of it to maximize his profits. For instance, suppose you value some items at $100, and submit the true valuation to the auctioneer in a sealedbid auction. Actually, the minimum bid value that you will win in the auction is $50. However, the auctioneer is willing to charge you $99 to maximize the profits, instead of charging you $50 for strategyproofness. In this situation, will you still submit your true valuation to the auctioneer?
To address the above problem, the bid values should be hidden throughout the whole procedure of the auction. Thus, protecting the privacy of bids should be regarded as an attractive objective in the design of auction mechanisms. In recent years, some researchers have dedicated their efforts in the auction mechanism design to privacy preservation. For instance, in Refs. [8,9], the authors designed mechanisms to protect the bid value in the first-price and the second-price sealedbid auctions. Huang et al. [10] proposed a strategyproof and bid privacy-preserving auction mechanism for spectrum allocation. Pan et al. [11,12] gave a secure combinatorial spectrum auction by using homomorphic encryption to deal with the untrustworthy auctioneer. However, none of these privacy-preserving auction mechanisms provided any performance guarantee on social efficiency, i.e., the total bid value of winners, which is a standard and critical auction metric [13,14] .
In this paper, we focus on the privacy-preserving and strategyproof auction mechanism design for resource allocation, which can simultaneously maximize the social efficiency. We observe that most of the existing auction mechanisms fail to consider the multiple-items trading. Nevertheless, bidders in practical applications may often express their preferences for a specified number of items or some specified bundles of items, instead of an individual item. This kind of auction is called as the multi-unit auction. There are two types of multi-unit auctions, in which the items to be sold are identical or distinct. In this paper, we will propose two auction mechanisms to manage the identical case and the distinct case, respectively. For the identical case, the demand of each bidder is a fixed number of items, which is inseparable. For example, if a cloud computing job requires 35 time slices, the bidder must auction off at least 35 time slices. It is meaningless to win an auction with less than 35 time slices. The auction of distinct items is also known as a combinatorial auction. In a combinatorial auction, all bidders can bid for bundles of items rather than individual items [15] . For instance, if a user wants to run a cloud application by using 130 CPUs and 8 GB of storage from 8AM to 10AM, the user will only be interested in the entire bundle of resources for meeting the demand. In addition, the bid value and the required items of each bidder are private and sensitive information of auctions, since the auctioneer might raise the price in future auctions to maximize the profit after learning these information. Hence, we need to protect the privacy of these sensitive information throughout the whole auction. Meanwhile, we also need to let the auctioneer know each winner's demand so that the auction can be completed.
Designing a multi-unit auction mechanism with the maximum social efficiency is an NP-hard problem [16] . Many efficient approximation algorithms have been proposed for both the Identical items Auction model (IA model) and Combinatorial Auctions model (CA model). For example, there is a Polynomial Time Approximation Scheme (PTAS), which is suitable for the IA auction model, as well as an approximation algorithm with an approximation factor of p h that has been proved to be a tight one for the CA. Our work is not to design approximation algorithms to improve the performance of the existing studies, but to construct the mechanisms with privacy preservation, based on these existing approximation mechanisms.
However, the computation burden, which relies on the bid values of bidders, is too heavy in the existing approximation algorithms with good performance guarantee. Thus, the task of designing privacypreserving auction mechanisms while guaranteeing high performance is very challenging. To tackle this problem, we introduce an agent into our auction model, which is a semi-trusted third-party and can help the auctioneer to decide the winners and compute their charges. In our design, the auctioneer generates a public key and a secret key of Paillier's homomorphic cryptosystem. Bidders encrypt their bids by using the public key. Then, the agent performs homomorphic computation on the ciphertexts, adds random numbers, and sends the results to the auctioneer for making an allocation decision and computing the payment of the winners. Such a design ensures the privacy protection without affecting the correctness of the auctions. Moreover, the extra costs incurred by this design are negligible. The whole auction mechanisms still have low computation and communication overheads.
Although there exists a PTAS for the IA model, it is a very challenging work to design a privacy-preserving version of PTAS. We propose a privacypreserving bid mechanism with an approximation factor of 2. For the combinatorial auction, we provide a privacy-preserving version of the auction mechanism proposed in Ref. [17], which has an approximation factor of p h. We prove that our new method for CA can protect both the bid values of all bidders and the items that each loser wants to buy. To the best of our knowledge, the auction mechanisms presented in this paper are the first strategyproof and privacy-preserving multi-unit auction mechanisms with a social efficiency performance guarantee.
The rest of the paper is organized as follows: Section 2 introduces some necessary preliminaries. Section 3 designs an approximately optimal social efficiency and privacy-preserving strategyproof auction mechanism for identical items. In Section 4, we further introduce a combinatorial auction with privacy-preserving. Section 5 evaluates the performance of our approach. Section 6 discusses the related literature and Section 7 concludes the paper.

Model, Problem, and Preliminaries
In this section, we first briefly introduce the auction system model. Then, we illustrate the necessary economic property of an auction mechanism and state our auction design targets in Section 2.2. In Section 2.3, we review the cryptographic tools used in this paper.

Auction model
In recent years, auctions have been deemed as a preeminent means to allocate resources in many areas. Many resource allocation problems can directly be seen as (resource) auction problems. In general, our auction design is not limited to a concrete resource allocation problem. Here we directly present the auction model, which can manage many resource allocation problems. Consider a sealed-bid auction, as shown in Fig. 1, in which there exists an auctioneer, a set of bidders, and an agent. At the beginning of the auction, all the bidders first encrypt their bids by using the public key generated from the agent, and then submit their encrypted bids to the auctioneer. Next, the auctioneer allocates the items to the bidders, and decides the charges for the winners after communicating with the agent. We assume that the agent is a semi-trusted third-party, who is curious about the bid values of the bidders, but will not collude with the auctioneer.
We study two auction models in this paper: IA Each bidder i is only interested in a fixed number of items, denoted by N i , and is willing to pay no more than v i for all items. In the CA model, the items in the market are distinct, and each bidder i 2 B wants to buy the items in a specified subset c i Â I. Note that in both the IA model and the CA model, the demand of each bidder is inseparable, which means that bidder i will get all the items that he wants to buy if he wins.

Auction goals
The goals of our auction mechanism are two-fold: (1) the proposed auction mechanism should preserve some economic properties, such as strategyproof and social efficiency maximization; and (2) the auction mechanism should preserve the privacy of bidders. The detailed description follows. Our primary goal is to design a strategyproof auction mechanism which can maximize the social efficiency. We define the social efficiency of an auction as the total bid values of the winning bidders. Suppose b i , v i , and p i are the bid value, true valuation, and the payment of bidder i for all the items he wants to buy, respectively. Then, the utility of bidder i is defined as Strategyproofness is often regarded as one of the most crucial properties of auction mechanisms. We say an auction is strategyproof if bidding truthfully is the dominant strategy for each bidder. Therefore, we need to prove that for each bidder i , u i is maximized when b i D v i to ensure the strategyproofness of bidders. It has been proven by Myerson that an auction is strategyproof, if and only if the following two conditions hold: Bid-monotone Constraint: The items allocation mechanism is bid-monotone, which means that, when bidder i wins the auction by bidding b i , he will always win by bidding b 0 i > b i . Critical value Constraint: The charge from a winner i is his critical value, i.e., the minimum bid that he will win the auction. Following this direction, we design the strategyproof auction mechanisms to satisfy the above-mentioned characteristics.
The privacy goals of our auction mechanisms are as follows: In the IA model, we protect the bid values of bidders, which means that all bids from bidders are blind to both the auctioneer and the agent. In the CA model, neither the auctioneer nor the agent knows the true bid values of bidders. Nor do they know which items each loser wants to get.

Paillier's homomorphic encryption cryptosystem
We use a 1024-bit length Paillier's homomorphic encryption system in this paper, which satisfies the following homomorphic operations: where E.msg i / is the ciphertext of message msg i . To facilitate reading, we summarize some symbols that are used in this paper in Table 1.

Application scenario illustration
In this subsection, we illustrate two typical application scenarios for the IA model and the CA model, respectively.
For the IA model, we consider the virtual machine resource allocation in cloud computing. In an infrastructure-as-a-service cloud, the computation resources (e.g., CPU, RAM, disk) have been packed into some virtual machines. Cloud users can request some virtual machines to run their computational tasks. For example, Amazon EC2 can provide seven categories and 23 types of virtual machines. When EC2 users want to request some virtual machines of the same type, the corresponding virtual machine allocation problem will fall into the IA model, and can Table 1 Some symbols used in this paper.

Symbol
Meaning I, B The set of items and bidders in the auction h, m The number of items and bidders in the auction The number / combination of items bidder i wants to buy v i , b i , p i The true valuation, bid value, and payment of bidder i for all the items he wants to buy u i The utility of bidder i EK;DK The encrypt key and decrypt key of the agent E.msg/ The ciphertext of message msg i 0 The bidder with rank i in the sorted bid set The permutation for the ID of bidders and items be solved by our proposed auction mechanism. Most existing studies focus on the storage and computational privacy in cloud computing. Only a few studies consider the bid privacy in the process of the resource allocation of cloud computing. None of them likes our solution considers strategyproofness, privacy, and the performance guarantee simultaneously. For the CA model, we consider a spectrum auction scenario where the spectrum channels are heterogeneous, due to the different frequencies, bandwidths, and licensed areas. All the spectrum channels in the market are viewed as items in the CA model. The new spectrum demanders are viewed as the bidders. Each bidder i needs a combination of spectrum channels, which is c i in the CA model. Then, the spectrum auction problem in this setting is exactly a concrete CA problem. Spectrum auctions have been widely studied in recent years, but only a few studies consider the privacy-preserving issue in their work. To the best of our knowledge, our work is the first to provide a strategyproof and privacy-preserving solution for the combinatorial spectrum auction problem.

Identical Items Auction Mechanism Design with Privacy Preservation (IAMP)
In this section, we propose an IAMP design, which achieves an approximately optimal social efficiency and supports privacy preservation. Our auction mechanism mainly consists of three steps: bidding, allocation, and payment calculation.

Bidding
Before running the auction, the agent first generates an encryption key EK and a decryption key DK of Paillier's cryptosystem. Then, the agent publishes EK as a public key, and keeps DK private. We assume that the parameter n is 1024-bit length in this work. Each bidder i encrypts the bid b i to E.b i /, and sends .E.b i /; N i / to the auctioneer, where N i is the number of items that he wants to buy.

Allocation mechanism
After receiving the encrypted bids from the bidders, the auctioneer needs to decide on the winner aiming to maximize the social efficiency. However, the social efficiency maximization problem can be reduced to the Knapsack Problem, which is a well-known NP-hard problem. To address this NP-hard problem, a PTAS has been proposed in Ref. [18], which is also suitable for our model. Unfortunately, there is a large computation and comparison overload in this PTAS, since it is based on dynamic programming. It is very difficult to design a bid privacy preservation version based on this PTAS. Therefore, we build our privacy-preserving method based on another approximation algorithm, which can approximate the optimal allocation within a factor of 2.
The main idea of the approximation method we used is depicted as follows: (1) We first sort the per-unit bid values of bidders in non-increasing order: where .i/ is the i -th bidder in the sorted bid set.
(2) Then, we find the critical bidder .k/, which satisfies where h is the number of items in the market. Proof Suppose O is the set of bidders in the optimal solution, and w.
Then, we can easily obtain This completes our proof. The details of our allocation mechanism with privacy preservation is depicted in Algorithm 1. First, we sort the per-unit bid values of bidders to decide the winners. To address the issue of privacy-preserving, bidders first encrypt their bids using the encryption key of the agent, and submit the encrypted bids to the auctioneer. Then, the auctioneer masks them by using two random values ı 1 2 Z 2 1 and ı 2 2 Z 2 2 as ı 1 b i C ı 2 N i . Note that the range OE1; 2 1 and OE1; 2 2 for ı 1 and ı 2 should be selected based on the consideration of the correctness of the modular operations: ı 1 b i C ı 2 N i should be smaller than the modulo used in Paillier's system. Since the agent has the decryption key, he can compute and sort ı 1 b i N i C ı 2 into non-increasing order without accessing any true bid values of the bidders. Furthermore, the Algorithm 1 Allocation mechanism for identical items model 1: The auctioneer randomly picks two integers ı 1 2 Z 2 1012 , ı 2 2 Z 2 1022 , and executes the homomorphic operation: 2: Then, the auctioneer maps the ID of bidders by using permutation W Z m ! Z m , and sends fE.ı 1 b i C ı 2 N i /; N i ; .i/g i 2B to the agent. 3: The agent decrypts E.ı 1 b i C ı 2 N i / by using his private key 4: The agent finds the critical bidder .k/ by computing: 5: To decide the winners, the agent sends .f .i/g i<k ; .k// to the auctioneer, where f .i/g i<k is out of order. 6: The auctioneer randomly picks two integers ı 3 2 Z 2 1012 , ı 4 2 Z 2 1022 , computes the following and sends the result back to the agent.
7: After receiving the ciphertexts, the agent decrypts them, and otherwise, the agent sends .k/ to the auctioneer. 8: The auctioneer chooses the bidders that the agent sends to him as winners, and sets other bidders as losers.
auctioneer also maps the true ID of the bidders by using a permutation before sending fE.
to the agent. Thus, the agent cannot map the masked bids fı 1 b i C ı 2 N i g i 2B to the bidders either. Then, we need to find the bidders with the top k 1 per-unit bids and the bidder with the k-th per-unit bid. The agent can do this easily with the sorted per-unit bids. Next, the agent sends the permutated ID of the bidders with the top k per-unit bids to the auctioneer. Then, the auctioneer computes the encrypted bid sum of the bidders with the top k 1 per-unit bids. Since the agent has the decryption key, the auctioneer then randomly chooses two integers, ı 3 and ı 4 , to hide the true value of b .i/ / and E.b .k/ /, and communicates with the agent to judge which one is bigger and further decides the winning bidders.
Next, we will show that our allocation mechanism for the IA model is bid-monotone.
Lemma 2 The proposed allocation mechanism is bid-monotone, which means that if bidder .i / wins by bidding b .i/ , he will always win by bidding b 0 Proof In our allocation mechanism, we set the bidder .k/ to win the auction, or the bidders with the top k 1 per-unit bids to win the auction. In the case of bidder .k/ winning the auction, we can easily Thus, bidder .k/ will always win no matter whether b 0 .k/ N .k/ is the k-th highest per-unit bid or not.
In the case of the bidders with the top k 1 perunit bids winning the auction, the bidders who are in the bidder set with the top k 1 per-unit bids remain unchanged when any of the k 1 bidders increase their bid. Suppose bidder .j / increases his bid to b 0 .j / , we can easily get that Thus, the bidders with the top k 1 bids will also win the auction. This completes our proof.

Payment calculation mechanism
It has been proven that an auction is strategyproof if and only if its winner determination mechanism is bidmonotone and it always charges each winner its critical value. We have proved that our allocation mechanism is bid-monotone, which indicates that there exists a critical value for each winner. Hence, the objective of this step is to compute the critical values of the winners with privacy preservation. Since our allocation mechanism is bid-monotone, there must exist some intervals denoted by OEL i ; U i , which satisfy that bidder .i / wins the auction provided the bidder's per-unit bid value is larger than the L i -th per-unit bid value in the sorted bid list and always loses if the bidder's per-unit bid value is less than the U i -th per-unit bid value. Here, OEL i ; U i is the critical interval of the winner .i / if L i D U i 1. It is not difficult to see that i is the lower bound of L i , and f is the upper bound of U i which satisfies: Obviously, the critical value of each winner .i/ is less than the L i -th bid value, and larger than the U ith bid value. To find the critical value of each winner, we first compute their critical intervals. As shown in Algorithm 2, we use a binary search to compute the critical interval for each winner .i /. In each round of the binary search, we set the per-unit bid of bidder  .i / is found. After obtaining the critical interval of each winner, we compute their critical values. For the case that winner .i / is the new k-th bidder, and the per-unit bid value is smaller than the L i -th, but larger than the U i -th per-unit bid value in the sorted list, we compute the critical value p .i / of winner .i / as follows: In the other case, the critical value of winner .i / is The details of our payment calculation mechanism with privacy preservation are described in Algorithm 3.
We have proved that our allocation mechanism is bidmonotone, and we charge each winner their respective critical value, thus we can also obtain Algorithm 1.

Algorithm 3 Payment calculation for winner σ(i)
The auctioneer randomly chooses two integers ı 5 2 Z 2 1012 , ı 6 2 Z 2 1022 , computes the following and sends the results to the agent.
After receiving the ciphertext, the agent computes p 0 Theorem 1 The auction mechanism we proposed is strategyproof.
Since the goal of this work is to design a strategyproof auction mechanism with privacy preservation, we will show that the proposed IAMP protects the true bid values of bidders in the next subsection.

Security analysis
The most important target of our auction mechanism is to protect the bid values of the bidders. There are two main parties in our mechanism, the auctioneer and the agent. In the following, we will show that the bid values of the bidders are blind for both the auctioneer and the agent.
Theorem 2 Our auction mechanism for identicalitems guarantees bid privacy.
Proof In our auction mechanism for identical items, the auctioneer can only obtain the encrypted bids of the bidders and the payments of the winners. Without the decryption key, the auctioneer cannot derive any other information from these encrypted bids. The auctioneer knows the payments of the winners but cannot construct the equations among them since the auctioneer does not know exactly which variables are involved in these equations, i.e., the auctioneer cannot determine which value is larger than the other in the payment equations. Thus, the bid values of the bidders can be well preserved from the auctioneer.
The agent holds the decryption key but has no direct access to the encrypted bids. According to our auction mechanism, the agent will receive many encrypted bids or bid sums which are masked by random numbers. Assume that the number of bids or bid sums received by the agent is n. With these bids or bid sums, the agent can build n functions that contain no less than n C 2 bids, bid sums, or random numbers. Since the number of variables is larger than the number of functions, the agent cannot decrypt any true bid values of the bidders. Furthermore, the payment of each winner is also considered. Note that the IDs of the bidders are permutated by the auctioneer. Thus, the agent cannot map the payment equation to each winner with the auction results, indicating that the true bid values of the bidders are blind for the agent.
In conclusion, the bids of the bidders are blind to both the auctioneer and the agent. That is, our auction mechanism for identical-items guarantees bid privacy.

Combinatorial Auction Mechanism Design with Privacy Preservation (CAMP)
In this section, we propose a CAMP design, which also achieves strategyproofness and maximizes social efficiency. Compared with IAMP, CAMP not only protects the true bid values of the bidders, but also preserves the demands of the losers.

Bidding
Like the bidding process in IAMP, the agent first generates encryption and decryption keys of Paillier's cryptosystem, and publishes the EK. Then, each bidder encrypts b i = p jc i j using the EK of the agent and sends the results to the auctioneer. However, all the bidders not only want to protect their own bids in our CA model, but also want to hide the items that they want to buy if they lose in the auction. Thus, each bidder will also encrypt the targeted set of items. Let X i D fx i;1 ; x i;2 ; :::; x i;h g be the demand vector of bidder i , where x i;j D 1 if I j 2 c i , otherwise x i;j D 0: For each x i;j , bidder i generates a random integer r and encrypts x i;j using the EK of the agent. Finally, bidder i sends .E.b i = p jc i j/; E.X i // to the auctioneer, where E.X i / D fE.x i;1 /; E.x i;2 /; :::; E.x i;h /g. Table 2 shows an example of the demand and encrypted demand of the bidders when h D 5.

Allocation mechanism
After receiving the encrypted bids and demands from the bidders, the auctioneer selects a set of bidders as winners if the social efficiency is maximized. It has been proven in Ref. [17] that the social efficiency maximization problem in the combinatorial auction is NP-hard, and the upper bound of approximation ratios of the polynomial time algorithms is p h. Dong et al. proposed an auction mechanism with a greedy allocation mechanism in Ref. [17], which can approximate the optimal one within a factor of p h. We briefly describe this mechanism below: First, a normalized bid b i p jc i j for each bid b i is calculated, and then the bidders are sorted according to the non-increasing order of the normalized bids. Next, the greedy allocation mechanism examines every bidder in the sorted list sequentially, and grants the bidder only if his demand does not overlap with all the demands of the previously granted bidders. Assume l.i / is the first bidder following i in the sorted list that has been denied but has been granted were it not for the presence of i . Then, bidder i pays zero if his bid is denied or l.i / does not exist; otherwise, he pays p jc i j n l.i / , where n l.i / is the normalized bid of bidder l.i /. Following the CA mechanism stated above, only two operations rely on the true bid values of the bidders: sorting the bidders according to their normalized bids and computing the payment for each winner i using the normalized bid of l.i /. Thus, we can similarly perform the same steps in IAMP to protect the bid privacy of the bidders. However, the agent needs to know the demand vectors of all the bidders to check if they overlap with each other in the combinatorial auction. Therefore, the most challenging issue of designing privacy- Table 2 The demand and encrypted demand of bidders. preserving CA mechanism is to protect the demand of the losers. To manage this challenge, we encrypt the demand vector of the bidders. More specifically, we confuse the ID of the bidders and the ID of the items by separately using permutations 1 W Z m ! Z m and 2 W Z h ! Z h , before the auctioneer sends the demand vectors to the agent. With the confused information and decryption key, the agent can also obtain the overlapping information of the bidders, but can barely map them to the true demands of the losers. Furthermore, the auctioneer is only provided the encrypted demand vectors and the auction result but has no idea about the demands of each loser. Then, the demands privacy of the losers is protected. The detail of our allocation mechanism with privacy preservation is shown in Algorithm 4.

Payment calculation mechanism
Recall that an auction is strategyproof if and only if it is bid-monotone and always charges each winner its critical value. For each winner i in the greedy Algorithm 4 Allocation mechanism for combinatorial auction 1: The auctioneer randomly picks two integers ı 1 2 Z 2 1012 , ı 2 2 Z 2 1022 , executes the following homomorphic operation, and then sends f fE.x i;j /; 2 .j /g I j 2I g i 2B to the agent.
The agent decrypts the set of bids fE.ı 1 b i p jc i j C ı 2 /g i2B by using the private key, and reorders them in the descending order: allocation mechanism, the normalized bid is larger than the normalized bid of l.i /. Thus, n l.i / p jc i j is the critical value of winner i if l.i / exists. Otherwise, the critical value of winner i is zero. Our payment calculation mechanism is shown in Algorithm 5.

Security analysis
Theorem 3 Our combinatorial auction mechanism protects the demand c i of each loser i .
Proof Since the demand vectors of the bidders are encrypted and the auctioneer does not have the decryption key, the auctioneer cannot retrieve anything from the encrypted vectors. Moreover, the agent only sends the demand vectors of the winners to the auctioneer. Thus, the auctioneer has no means to access the true demands of the losers. For the agent, he can decrypt the demand vector of any bidder but cannot determine the exact demand of each loser i since the real relationships between items and the IDs of the bidders are permutated by permutation functions, which are only possessed by the auctioneer. Therefore, we can conclude that our CA mechanism protects the demands of the losers.
Theorem 4 Our CA mechanism guarantees bid privacy.
Proof Without loss of generality, let us consider the bid b i of bidder i . The auctioneer can obtain the encrypted bid E.b i / and p i D b l.i / p jc i j= p jc l.i / j for each winner i . Since b i has been encrypted, the auctioneer cannot retrieve any information from E.b i /. Moreover, the auctioneer does not know which items each loser bids for and has no idea which bidder is l.i/ of winner i . Thus, the auctioneer cannot find the bid value of any bidder from each p i .
Although the agent possesses the decryption key, he cannot directly access the encrypted bids as the encrypted bids are masked by the auctioneer using random numbers, before they are sent to the agent. With the masked bids, the agent can build m functions with m encrypted bids and two random numbers. Since the number of variables is greater than the number of functions, the agent cannot decrypt any true bid values of the bidders. The payment p i of each winner i is available to the agent. However, the IDs and the demand vectors of the bidders are disrupted by the auctioneer. Thus, the agent does not know l.i / either. That is, the agent still cannot determine the bid value of any bidder using the p i 's.
In conclusion, our CA mechanism guarantees bid privacy.

Simulation Results
In this section, we present our evaluation results and the performance analysis of our auction mechanisms, including the auction performance and the cost of computation and communication.

Auction performance
We first introduce two major metrics to evaluate the performance of the auction mechanism, namely social efficiency ratio and revenue ratio.
Social efficiency ratio: the social efficiency ratio is defined as the ratio between the social efficiency of our approximation mechanism and the optimal mechanism. Revenue ratio: the revenue for an auction is the total payment received from all winners, that is, the ratio between the revenue of our approximation mechanism and the optimal mechanism. However, it is challenging to obtain the optimal revenue. Thus, we use the optimal social efficiency instead of the optimal revenue in our simulation, which is an upper bound of the optimal revenue. In our simulation, we assume the bid values of the bidders are randomly distributed in the range OE0; 10 000, and the number of items that each bidder wants to buy is randomly distributed in the range OE1; N max , where N max is the maximum number of items that each bidder can bid. In each set of evaluations, we vary one factor among the bidder number, items number, and N max , while fixing the other two factors. In our CA0 model, we first randomly generate a number N i from OE1; N max for each bidder i, and then randomly choose N i items from the item set I as bidder i 's demand c i .
Since one of the important goals of the auction design is to maximize the social efficiency, we first evaluate the social efficiency ratio of our approximation algorithms. As shown in Fig. 2, the social efficiency ratio increases with the number of bidders in both the IAMP and CAMP mechanisms. Theoretically, both the weights of the optimal solution and that of our approximation solution should increase with the bidder number and the number of items. However, we find an interesting result: the social efficiency ratio decreases with the increasing number of the items in CAMP. One possible reason is that, when the number of items increase, the optimal social efficiency increases faster than the approximation solution in CAMP, but increases slower than the approximation solution in other cases. We fix the number of bidders and items, and increase the maximum number of items that each bidder wants to buy, as shown in Fig. 2c. Due to the demands of the bidders being inseparable, the social efficiency ratio curve of the IA model declines with increasing N max in Fig. 2c. However, in the CA model, more items are sold to bidders with high bid values and the social efficiency ratio increases with increasing N max . Besides, we can also learn from Fig. 2 that our approximation algorithms perform much better than the theoretical values, especially for the IA model.
In addition, we also compare the social efficiency of CAMP with a greedy mechanism. This greedy mechanism first sorts the bids of the bidders in descending order, and then scans the bidders oneby-one to decide which bidder wins the auction, as we did in CAMP. The simulation result is shown in Fig. 3. Obviously, CAMP has better performance than the greedy mechanism. This is mainly because the proposed CAMP sorts the bidders according to their normalized bids, while the greedy mechanism sorts the bidders according to their bids. Thus, the unit bid value of the winners in CAMP is larger than that in the greedy mechanism, which can lead to greater social efficiency.
The revenue ratios of our approximation algorithms are described in Fig. 4. Since we charge each winner their respective critical value in our auction mechanisms, then theoretically, the total payment for winners should increase when the competitive rate increases. Conversely, the competitive rate is affected by the bidder number, item number, and N max . Basically, our evaluation results corroborate the theoretical analysis. However, due to the similar reason as that provided for the social efficiency ratio, the performance of the revenue ratio decreases with the increasing number of items in CAMP, while performing opposite in IAMP.

Computation and communication overhead
We evaluate the computation and communication overhead of our approximation algorithms. Since computation overhead is dominated by the auctioneer and the agent in both auction models, we do not consider the bidders' computation overhead. As shown in Fig. 5, the auctioneer spends more time in the IA model than in the CA model. This is because the auctioneer spends most of his time computing the payments from the winners. However, we can easily find them in the CA model.
The run-time of each bidder is roughly 30 ms in the IA model. However, bidders need to encrypt their bids and demands in the CA model. Thus, the run time of the agent or a bidder is related to the number of items in the combinatorial auction. Our simulation results show that the run time of each bidder is roughly 180 ms in CAMP when h D 5, and the run-time of the agent is greater in IAMP.
In the evaluation, we set n to be of 1024-bit length. Figure 5c shows the communication overhead of our auction mechanisms with privacy preservation. It is found that the communication overhead of CAMP is much higher than that of IAMP. The main reason is that bidders encrypt only their bids in the IA, but encrypt both their bids and demands in the CA.

Comparison with prior state-of-art work
To show superiority of the proposed mechanisms, we compare the performance of our work with prior work in Ref. [19], and further prove that our mechanisms perform better than the mechanisms in Ref. [19].
First, we consider the performance of social efficiency. The IA model studied in this work is similar to the auction model stated in Ref. [19]. However, the optimal allocation problem studied in Ref. [19] can be solved in polynomial time, which is easier than ours. The CA models studied in our work and Ref. [19] are identical. It has been proven that the optimal allocation problem of the CA model is NP-hard. However, Ref. [19] proposed a privacy-preserving mechanism for the optimal allocation, but not for the approximation allocation. Thus, the proposed mechanism of Ref. [19] for the CA model cannot be solved in polynomial time either. Moreover, in the auction mechanism design, there are two procedures to be addressed. The first is the allocation mechanism design and the second is payment calculation. The work of Ref. [19] concentrates on the privacy-preserving allocation mechanism design, so the payment calculation is not mentioned.
Then, we compare the performance of privacy preservation. We proved that our mechanisms can protect the bid privacy of bidders if the auctioneer does not collude with the agent. There are three parties in Ref. [19], namely the weight publisher, the evaluator, and the mask publisher. The proposed mechanism can protect the bid privacy of the bidders when no more than t w evaluators and t m mask publishers collude with each other. Note that the number of evaluators is no less than the possible maximal bid value, i.e., there are at least 1000 evaluators if the maximal bid is 1000. There is only one auctioneer and one agent in our mechanisms; thus, the privacy preservation of our mechanisms is easier to achieve than the mechanisms proposed in Ref. [19].  [19] is O.e .l C .t m C 1/ .log e C l C n log e///, where l D mh, e is the number of evaluators, t m C 1 is the number of mask publishers, and each bidder will submit the fraction of bid to n evaluators. Clearly, the communication overhead of our mechanism is lower than the mechanisms proposed in Ref. [19].

Literature Review
Many solutions have been proposed in previous literature to address the scarcity problem of the limited resources, such as radio spectrum, emissions permits, and airport landing slots. The auction has been shown to be one of the most effective methods among all the solutions. However, most studies on auctions (e.g., Refs. [3,4,[20][21][22]) only allow bidders to bid a single item in one round of the auction. There are only a few researchers who have considered the case that each bidder can bid for multiple items. Huang et al. [23] proposed an auction mechanism, in which all participants could exchange multi-unit items. Wurman et al. [24] designed an auction mechanism which transforms the buyers' multi-unit items demand to a single-unit transaction. Babaioff and Walsh [25] studied a budget-balanced and strategy-proof double auction mechanism, where each buyer desires for a bundle of items. Chu and Shen [26] proposed an asymptotically efficient strategyproof auction mechanism, namely BC-LP, which achieved bundling of commodities transactions for buyers. Combinatorial auction [15,27] allowing bidders to bid for packages of items has been widely studied in various research fields recently, such as cloud computing, spectrum auction, etc. The authors in Ref. [28] introduced combinatorial auctionbased allocation mechanisms for the virtual machine allocation problem of cloud computing. Dong et al. [17] applied a combinatorial spectrum auction model with time-frequency flexibility in cognitive radio networks. However, none of these auction mechanisms provided any guarantee on privacy preservation.
Several sealed-bid auction mechanisms with privacy preservation have been proposed in previous studies. For instance, Refs. [8,9] are works about the first-price or second-price auction mechanism design, which protect the bid values of bidders. In Refs. [10,[29][30][31][32][33][34], a second central party, called an "auction issuer", "auction authority", or "agent" in addition to the auctioneer, was introduced to the auction. These works model this second central party as a trusted or semi-trusted party, which communicates with the auctioneer to make the winner decision and to compute the payment from winners while protecting the privacy of the bidders. Brandt and Sandholm [35][36][37][38] focused on the design of unconditional full privacy auction protocols, which relies neither on a trusted third-party, nor on any computational intractability assumptions. Although these protocols are fully privacy-preserving, the computational and communication complexities are relatively high. Brandt and Sandholm [39] also designed secure mechanisms for three common types of multi-unit auctions: uniform-price, discriminatory, and the generalized Vickrey auctions. In Ref. [12], a secure combinatorial spectrum auction was designed using homomorphic encryption to deal with the untrustworthy auctioneer. In Ref. [19], several secure combinatorial auction mechanisms were proposed with dynamic programming via polynomial secret sharing. Unfortunately, the optimal allocation problem in most practical auctions is NP-hard, especially in multi-unit auctions. None of the existing solutions with privacy preservation have provided any performance guarantee, such as maximizing the social efficiency. In this work, we tackle this problem to design strategyproof and privacy-preserving auction mechanisms that maximize social efficiency.

Conclusion
In this paper, we proposed the first strategyproof and privacy-preserving multi-unit auction mechanisms that maximize social efficiency. We study two cases for multi-unit auctions, where the items in the market are identical and distinct. Under these two cases, the optimal item allocation problem is NP-hard to solve. Thus, we designed secure and near optimal allocation mechanisms for each case, which have the approximation factors of 2 and p h, respectively. Furthermore, we also computed the critical payment with privacy preservation for each winner, and theoretically proved the properties of our auction mechanisms, such as strategyproofness, privacy preservation, and approximation factor. Additionally, although the privacy-preserving design has incurred some computation and communication overheads, the auction mechanisms are still efficient. Our evaluation results demonstrated that our protocols not only achieve good social efficiency, but also perform well in computation and communication aspects.
Hence, we believe that this is the first study of multiunit auction mechanisms with performance guarantee and privacy preservation; however, there are several interesting questions left for future work. The first is to study the case when the bidder's demands are separable, and their per unit bids are related to the number of identical items they win in the auction. The second is to design strategyproof and privacy preserving auction mechanisms when bidders can bid on multicombinatorial items, but only want to buy one of the items in the combinatorial auction.