A Differentially Private Auction Mechanism in Online Social Networks

Abstract

The growing popularity of users in online social network gives a big opportunity for online auction. The famous Information Diffusion Mechanism (IDM) is an excellent method even meet the incentive compatibility and individual rationality. Although the existing auction in online social network has considered the buyers’ information which is not known by the seller, current mechanism still can not preserve the privacy information of users in online social network. In this paper, we propose a novel mechanism based on the IDM and differential privacy. Our mechanism can successfully process the auction and at the same time preserve clients’ price information from neighbours. We achieved these by adding virtual nodes to each node and Laplace noise for its price in the auction process. We also formulate this mechanism on the real network and the random network, scale-free network to show the feasibility and effectiveness of the proposed mechanism. The evaluation shows that the result of our methods only depend on the noise added to the agents. It is independent from the agents’ original price.

Keywords

Online social network auction / privacy preserving / differential privacy

References

[1] Abawajy JH, Ninggal MIH, Herawan T. Privacy preserving social network data publication. IEEE Communications Surveys & Tutorials, 2016, 18(3): 1974-1997.

[2] Bajari P, Hortaçsu A. RAND Journal of Economics, 2003

[3] Borgatti SP, Mehra A, Brass DJ, Labianca G. Network analysis in the social sciences. Science, 2009, 323(5916): 892-895.

[4] Chen Z, Ni T, Zhong H, Zhang S, Cui J. Differentially private double spectrum auction with approximate social welfare maximization. IEEE Transactions on Information Forensics and Security, 2019, 14(11): 2805-2818.

[5] Clarke EH. Multipart pricing of public goods. Public Choice, 1971, 11(1): 17-33.

[6] Dwork C, Roth A. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 2014, 9(3–4): 1-277.

[7] Edelman B, Ostrovsky M, Schwarz M. Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords. American Economic Review, 2007, 97(1): 242-259.

[8] Farajian N, Zamanifar K. Proceedings of ICAC3, 2013

[9] Ghosh A, Roth A. Selling privacy at auction. Games and Economic Behavior, 2015, 91: 334-346.

[10] Goldberg A, Hartline J, Wright A. Proceedings of 9th European Symposium on, 2000

[11] Goldberg AV, Hartline JD, Wright A. Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, 2001

[12] Groves T, et al. Incentives in teams. Econometrica, 1973, 41(4): 617-631.

[13] Jackson MO. Social and Economic Networks, 2010.

[14] Karwa V, Raskhodnikova S, Smith A, Yaroslavtsev G. Private analysis of graph structure. Proceedings of the VLDB Endowment, 2011, 4(11): 1146-1157.

[15] Kasiviswanathan SP, Nissim K, Raskhodnikova S, Smith A. Theory of Cryptography Conference, 2013

[16] Kong Y, Zhang M, Ye D. The Computer Journal, 2015

[17] Krishna V. Auction Theory, 2009

[18] Leskovec J, Kleinberg J, Faloutsos C. Graph evolution: Densification and shrinking diameters. ACM Transactions on Knowledge Discovery from Data (TKDD), 2007, 1(1): 2.

[19] Li B, Hao D, Zhao D, Zhou T. Thirty-First AAAI Conference on Artificial Intelligence, 2017

[20] Li B, Hao D, Zhao D, Zhou T (2018). Customer sharing in economic networks with costs. arXiv Preprint:1807.06822.

[21] McSherry F, Talwar K. Mechanism design via differential privacy. FOCS, 2007, 7: 94-103.

[22] Myerson RB. Optimal auction design. Mathematics of Operations Research, 1981, 6(1): 58-73.

[23] Nguyen KQ, Traoré J. Australasian Conference on Information Security and Privacy, 2000

[24] Rastogi V, Hay M, Miklau G, Suciu D. Proceedings of the 28th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2009

[25] Vickrey W. Counterspeculation, auctions, and competitive sealed tenders. The Journal of Finance, 1961, 16(1): 8-37.

[26] Wright M, Wellman MP. Proceedings of AAMAS, 2019

[27] Ye D, He Q, Wang Y, Yang Y. IEEE Transactions on Services Computing, 2019

[28] Ye D, Zhang M. A self-adaptive strategy for evolution of cooperation in distributed networks. IEEE Transactions on Computers, 2015, 64(4): 899-911.

[29] Ye D, Zhang M, Sutanto D. Cloning, resource exchange, and relationadaptation: An integrative self-organisation mechanism in a distributed agent network. IEEE Transactions on Parallel & Distributed Systems, 2014, 25(4): 887-897.

[30] Ye D, Zhu T, Shen S, Zhou W, Yu P. Differentially private multi-agent planning for logistic-like problems. IEEE Transactions on Dependable and Secure Computing, 2020, 99: 1-1.

[31] Ye D, Zhu T, Sheng S, Zhou W. IEEE Transactions on Information and Forentics Security, 2020

[32] Ye D, Zhu T, Zhou W, Yu PS. IEEE Transactions on Cybernetics, 2019

[33] Zhang T, Zhu T, Xiong P, Huo H, Tari Z, Zhou W. IEEE Transactions on Indistrial Informatics, 2019

[34] Zhao D, Li B, Xu J, Hao D, Jennings NR. Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, 2018

[35] Zhu T, Li G, Zhou W, Philip SY. Differentially private data publishing and analysis: A survey. IEEE Transactions on Knowledge and Data Engineering, 2017, 29(8): 1619-1638.

[36] Zhu T, Ye D, Wang W, Zhou W, Yu PS. IEEE Transactions on Knowledge and Data Engineering, 2020