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

Spectrum combinatorial auction mechanism based on random walk algorithm

作　　者：王菁怡 李超 宋衡[1,3] 李迪 朱俊武 WANG Jingyi;LI Chao;SONG Heng;LI Di;ZHU Junwu(College of Information Engineering,Yangzhou University,Yangzhou Jiangsu 225127,China;No.723 Research Institute,China State Shipbuilding Corporation Limited,Yangzhou Jiangsu 225001,China;Key Laboratory of Intelligent Information Processing,Institute of Computer Technology,Chinese Academy of Sciences,Beijing 100190,China)

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

出　　处：《计算机应用》2023年第8期2352-2357,共6页journal of Computer Applications

基　　金：国家自然科学基金资助项目(61872313);江苏省研究生科研与实践创新计划项目(KYCX21_3233)。

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

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

分 类 号：TP399[自动化与计算机技术—计算机应用技术]