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

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）（通信作者电子邮箱）摘要：如何将频谱有效地分配给用户并提高提供商的收益是目前研究的热点。针对频谱组合拍卖中提供商收益低的问题，结合用户估值分布不对称的特点，设计了基于随机游走的频谱组合拍卖（RWSCA）机制，以最大化频谱提供商的收益。首先引入了虚拟估值的思想，用随机游走算法在参数空间搜索一组最优参数，并根据参数线性映射买家的估值；然后运行基于虚拟估值的VCG（Vickrey-Clarke-Groves）机制，从而确定赢得拍卖的用户并计算相应的支付金额。理论分析证明了所提机制具有激励相容和个体理性的性质。在频谱组合拍卖仿真实验中，相较于VCG机制，RWSCA机制至少提高16.84%以上提供商收益。关键词：组合拍卖；频谱；随机游走算法；参数搜索；虚拟估值中图分类号：TP399 文献标志码：ASpectrum 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 225001，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 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 valuation0 引言 无线电频谱是自然界中的一种电磁波，主要用途是传输通信信号1。国际电信联盟根据频率将电磁波划分为多个频段供各国使用。作为珍贵而稀缺的战略性自然资源，政府有专门的部门来管理和分配频谱。传统的频谱资源的分配是静态的，效率不高，每年都有许多新的无线应用需要使用频谱进行通信。因此，如何设计一种频谱分配方式，在满足用户的需求同时确保频谱提供商获得高收益，这一问题至关重要。组合拍卖以公开竞价的方式将物品捆绑出售，根据分配规则将物品分配给用户，根据支付规则计算用户的支付，提供商可以获得收益。组合拍卖能有效提高频谱利用率，因此在频谱分配中被广泛使用2-4。例如，美国联邦通信委员会（Federal Communications Commission，FCC）采用多轮密封组合拍卖进行分配，提高了频谱的利用率。1981年，新西兰政府通过第一价格密封组合拍卖分配频谱资源，获得了高额收益。2012年，FCC成立了一个专门的组织研究激励拍卖，重新分配频谱来优化资源配置5。很多欧洲国家在拍卖 5G（5th Generation mobile communication technology）频谱，能充分利用有限的频谱资源6-7。频谱组合拍卖主要考虑如何分配频谱给用户，很少考虑到提供商的收益问题。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），女，江苏徐州人，硕士研究生，CCF会员，主要研究方向：机制设计、算法博弈论；李超（1982），男，黑龙江牡丹江人，硕士，主要研究方向：电子对抗；宋衡（1990），男，江苏常州人，博士，CCF会员，主要研究方向：自然语言处理、机制设计；李迪（1982），男，吉林白山人，博士，主要研究方向：无人集群电子对抗；朱俊武（1972），男，江苏江都人，教授，博士，CCF高级会员，主要研究方向：人工智能领域的知识工程及算法博弈论。第 8 期王菁怡等：基于随机游走算法的频谱组合拍卖机制户支付次高价格，提供商的收益还有提高的空间。VCG机制虽然提高了频谱的分配效率，但是设计一个收益最大化的频谱组合拍卖机制仍有一些问题需要解决：一方面拍卖总是以社会福利最大化的方式把物品分配物品，但是提供商的收益往往低于社会福利值，还有提升空间；另一方面，用户是自利的8，他们可能会操纵报价以提高自身的效用，这种操纵增加了机制设计者的负担。Myerson9使用虚拟估值方法解决了单物品收益最大化拍卖，但不能解决多物品多用户的最优拍卖问题。因此，本文设计了一种基于虚拟估值的VCG机制，能够激励用户诚实报价，并且可以用于解决多物品多用户拍卖问题，提高机制中提供商的收益。本文的主要工作归纳为以下3点：1）通过基于虚拟估值的VCG机制，能够提高出价较低用户的竞争力，使得机制能从出价高的用户身上获得更多利润，进而提高机制中提供商收益。2）提出的基于随机游走的频谱组合拍卖（Random Walk for Spectrum Combinatorial Auctions，RWSCA）机制能够保证机制激励相容和个体理性，使得参与拍卖的用户诚实报价，降低机制设计者的负担。3）使用随机游走算法在参数空间中搜索参数，可以从全局角度搜索参数，避免陷入局部最优解。模拟实验证明了该算法能在多物品多用户组合拍卖中提高提供商的收益。1 相关工作 随着无线电技术的发展，频谱在人们的生活中扮演着重要角色，越来越多的用户需要订购频谱信道完成通信任务。有很多专家和学者正在研究频谱拍卖机制的设计问题。Zheng等10为异质频谱设计了一个拍卖框架，并将赢家决策问题建模为一个二进制程序。使用贪婪算法计算社会福利最大化的分配方案，用户可以在这个框架下进行真实的出价。Yi等11把认知型无线频谱分配问题规划为一个背包问题，推导出多项式时间的上界，使用近似算法解决了频谱分配问题。该算法可以保证用户的真实报价，提高频谱分配的效率。Gandhi等12设计了一种频谱竞价语言来满足用户对频谱的实时需求，最大化频谱利用率，并相应地增加供应商的收益。以上工作均考虑到机制的真实性，但未考虑频谱提供商希望尽可能多地将频谱分配出去，以获得高收益的需求。Maskin等13在Myerson单物品最优拍卖基础上，研究了包含多个副本的单物品最优拍卖，提高了提供商的收益。当面对多种物品和不同数量的用户时，设计一个最大化提供商收益的拍卖仍然是一个具有挑战性的问题。Armstrong14研究了当一个物品的估值与另一个物品的估值成正比时，一个用户能赢得两个物品的最优拍卖。当用户的估值具有相同和对称分布时，Manelli等15用代数程序求解极值点，以确定收益最大化的机制。Pavlov16引入补贴机制提高机制的分配效率，满足用户的需求，进而提高提供商的收益。当用户对物品有连续或独立的附加价值时，Daskalakis等17使用最优传输理论和配对理论实例化物品拍卖框架，推导最优机制的充分必要条件。Tang等18研究了包含一个用户和两个物品的拍卖，当一个物品与另一个物品的估值负相关时，如果支付增加，那么两个物品被同时分配的概率就会增加。当可替代物品的估值服从独立二进制分布，用户的占优策略是诚实报价。Yao19使用贝叶斯方法在物品估值累加的前提下实现收益最大化的拍卖问题。机制设计有许多错综复杂的细节，越来越多的学者致力于将收益最大化的组合拍卖建模成一个优化问题。将机制用一组参数描述，并使用计算机程序自动搜索找到最大化机制收益的参数，减轻机制设计者的负担20。Sandholm等21研究了仿射最大化拍卖（Affine Maximizer Auction，AMA），AMA使用梯度下降算法搜索组合拍卖的参数，容易陷入局部最优解。Guo等22在AMA基础上，考虑时间变化对物品估值的影响，使用线性规划求解收益最大化的机制，此方法不适应于多物品多用户设置下的组合拍卖。Dtting等23将收益最大化的机制设计成带约束的学习问题，从先验分布采样用户估值进行训练，用机器学习方法找到一组近似最优的参数，该机制只达到近似的激励相容。为了解决上述问题，本文考虑了多物品多用户组合拍卖，在保证用户诚实报价和提高提供商收益的同时，设计了一种基于随机游走算法的收益最大化组合拍卖机制，RWSCA能产生良好的收益结果。2 问题描述和模型 本章将具体描述频谱拍卖的问题和模型。频谱拍卖的架构如图1所示。在频谱拍卖中，频谱提供商提供一些待售的频谱以获取利润；用户需要租用频谱来完成通信任务，他们提交报价信息；代理收集提供商和用户信息，根据分配规则将频谱分配给需要的用户，依照支付规则计算出得到频谱的用户支付的金额，将分配和支付结果返还给提供商和用户。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被 分 配 到 捆 绑 包，否 则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 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机制具有激励相容性，能保证用户诚实报价，考虑到了分配公平性；但是从频谱提供商的角度看，VCG机制中的提供商的实际收益较低。因此考虑了基于虚拟估值VCG机制，旨在保证机制激励相容的同时，提高提供商的收益。2.2基于虚拟估值的组合拍卖本节引入虚拟估值以提高提供商的收益。假设用户i的估 值 为vi，对 用 户 对 物 品 的 估 值 线 性 映 射，f：vi vi，i N，用户的虚拟估值为 vi=ivi，i表示用户i的估值权重（i R+)。当用户估值集中在高报价区间，能提高弱报价用户的竞争力。此外，对于分配结果x，增加一个保留价(x)，表示对物品的某种分配结果，增加一个分配提升值，改 善 提 供 商 的 收 益。假 定 所 有 用 户 提 交 估 值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 基于随机游走算法的频谱组合拍卖 本章使用随机游走算法搜索虚拟估值组合拍卖的参数。前面引入了虚拟估值的概念，将机制设计的问题转变成在参数空间中搜索的问题。常见的搜索算法有：1）网格搜索算法，该算法仅能搜索 45个参数，应用在两用户两物品组合拍卖中；2）梯度下降算法，该算法的缺点是仅能搜索局部最优参数，应用在n用户m物品组合拍卖中（n，m 2）。针对上述算法存在的问题，RWSCA 机制使用随机游走算法搜索任意人物数的组合拍卖参数，该算法优点如下：1）能够搜索较多数量的参数，可以扩展至多物品多用户的拍卖中；2）随机游走算法随机初始化一些解，根据目标值优化参数，能够跳出局部最优解。下面将描述RWSCA机制的具体流程。3.1RWSCA机制RWSCA 机制由 4 部分组成：基于随机游走的参数搜索（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-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、revenueavg8）if revenueavg rwscai6）vcgcnt=vcgcnt+17）revenue=revenue+vcgi8）else9）revenue=revenue+rwscai10）penalty=vcgcnt o*11）revenueavg=revenue o-penalty12）return revenueavgRWSCA-CR 算法调用 RWSCA-SW 算法得到分配结果，计 算 在 给 定 参 数 的 下 机 制 收 益。输 入 用 户 估 值v=(v1，v2，vn)，参数，输出收益revenuemax。第2）行计算全部人员参加情况下的社会最大福利与分配结果。第 3）6）行首先根据上面的分配，分别计算赢者不参加情况下的社会最大福利，并根据式（8）计算获胜用户的支付，对其支付求和后返回revenuemax。RWSCA-CR算法伪代码如算法3所示。算法3 RWSCA-CR算法。输入 估值向量v=(v1，v2，vn)，参数；输出 revenuemax。1）初始化revenuemax=02）SW，a=RWSCASW（v，）3）for i in winner_users4）SW-i，a-i=RWSCASW(v-i，-i)5）pi=SW-i-SW+ivii6）revenuemax=revenuemax+pi7）return revenuemaxRWSCA-SW算法虚拟映射用户估值，根据式（9）计算最大化虚拟社会福利，获得分配结果。输入用户估值函数v=(v1，v2，vn)，参数，输出最大社会福利SW和分配结果a。其中(x)是关于分配的函数，长度为(n+1)m，表示全部的分配方式，可视为一个进制为n+1，长度为m的数，代表着m个物品的分配结果。伪代码遍历全部可能的分配方式，记录并返回最大的社会福利值与分配结果。RWSCA-SW算法伪代码如算法4所示。算法4 RWSCA-SW算法。输入 估值向量v=(v1，v2，vn)，参数；输出 SW，a。1）for i=1 to(n+1)m2）根据(i)计算利用虚拟映射后的SWcur3）if SWcur SW4）SW=SWcur，a=(i)5）return SW，a3.2RWSCA机制性质分析与证明文献 8 中给出了机制激励相容的充分必要条件：机制的分配规则是单调的，支付规则基于临界值。为了证明RWSCA是激励相容的，须先证明引理1和引理2。假设用户i的估值为vi，获得的捆绑包为B（B M），此用户i的虚拟估值是 vi=ivi，i 0。引理1 RWSCA的分配规则是单调的。证明 考虑用户i对捆绑包B的估值变化对效用的影响，来证明RWSCA机制的分配规则是单调的。1）如果用户i对捆绑包B有更高的估值vi，会产生更高的虚拟估值 vi=ivi，d vi/vi=i是单递增函数，当vivi时，vi vi。在需要的物品数相同时，用户给出更高的估值，会有更高的虚拟估值。RWSCA根据虚拟估值的高低分配物品，那么用户i在分配顺序中保持不变或者上升到更高的位置，被分配到捆绑包B的可能性更大。因此，当用户i需要的物品不变时，却给出了更高的估值，分配不会改变。2）如果用户i需要的物品集合S（S B），S是B的真子集。当用户i的估值为vi，将获得捆绑包B。当他以同样的估值却需要更少的物品时，那么他将变得更有竞争力，会获得捆绑包S。3）用户i的估值由vi变成vi（vi vi），对物品的需求由捆绑包B变成捆绑包S（S B）。简单来说，用户i以更高的估值来获取更少的物品，那么分配结果不会改变，他仍然会获胜。在3种情况下，分配给用户i的物品不会改变，他仍然属于获胜用户。这意味着RWSCA的分配规则是单调的。引理2 RWSCA的支付算法是基于临界值的。证明 假 设vN(j)是 最 高 估 值 的 物 品j，其 中j M，vN(j)=maxi Nvi(j)。分配x通过vN(j)这种方式将物品分给用户；vN i(j)是除了用户i之外其他人对物品j的最高估值，vN i(j)=maxi N ivi(j)，分配x-i通过vN i(j)这种方式将物品分给用户。通过式（8）得到用户i的支付为：pi=SW(x-i)-SW(x)+vi(B)（11）SW(x-i)=j M-BvN i(j)+j BvN i(j)（12）SW(x)=j M-BvN(j)+j BvN(j)=j M-BvN i(j)+j BvN(j)（13）vi(B)=j BvN(j)（14）将式（11）（14）代入式（8）可以将用户支付改写为：pi=j BvN i(j)（15）用户i的支付是他不参加拍卖时，参与拍卖的其他用户对捆绑包B中物品的最高估值总和。当用户估值小于这个值，他将输掉拍卖，无法得到物品；否则，他会获胜。因此RWSCA的支付是基于临界值的。2355第 43 卷计算机应用定理1 RWSCA是激励相容的。由引理 1 可以得到 RWSCA 的分配规则是单调的，由引理2可以得到RWSCA的支付是基于临界值的，因此RWSCA是激励相容的。定理2 RWSCA是个体理性的。证明 由假设可知，用户i在拍卖中获得了捆绑包B，用户i对捆绑包B的估值vi(B)=j BvN i(j)，vi(B)是捆绑包B中每个物品j（j B）最大估值之和。当用户i不参与拍卖时，会有其他用户获得捆绑包B中的物品，此时捆绑包B的估值为：vN i(B)=j BvN i(j)=pij BvN(j)用户i的效用是非负的，因此可以证明RWSCA机制是个体理性的。4 实验与结果分析 4.1实验环境本章对基于随机游走算法的频谱组合拍卖进行了模拟实验。首先进行了包含两个用户和两个频谱信道的拍卖实验，研究了不同参数设置下的各个机制收益。随后在多物品多用户场景下，测试了该算法的扩展性能。本实验的机器配置为处理器Intel（R）Core（TM）i7-10510U，内存16 GB，操作系统为Windows 10，使用Python语言编码。4.2实验结果及分析1）两用户两物品：假设一个拍卖含有两个用户和两个待售的频谱信道。用户 1 对物品 1 的估值由从均匀分布f1得到，用户1对物品2的估值由从均匀分布f2得到。用户i对两个物品的估值为vi(1，2)=vi(1)+vi(2)+。可表示用户对捆绑包物品的可替代性。估值对称分布是指所有用户的先估值分布是相等的，即fi=fj(i，j N)。估值非对称分布则指用户先验估值分布不相等，fi fj。表 1 为本实验的参数设置，从先验分布中生成估值数据，在以下三种设置中测试了机制的收益。数据集由先验分布产生，训练集包含400组数据，测试集包含25 000组数据。对随机游走算法进行正则化约束，其中 RWSCA-1、RWSCA-2、RWSCA-3对应的正则化参数分别为0.4、0.6、0.8。表 1描述了实验的三种参数设置，表 1的第 24列表示了不同用户估值分布的参数设置。表 2描述了在不同参数设置下各个机制的收益以及相对 VGG 机制的收益提升百分比，相较于 VCG 机制，RWSCA机制至少提高 16.84%以上提供商收益。可以看出 AMA、RWSCA-1、RWSCA-2、RWSCA-3 收 益 高 于 VCG，其 中RWSCA-1、RWSCA-2、RWSCA-3收益均高于 AMA，RWSCA-1收益最高。当随机游走算法正则化参数为0.4时，RWSCA机制产生的收益最高。在设置三中，收益提升最多，说明在两个物品估值分布不对称即f1 f2时，虚拟估值方法能有效改善机制收益。2）多用户两物品：将物品数量固定为2，将用户数量从1增加 5，本实验测试用户数量增加时机制的收益性能。图 2描述了用户估值对称和估值不对称分布时不同机制的收益，结果显示RWSCA-1、RWSCA-2、RWSCA-3的机制收益均高于VCG，虚拟估值能够有效提高机制收益。其中，RWSCA-1收益最高，证明了参数选择影响机制收益，当正则化参数为0.4时，RWSCA机制产生的收益最高。3）两用户多物品：将用户数固定为2，将物品数从1增加到5，本实验测试物品数量增加时机制的收益性能。图3描述了用户估值对称和估值不对称分布时不同机制的收益结果，结果显示 RWSCA-1、RWSCA-2、RWSCA-3的机制收益均高 于 VCG，虚 拟 估 值 能 够 有 效 提 高 机 制 收 益。其 中，RWSCA-1收益最高，正则化参数为0.4时，机制收益最高，随机游走的参数影响机制收益。5 结语 在频谱拍卖市场中，设计一个使得频谱提供商收益最大化的拍卖是具有挑战的问题。受到Myerson单物品最优拍卖表1不同用户估值分布的参数设置Tab.1Parameter settings for different user valuation distributions参数f1f2设置一0，10，10设置二1，21，2-1，1设置三1，21，5-1，1表2不同参数设置下的机制收益Tab.2Mechanism revenue with different parameter setting机制VCGAMARWSCA-1RWSCA-2RWSCA-3设置一收益0.6670.8040.8160.8140.806提升/%20.5422.3422.0420.84设置二收益2.4052.8102.8592.8442.829提升/%16.8418.8818.2517.63设置三收益2.8474.3934.4514.4344.415提升/%54.3056.3455.7455.08图2用户数增加时的收益Fig.2Revenue with increasing number of users图3物品数增加时的收益Fig.3Revenue with increasing number of items2356第 8 期王菁怡等：基于随机游走算法的频谱组合拍卖机制的启发，线性映射用户对物品的估值。将机制设计的问题转化成在参数空间中搜索的问题。本文使用一个简单的全局搜索方法：随机游走算法，搜索到一组参数实现提供商收益最大化问题。本文在不同参数设置的情况下，模拟了收益情况。实验结果证明RWSCA机制产生的收益高于VCG机制，能够扩展到更大规模的问题中，在收益上具有较好的性能。本文从先验分布中采样用户的估值，样本的选取会影响算法的结果，如何选择合适的样本来进行训练是接下来要研究的内容之一。使用机器学习算法设计自动化机制能够降低机制设计者的负担，但是参数和模型的选择极大程度上影响了算法的结果。未来考虑使用更精巧的机器学习算法例如神经网络来自动地解决机制设计中的问题。参考文献（References）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.2 梁应敞，谭俊杰，NIYATO D.智能无线通信技术研究概况 J.通信学报，2020，41（7）：1-17.（LIANG Y C，TAN J J，NIYATO D.Overview on intelligent wireless communication technology J.Journal on Communications，2020，41（7）：1-17.）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 networkJ.Journal on Communications，2021，42（12）：182-191.）4 毛莺池，郝帅，平萍，等.基于组合双向拍卖的云资源调度方法J.计算机应用，2019，39（1）：1-7.（MAO Y C，HAO S，PING P，et al.Cloud resource scheduling method based on combinatorial double auctionJ.Journal of Computer Applications，2019，39（1）：1-7.）5 FOX J T，BAJARI P.Measuring the efficiency of an FCC spectrum auction J.American Economic Journal：Microeconomics，2013，5（1）：100-146.6 MARTNEZ-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.7 张朝辉，李靖，韩璐珩.基于数据-地理位置联合驱动的5G微基站最优分配策略 J.计算机学报，2022，45（5）：1087-1099.（ZHANG Z H，LI J，HAN L H.Data-location-joint-driven optimal allocation strategy for micro base stations in 5G networksJ.Chinese Journal of Computers，2022，45（5）：1087-1099.）8 ROUGHGARDEN T.Algorithmic game theoryJ.Communications of the ACM，2010，53（7）：78-86.9 MYERSON R B.Optimal auction designJ.Mathematics of Operations Research，1981，6（1）：58-73.10 ZHENG Z Z，WU F，CHEN G H.A strategy-proof combinatorial heterogeneous channel auction framework in noncooperative wireless networksJ.IEEE Transactions on Mobile Computing，2015，14（6）：1123-1137.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.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.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.14 ARMSTRONG M.Multiproduct nonlinear pricing J.Econometrica，1996，64（1）：51-75.15 MANELLI A M，VINCENT D R.Multidimensional mechanism design：revenue maximization and the multiple-good monopolyJ.Journal of Economic Theory，2007，137（1）：153-185.16 PAVLOV G.Optimal mechanism for selling two goods J.The B.E.Journal of Theoretical Economics，2011，11（1）：No.3.17 DASKALAKIS C，DECKELBAUM A，TZAMOS C.Mechanism design via optimal transportC/Proceedings of the 14th ACM Conference on Electronic Commerce.New York：ACM，2013：269-286.18 TANG P Z，WANG Z H.Optimal mechanisms with simple menusJ.Journal of Mathematical Economics，2017，69：54-70.19 YAO A C C.Dominant-strategy versus Bayesian multi-item auctions：maximum revenue determination and comparisonC/Proceedings of the 2017 AC