端到端服务拍卖：一种面向边缘计算服务的通用双重拍卖机制

End-to-End Service Auction: A General Double  Auction Mechanism for Edge Computing Services

Abstract

无处不在的强大个人计算设施，例如台式计算机和停放的自动驾驶汽车，可以通过利用其闲置资源充当微型边缘计算服务器。然而，为了将这些资源用于服务提供，将面临两个重要挑战：如何激励服务器所有者贡献其计算资源，以及如何为服务购买者保障端到端（E2E）服务质量（QoS）？在本文中，我们通过提出COMSA，以整体化的方式解决了这两个问题。与现有主要关注计算资源交易的边缘计算双边拍卖机制不同，COMSA同时考虑了频谱分配和数据路由问题，从而在设计双边拍卖机制的同时解决网络资源分配问题，进而为边缘计算服务提供端到端QoS保障。为应对设计复杂性，COMSA采用两步法将网络优化与机制设计解耦，因此可推广应用于一般的边缘计算网络优化问题。COMSA具备若干关键的经济特性，即真实性、预算平衡性和个体理性。我们的大量仿真研究证明了COMSA的有效性。  
关键词— 边缘计算，双边拍卖，频谱分配，服务提供。

总结来说就是通过提出COMSA（一种同时考虑频谱分配和数据路由问题的双端拍卖方式）来解决拍卖的一般问题：边缘计算资源的激励贡献与资源的服务质量QoS的均衡。

方法是：两步法解耦网络优化与机制设计，将网络优化变为一般边缘网络优化问题解决（简化难度）。

最终是保证了真实性、预算平衡和个体理性（系统效能差（因为此前证明拍卖只能保证真实性or系统效能））

INTRODUCTION

        物联网（IoT）和各类移动设备的迅速普及催生了一系列广泛的应用，例如视频分析、环境监测、虚拟/增强现实以及在线游戏[1]。这些新兴服务对数据分析和智能提取的需求急剧增长。为了满足这些服务需求，多接入边缘计算（MEC）应运而生，旨在终端设备附近提供强大的计算能力[1]，[2]。得益于数据源与服务器之间的短距离优势，MEC能够以低延迟和高吞吐量支持各种数据分析应用。

        与此同时，用户需求的持续增长也促使网络边缘需要密集部署功能强大的边缘服务器[3]，尤其是在人口密集区域。然而，由于部署成本高昂，至少在短期内实现边缘服务器的普遍部署并不现实。另一方面，我们注意到，许多私人拥有的设施，如个人电脑和自动驾驶汽车[4]–[6]，正逐渐配备性能显著提升的计算能力。为了解决上述困境，一个直观且颇具前景的解决方案是在这些个人设备空闲时，例如自动驾驶汽车停泊期间，充分利用其丰富的闲置计算资源，从而增强现有的计算基础设施，以更好地支持服务提供。

        尽管将这些个人设施用作边缘服务器极具吸引力，但在将其付诸实践之前，仍需解决两个基本问题：如何激励服务器所有者贡献其计算资源，以及如何确保服务订阅者获得高质量的端到端（E2E）服务？针对第一个问题，拍卖机制是一个天然的选择，因为它能够高效地撮合供需双方，而无需事先了解各参与方的估值信息[7]。第二个问题则源于MEC服务的提供需要对通信资源和计算资源进行合理管理。以视频分析为例，在边缘服务器上进行实时视频处理不仅需要强大的计算能力，还需要从终端设备到边缘服务器之间具备高带宽的视频传输通道。因此，基础设施不仅应合理分配所采集的计算资源，还应合理分配有限的网络资源，例如频谱资源，以支持具有端到端QoS保障的MEC服务。尽管先前的一些研究已尝试设计用于MEC的双重拍卖机制[8]，[9]，但这些研究大多侧重于计算资源的交易方面，而隐含地假设通信资源是充足的。正因如此，在实际网络中，拍卖机制可能无法满足中标服务请求的端到端QoS需求，导致服务购买者即使并未真正从交易中获益，也可能因网络拥塞而被收取费用。

        受到上述观察的启发，我们为MEC提出了计算服务拍卖（COMSA）。具体而言，我们研究了MEC系统中双重拍卖与端到端服务提供相结合的问题，其中由中央控制器（称为计算服务提供商，CSP）不仅通过拍卖机制获取可用的计算资源，还确保中标买方与卖方之间必要的端到端数据传输。在实际应用中，CSP可以作为移动网络运营商的一部分，该运营商拥有基础设施和频谱资源，但缺乏计算资源，因此通过建立双重拍卖机制来激励计算服务器所有者参与贡献。名称“端到端服务拍卖”表明我们的拍卖机制是“以服务为导向”的，即将端到端边缘计算服务视为商品，通过联合分配网络和计算资源给中标买方，以满足其端到端QoS需求。相比之下，现有的针对MEC的双重拍卖机制大多侧重于计算方面。特别是，虽然频谱分配和数据路由是保障边缘计算服务端到端QoS的基础，但在现有的MEC双重拍卖机制中尚未予以考虑。有关端到端服务拍卖的高层次思想及更广泛的应用，请参阅我们的教程论文[10]以获取详细信息。

        本文的主要贡献总结如下。

  • 为了向服务购买者提供端到端的QoS保障，我们提出了首个面向服务的真实型双层拍卖机制，该机制特别考虑了网络优化问题，尤其是频谱分配与数据路由。为应对设计复杂性，我们提出了一种两步法，将网络优化与机制设计解耦，这种方法可推广应用于MEC的一般网络优化问题。
  • 在我们的框架中，允许每个购买者发起多个请求，同时每个卖家也可服务于多个请求。我们提出了一种新颖的配对划分方法，以解决真实型拍卖机制的设计问题。此外，允许每个购买者发起多个服务请求，也使COMSA有别于现有的针对MEC的真实型双层拍卖方案。
  • 我们提出的机制被证明具有真实性、个体理性以及预算平衡特性。大量仿真实验表明，我们的方案能够在保证真实性的同时，不会导致显著的性能下降。

总结一下：
背景：物联网发展引发了数据分析和智能提取的促进增长。MEC由于低延迟和高吞吐的特性成为解决问题的关键。但是随处安放边缘设备是不现实的，而且很多移动设备的算力被浪费，所以想法是获取利用这些闲置的算力资源。这个想法有两个问题：

  • 如何激励设备去贡献算力
  • 如何保证得到的算力有高质量保障（QoS）

解决方法：

  • 拍卖
  • 同时考虑算力与通信资源

困难：先前的拍卖只是考虑了算力没有考虑到通信

想法实现：建立COMSA拍卖机制：中心控制者（CSP）不仅通过拍卖可以得到算力资源同时确保必要的端到端数据传输

II. RELATED WORK

关于移动边缘计算（MEC）中的资源分配与计算卸载问题，早期的大多数研究主要针对单个服务器与单个或多个用户的情况[11]–[13]。鉴于边缘服务器容量有限且部署密集，近期的一些研究进一步考虑了在多个地理分布的边缘服务器之间进行资源调配的问题[3]，[14]–[16]。在文献[3]中，Ding等人研究了无线网状网络中MEC服务的部署问题，同时考虑了频谱分配与数据路由，其中配备认知无线电的中继节点负责将数据源的输入数据传输至指定的边缘服务器。为了激励计算服务器的所有者并为最终用户提供服务，双重拍卖是一种有效的机制，能够自然地适应这种双边市场。我们的双重拍卖机制向最终用户交易的是“端到端服务”，而非单纯的计算资源，因此需要对计算资源与网络资源（如频谱资源）进行联合管理。本质上，我们的双重拍卖机制是在买家与卖家之间交易异构物品（即服务请求），同时受到网络约束，即能够相互交易的买家与卖家集合受到限制。这一特点源于这样一个事实：在资源受限的无线网络中，中标的服务请求必须同时满足端到端服务质量（E2E QoS）约束条件。

在经济学文献中，McAfee在其开创性工作中提出了一个诚实且预算平衡的双重拍卖机制，该机制允许买家与卖家交换同质化物品[17]。此后，又有一些关于具有单一或多类商品的多单位诚实双重拍卖的研究工作相继出现[18]–[21]。然而，上述研究并未对交易施加任何约束条件。在文献[22]中，Dütting等人提出了一种模块化的设计方法，用于构建在交易约束下具有社会福利近似保证的双重拍卖方案。然而，他们的方案仅考虑同质化物品，同样无法直接应用于我们的场景。

当将双重拍卖应用于无线网络时，固有的无线干扰约束会限制能够相互交易的买家与卖家集合。基于这一思路，针对动态频谱交易[23]–[25]以及协作通信或设备到设备通信[26]，[27]，已有研究探讨了异构物品的双重拍卖机制。这类机制通常包含两个步骤：一个独立于出价的分配过程，以及一个中标者确定与定价过程。受这一研究方向的启发，我们的COMSA机制也采用了类似的两步流程，但在两个步骤中均进行了变体设计。在第一步中，COMSA涉及求解一个网络资源优化问题（例如，联合频谱分配与请求路由问题），这与现有拍卖方案仅关注买家与卖家匹配的做法有所不同。在第二步中，COMSA采用了一种新颖的配对划分策略，以应对多对多的买家与卖家匹配问题。实际上，通过对现有协作通信双重拍卖方案进行简单修改，可以将其应用于我们的场景[26]。然而，遗憾的是，该方案仅适用于一对一的买家与卖家匹配，可能导致边缘服务器资源的利用率不足。

在云/边缘计算的背景下，一些单边拍卖机制已被提出[28]–[31]，这些机制仅考虑来自服务购买者的出价或来自服务器所有者的要价。遗憾的是，前一种情况未考虑服务器所有者的激励问题，而后一种情况下则不清楚如何合理地向购买者收费，甚至难以确定服务购买者的身份及其所在位置。与我们的工作类似，一些诚实的双重拍卖机制也被提出用于激励单个云/边缘服务器[8]，[9]，[32]–[34]。然而，上述研究在机制设计中并未考虑网络资源分配问题，特别是频谱分配与数据路由问题。

唯一的例外是最近一项针对MEC系统双拍卖机制设计的研究工作，该研究考虑了频谱分配问题[35]。然而，在他们的方案中，假设每个边缘服务器都拥有独立的频谱资源，这导致边缘服务器之间无法实现频谱复用，对于密集无线网络而言可能并不现实。此外，该研究也未涉及数据路由问题。考虑到双拍卖市场中存在多个服务器（即卖方），合理的频谱分配（复用）对于缓解信号干扰和提高资源利用率至关重要；同时，若考虑多跳网络，明智的数据路由对于流量均衡以及端到端QoS保障也必不可少。

总结一下

第二章主要是对现有移动边缘计算（MEC）中的资源分配与计算卸载问题研究的总结。本质上，我们的双重拍卖机制是在买家与卖家之间交易异构物品（即服务请求），同时受到网络约束。

  • 现有的双重拍卖的机制如MCAfee要么没有考虑到约束要么是交易的同质化物品。
  • 单边拍卖机制仅考虑来自服务购买者的出价或来自服务器所有者的要价。前一种情况未考虑服务器所有者的激励问题，而后一种情况下则不清楚如何合理地向购买者收费，甚至难以确定服务购买者的身份及其所在位置。而一些带有激励的单边拍卖没有考虑到路由分配和频谱分配

异构物品的双重拍卖机制通常包含两个步骤：一个独立于出价的分配过程，以及一个中标者确定与定价过程。

我们的COMSA机制也采用了类似的两步流程，但在两个步骤中均进行了变体设计。在第一步中，COMSA涉及求解一个网络资源优化问题（例如，联合频谱分配与请求路由问题），这与现有拍卖方案仅关注买家与卖家匹配的做法有所不同。在第二步中，COMSA采用了一种新颖的配对划分策略，以应对多对多的买家与卖家匹配问题。

三、系统模型

A. 网络架构

 

图1. COMSA 的一个示例范式。

如图1所示，我们的系统包含三方：

  • 计算服务提供商（CSP）通过利用来自卖方的计算资源，为服务购买者提供边缘计算服务。

        CSP拥有部分必要的基础设施和无线资源，例如（小型）基站、中继器以及频谱带宽，以支持数据源与边缘服务器之间的数据传输。

服务卖方即服务器所有者。

我们假设每个卖方拥有一台服务器，该服务器可根据其资源可用性同时托管多个计算服务。卖方的服务器状态用元组 描述，其中 \Theta_j表示可用的计算能力，\Phi_j表示可用的内存空间。

  • 服务购买者则是向CSP发送计算服务请求的用户。

        每个服务请求的输入数据假定由一个源节点生成，并需要被传输至边缘服务器进行处理或计算。我们假设每个购买者 i \in I 发起  K_i \geq 1个服务请求，这意味着它拥有  K_i个源节点。购买者 i 第 k个服务请求的QoS需求集用元组S_{i,k} = \{r_{i,k}, \theta_{i,k}, \varphi_{i,k}\} 描述，其中  r_{i,k} , \theta_{i,k} ,和 \varphi_{i,k} 分别表示端到端数据速率需求（单位：bps）、计算需求（单位：Hz）以及内存需求（单位：字节）。值得注意的是，带有QoS需求 S_{i,k} 的服务请求正是我们方案中所交易的商品。

        例如，假设一台监控摄像头以1280×720分辨率和30帧/秒的帧率持续生成视频流，且需要在边缘进行处理。这一请求可以自然地映射为一组QoS需求。当采用H.264进行视频压缩时，该请求要求端到端数据速率为2Mbps [36]。假设每个像素的RGB颜色值占用24位，若所采用的算法每处理一位需要5个CPU周期，则所需的处理能力为3.3GHz。此外，假设该请求需要1GB内存。综上所述，对应的QoS需求为 r_{i,k} = 2Mbps,\theta_{i,k} = 3.3GHz,\varphi_{i,k} = 1GB

B. 双重拍卖模型

        接下来，我们从经济学的角度对图1中的系统进行说明。

        我们将服务购买者与服务卖方之间的交互建模为一轮密封投标的双重拍卖，其中CSP充当拍卖师。在本文中，我们也将购买者和卖方统称为代理。CSP在每个周期开始时执行拍卖和网络优化，而我们只需关注其中一个周期即可。在所考虑的周期内，计算服务请求和服务卖方的计算服务器均处于活跃状态。

设  V_i = \{v_{i,1}, v_{i,2}, \dots, v_{i,K_i}\} 为购买者  i  的真实估值向量，其中 v_{i,k}表示购买者  i  对其第 k个服务请求的真实估值，它描述了购买者愿意为该请求支付的最高价格。需要注意的是，购买者对不同的边缘服务器并无偏好，因为它只关心其请求的QoS需求是否能够得到满足。

类似地，设  C_j = \{c_{1,j,1}, c_{1,j,2}, \dots, c_{|I|,j,K_i}\} 为卖方  j的真实成本向量，其中 c_{i,j,k}表示卖方j为购买者 i的第 k个服务请求提供服务的真实成本。

对于卖方j 而言，其真实成本取决于其服务器上的资源消耗情况。由于不同服务请求可能需要不同数量的资源，因此卖方针对这些请求可能具有不同的真实成本。

        在拍卖开始时，购买者i向CSP提交一个出价向量  B_i = \{b_{i,1}, b_{i,2}, \dots, b_{i,K_i}\} ，其中 b_{i,k}表示购买者 i对其第k个服务请求的出价。由于V_i为购买者i所私有，因此B_i可能不等于V_i。购买者 i  的效用为其赢得的服务的总估值减去其总支付：

 U_b^i = \sum_{1 \leq k \leq K_i} y_b^{i,k}(v_{i,k} - b_{i,k}), \quad \forall i \in I,\left ( 1 \right )

其中  y_b^{i,k} = 1表示购买者 i赢得了其第k个服务请求，否则  y_b^{i,k} = 0；b_{i,k}是购买者i在第 k个请求上的清算价格，将由我们的定价策略决定。此外，我们用 U_b^{i,k} = y_b^{i,k}(v_{i,k} - b_{i,k}) 表示购买者i  从其第k个请求中获得的效用。

        类似地，卖方j向 CSP 提供一个报价向量A_j = \{a_{1,j,1}, a_{1,j,2}, \dots, a_{|I|,j,K_i}\}，其中a_{i,j,k}表示其对买方i第k个服务请求的报价。同样，A_j可能不等于C_j，因为  C_j 是卖方  j  私有的信息。卖方 j  的效用等于其赢得（提供）服务所获得的总奖励减去其总成本：

\U_s^j = \sum_{i \in I} \sum_{1 \leq k \leq K_i} y_s^{i,j,k} (a_{i,j,k} - c_{i,j,k}), \quad \forall j \in J, \quad (2)

其中，y_s^{i,j,k} = 1表示卖方j赢得了买方i的第k个请求，否则 y_s^{i,j,k} = 0 ； y_s^{i,j,k} = 0是针对买方i  第k个请求，卖方 j的清算价格。此外，我们用 U_s^{i,j,k} = y_s^{i,j,k} (a_{i,j,k} - c_{i,j,k})来表示卖方  j  从买方i的第  k个请求中获得的效用。

        给定所有买方i \in I的出价向量 B_i、所有卖方  j \in J 的报价向量  A_j以及网络条件，CSP 应分配网络资源，做出服务分配决策（即选择中标出价和报价），并确定双方的清算价格。CSP（拍卖主持者）的效用等于其向买方收取的服务总费用减去支付给卖方的总支出：

U_A = \sum_{i \in I} \sum_{1 \leq k \leq K_i} y_b^{i,k} b_{i,k} - \sum_{i \in I} \sum_{1 \leq k \leq K_i} \sum_{j \in J} y_s^{i,j,k} a_{i,j,k}. \quad (3)

        在我们的系统中，拍卖机制旨在（近似地）最大化系统效率，该效率定义为本文中接受服务的加权总和（详见第四节）。我们假设 CSP 是可信的，即忠实执行拍卖机制，因此它不会试图最大化式 (3) 中的U_A，而仅确保 U_A \geq 0以避免出现赤字 [23]、[25]、[26]。这是一个合理的假设，因为 CSP 作为无线服务提供商，有动机维护其声誉和服务接受率。

为方便读者理解，本文中频繁使用的符号总结于表 I。

C. 理想的经济特性

与文献 [23]、[25]、[26] 中一致，我们的双边拍卖机制应满足以下经济特性：

  • • 预算平衡：如果从买方收取的付款不低于支付给卖方的付款，则双边拍卖是预算平衡的，即  U_A \geq 0 。
  • • 个体理性：如果每个中标出价的买方支付的价格不超过其出价，且每个中标报价的卖方获得的报酬不低于其报价，即U_A \geq 0且  a_{i,j,k} \geq a_{i,j,k}，则双边拍卖是个体理性的。
  • • 真实性：在双边拍卖中，真实性意味着任何买方或卖方都无法通过申报偏离其真实估值或成本的出价/报价来提高自身效用。换句话说，对于买方  i  而言，最优策略是出价 B_i = V_i，而对于卖方 j而言，最优策略是报价A_j = C_j，无论其他参与方如何出价或报价。

预算平衡、个体理性与真实性是双边拍卖机制的三个关键经济特性。

预算平衡保证了拍卖主持者不会出现赤字。

个体理性鼓励服务购买者发起服务请求，并激励卖方贡献其资源。

真实性消除了参与方为策略性博弈而产生的高昂开销。从参与方的角度来看，这种成本纯粹是一种浪费，会降低其效用。从系统角度来看，复杂的策略博弈以及对市场操纵的担忧可能会使许多资源较弱的用户不愿参与，从而导致非常糟糕的拍卖结果。这一点在无线网络环境中尤为明显，因为终端用户通常希望从操作简单、用户友好的平台上获取服务。此外，由于买方没有动机报低于其真实估值的价格，而卖方也没有动机报高于其真实成本的价格，真实性有可能在满足预算平衡要求的前提下增加交易数量。鉴于这三项经济特性的重要性，我们首先致力于实现它们，同时近似地最大化系统效率，这也是双边拍卖中广泛采用的设计目标 [23]、[25]、[26]。

总结一下：

整个的网络架构系统就是三个方面：

  • 计算服务提供商（CSP）也就是拍卖师
  • 卖方（服务器提供者）也就是seller
  • 购买者（向CSP发送计算服务请求的用户）也就是buyer

在这一章中主要是笼统的介绍了一下博弈论的三要素，买房、卖方的出价、报价以及各自的效用。最后说明这个双重拍卖满足预算平衡、个体理性、真实性（无法最大化系统效率）

IV. GENERAL SERVICE PROVISIONING PROBLEM四、通用服务提供问题

        设计COMSA的主要挑战在于，诚实的双边拍卖机制设计，即中标者确定与定价问题，本质上与网络优化问题紧密耦合。对于单边拍卖模型，可以借鉴广为人知的（VCG）机制来解决此类联合问题，如文献[37]中所采用的方法。然而，遗憾的是，基于VCG的双边拍卖机制会破坏预算平衡。为了使所考虑的问题易于处理，我们设计了一种两步程序：首先从一个与投标价格和要价无关的服务提供（ISP）问题中获得“候选”服务分配结果，该问题不考虑买方和卖方的报价；然后对这些候选服务进行中标者确定和定价，以实现理想的经济特性。+

        ISP问题避免了价格的出现，从而使得买卖双方无法通过市场操纵影响其解。为了提高可解释性，本节首先给出ISP问题的一般形式化描述，然后在下一节深入探讨拍卖机制的设计。

        我们考虑如图1所示的一个抽象通信网络，其中源节点集合和服务器（目的节点）集合N_d处于固定位置。CSP利用一组中继节点N_r以及一组频段（例如蜂窝频段）来促进这两侧之间的数据传输。我们用L表示网络中的传输链路集合，其中有线链路(m, n) \in L仅当节点m与节点n之间存在直接的有线连接时才存在；而无线链路(m, n) \in L仅当发射端m使用最大发射功率时，在接收端n处接收到的功率大于某个阈值时才存在。

        形式上，该网络可以用一个有向图G = (N, L)表示，其中N是网络中所有节点的集合。我们定义一个大小为|N| \times |L|的关联矩阵A，其元素a_{m,l}满足：若节点m是链路l的发射端，则a_{m,l} = 1；若节点m是链路l的接收端，则a_{m,l} = -1；否则，a_{m,l} = 0。

        我们用s_{i,k}表示一个向量，其中第m个分量s_{i,m,k} = 1当且仅当节点m是用户i第k个请求的源节点，否则s_{i,m,k} = 0；用h_j表示一个向量，其中第m个分量h_{j,m} = 1当且仅当节点m是卖家j的服务器，否则h_{j,m} = 0。

        我们考虑以下决策变量：令d_{i,k}^j \in \{0, 1\}为服务分配变量，仅当买家i的第k项服务被分配给卖家j时，d_{i,k}^j = 1。

        此外，我们用流量分配向量f_{i,k} = [f_{i,k}^1, \dots, f_{i,k}^{|L|}]表示用户i第k个请求在链路l上的流速，这是一个非负向量。另外，我们用x表示网络资源分配变量的集合，例如发射功率分配和/或频谱分配变量。

我们将一般的ISP问题表述如下：

P1: \max_{d,x,f} \sum_{i \in I} \sum_{1 \leq k \leq K_i} \sum_{j \in J} M_{i,k} d_{i,k}^j,

约束条件为：

\sum_{j \in J} d_{i,k}^j \leq 1,\quad \forall i \in I, 1 \leq k \leq K_i, {(4)}

A f_{i,k}^T = \sum_{j \in J} d_{i,k}^j r_{i,k} (s_{i,k} - h_j)^T, \quad \forall i \in I, 1 \leq k \leq K_i, (5)\sum_{i \in I} \sum_{1 \leq k \leq K_i} f_{i,k}^l \leq C_l(x), \quad \forall l \in L, (6)\\ \sum_{i \in I} \sum_{1 \leq k \leq K_i} d_{i,k}^j \theta_{i,k} \leq \Theta_j, \quad \forall j \in J, ({7})\\ \sum_{i \in I} \sum_{1 \leq k \leq K_i} d_{i,k}^j \phi_{i,k} \leq \Phi_j, \quad \forall j \in J, ({8})\\ f_{i,k}^l \geq 0, \quad \forall i \in I, 1 \leq k \leq K_i, l \in L, ({9})\\ d_{i,k}^j \in \{0, 1\}, \quad \forall i \in I, 1 \leq k \leq K_i, j \in J, ({10})

Constraints \quad on \quad x \quad(11)

其中，d和f分别表示变量d_{i,k}^j和f_{i,k}^l的集合，而M_{i,k}是每项服务的加权因子。特别地，当M_{i,k} = r_{i,k}时，目标是最大化系统服务吞吐量（每秒处理的比特数）；当所有服务的M_{i,k} = 1时，目标则是最大化被接受的服务数量。

  • 约束条件(4)表明，一项服务请求最多只能由一个边缘服务器提供服务。
  • (5)是用于数据路由的流量守恒方程[38]，确保能够支持买家i第k项服务的端到端数据速率r_{i,k}。
  •  (6)表示每条链路上的聚合数据流不应超过链路容量，其中链路l的容量C_l(x)取决于网络资源分配决策x。
  • (7)和(8)则保证每个服务器应具备足够的计算和内存资源来支持所分配的服务请求。
  • (11)代表关于x的一般约束条件。为了展示我们设计的广泛适用性，目前尚未具体指定x和C_l(x)。在第六节中，我们将给出包含频谱分配变量x的具体P1问题。

此外，考虑到买方和卖方可能不愿意为他人中继数据，除非有额外的激励措施，我们可以增加以下约束条件，以确保他们不会被用作中继节点：
\sum_{l \in L_{r,n_{i,k}}} \sum_{i \in I} \sum_{1 \leq k \leq K_i} f_{i,k}^l = 0, \quad \forall i \in I, 1 \leq k \leq K_i, ({12})
\sum_{l \in L_{t,n_j}} \sum_{i \in I} \sum_{1 \leq k \leq K_i} f_{i,k}^l = 0, \quad \forall j \in J, ({13})

其中，L_{t,n}和L_{r,n}分别表示发射端或接收端为节点n的链路集合。(12)和(13)意味着，买家i第k个请求的源节点n_{i,k} \in N_s没有流入的流量，而卖家j的边缘服务器n_j \in N_d也没有流出的流量。

总结一下：这章主要是作者把机制设计与网络优化解耦后，建模网络优化问题。即：

作者先不考虑价格（投标/要价），把“谁的服务由哪台边缘服务器处理、数据如何在网络中走、网络/算力/内存等资源如何分”写成一个联合指派+路由+资源分配的优化问题 P1。它输出一批“候选买卖对”和对应的路由/资源，用于后续的赢家确定与定价（也就是拍卖步骤）。

V. COMPUTING SERVICE AUCTION (COMSA) MECHANISM五、计算服务拍卖（COMSA）机制

在本节中，我们提出了COMSA机制，该机制包含两个步骤：

  • 1）与出价无关的优化与配对划分；
  • 2）胜出配对确定与定价。

A. 第一步：独立于出价的优化与配对划分

        在这一步中，我们首先通过一个独立于出价的优化问题获得服务分配结果，然后将这些结果划分为三个子集以进行后续操作。我们首先通过引入一个额外的约束条件（14）来重新表述问题P1。  
P2：


        其中，约束条件（14）确保同一买方的服务请求被分配到不同的服务器节点上，这是防止市场操纵所必需的，其原因将在第V-B.5节中详细说明。我们用一组买方-卖方配对集合P来表示由问题P2得到的服务分配结果d。具体而言，我们用元组来刻画一个买方-卖方配对，表示根据问题P2的解，买方i的第个请求被分配给了卖方j，其中。由于约束条件（14），买方-卖方配对P_{i,j}唯一对应于买方i的第K_{i,j}个请求。P_{i,j}\in P当且仅当d_{i,k_{i,j}} = 1，或者等价地，根据解d有。我们将P称为候选买方-卖方配对集合，最终的中标配对将在后续过程中从P中选出。

        接下来，我们尝试为P设计一种中标配对确定与定价算法，以保证所需的经济特性，特别是真实性。设计COMSA时面临的一个主要困难在于多需求特性，即每个代理都有多个出价或要价。一种直接的解决方案是用多个虚拟代理替代一个具有多需求的代理，每个虚拟代理提出一个出价或要价，然后在此基础上应用单需求双边拍卖[26]。然而，这种简单的转换方式留下了市场操纵的空间，因为一个多需求代理可以通过操纵其中一个出价或要价来影响其其他出价或要价的结果，从而破坏真实性。（？）

        为了应对这一具有挑战性的多需求双边拍卖机制设计问题，我们设计了配对划分程序，将P策略性地划分为三个独立的子集，随后这三个子集将分别进行独立的拍卖过程。这种划分产生了特殊的出价-要价结构，有助于设计真实性的拍卖机制。具体而言，我们将买方和卖方之间的映射关系表示为一个二分图G = (I, J, E)（参见图2中的示例），其中边$(i, j) \in E$及其关联的顶点表示集合P中的买方-卖方配对P_{i,j}。我们从图G中构造三个子图G1 = (IG1, JG1, EG1)、G2 = (IG2, JG2, EG2)和G3 = (IG3, JG3, EG3)，并根据图的结构将买方-卖方配对划分为三个独立的子集。具体来说，G1由那些卖方与多个买方相关联的买方-卖方配对构成。通过从图G中移除边(i, j) ∈ EG1，我们得到一个新的图G = (I, J, E\EG1)。接着，G2由那些买方与多个卖方相关联的配对构成，而G3则由剩余的买方-卖方配对构成，这些配对中的买方和卖方各自只与一个代理相关联。由于每个代理可以与一个或多个代理配对，这三个子图覆盖了原二分图G中所有可能的配对。我们用P1、P2和P3分别表示子图G1、G2和G3中的配对集合。显然，P1、P2和P3互不相交，满足P = P1∪P2∪P3。图2中展示了配对划分的一个示例，我们将在后续过程中继续使用该实例。

图2. 买卖双方对划分示意图。图G = (I, J, E) 被划分为三个子图，即 G1 = (IG1, JG1, EG1)，G2 = (IG2, JG2, EG2)，以及 G3 = (IG3, JG3, EG3)。

        需要注意的是，第一步与出价/要价价格无关。因此，任何代理都无法通过操纵其出价/要价来影响配对划分的结果，即其出价/要价将进入哪个子图。此外，在接下来的机制设计中，某个出价/要价的中标结果和定价仅取决于其所进入的子图。因此，为P设计一个真实性的中标配对确定与定价机制，归结为分别为子集P1、P2和P3设计真实性的机制。

B. 第二步：胜出对确定与定价

        在此步骤中，我们针对P1、P2和P3分别提出了三种胜出对确定与定价方案，即子程序1、子程序2和子程序3。为了在考虑多重需求特性的情况下确保真实性，我们的基本思路是剔除部分交易对，并将清算价格设定为被剔除的出价/要价或某些阈值（稍后定义），从而使得每个出价/要价的命运不会受到同一主体提出的其他出价/要价的影响。（？）

        在我们的设计中，CSP引入了阈值 b_{\text{min}}^{\text{th}} 和 a_{\text{max}}^{\text{th}}，以确保所有有效的出价均落在区间[b_{\text{min}}^{\text{th}}, +\infty)内，所有有效的要价均落在区间[b_{\text{min}}^{\text{th}}, +\infty)内。超出上述区间的出价和要价将被直接拒绝。在实际操作中， b_{\text{min}}^{\text{th}}和 a_{\text{max}}^{\text{th}}可由拍卖师根据历史信息确定。需要注意的是，即使由于缺乏先验信息而难以获得合适的b_{\text{min}}^{\text{th}} 和 a_{\text{max}}^{\text{th}} ，COMSA仍然适用于这种情况，此时拍卖师可以简单地将 b_{\text{min}}^{\text{th}} 设为0，将a_{\text{max}}^{\text{th}}设为+\infty。然而，我们稍后将展示，通过采用适当的 b_{\text{min}}^{\text{th}}和 a_{\text{max}}^{\text{th}}，可以显著提升系统性能。

        1) 子程序1：子程序1专为P1设计。如图3所示，图G_1是由多棵树构成的森林，其中每个卖方是每棵树的根节点。胜出对的确定与定价是针对每棵树独立进行的。

我们定义

为以卖方j \in J_{G_1} 为根节点的树。

令为树 G_j^1中出价最低的买方索引。

        如果 b_{s_j,\kappa_{s_j,j}} \geq a_{\text{max}}^{\text{th}} ，则可知所有卖方的要价均小于或等于最低出价b_{s_j,\kappa_{s_j,j}} ，因为它们均小于或等于 a_{\text{max}}^{\text{th}}。在这种情况下，树G_j^1中的所有买-卖对均胜出，且 G_j^1中所有胜出的出价/要价的清算价格均设为 a_{\text{max}}^{\text{th}}。

        如果 b_{s_j,\kappa_{s_j,j}} < a_{\text{max}}^{\text{th}} ，则首先牺牲涉及最低买方的交易对，即 s_j 。随后，树 G_j^1中剩余的要价不超过 b_{s_j,\kappa_{s_j,j}}的交易对胜出，而要价高于 b_{s_j,\kappa_{s_j,j}}的交易对则落选。这些胜出的出价/要价的清算价格均设为b_{s_j,\kappa_{s_j,j}}。

        我们注意到，当 b_{s_j,\kappa_{s_j,j}} \geq a_{\text{max}}^{\text{th}}时，最低买方未必一定会被牺牲。因此，采用适当 a_{\text{max}}^{\text{th}} 的方案可能比使用a_{\text{max}}^{\text{th}} = +\infty的方案表现更优。我们指出， a_{\text{max}}^{\text{th}}由CSP预先确定，不受买方或卖方的影响。

        现在我们可以解释为何约束条件(14)对于抵御市场操纵是必要的。如果我们将(14)从问题P2中移除，图G_1中的某棵树可能会包含同一买方的多个出价。在这种情况下，该买方可以通过将其某个出价改为该树中的最低出价，故意使其落选。由于在 b_{s_j,\kappa_{s_j,j}} < a_{\text{max}}^{\text{th}}的情况下，清算价格等于最低出价b_{s_j,\kappa_{s_j,j}} ，该买方可以通过降低这一数值，为其剩余的出价获取更多利益。类似的现象也可以在子程序2中发现。

        为了便于理解，我们以图3中的例子为例，其中图 G_1源自图2。在这种情况下，图G_1由两棵树组成，即 G^{_{1}^{5}}和G{_1}{^6} 。假设CSP将a_{\text{max}}^{\text{th}}设为4.5。在树 G_{15}中，买方4提供了最低出价 b_{4,\kappa_{4,5}}。由于b_{4,\kappa_{4,5}} < a_{\text{max}}^{\text{th}}，交易对P_{4,5}应被牺牲。此外，由于a_{2,5,\kappa_{2,5}} < b_{4,\kappa_{4,5}} 且 a_{6,5,\kappa_{6,5}} < b_{4,\kappa_{4,5}}，交易对P_{2,5}和P_{6,5}胜出。清算价格均设为b_{4,\kappa_{4,5}}，即b_{2,\kappa_{2,5}} = a_{2,5,\kappa_{2,5}} = b_{6,\kappa_{6,5}} = a_{6,5,\kappa_{6,5}} = 4。在树 G_{16}中，由于最低出价b_{5,\kappa_{5,6}} > a_{\text{max}}^{\text{th}}，G_{16}中的两个交易对均胜出，其清算价格均设为 a_{\text{max}}^{\text{th}} ，即 b_{5,\kappa_{5,6}} = a_{5,6,\kappa_{5,6}} = b_{9,\kappa_{9,6}} = a_{9,6,\kappa_{9,6}} = 4.5 。

        值得注意的是，当b_{s_j,\kappa_{s_j,j}} < a_{\text{max}}^{\text{th}}时，子程序1应在树 G_j^1中至少牺牲一个买-卖交易对。因此，在a_{\text{max}}^{\text{th}} = +\infty的情况下，子程序1对P2和P3无法产生任何胜出交易对，此时每个卖方仅与一个买方配对。这一观察表明，子程序1无法应用于P2和P3。

图3. 子程序1的示例。实线表示中标的配对，虚线表示未中标的配对。

2）子程序2：子程序2是为P2开发的。

        需要注意的是，在每个买方仅有一个请求的特殊情况下，P2为空，因此子程序2不会被执行。子程序2与子程序1对称，唯一的区别在于此时买方成为树的根节点（参见图4中的示例）。我们定义G_{2}^{i} = \left \{ {\left \{ i \right \}, J_{G_{2}^{i}},\varepsilon _{G_{2}^{i}}} \right\}为以买方i \in I_{G_{2}}为根节点的树。为集合 J_{G_{2}^{i}}中报价价格最高的卖方索引，即t_i = \arg \max_{j \in J_{G_{2}^{i}}} a_{i,j,\kappa_{i,j}}。

        如果 a_{i,t,\kappa_{i,t}} \leq b_{\min}^{\text{th}}，则所有买方的出价必须高于或等于最高报价价格a_{i,t,\kappa_{i,t}}。在这种情况下，树 {G_{2}^{i}}中的所有配对均获胜，且 {G_{2}^{i}}中所有出价/报价的清算价格均设为b_{\min}^{\text{th}}。

        如果 a_{i,t,\kappa_{i,t}} > b_{\min}^{\text{th}}，则首先剔除包含卖方 t_i的配对。在 {G_{2}^{i}}中剩余的配对中，出价不低于 a_{i,t,\kappa_{i,t}}的配对获胜，而其他配对则失败。所有获胜的出价/报价的清算价格均设为 a_{i,t,\kappa_{i,t}}。

        为了清晰起见，图4给出了子程序2的一个实例。图 G_{2}由两棵树组成，即G_{2}^{7} G_{2}^{10}。假设CSP将b_{\min}^{\text{th}}设置为2。在树G_{2}^{7}中，最高报价价格a_{7,4,\kappa_{7,4}} = 4.2 > b_{\min}^{\text{th}}。因此，拍卖师舍弃了配对 P_{7,4}。由于 b_{7,\kappa_{7,7}}和b_{7,\kappa_{7,10}}均高于a_{7,4,\kappa_{7,4}}，因此配对 P_{7,7} 和 P_{7,10}被确认为获胜配对，其清算价格统一设为 a_{7,4,\kappa_{7,4}}，即 b_{7,\kappa_{7,7}} = b_{7,\kappa_{7,10}} = a_{7,7,\kappa_{7,7}} = a_{7,10,\kappa_{7,10}} = 4.2 。在树 G_{2}^{10}中，由于最高报价价格a_{10,12,\kappa_{10,12}} = 2 \leq b_{\min}^{\text{th}}，因此配对 P_{10,11}和配对 P_{10,11}均获胜，其清算价格为 b_{10,\kappa_{10,11}} = b_{10,\kappa_{10,12}} = a_{10,11,\kappa_{10,11}} = a_{10,12,\kappa_{10,12}} = b_{\min}^{\text{th}} = 2

图4. 子程序2的一个示例。实线表示中标的配对，虚线表示未中标的配对。

3）子程序3：子程序3专为P3设计。

        由于在P3中存在一个简单的单射映射（参见图5中的示例），我们使用$b(i)$和$a(j)$分别表示买方$i$的出价和卖方$j$的要价，以简化记号。不失一般性，

我们将买方按照其出价非递增顺序排序，即$I = \{i_1, i_2, i_3, \dots, i_{|P3|}\}$。；将卖方按其要价非递减顺序排序，即$J = \{j_1, j_2, j_3, \dots, j_{|P_3|}\}$。P3中获胜的买方-卖方配对由一个“边界”(xˆ, yˆ)决定，即只有包含买方i{_{x}}且x ≤ xˆ以及卖方y且j_{y} ≤ yˆ的配对才能获胜。

我们对双方均采用统一定价策略，用B表示所有出价的清算价格，用A表示所有要价的清算价格。我们寻找最大的g，使得$b(ig) \geq a(jg)$，然后通过以下条件确定边界和清算价格：

  • 若$g = |P3|$，我们设定 $B = \min\{b(ig), a_{\max}^{\theta}\}$，$A = \max\{a(jg), b_{\min}^{\theta}\}$，以及 $(\hat{x}, \hat{y}) = g - (b(ig) < a_{\max}^{\theta})$，$g - (a(jg) > b_{\min}^{\theta})$其中 $I(\cdot)$是一个指示函数，当条件为真时返回 1，否则返回 0。
  • 若 $g < |P3|$ 且 $a(ig) \leq v \leq b(jg)$，我们设 $B = A = v$，$(\hat{x}, \hat{y}) = (g, g)$，其中 $v = \frac{b(ig+1) + a(jg+1)}{2}$。若 $g < |P3|$ 且 a(i_{g}) > v 或 $v > b(j_{g})$，我们设$B = b(ig)$，$A = a(jg)$，$(\hat{x}, \hat{y}) = (g - 1, g - 1)$。

        由上述分析可知，在 $g = |P3|$ 的情况下，买卖价差阈值有可能提升拍卖的性能。对于买方而言，当 $b(ig) \geq a_{\max}^{\text{th}}$时，$B$被设定为 $a_{\max}^{\text{th}}$；而当 $b(ig) < a_{\max}^{\text{th}}$时，$B$则由 $b(i_g)$决定。因此，在前一种情况下，买方(i_g) 可以被选为胜者，而在后一种情况下则必须被舍弃，以确保机制的真实性。这表明，采用适当的$a_{\max}^{\text{th}}$方案可能会比 $a_{\max}^{\text{th}} = +\infty$的方案多产生一对胜出的交易对。同样的现象在卖方侧也同样存在。

        总之，清算价格由以下因素决定：

        子程序3的设计灵感来源于TASC方案[26]。然而，与TASC不同的是，子程序3利用了阈值b_{\min}^{\text{th}}和a_{\max}^{\text{th}}来提升系统效率。

        为了说明子程序3的思想，我们在图5中给出了两个示例，其中映射关系与图2中的图G3相同。在两个子图中，买方均按照其出价价格以非递增顺序排序，即$\{i_1, i_2, i_3, i_4, i_5\} = \{1, 2, 4, 5, 8\}$；卖方则按照其要价价格以非递减顺序排序，即$\{j_1, j_2, j_3, j_4, j_5\} = \{1, 9, 3, 2, 8\}$。假设CSP设置的$b_{\min}^{\text{th}} = 2.0$，$a_{\max}^{\text{th}} = 4.5$。在图5(a)中，我们有$g = 5 = |P_3|$，且$b(i_5) = b(8) \geq a_{\max}^{\text{th}}$，同时$a(j_5) = a(8) > b_{\min}^{\text{th}}$。因此，我们得到$(\hat{x}, \hat{y}) = (5, 4)$，从而确定了中标对为$P_{1,3}$、$P_{2,1}$、$P_{4,9}$和$P_{8,2}$。$P_{5,8}$落标，因为卖方8位于边界$(5, 4)$的右侧。清算价格由$B = a_{\max}^{\text{th}} = 4.5$和$A = a(8) = 3.3$决定。在图5(b)中，我们有$A = a(8) = 3.3$，且$a(i_4) = a(2) \leq v \leq b(j_4) = b(5)$，其中$v = \frac{b(8) + a(8)}{2} = 4.3$。因此，我们得到边界$(\hat{x}, \hat{y}) = (4, 4)$，从而确定了中标对为$P_{1,3}$、$P_{2,1}$和$P_{4,9}$，清算价格为$B = A = v = 4.3$。

图5. 子程序3的两个示例。在每个子图中，虚线矩形标记了满足条件$b(i_g) \geq a(j_g)$ 的最大$g$ 对 $(i_g, j_g)$，实线矩形标记了边界$(\hat{x}, \hat{y})$，实线表示获胜对，虚线表示未获胜对。

        经过第二步后，由P2获得的资源分配和路由策略x和f可能导致资源浪费，因为为了确保所需的经济特性，一些候选配对被剔除了。因此，我们可以收回分配给失败候选对的网络资源。具体而言，根据问题P2的解$f$以及获胜候选对的判定结果，若候选对$P_{i,j}$失败，则我们将每个传输链路$l$上的$f_{i,\kappa_{i,j},l}$设为0，从而得到最终的流量路由策略$f^*$。接着，基于问题P2的解$x$，我们在确保支持链路$l$上$f^*$的前提下，最小化每个传输链路$l$的网络资源使用量（例如频谱分配），进而得到最终的资源分配策略$x^*$。

VI. CASE STUDY: EDGE COMPUTING OVER WIRELESS MESH NETWORKS六、案例研究：基于无线网状网络的边缘计算

        第四节中的问题P1是一个通用的表述形式，可以轻松地适应各种场景。为了展示一个具体的P1，我们以无线网状网络为例进行研究，其中中继节点通过无线方式互联，以将数据流从买家的数据源传输到卖家的服务器。此外，我们还允许源节点直接与附近的边缘服务器通信。我们将频谱分配变量表示为x，并在下文中给出关于x的约束条件。

        设W为系统中的频谱带集合，定义x_w^l \in \{0, 1\}为频谱分配变量，其中若频谱带w \in W被分配给链路l，则x_w^l = 1，否则x_w^l = 0 。一个节点不能在同一频谱带上同时向多个相邻节点发送或接收数据，即

        其中，L^t_n 或L^r_n 是指发射机或接收机为节点 n 的链路集合。n^t_l 或n^r_l表示链路 l的发射机或接收机。W_m是节点 m 周围可用的频段集合。为避免自干扰，一个节点不能同时使用相同的频段进行发送和接收，即：

        此外，应减轻来自其他节点的干扰。具体而言，如果节点n \in N 在频段w \in W_m上接收数据，则可能在频段w上对节点n产生干扰的相邻节点不应使用该频段，即：

其中，Y_{m^{'}}表示节点m^{'}干扰范围内的节点集合。此处采用协议干扰模型 [39]：在给定发射功率的情况下，干扰范围的确定方式为：该范围内接收到的功率超过某一阈值，而在该范围之外，干扰被认为可以忽略不计。

        此外，在给定 x 的情况下，每条链路上的聚合数据流只有在其不超过链路容量时才是可行的，即：

其中， B_w表示频带 w 的带宽，e_l表示链路l的频谱效率，其取决于发射机的发射功率以及链路 l  上的路径损耗。

        通过将问题 P1 中的式 (6) 替换为式 (21)，并将式 (11) 替换为式 (17)-(20)，我们得到了一个联合服务路由与频谱分配问题。在 COMSA 的第一步中，加入线性约束条件 (14)，可以得到问题 P2 的具体形式，该问题是一个混合整数线性规划（MILP）。尽管 MILP 通常属于 NP 难问题，但其求解方法已在文献中得到了广泛研究。例如，可以利用分支定界法来寻找全局最优解 [40]，或者采用粗粒度固定算法来获得次优解 [3], [41]。有了问题 P2 的解之后，我们便可以按照第 V 节中的步骤，得到拍卖结果。

VII. MECHANISM ANALYSIS七. 机制分析

        在本节中，我们首先分析COMSA的计算复杂度，然后证明COMSA具有个体理性、预算平衡和策略真实性。

        定理1：COMSA的复杂度为$\mathcal{O}(T + |I||J| + |I|\log|I| + |J|\log|J|)$，其中$T$表示在第一步中求解优化问题P2的复杂度。

        证明：COMSA 包含两个步骤。在第一步中，COMSA 求解问题 P2，并根据图 2 所示确定买方-卖方对的划分。由于求解 P2 的复杂度取决于具体的问题表述和求解方法，我们为了一般性将其表示为 $O(T)$。在我们的仿真中，我们采用文献 [3] 中的粗粒度固定算法，在第 VI 节的配置下获得问题 P2 的近似解，该算法通过求解一系列线性规划（LP）和一个小规模混合整数线性规划（MILP）来实现（详细内容请参阅第 VIII-A 节）。已知线性规划问题的求解复杂度为 $O(n^3)$ [42]，其中$n$为变量个数，因此粗粒度固定算法的复杂度为$O\big((|N_s|(|J| + |L|) + |L||W|)^3|L||W| + 2|N_s||J|(|L||N_s|)^3\big)$（证明略）。$O(\cdot)$ 中的第二项源于混合整数线性规划问题可通过分支定界法求解，而在最坏情况下，该方法退化为对 $|N_s||J|$个二元变量进行穷举搜索，并同时求解线性规划问题。然而，由于分支定界法通过剔除不会包含最优解的候选解来剪枝搜索空间，其平均计算复杂度远低于此。事实上，如第 VIII-B 节的仿真结果所示，粗粒度固定算法能够高效地求解具有实际网络规模的 P2 问题。在获得 P2 的解之后，配对划分过程的时间复杂度为$O(\max\{|I|, |J|\})$，其中包括为多个代理寻找买家和卖家。

        随后，在第二步中，COMSA 由三个子程序组成。在子程序1中，每棵树上寻找最低出价最多需要 $O(\max\{|I|, |J|\})$时间，而将各树上的要价与最低出价进行比较也最多需要$O(|I|)$时间。树的数量最多为$|J|$。子程序2的分析与子程序1类似，因此子程序1和子程序2的复杂度均为 $O(|I||J|)$。在子程序3中，对买家和卖家分别进行排序的时间复杂度分别为$O(|I|\log|I|)$ 和 $O(|J|\log|J|)$，而寻找边界并确定中标配对的时间复杂度为$O(\min\{|I|, |J|\})$。因此，COMSA 的总复杂度为 $O(T + \max\{|I|, |J|\} + |I||J| + |I|\log|I| + |J|\log|J| + \min\{|I|, |J|\}) = O(T + |I||J| + |I|\log|I| + |J|\log|J|)$。至此证明完成。可以看出，COMSA 的第二步计算效率较高，而第一步的复杂度则取决于具体问题及求解方法。

        定理2：COMSA具有个体理性。

        证明：为证明COMSA的个体理性，我们需证明子程序1、子程序2和子程序3均具有个体理性。

        子程序1独立地确定图$G_1$中每棵树的中标对及定价。在树$G_1$中，买方和卖方的清算价格记为$P_j^1$，其表达式为$P_j = \min\{bs_j, \kappa_{sj,j}, a_{\max}^{th}\}$。由于$bs_j, \kappa_{sj,j}$是$G_j^1$中的最低出价，因此$G_j^1$中任何中标买方支付的价格均不超过该出价。同时，若$G_j^1$中的某卖方要价高于$bs_j, \kappa_{sj,j}$或$a_{\max}^{th}$，则其将落标。总体而言，中标卖方获得的支付不低于其要价。因此，子程序1具有个体理性。子程序2的证明与此类似。

        在子程序3中，买方的清算价格，即$B$，以及卖方的清算价格，即$A$，由式(15)或式(16)确定。根据中标判定策略，中标买方的出价应不低于$B$，而中标卖方的要价应不高于$B$。因此，子程序3也具有个体理性，至此证明完成。

定理3：COMSA实现预算平衡。

        证明：显然，如果三个子程序分别确保预算平衡，则COMSA即可实现预算平衡。

        在子程序1和子程序2中，对于任何中标的买方-卖方配对，买方和卖方的清算价格是相同的。因此，拍卖人的利润为零。

        在子程序3中，如果支付由式(15)确定，则中标买方和卖方的清算价格相同，从而拍卖人的利润也为零。如果支付由式(16)确定，则拍卖人的利润为 $ U_A = \sum_{i,j \in S_3} \left( \min\{b_{ig}, a_{\max}^{\text{th}}\} - \max\{a_{jg}, b_{\min}^{\text{th}}\} \right) \geq 0 $，其中$ S_3 $是由子程序3得到的中标配对集合。由于 $ b_{ig} \geq a_{jg} $，$ a_{\max}^{\text{th}} > b_{\min}^{\text{th}} $，$ a_{\max}^{\text{th}} \geq a_{jg} $且 $ b_{\min}^{\text{th}} \leq b_{ig} $，拍卖人获得了非负的利润，这就完成了证明。

        $B_{-(i,j)} = B_i \setminus \{b_{i,\kappa_{i,j}}\}$为了证明COMSA的真实性，我们需要证明一系列引理。

        引理1：如果子程序1、子程序2和子程序3分别具有真实性，则COMSA具有真实性。

        证明：COMSA的第一步与出价/要价价格无关，即买方/卖方无法通过操纵出价来控制独立于出价的优化问题P2的解以及出价操纵下的配对划分。换句话说，无论是买方还是卖方，都无法控制其出价/要价进入哪个子程序。在不可操纵的第一步之后，某项出价/要价的拍卖结果（是否中标及定价）取决于相应的子程序，而与其他子程序无关。因此，如果子程序1、子程序2和子程序3各自都是诚实的，则COMSA也是诚实的。至此，证明完成。

        引理2：在子程序1中，配对Pi,j的拍卖结果与买方i的其他出价以及卖方j的其他要价无关，即出价向量B−(i,j) = Bi\{bi,κi,j }和要价向量$A_{-(i,j)}= A_j \setminus \{a_{i,j},\kappa_{i,j}\}$。

         证明：如前所述，第一步与出价/要价无关。在第二步中，假设配对 P_{i,j} 属于集合 P_1（因此位于图  G_1 的树 G_j^1中）。一方面，在树G_j^1  中，买方  i 唯一的出价是b_{i,\kappa_{i,j}} 。另一方面，尽管卖方j在G_j^1中可能有多个要价，但配对 P_{i,j}的拍卖结果仅取决于 a_{i,j,\kappa_{i,j}}  以及G_j^1中的出价。因此，买方i和卖方j不可能通过操纵除b_{i,\kappa_{i,j}}和a_{i,j,\kappa_{i,j}}之外的其他出价/要价来影响配对P_{i,j} 的拍卖结果。至此，证明完毕。

        引理3：子程序1对买方和卖方都是诚实的。

         证明：我们首先证明子程序1对买方是诚实的。为了证明其诚实性，只需表明对于任意服务，买方 i \in I通过如实报价能够最大化其效用，即 U_b^{i,k} = y_b^{i,k}(v_{i,k} - b_{i,k})。不失一般性，我们考虑 k = \kappa_{i,j} 的情形。根据引理2，我们只需考察b_{i,\kappa_{i,j}} 对 U_b^{i,\kappa_{i,j}}的影响。令 \hat{U}_b^{i,\kappa_{i,j}}  表示当买方  i  披露其真实估值 v_{i,\kappa_{i,j}}时U_b^{i,\kappa_{i,j}} 的值，而令 \tilde{U}_b^{i,\kappa_{i,j}} 表示当买方不实报价时 U_b^{i,\kappa_{i,j}}的值。我们考察表II中列出的所有可能情况，以证明\hat{U}_b^{i,\kappa_{i,j}} \geq \tilde{U}_b^{i,\kappa_{i,j}}。

  • 情况1：无论买方  i  如何行为，其均无法获得第 \kappa_{i,j} 项服务，从而有 \hat{U}_b^{i,\kappa_{i,j}} = \tilde{U}_b^{i,\kappa_{i,j}} = 0。
  • 情况2：由于定理2中已证明的个体理性条件，我们有\hat{U}_b^{i,\kappa_{i,j}} \geq \tilde{U}_b^{i,\kappa_{i,j}} = 0。
  • 情形3：买方i在如实投标时可能损失的两个原因如下：

1）a_{i,j,{k_{i,j}}}高于G_1^j中的最低出价，即a_{i,j,{k_{i,j}}}> b_{​{s_{j}},{k_{s_j}},{j}}；

2）v_{i,{k_i},{j}}等于\varepsilon ^j_1中的最低出价，且v_{i,{k_i},{j}} < a^{\max}_{\text{th}}。

在情形1）中，买方i无法通过操纵其出价赢得第 \kappa_{i,j} 项服务。在情形2）中，买方i必须出价高于G_1^j中第二低的出价或a^{\max}_{\text{th}}，才能获胜。在这种情况下，清算价格等于min{b' , a^{\max}_{\text{th}}}，其中b'表示G_1^j中除b_{i,{k_i},{j}}之外的最低出价，且满足b' >v_{i,{k_i},{j}}。因此，可以得出$\tilde{U}_{ib,\kappa_{i,j}} = v_{i,\kappa_{i,j}} - \min\{b , a_{\max}\} \leq 0 \leq \hat{U}_{b i,k_{i,j}}$。

  • 情形4：回顾一下，$b$表示在 $G_j^1$ 中除买方$i$ 的出价之外的最低出价。如果 $b < a^{\max}_{\text{th}}$，则买方 $i$应出价不低于$b$才能胜出，并按$b$收费。如果$b \geq a_{\max}^{\text{th}}$，则买方$i$ 应出价不低于 a^{\max}_{\text{th}}，并按 a^{\max}_{\text{th}} 收费。无论买方$i$如何出价，清算价格均不会改变。因此，我们得到 $\hat{U}_{ib,\kappa_{i,j}} = \tilde{U}_{ib,\kappa_{i,j}}$。

        由上述内容可知，我们证明了\hat{U}_{ib,\kappa_{i,j}} \geq \tilde{U}_{ib,\kappa_{i,j}}始终成立。因此，子程序1对买方是诚实的。由于卖方诚实性的推导与买方对称，我们省略了针对卖方的详细证明。至此，证明完成。

        引理4：在子程序2中，配对Pi,j的拍卖结果与买方i的其他出价以及卖方j的其他要价无关，例如出价价格向量 $B_j^{-(i,j)} = B_i \setminus \{b_{i,\kappa_{i,j}}\}$，而叫价价格向量 $A^{-(i,j)}_j = A_j \setminus \{a_{i,j},\kappa_{i,j}\}$。。

        证明：该证明与引理2的证明类似，因此省略。

        引理5：子程序2对买方和卖方都是诚实的。

        证明：借助引理4，我们可以通过类似于引理3的证明过程来证明引理5。具体细节省略。

        引理6：在子程序3中，配对Pi,j的拍卖结果（是否中标及定价）与买方i的其他出价以及卖方j的其他要价无关，即出价向量$B_{-(i,j)} = B_i \setminus \{b_{i,\kappa_{i,j}}\}$和要价向量$A_{-(i,j)}^j = A_j \setminus \{a_{i,j}, \kappa_{i,j}\}$。

        证明：在图$G_3$中，买方$i$唯一的出价为$b_{i,\kappa_{i,j}}$，卖方$j$唯一的要价为$a_{i,j,\kappa_{i,j}}$。因此，对偶$(P_{i,j})$的拍卖结果显然与买方$i$和卖方$j$的其他价格无关，即$B^{-(i,j)}_i = B_i \setminus \{b_{i,\kappa_{i,j}}\}$以及$A^{-(i,j)}_j = A_j \setminus \{a_{i,j,\kappa_{i,j}}\}$。证明完毕。

        引理7：在子程序3中，如果买方i能够通过同时出价$ v_{i,\kappa_{i,j}} $和$\tilde{b}_{i,\kappa_{i,j}}$赢得其第$\kappa_{i,j}$项服务，其中$\tilde{b}_{i,\kappa_{i,j}} = v_{i,\kappa_{i,j}}$，则其被收取相同的价格。

        证明：设g表示当买方i  报价为v_{i,\kappa_{i,j}}时，满足 b_{(i_g)} \geq a_{(j_g)}的最大索引。根据式（15）和式（16），当买方i 报价为 v_{i,\kappa_{i,j}} 时，其清算价格有三种可能的取值：1）a^{\max}_{\text{th}}；2）b_{(i_g)} ；以及 3）v 。在情况 1）中，我们知道，在排序I中，所有买家的出价均高于a^{\max}_{\text{th}}。因此，买方$i$必须出价 $\tilde{b}_{i,k,j} > a_{\max}$才能获胜，在这种情况下，其需支付的费用为$m_{\max}$。在情况 2) 中，若买方$i$ 出价满足 $\tilde{b}_{i,\kappa_i,j} \geq b(i,g)$，则需支付 b_{(i_g)}；否则将失去竞标资格。在情况 3) 中，若买方 $i$出价满足 $\tilde{b}_{i,\kappa_i,j} \geq v$，则需支付$v$；否则将失去竞标资格。因此，如果买方$i$ 赢得竞标，无论其出价为 v_{i,\kappa_{i,j}} 还是$\tilde{b}_{i,\kappa_{i,j}}$，都将被收取相同的价格。

        引理8：在子程序3中，如果卖方j能够通过请求$c_{i,j,\kappa_{i,j}}$和$\tilde{a}_{i,j,\kappa_{i,j}}$赢得买方i的第κ项服务，其中$\tilde{a}_{i,j,\kappa_{i,j}}$ = $c_{i,j,\kappa_{i,j}}$，则其支付的价格相同。

        证明：该证明与引理7的证明类似，因此省略。

        引理9：子程序3对买方和卖方都是诚实的。

        证明：我们首先证明子程序3对买方是诚实的。同样地，我们考察表II中列出的所有可能情况，以证明 \hat{U}_{ib,\kappa_{i,j}} \geq \tilde{U}_{ib,\kappa_{i,j}} 成立。  
• 情况1：我们有 \hat{U}_{ib,\kappa_{i,j}} = \tilde{U}_{ib,\kappa_{i,j}} = 0 。  
• 情况2：根据个体理性，我们得到\hat{U}_{ib,\kappa_{i,j}} \geq \tilde{U}_{ib,\kappa_{i,j}} = 0 。  
• 情况3：根据式(15)和式(16)，当买方 i 出价为\tilde{b}_{i,\kappa_{i,j}}时，其清算价格有三种可能的取值：

1)  a^{\max}_{\text{th}}；2) b_{(i\tilde{g})} ，其中 \tilde{g}是使得 b_{(i\tilde{g})} \geq a_{(j\tilde{g})} 的最大索引，且买方 i 出价为 \tilde{b}_{i,\kappa_{i,j}} ；3)  v 。需要注意的是，当买方i出价为v_{i,\kappa_{i,j}}时会落标。因此，子情况1仅在 \tilde{b}_{i,\kappa_{i,j}} \geq a_{\max}^{\text{th}} > v_{i,\kappa_{i,j}} 时发生，此时 \tilde{U}_{ib,\kappa_{i,j}} = v_{i,\kappa_{i,j}} - a_{\max}^{\text{th}} < 0 = \hat{U}_{ib,\kappa_{i,j}} 。子情况2仅在 \tilde{b}_{i,\kappa_{i,j}} \geq b_{(i\tilde{g})} \geq v_{i,\kappa_{i,j}}时发生，此时\tilde{U}_{ib,\kappa_{i,j}} = v_{i,\kappa_{i,j}} - b_{(i\tilde{g})} \leq 0 = \hat{U}_{ib,\kappa_{i,j}}。子情况3仅在 \tilde{b}_{i,\kappa_{i,j}} \geq v \geq v_{i,\kappa_{i,j}}时发生，此时 \tilde{U}_{ib,\kappa_{i,j}} = v_{i,\kappa_{i,j}} - v \leq 0 = \hat{U}_{ib,\kappa_{i,j}}。对于所有子情况，我们均得到 \hat{U}_{ib,\kappa_{i,j}} \geq \tilde{U}_{ib,\kappa_{i,j}} 。  
• 情况4：根据引理7，两种情况下清算价格相同，从而有 \hat{U}_{ib,\kappa_{i,j}} = \tilde{U}_{ib,\kappa_{i,j}}。

        接下来，我们应当证明子程序3对卖家是诚实的。如子程序3所示，从胜者确定和定价两方面来看，卖家与买家是对称的。因此，对卖家诚实性的证明与对买家的证明类似，故此处省略。至此，证明完成。利用上述引理，我们给出了关于COMSA诚实性的最终结果。

定理4：COMSA是诚实的。

        证明：引理1、引理3、引理5和引理9共同证明了COMSA具有真实性。

VIII. PERFORMANCE EVALUATION八、性能评估

IX. CONCLUSIONIX. 九结论

        在无线通信领域，现有的大多数双边拍卖机制仅关注计算资源或通信资源中的一种。即使有极少数机制在拍卖设计中同时考虑了这两种资源类型，它们也最多只是将拍卖设计视为联合资源优化问题，其中竞标者仍然需要主动选择并竞标资源。然而，最终用户最关心的其实是其服务能否以期望的服务质量水平得到提供，而并不真正在意自己被分配了多少资源。

        针对这一观察，本文提出了一种通用的“面向服务”的双边拍卖机制——COMSA，以解决边缘计算中激励设计与服务提供相结合的问题。具体而言，COMSA不仅建立了一个双边拍卖市场，使服务提供商能够从服务需求方获得满意的回报以补偿其成本，还通过合理分配有限的计算和网络资源，支持中标的服务请求，并为其提供适当的端到端服务质量（E2E QoS）保障。

        我们已经证明，COMSA具有真实性、个体理性以及预算平衡的特性。仿真结果表明，COMSA能够在实现理想经济属性的同时，保持令人满意的系统服务吞吐量。

        除了服务吞吐量之外，社会福利也是拍卖设计中的另一个重要指标。在COMSA中，第一步的独立于投标的优化问题旨在最大化已接受服务的加权总和，而不考虑出价或要价。因此，那些估值较高的请求可能会在COMSA的第一步被拒绝，从而导致社会福利的下降。因此，如何为移动边缘计算（MEC）设计一种能够提升社会福利的端到端服务拍卖机制，是一个既具有挑战性又引人关注的研究问题。

# 机器学习 # 人工智能 # 分布式 # 算法
Logo
火山引擎 ADG 社区

火山引擎开发者社区是火山引擎打造的AI技术生态平台，聚焦Agent与大模型开发，提供豆包系列模型（图像/视频/视觉）、智能分析与会话工具，并配套评测集、动手实验室及行业案例库。社区通过技术沙龙、挑战赛等活动促进开发者成长，新用户可领50万Tokens权益，助力构建智能应用。

更多推荐

OpenClaw 本地部署完整指南（Windows + Ollama）

本文档基于实际部署经验编写，旨在帮助你在 Windows 系统上从零开始搭建 OpenClaw，并连接本地 Ollama 模型（如 Qwen2.5 或 Qwen3），使其具备完整的智能体能力。文档包含了所有关键步骤以及常见问题的解决方案。

avatar 火山引擎 ADG 社区

OpenClaw 小白安装指南（Windows版）

（类似一个能自动执行任务的AI机器人），不是游戏。API Key只保存在你本地电脑的加密文件里，不会上传到任何地方。访问：https://github.com/miaoxworld/openclaw-manager/releases。: 一键安装脚本会自动安装Node.js 22+，如果失败，手动下载安装：https://nodejs.org/：在PowerShell中，鼠标右键就是粘贴，不需要按

avatar 火山引擎 ADG 社区

飞书 × OpenClaw 接入指南：不用服务器，用长连接把机器人跑起来

这个项目存在的意义，就是把“飞书接 OpenClaw”这件事，整理成一套的配置入口，并把官方文档没覆盖到的坑集中写成排查清单。先说清楚它的角色：OpenClaw 现在已经内置官方飞书插件 @openclaw/feishu，功能更完整、维护也更及时。，说明飞书 + AI 的接入已经走通。另外，仓库也推荐了一个新项目：把 OpenClaw 变成“多 Agent 团队”，用多个 Agent 分工，Sla

avatar 火山引擎 ADG 社区