Incentive mechanism design for hierarchical federated learning based on multi-leader Stackelberg game

doi:10.11772/j.issn.1001-9081.2022111727

Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (11): 3551-3558.DOI: 10.11772/j.issn.1001-9081.2022111727

Special Issue: 网络与通信

• Network and communications • Previous Articles Next Articles

Incentive mechanism design for hierarchical federated learning based on multi-leader Stackelberg game

Fangxing GENG¹^,², Zhuo LI¹^,²(), Xin CHEN²

^1.Beijing Key Laboratory of Internet Culture and Digital Dissemination Research （Beijing Information Science and Technology University），Beijing 100101，China
^2.Computer School，Beijing Information Science and Technology University，Beijing 100101，China

Received:2022-11-21 Revised:2023-04-03 Accepted:2023-04-04 Online:2023-05-08 Published:2023-11-10
Contact: Zhuo LI
About author:GENG Fangxing， born in 1999， M. S. candidate. His research interests include edge computing.
LI Zhuo， born in 1983， Ph. D.， associate professor. His research interests include mobile wireless network， distributed computing.
CHEN Xin， born in 1965， Ph. D.， professor. His research interests include network performance evaluation， network security.
Supported by:
Beijing Natural Science Foundation(4232024);National Key Research and Development Program of China(2022YFF0604502);National Natural Science Foundation of China(61872044);Beijing Municipal Program for Young Talents

基于多领导者Stackelberg博弈的分层联邦学习激励机制设计

耿方兴¹^,², 李卓¹^,²(), 陈昕²

^1.网络文化与数字传播北京市重点实验室（北京信息科技大学），北京 100101
^2.北京信息科技大学计算机学院，北京 100101

通讯作者: 李卓
作者简介:耿方兴（1999—），男，河南驻马店人，硕士研究生，主要研究方向：边缘计算
李卓（1983—），男，河南南阳人，副教授，博士，CCF会员，主要研究方向：移动无线网络、分布式计算 lizhuo@bistu.edu.cn
陈昕（1965—），男，江西南昌人，教授，博士，CCF会员，主要研究方向：网络性能评价、网络安全。
基金资助:
北京市自然科学基金资助项目(4232024);国家重点研发计划项目(2022YFF0604502);国家自然科学基金资助项目(61872044);北京市青年拔尖人才项目

Abstract

Abstract:

The existence of privacy security and resource consumption issues in hierarchical federated learning reduces the enthusiasm of participants. To encourage a sufficient number of participants to actively participate in learning tasks and address the decision-making problem between multiple mobile devices and multiple edge servers， an incentive mechanism based on multi-leader Stackelberg game was proposed. Firstly， by quantifying the cost-utility of mobile devices and the payment of edge servers， a utility function was constructed， and an optimization problem was defined. Then， the interaction among mobile devices was modeled as an evolutionary game， and the interaction among edge servers was modeled as a non-cooperative game. To solve the optimal edge server selection and pricing strategy， a Multi-round Iterative Edge Server selection algorithm （MIES） and a Gradient Iterative Pricing Algorithm （GIPA） were proposed. The former was used to solve the evolutionary game equilibrium solution among mobile devices， and the latter was used to solve the pricing competition problem among edge servers. Experimental results show that compared with Optimal Pricing Prediction Strategy （OPPS）， Historical Optimal Pricing Strategy （HOPS） and Random Pricing Strategy （RPS）， GIPA can increase the average utility of edge servers by 4.06%， 10.08%， and 31.39% respectively.

Key words: hierarchical federated learning, incentive mechanism, pricing strategy, multi-leader Stackelberg game, evolutionary game

摘要：

分层联邦学习中隐私安全与资源消耗等问题的存在降低了参与者的积极性。为鼓励足够多的参与者积极参与学习任务，并针对多移动设备与多边缘服务器之间的决策问题，提出基于多领导者Stackelberg博弈的激励机制。首先，通过量化移动设备的成本效用与边缘服务器的支付报酬，构建效用函数并定义最优化问题；其次，将移动设备之间的交互建模为演化博弈，将边缘服务器之间的交互建模为非合作博弈。为求解最优边缘服务器选择和定价策略，提出多轮迭代边缘服务器选择算法（MIES）和梯度迭代定价算法（GIPA），前者用于求解移动设备之间的演化博弈均衡解，后者用于求解边缘服务器之间的定价竞争问题。实验结果表明，所提算法GIPA与最优定价预测策略（OPPS）、历史最优定价策略（HOPS）和随机定价策略（RPS）相比，可使边缘服务器的平均效用分别提高4.06%、10.08%和31.39%。

关键词: 分层联邦学习, 激励机制, 定价策略, 多领导者Stackelberg博弈, 演化博弈

CLC Number:

TP393

Fangxing GENG, Zhuo LI, Xin CHEN. Incentive mechanism design for hierarchical federated learning based on multi-leader Stackelberg game[J]. Journal of Computer Applications, 2023, 43(11): 3551-3558.

耿方兴, 李卓, 陈昕. 基于多领导者Stackelberg博弈的分层联邦学习激励机制设计[J]. 《计算机应用》唯一官方网站, 2023, 43(11): 3551-3558.

Figures/Tables 10

Fig. 1 Framework of hierarchical federated learning

Fig. 2 Multi-leader Stackelberg game model

Tab. 1 Simulation parameters setting

参数	值	参数说明
N	90	移动设备数量
J	3	边缘服务器数量
M	3	种群数量
$D m$	［2 400，4 800］	种群m中的总数据量
$δ$	0.001	移动设备对信息的获取率
$c m υ$	0.001	种群m中单位数据所产生的计算成本
$c m τ$	50	种群m中单位功率传输的成本
$I m$	0.1	种群m中模型数据大小
$λ$	100	移动设备训练迭代的轮次
$ρ m$	10	种群m中传输速率
$ζ j$	［3，3.6］	边缘服务器j收益参数
$μ$	1	网络拥塞系数
$β j$	［2，3］	边缘服务器j定价的改变幅度

Tab. 1 Simulation parameters setting

参数	值	参数说明
N	90	移动设备数量
J	3	边缘服务器数量
M	3	种群数量
$D m$	［2 400，4 800］	种群m中的总数据量
$δ$	0.001	移动设备对信息的获取率
$c m υ$	0.001	种群m中单位数据所产生的计算成本
$c m τ$	50	种群m中单位功率传输的成本
$I m$	0.1	种群m中模型数据大小
$λ$	100	移动设备训练迭代的轮次
$ρ m$	10	种群m中传输速率
$ζ j$	［3，3.6］	边缘服务器j收益参数
$μ$	1	网络拥塞系数
$β j$	［2，3］	边缘服务器j定价的改变幅度

Fig. 3 Trend of a1 varying with number of iterations （m=1）

Fig. 4 Trend of a11 varying with number of iterations （m=1） under different initial status

Fig. 5 Comparison of total mobile device utility in different populations with constant edge server pricing

Fig. 6 Pricing trends for edge servers after finite iterations

Fig. 7 Utilities of edge servers with different revenue parameters

Fig. 8 Utility comparison of edge servers under different pricing strategies

Fig. 9 Comparison of model positivity under different pricing strategies

References 28

1	谭作文，张连福. 机器学习隐私保护研究综述［J］. 软件学报， 2020， 31（7）：2127-2156. 10.13328/j.cnki.jos.006052
	TAN Z W， ZHANG L F. Survey on privacy preserving techniques for machine learning［J］. Journal of Software， 2020， 31（7）： 2127-2156. 10.13328/j.cnki.jos.006052
2	McMAHAN H B， MOORE E， RAMAGE D， et al. Communication-efficient learning of deep networks from decentralized data［C］// Proceedings of the 20th International Conference on Artificial Intelligence and Statistics. New York： JMLR.org， 2017：1273-1282.
3	ABAD M S H， OZFATURA E， GÜNDÜZ D， et al. Hierarchical federated learning across heterogeneous cellular networks［C］// Proceedings of the 2020 IEEE International Conference on Acoustics， Speech and Signal Processing. Piscataway： IEEE， 2020： 8866-8870. 10.1109/icassp40776.2020.9054634
4	TU X， ZHU K， LUONG N C， et al. Incentive mechanisms for federated learning： from economic and game theoretic perspective［J］. IEEE Transactions on Cognitive Communications and Networking， 2022， 8（3）： 1566-1593. 10.1109/tccn.2022.3177522
5	TIAN M， CHEN Y， LIU Y， et al. A contract theory based incentive mechanism for federated learning［EB/OL］. （2021-08-12）［2022-08-10］.. 10.1007/978-3-031-11748-0_6
6	YU H， LIU Z， LIU Y， et al. A fairness-aware incentive scheme for federated learning［C］// Proceedings of the 2020 AAAI/ACM Conference on AI， Ethics， and Society. New York： ACM， 2020： 393-399. 10.1145/3375627.3375840
7	ZENG R， ZHANG S， WANG J， et al. FMore： an incentive scheme of multi-dimensional auction for federated learning in MEC［C］// Proceedings of the IEEE 40th International Conference on Distributed Computing Systems. Piscataway： IEEE， 2020： 278-288. 10.1109/icdcs47774.2020.00094
8	李从东，黄浩，张帆顺. 基于演化博弈的领先用户知识共享行为激励机制［J］. 计算机应用， 2021， 41（6）：1785-1791. 10.11772/j.issn.1001-9081.2020091449
	LI C D， HUANG H， ZHANG F S. Knowledge sharing behavior incentive mechanism for lead users based on evolutionary game［J］. Journal of Computer Applications， 2021， 41（6）： 1785-1791. 10.11772/j.issn.1001-9081.2020091449
9	CHEN Y， ZHANG Y， WANG S， et al. DIM-DS： dynamic incentive model for data sharing in federated learning based on smart contracts and evolutionary game theory［J］. IEEE Internet of Things Journal， 2022， 9（23）： 24572-24584. 10.1109/jiot.2022.3191671
10	ZOU Y， FENG S， NIYATO D， et al. Mobile device training strategies in federated learning： an evolutionary game approach［C］// Proceedings of the 2019 IEEE International Conference on Internet of Things/ Green Computing and Communications/ Cyber， Physical and Social Computing/ Smart Data. Piscataway： IEEE， 2019： 874-879. 10.1109/ithings/greencom/cpscom/smartdata.2019.00157
11	王月平，徐涛. 基于演化博弈的用户接入机制［J］. 计算机应用， 2020， 40（5）：1392-1396. 10.11772/j.issn.1001-9081.2019112024
	WANG Y P， XU T. User association mechanism based on evolutionary game［J］. Journal of Computer Applications， 2020， 40（5）： 1392-1396. 10.11772/j.issn.1001-9081.2019112024
12	LIM W Y B， NG J S， XIONG Z， et al. Dynamic edge association and resource allocation in self-organizing hierarchical federated learning networks［J］. IEEE Journal on Selected Areas in Communications， 2021， 39（12）： 3640-3653. 10.1109/jsac.2021.3118401
13	FENG S， NIYATO D， WANG P， et al. Joint service pricing and cooperative relay communication for federated learning［C］// Proceedings of the 2019 IEEE International Conference on Internet of Things/ Green Computing and Communications/ Cyber， Physical and Social Computing/ Smart Data. Piscataway： IEEE， 2019： 815-820. 10.1109/ithings/greencom/cpscom/smartdata.2019.00148
14	XIAO G， XIAO M， GAO G， et al. Incentive mechanism design for federated learning： a two-stage Stackelberg game approach［C］// Proceedings of the IEEE 26th International Conference on Parallel and Distributed Systems. Piscataway： IEEE， 2020： 148-155. 10.1109/icpads51040.2020.00029
15	KHAN L U， PANDEY S R， TRAN N H， et al. Federated learning for edge networks： resource optimization and incentive mechanism［J］. IEEE Communications Magazine， 2020， 58（10）： 88-93. 10.1109/mcom.001.1900649
16	NIE J， LUO J， XIONG Z， et al. A Stackelberg game approach toward socially-aware incentive mechanisms for mobile crowdsensing［J］. IEEE Transactions on Wireless Communications， 2019， 18（1）： 724-738. 10.1109/twc.2018.2885747
17	SU Y， FAN W， LIU Y， et al. Game-based pricing and task offloading in mobile edge computing enabled edge-cloud systems［EB/OL］. （2021-01-14）［2022-08-10］.. 10.1016/j.comnet.2021.108523
18	ZHAN Y， LI P， QU Z， et al. A learning-based incentive mechanism for federated learning［J］. IEEE Internet of Things Journal， 2020， 7（7）： 6360-6368. 10.1109/jiot.2020.2967772
19	GONG X， DUAN L， CHEN X， et al. When social network effect meets congestion effect in wireless networks： data usage equilibrium and optimal pricing［J］. IEEE Journal on Selected Areas in Communications， 2017， 35（2）： 449-462. 10.1109/jsac.2017.2659059
20	HAN Z， NIYATO D， SAAD W， et al. Game Theory in Wireless and Communication Networks： Theory， Models， and Applications［M］. Cambridge： Cambridge University Press， 2012： 139-143. 10.1017/cbo9780511895043
21	HOFBAUER J， SIGMUND K. Evolutionary game dynamics［J］. Bulletin of the American Mathematical Society， 2003， 40（4）： 479-519. 10.1090/s0273-0979-03-00988-1
22	GAO X， FENG S， NIYATO D， et al. Dynamic access point and service selection in backscatter-assisted RF-powered cognitive networks［J］. IEEE Internet of Things Journal， 2019， 6（5）： 8270-8283. 10.1109/jiot.2019.2923566
23	PEJÓ B， TANG Q， BICZÓK G. Together or alone： the price of privacy in collaborative learning［EB/OL］. ［2022-08-10］.. 10.2478/popets-2019-0019
24	WENG J， WENG J， HUANG H， et al. FedServing： a federated prediction serving framework based on incentive mechanism［C］// Proceedings of the 2021 IEEE Conference on Computer Communications. Piscataway： IEEE， 2021： 1-10. 10.1109/infocom42981.2021.9488807
25	GONDZIO J. Interior point methods 25 years later［J］. European Journal of Operational Research， 2012， 218（3）： 587-601. 10.1016/j.ejor.2011.09.017
26	LENG Y， WANG M， MA B， et al. A game-based scheme for resource purchasing and pricing in MEC for Internet of Things［J］. Security and Communication Networks， 2021， 2021： No.1951141. 10.1155/2021/1951141
27	DENG Y， LYU F， REN J， et al. Improving federated learning with quality-aware user incentive and auto-weighted model aggregation［J］. IEEE Transactions on Parallel and Distributed Systems， 2022， 33（12）： 4515-4529. 10.1109/tpds.2022.3195207
28	ZHAN Y， ZHANG J， HONG Z， et al. A survey of incentive mechanism design for federated learning［J］. IEEE Transactions on Emerging Topics in Computing， 2022， 10（2）： 1035-1044.

[1]	Tingwei CHEN, Jiacheng ZHANG, Junlu WANG. Random validation blockchain construction for federated learning [J]. Journal of Computer Applications, 2024, 44(9): 2770-2776.
[2]	Sunjie YU, Hui ZENG, Shiyu XIONG, Hongzhou SHI. Incentive mechanism for federated learning based on generative adversarial network [J]. Journal of Computer Applications, 2024, 44(2): 344-352.
[3]	Peiyao ZHANG, Xiaodong FU. Incentive mechanism of crowdsourcing multi-task assignment against malicious bidding [J]. Journal of Computer Applications, 2024, 44(1): 261-268.
[4]	Yanan PAN, Qingxian PAN, Zhaoyi YU, Jiajing CHU, Song YU. Online incentive mechanism based on quality perception in spatio-temporal crowdsourcing [J]. Journal of Computer Applications, 2023, 43(7): 2091-2099.
[5]	ZHENG Wanbo, CHEN Huimin, WU Yanqing, XIA Yunni. Simulation of information sharing strategy based on emergency rescue [J]. Journal of Computer Applications, 2023, 43(1): 306-311.
[6]	Wenting BI, Haitao LIN, Liqun ZHANG. Moving target defense decision-making algorithm based on multi-stage evolutionary signal game model [J]. Journal of Computer Applications, 2022, 42(9): 2780-2787.
[7]	Youzhi LI, Zhihua HU, Chun CHEN, Peibei YANG, Yajing DONG. Prediction model of transaction pricing in internet freight transport platform based on combination of dual long short-term memory networks [J]. Journal of Computer Applications, 2022, 42(5): 1616-1623.
[8]	GONG Ying, HE Yanting, CAO Cejun. Co-evolutionary simulation regarding emergency logistics in major public health risk governance [J]. Journal of Computer Applications, 2021, 41(9): 2754-2760.
[9]	LI Congdong, HUANG Hao, ZHANG Fanshun. Knowledge sharing behavior incentive mechanism for lead users based on evolutionary game [J]. Journal of Computer Applications, 2021, 41(6): 1785-1791.
[10]	Ying LEI, Wanbo ZHENG, Wei WEI, Yunni XIA, Xiaobo LI, Chengwu LIU, Hong XIE. Task offloading method based on probabilistic performance awareness and evolutionary game strategy in “cloud + edge” hybrid environment [J]. Journal of Computer Applications, 2021, 41(11): 3302-3308.
[11]	WU Guangfu, WANG Yingjun. Secure storage and sharing scheme of internet of vehicles data based on hybrid architecture of blockchain and cloud-edge computing [J]. Journal of Computer Applications, 2021, 41(10): 2885-2892.
[12]	WANG Yueping, XU Tao. User association mechanism based on evolutionary game [J]. Journal of Computer Applications, 2020, 40(5): 1392-1396.
[13]	CHEN Xiuhua, LIU Hui, XIONG Jinbo, MA Rong. Task requirement-oriented user selection incentive mechanism in mobile crowdsensing [J]. Journal of Computer Applications, 2019, 39(8): 2310-2317.
[14]	WANG Xilong, WANG Jicheng, LUO Cheng, TIAN Xiuxia. Evolutionary game model under synergistic effect of time scale and selection preference [J]. Journal of Computer Applications, 2019, 39(6): 1824-1828.
[15]	WANG Yingjie, CAI Zhipeng, TONG Xiangrong, PAN Qingxian, GAO Yang, YIN Guisheng. Online incentive mechanism based on reputation for mobile crowdsourcing system [J]. Journal of Computer Applications, 2016, 36(8): 2121-2127.

Incentive mechanism design for hierarchical federated learning based on multi-leader Stackelberg game

基于多领导者Stackelberg博弈的分层联邦学习激励机制设计

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 28

Related Articles 15

Recommended Articles

Metrics