AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (574.6 KB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

Privacy-Preserving Strategyproof Auction Mechanisms for Resource Allocation

Yu-E Sun, He Huang( ), Xiang-Yang Li, Yang Du, Miaomiao Tian, Hongli Xu, Mingjun Xiao
School of Urban Rail Transportation, Soochow University, Suzhou 215006, China.
School of Computer Science and Technology, Soochow University, Suzhou 215006, China.
School of Computer Science and Technology, University of Science and Technology of China, Hefei 230026, China.
Suzhou Institute for Advanced Study, University of Science and Technology of China, Suzhou 215123, China.
School of Computer Science and Technology, Anhui University, Hefei 230031, China.
Show Author Information

Abstract

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 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 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.

Keywords

approximation mechanismmulti-unit auctionprivacy preservingsocial efficiencystrategyproof

References

[1]
Lin W. Y., Lin G. Y., and Wei H. Y., Dynamic auction mechanism for cloud resource allocation, in Proc. 10th IEEE/ACM CCGrid, Melbourne, Australia, 2010, pp. 591-592.
Crossref
[2]
Gopinathan A., Li Z., and Wu C., Strategyproof auctions for balancing social welfare and fairness in secondary spectrum markets, in Proc. 31st IEEE INFOCOM, Orlando, FL, USA, 2012, pp. 2813-2821.
Crossref
[3]
Huang H., Sun Y., Li X. Y., Chen Z., Yang W., and Xu H., Near-optimal truthful spectrum auction mechanisms with spatial and temporal reuse in wireless networks, in Proc. 14th ACM MobiHoc, Bangalore, India, 2013, pp. 237-240.
Crossref
[4]
Zhou X., Gandhi S., Suri S., and Zheng H., ebay in the sky: Strategy-proof wireless spectrum auctions, in Proc. 14th ACM Mobicom, San Francisco, CA, USA, 2008, pp. 2-13.
Crossref
[5]
Dong W., Rallapalli S., Jana R., Qiu L., Ramakrishnan K., Razoumov L., Zhang Y., and Cho T. W., Ideal: Incentivized dynamic cellular offloading via auctions, in Proc. 32nd IEEE INFOCOM, Turin, Italy, 2013, pp. 755-763.
Crossref
[6]
Wang X., Li Z., Xu P., Xu Y., Gao X., and Chen H. H., Spectrum sharing in cognitive radio networksan auction-based approach, IEEE Trans. on Sys., Man, and Cybernetics, Part B: Cybernetics, vol. 40, no. 3, pp. 587-596, 2010.
Crossref Google Scholar
[7]
Krishna V., Auction Theory. Academic Press, 2009.
[8]
Chung Y. F., Huang K. H., Lee H. H., Lai F., and Chen T. S., Bidder-anonymous english auction scheme with privacy and public verifiability, Journal of Systems and Software, vol. 81, no. 1, pp. 113-119, 2008.
Crossref Google Scholar
[9]
Kikuchi H., (M+1)st-price auction protocol, Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. 85, no. 3, pp. 676-683, 2002.
Crossref Google Scholar
[10]
Huang Q., Tao Y., and Wu F., SPRING: A strategy-proof and privacy preserving spectrum auction mechanism, in Proc. 32nd IEEE INFOCOM, Turin, Italy, 2013, pp. 2219-2227.
Crossref
[11]
Pan M., Zhu X., and Fang Y., Using homomorphic encryption to secure the combinatorial spectrum auction without the trustworthy auctioneer, Wireless Networks, vol. 18, no. 2, pp. 113-128, 2012.
Crossref Google Scholar
[12]
Pan M., Li H., Li P., and Fang Y., Dealing with the untrustworthy auctioneer in combinatorial spectrum auctions, in Proc. GLOBECOM 2011, Houston, TX, USA, 2011, pp. 1-5.
Crossref
[13]
Dobzinski S., Nisan N., and Schapira M., Approximation algorithms for combinatorial auctions with complement-free bidders, in Proc. 37th ACM STOC, Baltimore, MD, USA, 2005, pp. 610-618.
Crossref
[14]
Lehmann D., Oćallaghan L. I., and Shoham Y., Truth revelation in approximately efficient combinatorial auctions, Journal of the ACM, vol. 49, no. 5, pp. 577-602, 2002.
Crossref Google Scholar
[15]
Cramton P., Shoham Y., and Steinberg R., Combinatorial Auctions. MIT Press, 2006.
Crossref
[16]
Rothkopf M. H., Pekeč A., and Harstad R. M., Computationally manageable combinational auctions, Management Science, vol. 44, no. 8, pp. 1131-1147, 1998.
Crossref Google Scholar
[17]
Dong M., Sun G., Wang X., and Zhang Q., Combinatorial auction with time-frequency flexibility in cognitive radio networks, in Proc. 31st IEEE INFOCOM, Orlando, FL, USA, 2012, pp. 2282-2290.
Crossref
[18]
Lai K. and Goemans M. X., The knapsack problem and fully polynomial time approximation schemes (FPTAS), Retrieved November, vol. 3, pp. 2012, 2006.
Google Scholar
[19]
Suzuki K. and Yokoo M., Secure combinatorial auctions by dynamic programming with polynomial secret sharing, in Proc. 7th Financial Cryptography, Le Gosier, Guadeloupe, 2003, pp. 44-56.
Crossref
[20]
Xu P. and Li X. Y., Online market driven spectrum scheduling and auction, in Proc. the CoRoNet workshop of 15th ACM MobiCom, Beijing, China, 2009, pp. 49-54.
Crossref
[21]
Wang S. G., Xu P., Xu X. H., Tang S. J., Li X. Y., and Liu X., TODA: Truthful online double auction for spectrum allocation in wireless networks, in Proc. IEEE Dyspan 2010, Singapore, 2010, pp. 1-10.
Crossref
[22]
Xu P., Wang S. G., and Li X. Y., SALSA: Strategyproof online spectrum admissions for wireless networks, IEEE Trans. on Computers, vol. 59, no. 12, pp. 1691-1702, 2010.
Crossref Google Scholar
[23]
Huang P., Scheller-Wolf A., and Sycara K., Design of a multi–unit double auction e-market, Computational Intelligence, vol. 18, no. 4, pp. 596-617, 2002.
Crossref Google Scholar
[24]
Wurman P. R., Walsh W. E., and Wellman M. P., Flexible double auctions for electronic commerce: Theory and implementation, Decision Support Systems, vol. 24, no. 1, pp. 17-27, 1998.
Crossref Google Scholar
[25]
Babaioff M. and Walsh W. E., Incentive-compatible, budget-balanced, yet highly efficient auctions for supply chain formation, Decision Support Systems, vol. 39, no. 1, pp. 123-149, 2005.
Crossref Google Scholar
[26]
Chu L. Y. and Shen Z. J. M., Truthful double auction mechanisms, Operations Research, vol. 56, no. 1, pp. 102-120, 2008.
Crossref Google Scholar
[27]
Mu’Alem A. and Nisan N., Truthful approximation mechanisms for restricted combinatorial auctions, Games and Economic Behavior, vol. 64, no. 2, pp. 612-631, 2008.
Crossref Google Scholar
[28]
Zaman S. and Grosu D., Combinatorial auction-based allocation of virtual machine instances in clouds, Journal of Parallel and Distributed Computing, vol. 73, no. 4, pp. 495-508, 2013.
Crossref Google Scholar
[29]
Abe M. and Suzuki K., M+1-st price auction using homomorphic encryption, in Proc. 5th Public Key Cryptography, Paris, France, 2002, pp. 115-124.
Crossref
[30]
Baudron O. and Stern J., Non-interactive private auctions, in Proc. 6th Financial Cryptography, Southampton, Bermuda, 2002, pp. 364-377.
Crossref
[31]
Cachin C., Efficient private bidding and auctions with an oblivious third party, in Proc. 6th ACM CCS, Singapore, 1999, pp. 120-127.
Crossref
[32]
Naor M., Pinkas B., and Sumner R., Privacy preserving auctions and mechanism design, in Proc. 1st ACM EC, Denver, CO, USA, 1999, pp. 129-139.
Crossref
[33]
Juels A. and Szydlo M., two-server A, sealed-bid auction protocol, in Proc. 7th Financial Cryptography, Le Gosier, Guadeloupe, 2003, pp. 72-86.
Crossref
[34]
Lipmaa H., Asokan N., and Niemi V., Secure vickrey auctions without threshold trust, in Proc. 7th Financial Cryptography, Le Gosier, Guadeloupe, 2003, pp. 87-101.
Crossref
[35]
Brandt F., Secure and private auctions without auctioneers, Technical Report FKI-245-02, Institut für Informatik, Technische Universität München, 2002.
[36]
Brandt F., Fully private auctions in a constant number of rounds, in Proc. 7th Financial Cryptography, Le Gosier, Guadeloupe, 2003, pp. 223-238.
Crossref
[37]
Brandt F., How to obtain full privacy in auctions, International Journal of Information Security, vol. 5, no. 4, pp. 201-216, 2006.
Crossref Google Scholar
[38]
Brandt F. and Sandholm T., On the existence of unconditionally privacy-preserving auction protocols, ACM TISSEC, vol. 11, no. 2, p. 6, 2008.
Crossref Google Scholar
[39]
Brandt F. and Sandholm T., Efficient privacy-preserving protocols for multi-unit auctions, in Proc. Financial Cryptography and Data Security, Roseau, Dominica, 2005, pp. 298-312.
Crossref
Tsinghua Science and Technology
Volume 22 Issue 2,
April 2017
Pages 119-134
DOI: 10.23919/TST.2017.7889635
Cite this article:
Sun Y-E, Huang H, Li X-Y, et al. Privacy-Preserving Strategyproof Auction Mechanisms for Resource Allocation. Tsinghua Science and Technology, 2017, 22(2): 119-134. https://doi.org/10.23919/TST.2017.7889635

555

Views

23

Downloads

2

Crossref

N/A

Web of Science

5

Scopus

0

CSCD

Altmetrics
Received: 25 August 2016
Revised: 08 February 2017
Accepted: 13 February 2017
Published: 06 April 2017
© The author(s) 2017
Return