基于随机游走算法的频谱组合拍卖机制

doi:10.11772/j.issn.1001-9081.2022091351

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (8): 2352-2357.DOI: 10.11772/j.issn.1001-9081.2022091351

• 第十九届CCF中国信息系统及应用大会 • 上一篇

基于随机游走算法的频谱组合拍卖机制

王菁怡¹, 李超¹^,², 宋衡¹^,³, 李迪¹^,², 朱俊武¹()

^1.扬州大学信息工程学院，江苏扬州 225127
^2.中国船舶集团有限公司第七二三研究所，江苏扬州 225001
^3.中国科学院计算技术研究所智能信息处理重点实验室，北京 100190

收稿日期:2022-09-06 修回日期:2022-10-17 接受日期:2022-10-22 发布日期:2022-11-25 出版日期:2023-08-10
通讯作者: 朱俊武
作者简介:王菁怡（1997—），女，江苏徐州人，硕士研究生，CCF会员，主要研究方向：机制设计、算法博弈论
李超（1982—），男，黑龙江牡丹江人，硕士，主要研究方向：电子对抗
宋衡（1990—），男，江苏常州人，博士，CCF会员，主要研究方向：自然语言处理、机制设计
李迪（1982—），男，吉林白山人，博士，主要研究方向：无人集群电子对抗；
基金资助:
国家自然科学基金资助项目(61872313);江苏省研究生科研与实践创新计划项目(KYCX21_3233)

Spectrum combinatorial auction mechanism based on random walk algorithm

Jingyi WANG¹, Chao LI¹^,², Heng SONG¹^,³, Di LI¹^,², Junwu ZHU¹()

^1.College of Information Engineering，Yangzhou University，Yangzhou Jiangsu 225127，China
^2.No. 723 Research Institute，China State Shipbuilding Corporation Limited，Yangzhou Jiangsu 225001，China
^3.Key Laboratory of Intelligent Information Processing，Institute of Computer Technology，Chinese Academy of Sciences，Beijing 100190，China

Received:2022-09-06 Revised:2022-10-17 Accepted:2022-10-22 Online:2022-11-25 Published:2023-08-10
Contact: Junwu ZHU
About author:WANG Jingyi， born in 1997， M. S. candidate. Her research interests include mechanism design， algorithmic game theory.
LI Chao， born in 1982， M. S. His research interests include electronic countermeasures.
SONG Heng， born in 1990， Ph. D. His research interests include natural language processing， mechanism design.
LI Di， born in 1982， Ph. D. His research interests include unmanned swarm electronic countermeasures.
Supported by:
National Natural Science Foundation of China(61872313);Postgraduate Research and Practice Innovation Program of Jiangsu Province(KYCX21_3233)

摘要/Abstract

摘要：

如何将频谱有效地分配给用户并提高提供商的收益是目前研究的热点。针对频谱组合拍卖中提供商收益低的问题，结合用户估值分布不对称的特点，设计了基于随机游走的频谱组合拍卖（RWSCA）机制，以最大化频谱提供商的收益。首先引入了虚拟估值的思想，用随机游走算法在参数空间搜索一组最优参数，并根据参数线性映射买家的估值；然后运行基于虚拟估值的VCG （Vickrey-Clarke-Groves）机制，从而确定赢得拍卖的用户并计算相应的支付金额。理论分析证明了所提机制具有激励相容和个体理性的性质。在频谱组合拍卖仿真实验中，相较于VCG机制，RWSCA机制至少提高16.84%以上提供商收益。

关键词: 组合拍卖, 频谱, 随机游走算法, 参数搜索, 虚拟估值

Abstract:

How to allocate spectra to users efficiently and improve the revenue of providers are popular research topics recently. To address the problem of low revenue of providers in spectrum combinatorial auctions， Random Walk for Spectrum Combinatorial Auctions （RWSCA） mechanism was designed to maximize the revenue of spectrum providers by combining the characteristics of asymmetric distribution of user valuations. First， the idea of virtual valuation was introduced， the random walk algorithm was used to search for a set of optimal parameters in the parameter space， and the valuations of buyers were linearly mapped according to the parameters. Then， VCG （Vickrey-Clarke-Groves） mechanism based on virtual valuation was run to determine the users who won the auction and calculate the corresponding payments. Theoretical analysis proves that the proposed mechanism is incentive compatible and individually rational. In spectrum combinatorial auction simulation experiments， the RWSCA mechanism increases the provider’s revenue by at least 16.84%.

Key words: combinatorial auction, spectrum, random walk algorithm, parametric search, virtual valuation

中图分类号:

TP399

王菁怡, 李超, 宋衡, 李迪, 朱俊武. 基于随机游走算法的频谱组合拍卖机制[J]. 计算机应用, 2023, 43(8): 2352-2357.

Jingyi WANG, Chao LI, Heng SONG, Di LI, Junwu ZHU. Spectrum combinatorial auction mechanism based on random walk algorithm[J]. Journal of Computer Applications, 2023, 43(8): 2352-2357.

图/表 5

图1 频谱拍卖的架构

Fig. 1 Architecture of spectrum auction

表1 不同用户估值分布的参数设置

Tab. 1 Parameter settings for different user valuation distributions

参数	设置一	设置二	设置三
$f 1$	［0，1］	［1，2］	［1，2］
$f 2$	［0，1］	［1，2］	［1，5］
$δ$	0	［-1，1］	［-1，1］

表1 不同用户估值分布的参数设置

Tab. 1 Parameter settings for different user valuation distributions

参数	设置一	设置二	设置三
$f 1$	［0，1］	［1，2］	［1，2］
$f 2$	［0，1］	［1，2］	［1，5］
$δ$	0	［-1，1］	［-1，1］

表2 不同参数设置下的机制收益

Tab. 2 Mechanism revenue with different parameter setting

机制	设置一		设置二		设置三
机制	收益	提升/%	收益	提升/%	收益	提升/%
VCG	0.667	—	2.405	—	2.847	—
AMA	0.804	20.54	2.810	16.84	4.393	54.30
RWSCA-1	0.816	22.34	2.859	18.88	4.451	56.34
RWSCA-2	0.814	22.04	2.844	18.25	4.434	55.74
RWSCA-3	0.806	20.84	2.829	17.63	4.415	55.08

图2 用户数增加时的收益

Fig. 2 Revenue with increasing number of users

图3 物品数增加时的收益

Fig. 3 Revenue with increasing number of items

参考文献 23

1	CHEN J X， WU Q H， XU Y H， et al. Joint task assignment and spectrum allocation in heterogeneous UAV communication networks： a coalition formation game-theoretic approach［J］. IEEE Transactions on Wireless Communications， 2020， 20（1）： 440-452. 10.1109/twc.2020.3025316
2	梁应敞，谭俊杰， NIYATO D. 智能无线通信技术研究概况［J］. 通信学报， 2020， 41（7）：1-17. 10.11959/j.issn.1000-436x.2020145
	LIANG Y C， TAN J J， NIYATO D. Overview on intelligent wireless communication technology［J］. Journal on Communications， 2020， 41（7）：1-17. 10.11959/j.issn.1000-436x.2020145
3	盖建新，薛宪峰，南瑞祥，等. 基于残差密集网络的频谱感知方法［J］. 通信学报， 2021， 42（12）：182-191.
	GAI J X， XUE X F， NAN R X， et al. Spectrum sensing method based on residual dense network［J］. Journal on Communications， 2021， 42（12）： 182-191.
4	毛莺池，郝帅，平萍，等. 基于组合双向拍卖的云资源调度方法［J］. 计算机应用， 2019， 39（1）：1-7. 10.11772/j.issn.1001-9081.2018071614
	MAO Y C， HAO S， PING P， et al. Cloud resource scheduling method based on combinatorial double auction［J］. Journal of Computer Applications， 2019， 39（1）： 1-7. 10.11772/j.issn.1001-9081.2018071614
5	FOX J T， BAJARI P. Measuring the efficiency of an FCC spectrum auction［J］. American Economic Journal： Microeconomics， 2013， 5（1）： 100-146. 10.1257/mic.5.1.100
6	MARTÍNEZ-SANTOS F， FRIAS Z， ESCRIBANO Á. What drives spectrum prices in multi-band spectrum markets？ an empirical analysis of 4G and 5G auctions in Europe［J］. Applied Economics， 2022， 54（5）： 536-553. 10.1080/00036846.2021.1967277
7	张朝辉，李靖，韩璐珩. 基于数据-地理位置联合驱动的5G微基站最优分配策略［J］. 计算机学报， 2022， 45（5）：1087-1099. 10.11897/SP.J.1016.2022.01087
	ZHANG Z H， LI J， HAN L H. Data-location-joint-driven optimal allocation strategy for micro base stations in 5G networks［J］. Chinese Journal of Computers， 2022， 45（5）：1087-1099. 10.11897/SP.J.1016.2022.01087
8	ROUGHGARDEN T. Algorithmic game theory［J］. Communications of the ACM， 2010， 53（7）： 78-86. 10.1145/1785414.1785439
9	MYERSON R B. Optimal auction design［J］. Mathematics of Operations Research， 1981， 6（1）： 58-73. 10.1287/moor.6.1.58
10	ZHENG Z Z， WU F， CHEN G H. A strategy-proof combinatorial heterogeneous channel auction framework in noncooperative wireless networks［J］. IEEE Transactions on Mobile Computing， 2015， 14（6）： 1123-1137. 10.1109/tmc.2014.2343624
11	YI C Y， CAI J. Combinatorial spectrum auction with multiple heterogeneous sellers in cognitive radio networks［C］// Proceedings of the 2014 IEEE International Conference on Communications. Piscataway： IEEE， 2014： 1626-1631. 10.1109/icc.2014.6883555
12	GANDHI S， BURAGOHAIN C， CAO L L， et al. A general framework for wireless spectrum auctions［C］// Proceedings of the 2nd IEEE International Symposium on New Frontiers in Dynamic Spectrum Access Networks. Piscataway： IEEE， 2007： 22-33. 10.1109/dyspan.2007.12
13	MASKIN E， RILEY J. Optimal multi-unit auctions［M］// HAHN F.The Economics of Missing Markets， Information， and Games. Oxford： Oxford University Press， 1989： 312-335. 10.2307/2233672
14	ARMSTRONG M. Multiproduct nonlinear pricing［J］. Econometrica， 1996， 64（1）： 51-75. 10.2307/2171924
15	MANELLI A M， VINCENT D R. Multidimensional mechanism design： revenue maximization and the multiple-good monopoly［J］. Journal of Economic Theory， 2007， 137（1）： 153-185. 10.1016/j.jet.2006.12.007
16	PAVLOV G. Optimal mechanism for selling two goods［J］. The B.E. Journal of Theoretical Economics， 2011， 11（1）： No.3. 10.2202/1935-1704.1664
17	DASKALAKIS C， DECKELBAUM A， TZAMOS C. Mechanism design via optimal transport［C］// Proceedings of the 14th ACM Conference on Electronic Commerce. New York： ACM， 2013： 269-286. 10.1145/2482540.2482593
18	TANG P Z， WANG Z H. Optimal mechanisms with simple menus［J］. Journal of Mathematical Economics， 2017， 69： 54-70. 10.1016/j.jmateco.2017.01.002
19	YAO A C C. Dominant-strategy versus Bayesian multi-item auctions： maximum revenue determination and comparison［C］// Proceedings of the 2017 ACM Conference on Economics and Computation. New York： ACM， 2017： 3-20. 10.1145/3033274.3085120
20	CONITZER V， SANDHOLM T. Complexity of mechanism design［C］// Proceedings of the 18th Conference on Uncertainty in Artificial Intelligence. San Francisco： Morgan Kaufmann Publishers Inc.， 2002： 103-110. 10.1145/948005.948008
21	SANDHOLM T， LIKHODEDOV A. Automated design of revenue-maximizing combinatorial auctions［J］. Operations Research， 2015， 63（5）： 1000-1025. 10.1287/opre.2015.1398
22	GUO M Y， HATA H， BABAR A. Optimizing affine maximizer auctions via linear programming： an application to revenue maximizing mechanism design for zero-day exploits markets［C］// Proceedings of the 2017 International Conference on Principles and Practice of Multi-Agent Systems， LNCS 10621. Cham： Springer， 2017： 280-292.
23	DÜTTING P， FENG Z， NARASIMHAN H， et al. Optimal auctions through deep learning［C］// Proceedings of the 36th International Conference on Machine Learning. New York： JMLR.org， 2019： 1706-1715. 10.1007/978-3-030-18050-8_70

[1]	刘万军, 王佳铭, 曲海成, 董利兵, 曹欣宇. 基于频谱空间域特征注意的音乐流派分类算法[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2072-2077.
[2]	董明宇, 严迪群. 基于ResNet的音频场景声替换造假的检测算法[J]. 《计算机应用》唯一官方网站, 2022, 42(6): 1724-1728.
[3]	凌欣, 李民政. 无人机巡检系统中高频效的混合波束赋形方法[J]. 《计算机应用》唯一官方网站, 2022, 42(3): 980-984.
[4]	刘贻杰, 李江春, 陈维娜, 黄颀涵. 信道对汉语普通话元音共振峰的影响[J]. 《计算机应用》唯一官方网站, 2022, 42(12): 3906-3912.
[5]	王大为, 刘新浩, 李竹, 芦宾, 郭爱心, 柴国强. 离散蝠鲼觅食优化算法及在频谱分配中的应用[J]. 《计算机应用》唯一官方网站, 2022, 42(1): 215-222.
[6]	牛晓可, 黄伊鑫, 徐华兴, 蒋震阳. 基于听皮层神经元感受野的强噪声环境下说话人识别[J]. 计算机应用, 2020, 40(10): 3034-3040.
[7]	张刚, 黄南飞, 张天骐. 多用户正交相关延迟键控方案性能分析[J]. 计算机应用, 2019, 39(5): 1425-1428.
[8]	文槿奕, 唐伦, 陈前斌. 物联网传感器网络中次级用户在不完美信道下的带宽和功率分配[J]. 计算机应用, 2018, 38(8): 2330-2336.
[9]	裴安山, 王让定, 严迪群. 基于语音频谱融合特征的手机来源识别[J]. 计算机应用, 2018, 38(3): 884-890.
[10]	王桂胜, 任清华, 徐兵政, 刘洋. 远距航空通信变换域通信系统设计[J]. 计算机应用, 2018, 38(2): 522-527.
[11]	张海波, 彭星萤, 陈善学. 宏-飞蜂窝双层网络中基于毫微微基站分组的资源分配[J]. 计算机应用, 2017, 37(5): 1311-1316.
[12]	王思秀, 郭文强, 汪晓洁. 认知无线电中基于多址接入信道的多用户联合频谱感知算法[J]. 计算机应用, 2017, 37(4): 960-964.
[13]	段瑞杰, 姚富强, 李永贵, 郭鹏程. 基于智能跳频的短波无线接入网动态频谱分配算法[J]. 计算机应用, 2016, 36(8): 2163-2169.
[14]	廖云峰, 陈勇, 孙爱伟, 邵鸿翔. 基于用户预算和服务质量的动态频谱接入[J]. 计算机应用, 2016, 36(4): 899-904.
[15]	王立夫, 孙怡. 基于一致性稀疏表示的地震信号补全算法[J]. 计算机应用, 2016, 36(4): 1167-1172.

基于随机游走算法的频谱组合拍卖机制

Spectrum combinatorial auction mechanism based on random walk algorithm

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 23

相关文章 15

编辑推荐

Metrics