A Truthful, Privacy-Preserving, Approximately Efficient Combinatorial Auction For Single-minded Bidders

Combinatorial auctions are widely used to sell resources/items. The challenges in such auctions are multi-fold. We need to ensure that bidders, the strategic agents, bid their valuations truthfully to the auction mechanism. Besides, the agents may desire privacy of their identities as well as their bidding information. We consider three types of privacies: agent privacy, the identities of the losing bidders must not be revealed to any other agent except the auctioneer (AU), bid privacy, the bid values must be hidden from the other agents as well as the AU and bid-topology privacy, the items for which the agents are bidding must be hidden from the other agents as well as the AU. In this paper, we address whether can we solve the allocation and payment determination problems, which are NP-hard, approximately for single-minded bidders while preserving privacy. In the literature, root m-approximation, where m is the number of items auctioned, and a strategy-proof mechanism is available for this, which we refer to as ICA-SM. To implement ICA-SM with privacy, we propose a novel cryptographic protocol TPACAS. We show that TPACAS achieves these privacy guarantees with high probability. To accomplish this, we use notaries who are semi-trusted third parties. We show that, in TPACAS, notaries do not learn any information about the agents and their bidding information.