A Fast Distributed Algorithm for Uniform Price Auction with Bidding Information Protection

In this paper, a fast distributed algorithm is proposed for solving the winners and price determination problems in a uniform price auction in which each bidder bids for multiple units out of a lot of k identical items with a per-unit price. In a conventional setting, all bidders disclose their bidding information to an auctioneer and let the auctioneer allocate the items and determine the uniform price, i.e., the least winning price. In our setting, all bidders do not need to disclose their bidding information to the auctioneer. The bidders and the auctioneer collaboratively compute by the distributed algorithm to determine in a small number of steps the units allocated and the uniform price. The number of steps is independent of the number of bidders. At the end of the computing process, each bidder can only know the units allocated to him/her and the uniform price. The auctioneer can only know the units being allocated to the bidders and the uniform price. Therefore, neither the bidders nor the auctioneer are able to know the per-unit bidding prices of the bidders except the uniform price. Moreover, the auctioneer is not able to know the bidding units of the losing bidders. Bidders’ per-unit bidding prices are protected, and the bidding units of the losing bidders are protected. Bidding information privacy is preserved.