基于社交网络的分布式机制设计

doi:10.13232/j.cnki.jnju.2020.01.012

南京大学学报(自然科学版) ›› 2020, Vol. 56 ›› Issue (1): 107–115.doi: 10.13232/j.cnki.jnju.2020.01.012

基于社交网络的分布式机制设计

何昕,徐珺平,赵登吉()

上海科技大学信息科学与技术学院，上海，201210

收稿日期:2019-08-31 出版日期:2020-01-30 发布日期:2020-01-10
通讯作者: 赵登吉 E-mail:zhaodj@shanghaitech.edu.cn

Distributed mechanism design on social networks

Xin He,Junping Xu,Dengji Zhao()

School of Information Science and Technology, ShanghaiTech University, Shanghai, 201210, China

Received:2019-08-31 Online:2020-01-30 Published:2020-01-10
Contact: Dengji Zhao E-mail:zhaodj@shanghaitech.edu.cn

摘要/Abstract

摘要：

人们通过社交关系构成一个庞大的社交网络，网络中的每个节点只能与其周围的节点进行通信，因此当网络中的某个节点进行物品拍卖销售时，在不借助第三方推广的情况下只能邀请其邻居节点参与.中心化机制能使网络中的其他非邻居节点都能参与拍卖，以此可以提高卖家节点的最终收益，然而在该机制中卖家可以轻易地与买家串通，并且买家需要将社交网络结构（买家的私人社交信息）完全透露给卖家，因此网络中的节点没有很强的动机来参与该机制.提出一种分布式的解决方案，可以防止卖家与买家勾结，同时保持网络结构不被泄露.实验证明，该分布式机制保留了传统机制的优点，而且不需要一个可以完全获得网络结构的中心机构来执行该机制.通过模拟实验还发现，在大多数情况下，社交网络越复杂，泄露的隐私信息就越少.

关键词: 分布式机制设计, 拍卖, 信息传播, 算法博弈论

Abstract:

This paper studies a market where a seller sells one item on a social network,but she can only directly communicate with her neighbours in the network. The seller's goal is to promote the sale to all potential buyers in the network to increase her revenue. This problem has been first attempted with a centralised mechanism. However,buyers are not well incentivised to participate in the mechanism due to (i) the seller can easily collude with a buyer,and (ii) the network structure is fully revealed to the seller. Hence,we propose another novel distributed solution that prevents the seller's collusion with buyers and also keeps the network structure unrevealed. We also prove that our mechanism preserve the advantages of the centralized mechanisms and show that we don't need a central part to run this mechanism. Our simulations show that the more complicated social networks are,the less privacy information are revealed.

Key words: distributed mechanism design, auction, information diffusion, algorithmic game theory

中图分类号:

TP301

何昕,徐珺平,赵登吉. 基于社交网络的分布式机制设计[J]. 南京大学学报(自然科学版), 2020, 56(1): 107–115.

Xin He,Junping Xu,Dengji Zhao. Distributed mechanism design on social networks[J]. Journal of Nanjing University(Natural Sciences), 2020, 56(1): 107–115.

图/表 5

图1

图2

图3

图4

表1

参考文献 16

1	Li B,Hao D,Zhao D J,et al. Mechanism design in social networks∥The 31^st AAAI Conference on Artificial Intelligence. San Francisco，CA,USA：AAAI Press，2017：586-592.
2	Zhao D J，Li B，Xu J P，et al. Selling multiple items via social networks∥Proceedings of the 17^th International Conference on Autonomous Agents and MultiAgent Systems. Stockholm，Sweden：International Foundation for Autonomous Agents and Multiagent Systems，2018：68-76.
3	Nisan N，Roughgarden T，Tardos E，et al. Algorithmic game theory. Cambridge：Cambridge University Press，2007，776.
4	Parkes D C，Shneidman J. Distributed implementations of vickrey?clarke?groves mechanisms∥Proceedings of the 3^rd International Joint Conference on Autonomous Agents and Multiagent Systems，New York，NY，USA：IEEE，2004：261-268.
5	Petcu A，Faltings B，Parkes D C. Mdpop：faithful distributed implementation of efficient social choice problems∥Proceedings of the 5^th International Conference on Autonomous Agents and Multiagent Systems. Hakodate,Japan：IEEE Computer Society，2006：1397-1404.
6	Groves T. Incentives in teams. Econometrica,1973，41(4)：617-631.
7	Archer A，Feigenbaum J，Krishnamurthy A，et al. Approximation and collusion in multicast cost sharing. Games and Economic Behavior，2004，47(1)：36-71.
8	Shneidman J，Parkes D C. Specification faithfulness in networks with rational nodes∥Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing. St. John's，Canada：ACM，2004：88-97.
9	Peng D，Yang S，Wu F，et al. Resisting three?dimensional manipulations in distributed wireless spectrum auctions∥2015 IEEE Conference on Computer Communications. Hong Kong，China：IEEE，2015：2056-2064.
10	Yang S，Peng D，Meng T. On designing distributed auction mechanisms for wireless spectrum allocation. IEEE Transactions on Mobile Computing，2019，18(9)：2129-2146.
11	Feigenbaum J，Shenker S. Distributed algorithmic mechanism design：recent results and future directions∥Proceedings of the 6^th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications. Atlanta，GE，USA：ACM，2002：1-13.
12	Liu T Y. A decade of online advertising research：what we learned and what we need to know. Journal of Advertising，2019，48(1)：1-13.
13	Tarjan R. Depth?first search and linear graph algorithms∥2^nd Annual Symposium on Switching and Automata Theory. East Lansing，MI，USA：IEEE，1971：114-121.
14	Erciyes K. Guide to graph algorithms. Cham：Springer，2018，471.
15	Makki S A M，Havas G. Distributed algorithms for constructing a depth?first?search tree∥1994 International Conference on Parallel Processing. North Carolina，CA，USA：IEEE，1994：270-273.
16	Watts D J，Strogatz S H. Collective dynamics of 'small?world' networks. Nature，1998，393(6684)：440-442.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

k	RedR	OrangeR	GreenR	PRR	ChainL	Revenue
2	10.29%	14.51%	73.2%	0.268	3.99	48.44
4	5.73%	13.64%	79.63%	0.201	2.3	90.43
6	1%	11.48%	86.52%	0.135	1.0	98.48
8	1%	5.27%	92.73%	0.073	1.0	98.73

[1]	李亚重,杨有龙,仇海全. 一种基于嵌入式的弱标记分类算法[J]. 南京大学学报(自然科学版), 2020, 56(4): 549-560.
[2]	王丽娟,丁世飞,丁玲. 基于迁移学习的软子空间聚类算法[J]. 南京大学学报(自然科学版), 2020, 56(4): 515-523.
[3]	李俊余, 李星璇, 王霞, 吴伟志. 基于三元因子分析的三元概念约简[J]. 南京大学学报(自然科学版), 2020, 56(4): 480-493.
[4]	袁友宏,刘欣,鲍蕾. 求解非凸截断L ₁⁃SVM的多阶段非精确线搜割平面方法[J]. 南京大学学报(自然科学版), 2020, 56(1): 98-106.
[5]	李子龙,周勇,鲍蓉. AdaBoost图像到类距离学习的图像分类方法[J]. 南京大学学报(自然科学版), 2020, 56(1): 51-56.
[6]	刘亮,何庆. 基于改进蝗虫优化算法的特征选择方法[J]. 南京大学学报(自然科学版), 2020, 56(1): 41-50.
[7]	袁燕,陈伯伦,朱国畅,花勇,于永涛. 基于社区划分的空气质量指数（AQI）预测算法[J]. 南京大学学报(自然科学版), 2020, 56(1): 142-150.
[8]	王霞, 谭斯文, 李俊余, 吴伟志. 基于条件属性蕴含的概念格构造及简化[J]. 南京大学学报(自然科学版), 2019, 55(4): 553-563.
[9]	王博闻, 史江峰, 史逝远, 张伟杰, 马晓琦, 赵业思. 基于遥感数据定位老龄树群[J]. 南京大学学报(自然科学版), 2019, 55(4): 699-707.
[10]	陈晓冬, 底晓强, 李锦青. 基于多混沌和分数Fourier的光学图像加密算法[J]. 南京大学学报(自然科学版), 2019, 55(2): 251-263.
[11]	洪思思，曹辰捷，王　喆*，李冬冬. 基于矩阵的AdaBoost多视角学习[J]. 南京大学学报(自然科学版), 2018, 54(6): 1152-1160.
[12]	周星星，张海平，吉根林. 具有时空特性的区域移动模式挖掘算法[J]. 南京大学学报(自然科学版), 2018, 54(6): 1171-1182.

基于社交网络的分布式机制设计

Distributed mechanism design on social networks

RichHTML

PDF (PC)

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 16

相关文章 12

Metrics

本文评价

推荐阅读 10