论文阅读/博弈论/拍卖：《Truthful Auction for Cooperative Communications》-EW帮帮网

摘要：

一方面，协作通信由于其在提升无线网络容量方面的巨大潜力而日益受到关注。另一方面，协作通信技术的实际应用却很少见，即使在一些对带宽需求极高的应用场景中，系统设计者也并未采用协作通信技术来开发创新的网络解决方案。协作通信从理论上能够提高信道容量，但其广泛应用面临的主要障碍是缺乏激励机制，促使参与节点愿意充当中继节点。因此，在本文中，我们设计了一种名为TASC的拍卖方案，用于协作通信中的中继服务交易。TASC在实现其他设计目标的同时，还保证了机制的真实性。我们通过理论分析证明了TASC具有真实性，并且时间复杂度为多项式级别。大量实验表明，TASC能够在不显著降低性能的情况下实现多种经济特性。

图1：协作通信的拍卖过程。中继节点（卖方）提供其中继服务的价格，源节点（买方）竞标这些服务以实现协作通信。基站（拍卖人）确定中标者及清算价格。

TASC

INTRODUCTION：
与3G/4G无线网络相比，协作通信技术不需要额外的基础设施，并且具有灵活性的优势。然而，协作通信技术在实现信道容量提升潜力与广泛应用之间面临的主要障碍，是缺乏激励机制来促使参与节点充当中继节点。为什么一家手机运营商会愿意以牺牲自身资源为代价来中继另一家运营商的流量呢？对此问题的一个答案是让中继节点能够获得相应的经济回报。因此，需要在请求中继服务的无线节点和提供中继服务的节点之间建立一种交易机制。拍卖是最流行的交易形式之一[12]，因为它可以实现竞争性价格发现，以及公平高效的资源分配。

涉及买家和卖家的拍卖称为双向拍卖（double auction）。更具体地说，本文设计的双向拍卖方案属于单轮多物品双向拍卖。在该拍卖方案中，如图1所示，有n个买家对来自m个卖家的多个物品感兴趣。

拍卖机制是交易市场中的一个关键方面，因为拍卖方案不仅直接定义了交易规则，还隐含地决定了参与代理的行为。具体而言，真实性（也称为策略稳健性）是拍卖方案中最关键的特性。如果无论其他参与者采取何种策略，每个参与者的主导策略都是如实披露其真实的私有价值，则该拍卖方案即为真实性的。理论和实践都表明，如果这一特性得不到保证，拍卖可能会受到市场操纵的影响，并产生非常糟糕的结果[11]。除了真实性之外，在设计拍卖方案时，以下特性也是理想的：1）个体理性：每个参与拍卖的代理都能期望获得非负收益；2）预算平衡：拍卖方在拍卖结束后不应出现亏损；3）系统效率：所有代理估值之和达到最优，例如本文中总容量的最大化。遗憾的是，[16]中著名的结论表明，即使不考虑个体理性，任何双侧拍卖机制都无法同时实现真实性、预算平衡和系统效率。由于本研究的目标是激励无线节点参与中继服务，因此我们专注于设计满足真实性、个体理性和预算平衡的方案。本文中，我们设计了一种用于协作通信的真实拍卖方案（TASC）。

本文的主要贡献如下：

首先，我们首次设计了一种用于协作通信的真实拍卖方案，命名为TASC。TASC隐式地使参与代理的主导策略成为如实出价或报价，从而消除了对市场操纵的担忧以及与其他参与者博弈策略的开销。其次，除了真实性之外，TASC还具备个体理性和预算平衡的特性。据我们所知，这也是经济文献中首个真实性的多物品双侧拍卖方案。我们希望我们的研究能够引起更多研究人员对该类拍卖的关注。第三，TASC允许拍卖方根据性能需求选择任意中继分配算法。例如，可以使用最大加权匹配算法来最大化总容量；使用算法ORA [20]来最大化最小容量；或者使用最大匹配算法来最大化成功交易的数量。最后但同样重要的是，大量的实验验证了TASC的真实性，并表明TASC在系统效率上仅有有限的下降，但仍能满足所有要求的特性。

RELATED WORK

尽管拍卖理论在经济学文献中已得到广泛研究，但现有的拍卖设计无法完全满足第1节中所提出的各项要求。我们在表1中总结了最相关的工作。在该表中，我们列出了现有工作与本文所设计拍卖方案之间的主要差异。其中，交易物品的异质性在拍卖设计中起到了重要作用，使得设计更具挑战性，因为每个买家对来自不同卖家的不同物品具有不同的偏好。除了表格中列出的差异之外，一些现有方案还采用了多轮拍卖机制[6, 2, 15]。然而，多轮拍卖并不适用于协作通信场景，因为在协作通信中，及时性是一个必要条件，而较大的通信开销则不可取。

表1：现有的拍卖方案。“−”表示相应属性未知。

3. PRELIMINARIES AND PROBLEM FORMULATION

3.1 Cooperative Communications

我们使用图2中一个著名的三节点示例来描述协作通信（CC）的本质。在这个示例中，s是发送信息的源节点，d是接收信息的目的节点，而r是中继节点，它既接收又转发信息，以增强源节点和目的节点之间的通信。协作通信以帧为单位进行，每帧被划分为两个时隙。在第一个时隙中，源节点s向目的节点d传输数据。由于广播特性，中继节点r可以监听到这一传输。在第二个时隙中，r根据不同的协作通信模式，采用不同的技术将数据转发给d。协作通信有两种模式：放大转发（AF）和解码转发（DF）[13]。关于AF和DF的详细内容，请感兴趣的读者参考文献[13]。我们用cR(s,r,d)表示协作通信下的可达容量，用𝑐D(s,d)表示无协作通信下的可达容量。

图2：CC的三个节点示例

3.2 Problem Model

本文考虑一个由 $n$ 个源-目的地对 $\{s_1, d_1; s_2, d_2; \dots; s_n, d_n\}$ 和 $m$ 个中继节点集合 $R = \{r_1, r_2, \dots, r_m\}$ 组成的静态自组织无线网络。我们用 $\mathcal{S} = \{s_1, s_2, \dots, s_n\}$ 表示源节点集合，用 $\mathcal{D} = \{d_1, d_2, \dots, d_n\}$ 表示目的节点集合。我们假设存在一个基站作为中央控制器，并在拍卖机制中充当拍卖人角色，例如在蜂窝网络中，基站即为所有源节点 $s_i$ 的基站，如图1所示。

我们将协作通信拍卖设计为一轮多物品双向拍卖。在此拍卖中，源节点是买家，中继节点是卖家，基站是拍卖人。在本文中，我们可能会交替使用“源节点”与“买家”，“中继节点”与“卖家”，以及“基站”与“拍卖人”。为了叙述方便，我们一般将买家和卖家统称为代理。买家为协作通信的中继服务出价，而卖家则以消耗资源（例如能量）为代价提供协作服务，并获得相应的货币支付。对于每个买家而言，由于与不同中继节点协作可实现不同的容量，因此其对各个中继节点的估值也有所不同。令 $\mathcal{V}_{j}^{i}$ 表示买家 $\mathcal{s}_i$ 对来自卖家 $\mathcal{r}_j$ 的中继服务的真实估值，即 $\mathcal{s}_i$ 愿意为该中继服务支付的真实价格。令 $\mathbf{V}_i = (\mathcal{V}_1^i, \mathcal{V}_2^i, ..., \mathcal{V}_m^i)$ 表示买家 $\mathcal{s}_i$ 的真实估值向量。显然，当 $\mathcal{c}_{R}(\mathcal{s}_i, \mathcal{r}_j, \mathcal{d}_i) > \mathcal{c}_{D}(\mathcal{s}_i, \mathcal{d}_i)$ 时，有 $\mathcal{V}_j^i > 0$ ；否则 $\mathcal{V}_j^i = 0$ 。买家没有动机购买无法提供比直接传输更高容量的中继服务。类似地，令 $\mathcal{C}_j$ 表示卖家 $\mathcal{r}_j$ 提供中继服务的真实成本，例如与能耗相关。卖家不会区分不同的买家，因为它使用相同的发射功率。我们假设每个买家最多只需要一个中继节点来协助协作通信。Zhao等人[23]最近的一项研究表明，即使存在多个可用的中继节点，源节点只需选择最佳的中继节点即可实现完全分集增益。我们还假设每个中继节点最多只能被一个源节点共享，否则它所提供的容量将不同于买家所期望的值。

该拍卖是一个密封投标拍卖。根据拍卖理论中的术语，我们将买方提交的价格称为出价（bid），卖方提交的价格称为要价（ask）。每个买方（或卖方）向拍卖人提交其私有的出价（或要价），且不知道其他人的出价信息。我们假设所有要价和出价都是静态的，在拍卖过程中不会发生变化。在拍卖开始时，每个买方 $\mathcal{S}_i$ 提交一个出价向量 $\mathbf{B}_i = (B_{1i}, B_{2i}, \dots, B_{mi})$ ，其中 $B_{ji}$ 表示买方 $\mathcal{S}_i$ 对卖方 $\mathcal{R}_j$ 的出价。 $\mathbf{B}_i$ 可能与其真实估值向量 $\mathbf{V}_i$ 相同，也可能不同。每个卖方 $\mathcal{R}_j$ 提交其要价 $A_j$ ，该要价可能与其真实成本 $C_j$ 相同，也可能不同。令 $\mathbf{B} = (B_1; B_2; \dots; B_n)$ 表示由所有买方提交的出价向量组成的出价矩阵。类似地，令 $\mathbf{A} = (A_1, A_2, \dots, A_m)$ 表示由所有卖方提交的要价组成的集合。记 $\mathbf{B}_{-j}^i = (B_{1i}, \dots, B_{j-1i}, B_{j+1i}, \dots, B_{mi})$ 为买方 $\mathcal{S}_i$ 的出价向量，其中 $B_{ji}$ 被移除。记 $\mathbf{B}_{-i} = (B_1; \dots; B_{i-1}; B_{i+1}; \dots; B_n)$ 为出价矩阵，其中 $\mathcal{S}_i$ 的出价向量 $\mathbf{B}_i$ 被移除。记 $\mathbf{B}|_{iB}$ 为出价矩阵，其中 $\mathcal{S}_i$ 的出价向量被替换为 $B$ 。类似地，定义 $\mathbf{A}_{-j}$ 和 $\mathbf{A}|_{jA}$ 。给定 $\mathcal{S}$ 、 $\mathcal{R}$ 、 $\mathcal{D}$ 、 $\mathbf{B}$ 和 $\mathbf{A}$ ，拍卖人根据设计的拍卖方案决定获胜者（包括获胜买方和获胜卖方），将中继节点分配给源节点，并确定获胜买方和获胜卖方的清算价格。设 $\mathcal{S}_w \subseteq \mathcal{S}$ 获胜买方的集合， $\mathcal{R}_w \subseteq \mathcal{R}$ 为获胜卖方的集合。令 $\sigma: \{i : \mathcal{S}_i \in \mathcal{S}_w\} \to \{j : \mathcal{R}_j \in \mathcal{R}_w\}$ 为拍卖人决定的中继节点分配。注意， $\sigma(\cdot)$ 实际上是从获胜买方索引到获胜卖方索引的一一映射。因此， $\sigma^{-1}(j)$ 是中继节点 $\mathcal{R}_j$ 所分配的源节点的索引。设 $P_b^i$ 为获胜买方 $\mathcal{S}_i$ 需要支付的价格。设 $P_s^j$ 为拍卖人支付给获胜卖方 $\mathcal{R}_j$ 的付款。则买方 $\mathcal{S}_i \in \mathcal{S}$ 的效用定义为：

相应地，卖方 $\mathcal{R}_j \in \mathcal{R}$ 的效用定义为：

本文中的符号总结见表2。

表二符号表

3.3 Economic Properties

拍卖方案的设计在很大程度上取决于所期望的特性。在下文中，我们介绍四种最常见的经济特性：

诚实性：如果对于每个买方（或卖方）而言，披露真实的私人估值（或成本）是占优策略，则该拍卖是诚实的。换句话说，无论其他参与者如何出价，任何买方（或卖方）都无法通过提交与其真实估值（或成本）不同的报价（或要价）来提高自身的效用。
个体理性（Individual Rationality）：若没有获胜的买方支付的价格超过其出价，且没有获胜的卖方获得的支付低于其要价，则该拍卖是个体理性的。即对所有 $s_i \in S_w$ 与 $r_j \in \mathcal{R}_w$ 有 $B_i^{\phi(i)} \;\geq\; P_i^b, \qquad A_j \;\leq\; P_j^s.$ 该性质确保了源节点与中继节点都有动力参与协作通信。
预算平衡（Budget Balance）：若所有买方的总支付金额不小于支付给所有卖方的总金额，则该拍卖是预算平衡的，即： $\sum_{s_i \in S_w} P_i^b \geq \sum_{r_j \in \mathcal{R}_w} P_j^s$
系统效率（System Efficiency）：若拍卖能优化所有参与者估值的总和，则该拍卖是系统高效的。在本文的上下文中，系统效率等价于总容量最大化。

3.4 Objective

设计一种同时满足前一节所述全部四种性质的拍卖方案是可取的。然而，文献[16]中的一个著名结果表明，即使不考虑个体理性，也不存在任何双重拍卖机制能够同时实现真实性、预算平衡和效率。我们的最终目标是设计一种拍卖方案，既能激励中继节点和源节点参与协作通信，又能防止任何代理通过操纵其出价或要价来操控市场。因此，在牺牲系统效率的情况下，优先设计具备前三种性质的拍卖方案具有最高重要性。这种方法论也被现有的多重拍卖广泛采用[3, 7, 10, 24]。

总之，我们的目标是设计一个用于协作通信（Cooperative Communications, CC）的真诚拍卖方案（TASC），记为： $\Psi = (S, \mathcal{R}, D, \mathbb{B}, A)$

其中，给定 $S, \mathcal{R}, D, \mathbb{B}, A$ 拍卖师需要确定：

获胜买方集合 $S_w$
获胜卖方集合 $\mathcal{R}_w$
中继分配映射 $\sigma$
每个买方的支付价格 $P_i^b$
以及每个卖方的支付金额 $P_j^s$

并满足以下条件：

对于每个买方 $s_i$ ，其效用 $U_i^b$ 在出价为 $V_i$ 时达到最大；
对于每个卖方 $r_j$ ，其效用 $U_j^s$ 在要价为 $C_j$ 时达到最大。

对于每个买方 $s_i$ ，有 $B_i^{\sigma(i)} \geq P_i^b,$
对于每个卖方 $r_j$ ，有 $A_j \leq P_j^s.$

- 预算平衡条件：
$\sum_{s_i \in S_w} P_i^b \geq \sum_{r_j \in \mathcal{R}_w} P_j^s.$

4. CHALLENGES OF COOPERATIVE COMMUNICATION AUCTION DESIGN

在本节中，我们阐述了设计诚实合作通信拍卖所面临的挑战。为了更好地理解这些挑战，我们展示了现有双重拍卖机制直接应用于合作通信拍卖时的失败情况。现有的双重拍卖机制有两种，即基于VCG的双重拍卖和McAfee双重拍卖。我们分别在第4.1节和第4.2节对这两种机制进行了分析。

4.1 基于 VCG 的双边拍卖

VCG（Vickrey–Clarke–Groves）可以保证真诚性。在基于 VCG 的双边拍卖中，赢家与买卖匹配的确定方式是使社会福利最大化： $W = \sum_{s_i \in S_w} \big( B_i^{\phi(i)} - A_{\phi(i)} \big)$

直观地，这可通过在二分图 $G = (S, \mathcal{R}, \mathcal{E}, \omega)$ 上求最大权匹配实现；其中若 $B_i^{j} > 0$ 则 $(s_i, r_j) \in \mathcal{E}$ 且边权 $\omega(s_i, r_j) = B_i^{j} - A_j.$ 记 $W^*$ 为最优值， $W^*_{-s_i}$ 为移除买方 $s_i$ 后的最优值， $W^*_{-r_j}$ 为移除卖方 $r_j$ 后的最优值。则每个赢家买方的支付为（式(3)）： $P_i^b = B_i^{\phi(i)} - ( W^* - W^*_{-s_i} ).$

每个赢家卖方获得的支付为（式(4)）： $P_j^s = A_j + ( W^* - W^*_{-r_j} ).$ 由此可见 $W^* - W^*_{-s_i} \ge 0,\; W^* - W^*_{-r_j} \ge 0$ 成立，因而个体理性成立；VCG 亦是真诚的。
但图 3 给出预算不平衡的反例： $W^* = 9,\; W^*_{-s_1} = 4,\; W^*_{-s_2} = 7,\; W^*_{-r_1} = 7,\; W^*_{-r_2} = 3,$

据此 $P_1^b = 10-(9-4) = 5,\quad P_2^b = 4-(9-7) = 2,$ $P_1^s = 2+(9-7) = 4,\quad P_2^s = 3+(9-3) = 9,$

拍卖师亏损 $(4+9) - (5+2) = 6.$ 这说明 VCG 双边拍卖不预算平衡，不适合直接用于协作通信。

图3：一个展示基于 VCG 的双边拍卖预算失衡的示例。与连边 $(s_i, r_j)$ 相关的两个数值分别为出价 $B_i^j$ 与权重 $\delta(s_i, r_j)$ 。加粗的蓝色连线表示最大权匹配。每个卖方节点旁边的数字是该卖方的要价

4.2 McAfee 双边拍卖

McAfee 拍卖假设拍卖物品同质：买方无差异偏好。因而每个买方仅报一个出价，每个卖方仅报一个要价。流程为：将买方出价按非增序、卖方要价按非减序排序：

$B_{i_1} \ge B_{i_2} \ge \dots \ge B_{i_n},\quad A_{j_1} \le A_{j_2} \le \dots \le A_{j_m}.$

找最大k使得

$B_{i_k} \ge A_{j_k}\quad \text{and}\quad B_{i_{k+1}} < A_{j_{k+1}}.$ 令 $t = \frac{B_{i_{k+1}} + A_{j_{k+1}}}{2}.$

结算价规则：

$\{\, P^b = P^s = t \text{ if } A_{j_k} \le t \le B_{i_k},\;\; P^b = B_{i_k},\; P^s = A_{j_k} \text{ otherwise} \,\}.$

该机制可同时满足真诚性、个体理性与预算平衡；但由于协作通信中的“中继—源”异质性强（不同中继对不同源的容量增益不同），同质物品假设不成立，因此 McAfee 机制不能直接应用于协作通信，需要进一步的机制设计改造。

5. 我们的拍卖方案

在本节中，我们提出了TASC，一种针对协作通信的诚实且计算高效的拍卖方案。我们首先简要概述其设计原理，然后详细描述该方案的两个主要阶段。我们通过一个示例来帮助理解TASC。接下来，我们证明TASC满足第3.4节末尾列出的三个性质。最后，我们证明TASC的时间复杂度为多项式时间 $\mathcal{O}(\mathcal{T} + l^3)$ ，其中 $\mathcal{T}$ 是中继分配算法的时间复杂度， $l = \min\{n, m\}$ 。

5.1 概述

尽管基于VCG的双重拍卖在表面上最接近我们所要设计的拍卖，但其预算失衡对拍卖人来说是不可接受的。相比之下，TASC的设计灵感来源于McAfee双重拍卖。TASC包含两个阶段：分配阶段和胜者确定与定价阶段。为了克服McAfee双重拍卖的局限性，我们在分配阶段应用了一种分配算法来寻找中继分配。在第二阶段，我们为卖方和买方战略性地确定清算价格，而不是简单地将出价和要价对齐，以避免在最终胜者选择中出现低效的中继分配。与McAfee双重拍卖类似，拍卖人向所有中标买方收取相同的价格，并向所有中标卖方支付相同的款项。

5.2 设计

我们现在详细描述TASC的设计。在分配阶段，我们需要设计一种新的中继分配算法，或者应用现有的中继分配算法，并要求其与买方的出价和卖方的要价无关。中继分配算法对出价或要价的依赖可能会使拍卖容易受到市场操纵的影响。我们在算法1中展示了分配阶段的流程。

根据具体场景，拍卖师可针对不同目的选择不同的分配算法（Φ(⋅)）。例如，为最大化总容量，可采用最大加权匹配算法；为最大化所有源节点中的最小容量，可采用文献[20]中的算法ORA；为最大化交易数量，则可使用最大匹配算法来实现。返回值包括候选中标买方 $S_c$ 、候选中标卖方 $R_c$ 以及分配 $\sigma$ 。

图4：更好的胜者确定与定价。选择蓝色虚点线中的边界对不会产生任何胜者对。选择红色虚线方框中的边界对会产生两个胜者对。

在胜者确定与定价阶段，我们将胜者确定与定价操作紧密集成。利用上一阶段得到的分配结果，一个直观的想法是应用McAfee双重拍卖来确定胜者和清算价格。然而，在寻找合适的卖方-买方对时进行简单匹配，并未考虑卖方与买方之间的映射关系。图 4 的例子表明，存在一种更好的方法来确定赢家与清算价格。我们不是只考虑买卖对 $s_{i_k}-r_{j_k}$ ，而是再执行两个步骤：首先，固定 $s_{i_k}$ ，寻找最大的 y 使得 $B_{i_k}^{\phi(i_k)} \ge A_{j_y}$ ；接着，固定 $r_{j_k}$ ，寻找最大的 x 使得 $B_{i_x}^{\phi(i_x)} \ge A_{j_k}$ 。我们比较两种结果并返回更优者。其详细算法见算法 2。

为便于说明，我们引入更多记号与概念：

记 S 为按买方在其被指派中继上的出价非增序排列得到的有序买方列表。
记 $\mathbb{R}$ 为按卖方要价非减序排列得到的有序卖方列表。
$S_k$ 表示 S 的前 k个买方所构成的子列表。
$\mathbb{R}_k$ 表示 \ $\mathbb{R}$ 的前 k 个卖方所构成的子列表。
$\Sigma(S,\mathbb{R})$ 表示由 S 与 $\mathbb{R}$ 诱导的匹配集合，即
$\Sigma(S,\mathbb{R})=\{(s_i,r_j):\, s_i\in S,\; r_j\in \mathbb{R},\; j=\sigma(i)\}.$
我们称拍卖师据以确定赢家与清算价格的买卖对为边界对（boundary pair）。在第 4 节的 McAfee 双边拍卖中， $s_{i_k}-r_{j_k}$ 即为一例。
由于赢家买方与赢家卖方是成对确定的，我们称 $(s_i, r_{\sigma(i)})$ 或 $(s_{\sigma^{-1}(j)}, r_j)$ 为赢家对（winning pair）。

TASC 的主算法见 Algorithm 3。

5.3 一个说明性示例

我们使用一个简单的示例来说明TASC的思想。可实现容量矩阵，同时也是出价矩阵，如表3(a)所示，而要价向量如表3(b)所示。

表3：一个包含5个源-目的地对和7个中继节点的例子。

在指派阶段，我们假设拍卖师采用最大权匹配算法。得到的指派在表 3(a) 中以高亮标注，例如，卖方 r1 被指派给买方 s1。我们把该指派画成二分图，如图 5，其中各节点按其出价或要价排序。对应序列为S = ⟨ s1, s4, s5, s2, s3 ⟩，ℝ = ⟨ r6, r1, r5, r4, r7 ⟩。

图5：展示TASC中胜者确定与定价阶段的二分图。

在“赢家确定与定价”阶段，拍卖师首先得到 k = 4。随后考察配对 s2–r7 与 s3–r4，并选择 s2–r7 作为边界对。因此，赢家对包括 (s1, r1)、(s4, r4) 与 (s5, r6)。每个赢家买方需支付的价格为 $P^b = 8$ ，每个赢家卖方获得的支付为 $P^s = 7$ 拍卖师的利润为 $3 \times (8 - 7) = 3$ 。

5.4 经济性质的证明

在给出 TASC 的详细设计之后，我们现在证明第 3.4 节所述的目标经济性质。

定理 1（个体理性）。 TASC 是个体理性的。□

证明:对任一赢家买方 $s_i \in S_w \in S_x$ ，满足 $B_i^{\phi(i)}\geqslant B_x^{\phi(x)} = P^b$ 。对卖方同理。证毕。

定理 2（预算平衡）。 TASC 是预算平衡的。□

证明。 由指派可知 $|S_w| = |\mathcal{R}w|$ 。对任一赢家买方 $s_i$ ∈ $S_w$ 及其对应赢家卖方 $r{\phi(i)}$ ∈ $\mathcal{R}w$ ，均有 $P_i^b = P^b = B_x^{\phi(x)} \geqslant A_y = P^s = P_j^s$ 。于是
$\sum_{s_i \in S_w} P_i^b - \sum_{r_j \in \mathcal{R}_w} P_j^s = |S_w|(P^b - P^s) \ge 0$ 。证毕。

定理 3（真诚性）。 TASC 是真诚的。□

在证明该定理之前，我们先给出一系列引理：

我们在引理 1 中表明每个买方的拍卖结果部分独立于其自身投标；

在引理 2（对应买方）与引理 3（对应卖方）中表明赢家确定过程分别具有投标单调性与要价单调性；

在引理 4（买方）与引理 5（卖方）中表明定价分别独立于其自身投标/要价；

最后在引理 6（买方）与引理 7（卖方）中证明 TASC 的真诚性。

这里以后，我们用“波浪号”来区分含义相同但取值不同的记号；例如，

例如：和 $B_i$ 表示买方 $s_i$ 的两个不同的投标向量。
另外，我们定义三个比较算子：>_j、=_j、<_j。约定如下：

当时，记为 $\tilde{B}_i >_j B_i$ ；
当 $\tilde{B}_i^j = B_i^j$ 时，记为 $\tilde{B}_i =_j B_i$ ；
当 $\tilde{B}_i^j < B_i^j$ 时，记为。
引理 1。 若买方 $s_i$ 在指派阶段被指派到中继 $r_{\phi(i)}$ ，则 $s_i$ 的拍卖结果与其投标向量 $B_i^{-\phi(i)}$ 无关。等价地，若 $B_i^{\phi(i)} = \tilde{B}_i^{\phi(i)}$ ，则 $\Psi = (S, \mathcal{R}, D, \mathbb{B}\,|_i\, B_i, A)$ 与 $\tilde{\Psi} = (S, \mathcal{R}, D, \mathbb{B}\,|_i\, \tilde{B}_i, A).$ 的结果相同。□

证明（要点）。分配阶段与出价和要价无关。在中标判定与定价阶段（算法2）中，显然中标判定以及向买方收取的价格仅取决于买方对 $r{\phi(i)}$ 的出价以及卖方的要价 A。因此，我们的引理成立。由于篇幅限制，我们将在以下引理中证明关于买方的性质，并仅对卖方证明一个性质。其他关于卖方的性质可采用与我们证明买方性质类似的方式进行证明。

引理 2。 如果买方 $s_i$ 在 $\Psi = (S, \mathcal{R}, D, B|_i B_i, A)$ 中以出价 $B_i$ 获胜，那么当其出价满足 $\tilde{B}_i >_{\phi(i)} B_i$ 时，它在 $\tilde{\Psi} = (S, \mathcal{R}, D, B|_i \tilde{B}_i, A)$ 中也能获胜。

证明。 在指派阶段，由于中继指派算法与出价和要价无关，如果 $s_i$ 在 $\Psi$ 中被指派到某个中继节点，那么它在 $\tilde{\Psi}$ 中也会被指派到相同的中继节点。令 $p_i$ 与 $\tilde{p}_i$ 分别表示 $s_i$ 在 S 和 $\tilde{S}$ 中的位置（示意见图 6）。由于 $\tilde{B}_i^{\phi(i)} > B_i^{\phi(i)}$ ，因此在位置 $p_i$ 之后，S 与 $\tilde{S}$ 的顺序完全相同。此外，我们知道两者中第 4 行得到的 k 的取值也相同。因此，在赢家确定阶段，中依然会选取 $s_x$ 与 $r_y$ 作为边界对，这意味着买方 $s_i$ 在 $\tilde{\Psi}$ 中同样是赢家。

图6：引理2的说明

引理 3。 如果卖方 $r_j$ 在 $\Psi = (S, \mathcal{R}, D, B, A|_j A_j)$ 中以要价 $A_j$ 获胜，那么当其要价满足 $\tilde{A}_j < A_j$ 时，它在 $\tilde{\Psi} = (S, \mathcal{R}, D, B, A|_j \tilde{A}_j)$ 中也能获胜。□

证明。 由于中继指派算法与出价和要价无关，在 $\Psi$ 与 $\tilde{\Psi}$ 中都被指派给同一个买方 $s_{\phi^{-1}(j)}$ 。令 $q_i$ 与 $\tilde{q}_i$ 分别为 $r_j$ 在 $\mathbb{R}$ 与 $\tilde{\mathbb{R}}$ 中的位置（示意见图 7）。由于，因此在位置 $q_i$ 之后，与 $\tilde{\mathbb{R}}$ 的顺序完全相同。此外，我们知道两者中第 4 行得到的 k 的取值也相同。因此，在赢家确定阶段， $\tilde{\Psi}$ 中依然会选取 $s_x$ 与 $r_y$ 作为边界对，这意味着卖方 $r_j$ 在 $\tilde{\Psi}$ 中同样是赢家。

图7：引理3的说明

引理 4。 如果在 $\Psi = (S, \mathcal{R}, D, B|_i B_i, A) and \tilde{\Psi} = (S, \mathcal{R}, D, B|_i \tilde{B}_i, A)$ 中分别以 $B_i$ 与获胜，则其被收取的价格相同，即 $P^b = \tilde{P}^b .$

证明。 由引理 1，若买方 $s_i$ 获胜，则其投标向量的其他分量 $B_i^{-\phi(i)}$ 不会改变拍卖结果或被收取的价格。因此，不失一般性，假设 $\tilde{B}_i >_{\phi(i)} B_i$ 。如引理 2 的证明所述， $s_x$ 与 $r_y$ 在 $\Psi$ 与中都会被选作边界对。按定价策略可知，买方 $s_i$ 在两种情况下被收取相同价格: $P^b = \tilde{P}^b = B_x^{\phi(x)} .$

引理 5。 如果 $r_j$ 在 $\Psi = (S, \mathcal{R}, D, B, A|_j A_j)$ 与 $\tilde{\Psi} = (S, \mathcal{R}, D, B, A|_j \tilde{A}_j)$ 中分别以 $A_j$ 与 $\tilde{A}_j$ 获胜，则其获得的支付相同，即 $P^s = \tilde{P}^s .$

表4：引理6的证明逻辑。w表示它获胜，l表示它失败。

引理 6。 TASC 对买方是真诚的。

证明。 我们通过证明：不存在任何买方能够通过提交与其真实估值不同的投标向量来提升效用，即对任意 $B_i \ne V_i$ 均有 $\tilde{U}_i^b \le U_i^b ,$

其中 $\tilde{U}_i^b$ 与分别是 $s_i$ 在出价 $B_i$ 与 $V_i$ 时的效用。我们逐一考察表 4 所示的所有可能情况。

情况 1：。

由引理 1 可知，当 $B_i =_{\phi(i)} V_i$ 时， $s_i$ 在两次拍卖中被收取的价格 $P^b$ 相同。因此 $\tilde{U}_i^b = V_i^{\phi(i)} - P^b = U_i^b .$

情况 2：。

由引理 2 可知，不可能出现“ 用出价获胜、改为反而失败”的情形。因此存在三种子情形：

$s_i$ 用 $V_i$ 与 $B_i$ 都获胜；
用 $B_i$ 获胜而用 $V_i$ 失败；
$s_i$ 两者都失败。

对于 1)，由引理 4， $s_i$ 被收取相同价格，因此 $\tilde{U}_i^b = U_i^b = V_i^{\phi(i)} - P^b .$

对于 3)，由于两次都失败， $\tilde{U}_i^b = U_i^b = 0 .$

现关注 2)。既然 $s_i$ 用 $B_i$ 获胜而用 $V_i$ 失败，则有 $\tilde{P}^b = B_{\tilde{x}}^{\phi(\tilde{x})} \ge V_i^{\phi(i)} ,$

其中 $\tilde{x}$ 是中第 7 行所选买方的索引。于是 $\tilde{U}_i^b = V_i^{\phi(i)} - \tilde{P}^b \le 0 = U_i^b .$

情况 3：。

由引理 2 可知，不可能出现“ $s_i$ 用 $B_i$ 获胜、改为 $V_i$ 失败”的情形。因此亦有三种子情形：

$s_i$ 用 $V_i$ 与 $B_i$ 都获胜；
用 $B_i$ 失败而用 $V_i$ 获胜；
$s_i$ 两者都失败。

对于 1) 与 3)，与情况 2 的分析相同，可得 $\tilde{U}_i^b = U_i^b .$

对于 2)，显然 $\tilde{U}_i^b = 0 \quad \text{and } \quad U_i^b \ge 0 .$

我们已证明：买方无法通过提交与真实估值不同的投标向量来提升其效用。证毕。

引理 7。 TASC 对卖方是真诚的。

定理 3 的证明。 由引理 6 与引理 7 可知，TASC 对买方与卖方均真诚，从而 TASC 真诚。

5.5 时间复杂度

定理 4。 TASC 的时间复杂度为 $O(T + l^3) ,$ 其中 T 是中继指派算法的时间复杂度，。

证明。 对于指派阶段，时间复杂度取决于所使用的中继指派算法。例如，最大权匹配算法的复杂度为 $O\big((n+m)^2 \log(n+m) + (n+m)\,n\,m\big) ,$

算法 ORA 的复杂度为 $O(n\,m^2) ,$ 而最大匹配算法的复杂度为 $O\big(\sqrt{n+m}\cdot n\,m\big) .$

一般地，我们用 T 表示中继指派算法的时间复杂度。在赢家确定与定价阶段，由于输入是指派结果，买方数量与卖方数量相等。显然，该数量小于。由于最多检查 $O(l)$ 个买卖对，且计算赢家对需要，因此该阶段的复杂度为 $O(l^3)$ 。于是，TASC 的总体时间复杂度为。

6. 数值结果

在本节中，我们通过大量实验来评估TASC的性能，并研究其对系统效率的经济影响。

6.1 实验设置（Experiment Setup）
我们考虑一个无线网络，节点在一个 $1000 \times 1000$ 的正方形区域内随机分布。我们沿用文献 [20] 中相同的参数设置。令所有信道的带宽为 $22\,\text{MHz}$ 。所有无线节点的发射功率为。在传输模型中，我们假设路径损耗指数为 4，噪声为。在协作通信中，使用 DF 模式。我们将买方数量 n 固定为 100，并将卖方数量 m 从 50 到 150 以步长 10 变化。对于每一种设置，我们随机生成 1000 个实例并对结果取平均。所有测试在一台 Linux 个人电脑上运行，处理器为 $2.00\,\text{GHz}$ 的 Intel Pentium，内存为 $1.5\,\text{GB}$ 。

在拍卖方面，我们假设买方的出价在区间 $(0, V_{\max}]$ 上均匀随机分布，其中 $V_{\max}$ 在大多数实验中设为 4，并在考察“出价分布对系统效率影响”的实验中取不同的值。同样地，我们假设卖方的要价在区间 (0, 1] 上均匀随机分布。

实验中的性能度量包括：参与者效用、拍卖师利润、总容量、成功交易数以及所有买方中的最小容量。在所有实验中，我们用 MWM 表示最大权匹配算法，用 MM 表示最大匹配算法。

6.2 TASC 的真诚性（Truthfulness of TASC）
为验证 TASC 的真诚性，我们随机选取一个买方和一个卖方，考察当他们采用不同的出价或要价时，其效用如何变化。对于买方的结果见图 8(a)–(c)，对于卖方的结果见图 8(d)–(f)。我们注意到：在每一种“真实估值与指派算法”的组合下，没有任何买方（对应地，卖方）能够通过不如实出价（对应地，要价）来提升其效用。

6.3 对利润的影响（Impact on Profit）
尽管盈利并不是设计 TASC 的目标，但仍有必要研究不同指派算法对利润的影响。图 9 绘出了在采用不同中继指派算法时拍卖师的利润。第一个观察是：对于三种不同的中继指派算法，利润都比较低，最大利润小于 1。由于我们确定价格与支付的方式，在大多数情况下有

因此，在大多数实例中利润为 0。另一个观察是：随着卖方数量的增加，利润下降。这是因为有越来越多的卖方参与拍卖时，出现的概率更高。

图9：拍卖人的利润

图8：在具有不同分配算法的拍卖中，买方（(a)-(c)）和卖方（(d)-(f)）的效用，其中 $n = m = 100$ 。在每一场拍卖中， $V$ 是买方的真实估值， $C$ 是卖方的真实成本。对于买方的真实估值 $V$ 和卖方的真实成本 $C$ ，分别测试了两个不同的值。对于每一个不同的真实估值（或成本），买方（或卖方）无法通过提交与其真实估值（或成本）不同的出价（或要约）来提高其效用。

6.4 对系统效率的影响

根据系统性能要求的不同，系统效率可以是总容量、成功交易的数量，以及所有参与买方中的最小容量。显然，由于拍卖师无法让所有参与代理都成为赢家，因此与纯粹的中继分配相比，性能不可避免地会有所下降，除非采用带有ORA的拍卖机制。当以最小容量作为系统效率时，TASC不会降低性能，因为胜者决策是基于最优结果做出的。为了捕捉经济因素对系统效率的影响，我们在图10(a)中绘制了TASC相对于纯粹中继分配算法的性能下降情况。令人惊讶的是，无论对于MWM还是MM，这种性能下降均与卖家数量无关。接下来，我们研究了出价分布对系统效率的影响。图10(b)展示了在不同 $V_{\text{max}}$ 值下，TASC分别采用MWM和MM时的性能下降情况。我们观察到，当最大出价值 $V_{\text{max}}$ 增加时，TASC相对于纯粹中继分配算法的性能下降幅度减小。换句话说，当买方对中继节点服务的真实估值较高时，TASC能够在显著不降低系统效率的情况下实现所有所需的经济特性。

6.5 运行时间

为了验证我们在第5.5节中对时间复杂度的分析，我们在图11中展示了TASC在不同分配算法下的运行时间。我们注意到，对于MWM和ORA，随着卖家数量的增加，运行时间也随之增加。然而，对于MM，运行时间先增加，然后在 $m = n$ 之后趋于稳定。这是因为即使 $m$ 持续增加，匹配的最大数量也受到 $n$ 的限制。

图10：TASC相对于纯中继分配算法的系统性能下降

图11：TASC的运行时间，其中n = 100，m从50到150变化。（a）和（b）使用同一组结果，而（b）为了清晰起见，展示了未使用MWM的结果。

7. 结论

本文设计了TASC，一种用于协作通信的诚实拍卖方案。为了激励无线设备参与为其他设备中继流量，TASC允许潜在的中继节点对其中继服务进行报价，并要求感兴趣的源节点对这些报价进行出价。通过精心的设计，TASC明确地促使卖方和买方提交其真实估值，从而消除了市场操纵的担忧以及为他人制定策略所带来的开销。同时，TASC还满足个体理性与预算平衡特性。此外，TASC可以使用任意中继分配算法以满足不同的系统性能需求。广泛的实验结果证实了我们对TASC的理论分析，并表明TASC能够在系统效率有限下降的情况下实现所有所需的经济特性。

论文阅读/博弈论/拍卖：《Truthful Auction for Cooperative Communications》

摘要：