基于随机游走算法的频谱组合拍卖机制.pdf
《基于随机游走算法的频谱组合拍卖机制.pdf》由会员分享,可在线阅读,更多相关《基于随机游走算法的频谱组合拍卖机制.pdf(6页珍藏版)》请在咨信网上搜索。
1、2023 08 10计算机应用,Journal of Computer Applications2023,43(8):2352-2357ISSN 10019081CODEN JYIIDUhttp:/基于随机游走算法的频谱组合拍卖机制王菁怡1,李超1,2,宋衡1,3,李迪1,2,朱俊武1*(1.扬州大学 信息工程学院,江苏 扬州 225127;2.中国船舶集团有限公司 第七二三研究所,江苏 扬州 225001;3.中国科学院计算技术研究所 智能信息处理重点实验室,北京 100190)(通信作者电子邮箱)摘要:如何将频谱有效地分配给用户并提高提供商的收益是目前研究的热点。针对频谱组合拍卖中提供商收
2、益低的问题,结合用户估值分布不对称的特点,设计了基于随机游走的频谱组合拍卖(RWSCA)机制,以最大化频谱提供商的收益。首先引入了虚拟估值的思想,用随机游走算法在参数空间搜索一组最优参数,并根据参数线性映射买家的估值;然后运行基于虚拟估值的VCG(Vickrey-Clarke-Groves)机制,从而确定赢得拍卖的用户并计算相应的支付金额。理论分析证明了所提机制具有激励相容和个体理性的性质。在频谱组合拍卖仿真实验中,相较于VCG机制,RWSCA机制至少提高16.84%以上提供商收益。关键词:组合拍卖;频谱;随机游走算法;参数搜索;虚拟估值中图分类号:TP399 文献标志码:ASpectrum
3、combinatorial auction mechanism based on random walk algorithmWANG Jingyi1,LI Chao1,2,SONG Heng1,3,LI Di1,2,ZHU Junwu1*(1.College of Information Engineering,Yangzhou University,Yangzhou Jiangsu 225127,China;2.No.723 Research Institute,China State Shipbuilding Corporation Limited,Yangzhou Jiangsu 225
4、001,China;3.Key Laboratory of Intelligent Information Processing,Institute of Computer Technology,Chinese Academy of Sciences,Beijing 100190,China)Abstract:How to allocate spectra to users efficiently and improve the revenue of providers are popular research topics recently.To address the problem of
5、 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 w
6、as 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 t
7、he 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:com
8、binatorial auction;spectrum;random walk algorithm;parametric search;virtual valuation0 引言 无线电频谱是自然界中的一种电磁波,主要用途是传输通信信号1。国际电信联盟根据频率将电磁波划分为多个频段供各国使用。作为珍贵而稀缺的战略性自然资源,政府有专门的部门来管理和分配频谱。传统的频谱资源的分配是静态的,效率不高,每年都有许多新的无线应用需要使用频谱进行通信。因此,如何设计一种频谱分配方式,在满足用户的需求同时确保频谱提供商获得高收益,这一问题至关重要。组合拍卖以公开竞价的方式将物品捆绑出售,根据分配规则将物品
9、分配给用户,根据支付规则计算用户的支付,提供商可以获得收益。组合拍卖能有效提高频谱利用率,因此在频谱分配中被广泛使用2-4。例如,美国联邦通信委员会(Federal Communications Commission,FCC)采用多轮密封组合拍卖进行分配,提高了频谱的利用率。1981年,新西兰政府通过第一价格密封组合拍卖分配频谱资源,获得了高额收益。2012年,FCC成立了一个专门的组织研究激励拍卖,重新分配频谱来优化资源配置5。很多欧洲国家在拍卖 5G(5th Generation mobile communication technology)频谱,能充分利用有限的频谱资源6-7。频谱组合
10、拍卖主要考虑如何分配频谱给用户,很少考虑到提供商的收益问题。VCG(Vickrey-Clarke-Groves)机制8作为组合拍卖的基准,它以社会福利最大化的方式分配物品。当拍卖中仅包含一个物品时,该拍卖变成了二价拍卖,获胜用文章编号:1001-9081(2023)08-2352-06DOI:10.11772/j.issn.1001-9081.2022091351收稿日期:20220906;修回日期:20221017;录用日期:20221022。基金项目:国家自然科学基金资助项目(61872313);江苏省研究生科研与实践创新计划项目(KYCX21_3233)。作者简介:王菁怡(1997),女
11、,江苏徐州人,硕士研究生,CCF会员,主要研究方向:机制设计、算法博弈论;李超(1982),男,黑龙江牡丹江人,硕士,主要研究方向:电子对抗;宋衡(1990),男,江苏常州人,博士,CCF会员,主要研究方向:自然语言处理、机制设计;李迪(1982),男,吉林白山人,博士,主要研究方向:无人集群电子对抗;朱俊武(1972),男,江苏江都人,教授,博士,CCF高级会员,主要研究方向:人工智能领域的知识工程及算法博弈论。第 8 期王菁怡等:基于随机游走算法的频谱组合拍卖机制户支付次高价格,提供商的收益还有提高的空间。VCG机制虽然提高了频谱的分配效率,但是设计一个收益最大化的频谱组合拍卖机制仍有一些
12、问题需要解决:一方面拍卖总是以社会福利最大化的方式把物品分配物品,但是提供商的收益往往低于社会福利值,还有提升空间;另一方面,用户是自利的8,他们可能会操纵报价以提高自身的效用,这种操纵增加了机制设计者的负担。Myerson9使用虚拟估值方法解决了单物品收益最大化拍卖,但不能解决多物品多用户的最优拍卖问题。因此,本文设计了一种基于虚拟估值的VCG机制,能够激励用户诚实报价,并且可以用于解决多物品多用户拍卖问题,提高机制中提供商的收益。本文的主要工作归纳为以下3点:1)通过基于虚拟估值的VCG机制,能够提高出价较低用户的竞争力,使得机制能从出价高的用户身上获得更多利润,进而提高机制中提供商收益。
13、2)提出的基于随机游走的频谱组合拍卖(Random Walk for Spectrum Combinatorial Auctions,RWSCA)机制能够保证机制激励相容和个体理性,使得参与拍卖的用户诚实报价,降低机制设计者的负担。3)使用随机游走算法在参数空间中搜索参数,可以从全局角度搜索参数,避免陷入局部最优解。模拟实验证明了该算法能在多物品多用户组合拍卖中提高提供商的收益。1 相关工作 随着无线电技术的发展,频谱在人们的生活中扮演着重要角色,越来越多的用户需要订购频谱信道完成通信任务。有很多专家和学者正在研究频谱拍卖机制的设计问题。Zheng等10为异质频谱设计了一个拍卖框架,并将赢家决
14、策问题建模为一个二进制程序。使用贪婪算法计算社会福利最大化的分配方案,用户可以在这个框架下进行真实的出价。Yi等11把认知型无线频谱分配问题规划为一个背包问题,推导出多项式时间的上界,使用近似算法解决了频谱分配问题。该算法可以保证用户的真实报价,提高频谱分配的效率。Gandhi等12设计了一种频谱竞价语言来满足用户对频谱的实时需求,最大化频谱利用率,并相应地增加供应商的收益。以上工作均考虑到机制的真实性,但未考虑频谱提供商希望尽可能多地将频谱分配出去,以获得高收益的需求。Maskin等13在Myerson单物品最优拍卖基础上,研究了包含多个副本的单物品最优拍卖,提高了提供商的收益。当面对多种物
15、品和不同数量的用户时,设计一个最大化提供商收益的拍卖仍然是一个具有挑战性的问题。Armstrong14研究了当一个物品的估值与另一个物品的估值成正比时,一个用户能赢得两个物品的最优拍卖。当用户的估值具有相同和对称分布时,Manelli等15用代数程序求解极值点,以确定收益最大化的机制。Pavlov16引入补贴机制提高机制的分配效率,满足用户的需求,进而提高提供商的收益。当用户对物品有连续或独立的附加价值时,Daskalakis等17使用最优传输理论和配对理论实例化物品拍卖框架,推导最优机制的充分必要条件。Tang等18研究了包含一个用户和两个物品的拍卖,当一个物品与另一个物品的估值负相关时,如
16、果支付增加,那么两个物品被同时分配的概率就会增加。当可替代物品的估值服从独立二进制分布,用户的占优策略是诚实报价。Yao19使用贝叶斯方法在物品估值累加的前提下实现收益最大化的拍卖问题。机制设计有许多错综复杂的细节,越来越多的学者致力于将收益最大化的组合拍卖建模成一个优化问题。将机制用一组参数描述,并使用计算机程序自动搜索找到最大化机制收益的参数,减轻机制设计者的负担20。Sandholm等21研究了仿射最大化拍卖(Affine Maximizer Auction,AMA),AMA使用梯度下降算法搜索组合拍卖的参数,容易陷入局部最优解。Guo等22在AMA基础上,考虑时间变化对物品估值的影响,
17、使用线性规划求解收益最大化的机制,此方法不适应于多物品多用户设置下的组合拍卖。Dtting等23将收益最大化的机制设计成带约束的学习问题,从先验分布采样用户估值进行训练,用机器学习方法找到一组近似最优的参数,该机制只达到近似的激励相容。为了解决上述问题,本文考虑了多物品多用户组合拍卖,在保证用户诚实报价和提高提供商收益的同时,设计了一种基于随机游走算法的收益最大化组合拍卖机制,RWSCA能产生良好的收益结果。2 问题描述和模型 本章将具体描述频谱拍卖的问题和模型。频谱拍卖的架构如图1所示。在频谱拍卖中,频谱提供商提供一些待售的频谱以获取利润;用户需要租用频谱来完成通信任务,他们提交报价信息;代
18、理收集提供商和用户信息,根据分配规则将频谱分配给需要的用户,依照支付规则计算出得到频谱的用户支付的金额,将分配和支付结果返还给提供商和用户。2.1问题描述假设频谱提供商可以提供m个正交异质的频谱信道M=1,2,m,并且有n个用户N=1,2,n 参与拍卖。用户i的估值函数为vi=(vi(b1),vi(b2),vi(b2m),i N,最多可以从最大的捆绑包G=b1,b2,b2m中得到一个捆绑包。vi(bj)是用户i对捆绑包bj的估值,且bj G。所有用户的估值用v=(v1,v2,vn)表示。代理根据收集到的信息计算出一组分配结果x=(x1,x2,xn),其中xi=1表示用户i被 分 配 到 捆 绑
19、 包,否 则xi为 0。所 有 用 户 支 付 为p=(p1,p2,pn),用户i的支付是pi,效用函数ui为用户i的估值与支付之差,定义如下:ui=xivi(x)-pi(x)(1)社会福利(Social Welfare,SW)表示所有获得了频谱捆绑包的用户估值之和,定义如下:图1频谱拍卖的架构Fig.1Architecture of spectrum auction2353第 43 卷计算机应用SW=i=1nxivi(x)(2)提供商以社会福利最大化的方式向用户分配频谱,频谱分配问题可以被建模为一个整数规划问题。Maximize SW(3)s.t.i N j S,S Mxi(S)1(4)S
20、Mxi(S)1(5)xi 0,1(6)为 了 找 到 最 大 的 社 会 福 利SW,分 配 结 果 用x=(x1,x2,xn)表示。xi是指用户i的分配结果:当xi=1时,用户i被分配到物品;否则xi为 0。S 表示用户获得的捆绑包。约束(4)表示每个物品最多只能被分给一个用户,约束(5)表示每一个用户至多获得一个捆绑包。由于用户是自私的,可能会谎报价格,提高自身效用。通常使用 VCG 机制支付公式来计算支付,以保证用户诚实报价。假设x*是最优分配,x-i*是指用户i不参加拍卖时的最优分配,那么用户i的实际支付为:pi=j ivj(x-i*)-j ivj(x*)(7)VCG机制具有激励相容性
21、,能保证用户诚实报价,考虑到了分配公平性;但是从频谱提供商的角度看,VCG机制中的提供商的实际收益较低。因此考虑了基于虚拟估值VCG机制,旨在保证机制激励相容的同时,提高提供商的收益。2.2基于虚拟估值的组合拍卖本节引入虚拟估值以提高提供商的收益。假设用户i的估 值 为vi,对 用 户 对 物 品 的 估 值 线 性 映 射,f:vi vi,i N,用户的虚拟估值为 vi=ivi,i表示用户i的估值权重(i R+)。当用户估值集中在高报价区间,能提高弱报价用户的竞争力。此外,对于分配结果x,增加一个保留价(x),表示对物品的某种分配结果,增加一个分配提升值,改 善 提 供 商 的 收 益。假
22、定 所 有 用 户 提 交 估 值v=(v1,v2,vn),基于虚拟估值的组合拍卖通过最大化虚拟社会福利获得分配结果x,虚拟社会福利定义如下:SW,(x)=i=1nivi(x)+(x)(8)用户i的支付是指该用户不参加拍卖时的社会福利,减去参加拍卖时的社会福利,除以自身估值i,该支付能够保证机制的激励相容性,跟 VCG 支付原理相同。它的计算公式如下:pi=1i()j ijvj(x-i)+(x-i)-j ijvj(x)-(x)(9)频谱提供商的收益R定义为所有用户支付和,定义如下:R=i=1npi(10)3 基于随机游走算法的频谱组合拍卖 本章使用随机游走算法搜索虚拟估值组合拍卖的参数。前面引
23、入了虚拟估值的概念,将机制设计的问题转变成在参数空间中搜索的问题。常见的搜索算法有:1)网格搜索算法,该算法仅能搜索 45个参数,应用在两用户两物品组合拍卖中;2)梯度下降算法,该算法的缺点是仅能搜索局部最优参数,应用在n用户m物品组合拍卖中(n,m 2)。针对上述算法存在的问题,RWSCA 机制使用随机游走算法搜索任意人物数的组合拍卖参数,该算法优点如下:1)能够搜索较多数量的参数,可以扩展至多物品多用户的拍卖中;2)随机游走算法随机初始化一些解,根据目标值优化参数,能够跳出局部最优解。下面将描述RWSCA机制的具体流程。3.1RWSCA机制RWSCA 机制由 4 部分组成:基于随机游走的参
24、数搜索(RWSCA Parametric Search,RWSCA-PS)算法、损失函数计算(RWSCA Calculate Loss,RWSCA-CL)算法、机制收益计算(RWSCA Calculate Revenue,RWSCA-CR)算法和社会福利计算(RWSCA Social Welfare,RWSCA-SW)算法。其中,利用RWSCA-PS算法来搜索参数;在搜索过程中调用RWSCA-CL算法对惩罚项进行约束,帮助算法搜索到更好的参数;在获得一组参数之后带入社会福利计算算法RWSCA-SW中计算分配;在支付算法RWSCA-CR中计算该组参数收益,直到搜索到收益最高的一组参数。RWSCA
25、-PS 算法的设计思想是使用随机游走算法搜索一组参数,对用户的估值进行虚拟映射,计算对应的收益,寻找到一组收益最高的参数并返回。输入为拍卖训练集A=(a1,a2,ao),每一个拍卖ai都包含n个用户的估值函数v1,v2,vn,其中i=1,2,。并输入步长,中止阈值,迭 代 次 数K,正 则 化 参 数,输 出 参 数,其 中=()1,2,n,1,2,(n+1)m,根据VCG机制初始化参数。当 3)while k K4)生成向量x=(x1,x2,xn),其中-1 xi 15)归一化x=x i=1nxi6)更新参数=+x7)调用RWSCACL计算训练集在参数和中的收益revenueavg、reve
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 随机 游走 算法 频谱 组合 拍卖 机制
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。