Differentially private spectrum auction with approximate revenue maximization

ABSTRACT

Dynamic spectrum redistribution---under which spectrum owners lease out under-utilized spectrum to users for financial gain---is an effective way to improve spectrum utilization. Auction is a natural way to incentivize spectrum owners to share their idle resources. In recent years, a number of strategy-proof auction mechanisms have been proposed to stimulate bidders to truthfully reveal their valuations. However, it has been shown that truthfulness is not a necessary condition for revenue maximization. Furthermore, in most existing spectrum auction mechanisms, bidders may infer the valuations---which are private information---of the other bidders from the auction outcome. In this paper, we propose a Differentially privatE spectrum auction mechanism with Approximate Revenue maximization (DEAR). We theoretically prove that DEAR achieves approximate truthfulness, privacy preservation, and approximate revenue maximization. Our extensive evaluations show that DEAR achieves good performance in terms of both revenue and privacy preservation.

References

1. I. F. Akyildiz, W. Y. Lee, M. C. Vuran, and S. Mohanty, "NeXt generation/dynamic spectrum access/cognitive radio wireless networks: A survey," Computer Networks, vol. 50, no. 13, pp. 2027--2159, 2006.
2. Spectrum Policy Task Force, "Spectrum policy task force report," Federal Communications Commission ET docket, 02-135, 2002.
3. Spectrum Bridge, Inc., http://www.spectrumbridge.com
4. Z. Ji and K. Liu, "Dynamic spectrum sharing: A game theoretical overview," IEEE Communications Magazine, vol. 45, no. 5, pp. 88--94, 2007.
5. X. Zhou and H. Zheng, "TRUST: A general framework for truthful double spectrum auctions," in INFOCOM'09, 2009.
6. F. Wu and N. Vaidya, "SMALL: A strategy-proof mechanism for radio spectrum allocation," in INFOCOM'11, 2011.
7. J. Peha, "Approaches to spectrum sharing," IEEE Communications Magazine, vol. 43, no. 2, pp. 10--12, 2005.
8. S. Gandhi, C. Buragohain, L. Cao, H. Zheng, and S. Suri, "A general framework for wireless spectrum auctions," in DySPAN'07, 2007.
9. S. Sengupta, and M. Chatterjee, "An economic framework for dynamic spectrum access and service pricing," IEEE/ACM Transactions on Networking, vol. 17, no. 4, pp. 1200--1213, 2009.
10. J. Jia, Q. Zhang, Q. Zhang, and M. Liu, "Revenue generation for truthful spectrum auction in dynamic spectrum access," in MobiHoc'09, 2009.
11. M. Al-Ayyoub and H. Gupta, "Truthful spectrum auctions with approximate revenue," in INFOCOM'11, 2011.
12. A P. Subramanian, M. Al-Ayyoub, H. Gupta, et al. "Near-optimal dynamic spectrum allocation in cellular networks," in DySPAN'08, 2008.
13. R. Myerson, "Optimal auction design," Mathematics of operations research, vol. 6, no. 1, pp. 58--73, 1981.
14. Q. Huang, Y. Tao, and F. Wu, "SPRING: A strategy-proof and privacy preserving spectrum auction mechanism," in INFOCOM'13, 2013.
15. M. Jakobsson and A. Juels, "Mix and match: Secure function evaluation via ciphertexts," in ASIACRYPT'00, 2000.
16. K. Sako, "An auction protocol which hides bids of losers," in PKC'00, 2000.
17. K. Peng, C. Boyd, E. Dawson, and K. Viswanathan, "Robust, privacy protecting and publicly verifiable sealed-bid auction," in ICICS'02, 2002.
18. Y. F. Chung, K. H. Huang, H. H. Lee, F. Lai, and T. S. Chen, "Bidder-anonymous english auction scheme with privacy and public verifiability," Journal of Systems and Software, vol. 81, no. 1, pp. 113--119, 2008.
19. A. Archer and E. Tardos, "Frugal path mechanisms," in TALG'07, 2007.
20. J. Feigenbaum, and S. Shenker, "Distributed algorithmic mechanism design: Recent results and future directions," September, in DialM'02, 2002.
21. C. Dwork, "Differential privacy," in ICALP'06, 2006.
22. F. McSherry and K. Talwar, "Mechanism design via differential privacy," in FOCS'07, 2007.
23. A. Gupta, K. Ligett, F. McSherry, A. Roth and K. Talwar. "Differentially private combinatorial optimization," in SODA'10, 2010.
24. A. Gopinathan and Z. Li, "A prior-free revenue maximizing auction for secondary spectrum access," in INFOCOM'11, 2011.
25. A. Kothari, DC. Parkes, and S. Suri, "Approximately-strategyproof and tractable multiunit auctions," Decision Support Systems, vol. 39, no. 1, pp. 105--121, 2005.
26. A. Mu'Alem, and N. Nisan, "Truthful approximation mechanisms for restricted combinatorial auctions," Games and Economic Behavior, vol. 64, no. 1, pp. 612--631, 2008.
27. K. Nissim, R. Smorodinsky and M. Tennenholtz, "Approximately optimal mechanism design via differential privacy," in ITCS'12, 2012.
28. C. Dwork, "Differential privacy: A survey of results," in TAMC'08, 2008.
29. V. Krishna, "Auction theory," Academic Press, 2002.
30. N. Nisan, "Algorithmic game theory," Cambridge University Press, 2007.
31. L. Sweeney, "k-anonymity: A model for protecting privacy," International Journal on Uncertainty, Fuzziness and Knowledge based Systems, vol. 10, no. 5, pp. 557--570, 2002.
32. M. Naor, B. Pinkas, and R. Sumner, "Privacy preserving auctions and mechanism design," in EC'99, 1999.
33. H. Lipmaa, N. Asokan, V. Niemi, "Secure Vickrey auctions without threshold trust," in FC'03, 2003.
34. J. Schummer, "Almost-dominant strategy implementation: exchange economies," Games and Economic Behavior, vol. 48, no. 1, pp. 154--170, 2004.
35. K. Jain, J. Padhye, V. N. Padmanabhan, and L. Qiu, "Impact of interference on multi-hop wireless network performance," in MobiCom'03, 2003.
36. H. Huang, X. Li, Y. Sun, H. Xu, and L. Huang, "PPS: Privacy-Preserving Strategyproof Social-Efficient Spectrum Auction Mechanisms," in http://arxiv.org/pdf/1307.7792v1.pdf, 2013.
37. F. Wu and N. Vaidya, "A Strategy-Proof Radio Spectrum Auction Mechanism in Noncooperative Wireless Networks," in IEEE Transaction on Mobile Computing, vol. 12, no. 5, pp. 885--894, 2013.
38. Z. Huang and S. Kannan, "The exponential mechanism for social welfare: Private, truthful, and nearly optimal," in FOCS'12, 2012.

Index Terms

• Networks

  • Network types

    • Mobile networks

    • Wireless access networks