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 a...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 efficiency 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 efficiency is NPhard, 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 first work on the strategyproof multi-unit auction mechanisms that simultaneously consider privacy preservation and social efficiency maximization. The extensive simulations show that the proposed mechanisms have low computation and communication overheads.展开更多
基金supported by the National Natural Science Foundation of China (Nos. 61572342 and 61672369)the Natural Science Foundation of Jiangsu Province (Nos. BK20151240 and BK20161258)China Postdoctoral Science Foundation (Nos. 2015M580470 and 2016M591920)
文摘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 efficiency 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 efficiency is NPhard, 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 first work on the strategyproof multi-unit auction mechanisms that simultaneously consider privacy preservation and social efficiency maximization. The extensive simulations show that the proposed mechanisms have low computation and communication overheads.
