通用的多元抵制假名的云计算拍卖机制

游坤，王钦辉，李鑫

通用的多元抵制假名的云计算拍卖机制

游坤1，王钦辉2*，李鑫3

（1.金陵科技学院 软件工程学院，南京 211169； 2.陆军指挥学院 训练管理系，南京 210045； 3.南京航空航天大学 计算机科学与技术学院，南京 211106）（ ∗ 通信作者电子邮箱qinhuiwang@aliyun.com）

针对云环境下资源拍卖机制设计问题，研究设计了一种更通用的多元抵制假名拍卖机制（GFAITH）。首先形式化定义了系统模型，其次围绕诚信和抵制假名的设计目标，证明了当考虑用户需求多样性时，会出现新的作弊形式——需求减少作弊，它将破坏诚信属性和抵制假名属性，且实验结果表明它将严重影响系统性能。据此，提出了GFAITH机制，从用户预处理、预分配与定价、抵制需求减少作弊三个阶段实现设计目标，并验证了GFAITH的资源分配是可行的，而且能够抵制假名。实验结果表明，GFAITH能从利润和社会财富等指标上有效保证系统的性能，验证了该机制的有效性和效率。

云计算；机制设计；诚信；抵制假名；拍卖

0 引言

云计算是一种能够提供按需访问共享资源池的模型，这些资源包括CPU、存储、内存等，且通常被划分为不同类型的虚拟机（Virtual Machines， VM），用户按需访问，并支付相应的费用［1］。云计算的灵活性和高可靠性带来了巨大的经济效益，但一个重要挑战是需要共同解决资源管理与定价问题，以提高系统效率并激励用户和提供商参与［1］。

拍卖被广泛应用于销售珍贵的商品，这引发了一波研究设计云资源拍卖机制的浪潮［2-3］。然而参与拍卖的投标人多是自私的，他们总是试图通过操纵标价来获利。因此，为充分利用云资源，拍卖机制必须阻止投标人作弊，而且鼓励他们向拍卖人透露他们对竞拍资源的真实估值。为解决这一问题，通常设计诚信（truthful）拍卖机制来阻止这种单纯的投标作弊，如文献［4-6］。然而，当可能出现假名投标时（即投标人以多个假名进行投标），诚信拍卖机制会失效。通过这种方式，不诚实的投标人能够通过虚假名称来投标，实现操纵拍卖结果的目标，这将导致机制不公平和效率损失。事实上，假名投标在互联网上运行的各类拍卖中极易出现［7-8］，因为此情况下投标人可以很容易地生成多个假名，且不易被发现。由于云拍卖机制总是在互联网上运行，导致容易出现同样的作弊行为，比如通过多个邮件注册不同的账号来实现假名投标。然而现有的诚信拍卖机制并不能应对这类新型作弊方式。因此，设计拍卖机制时既要保证诚信，还需要保护拍卖免受假名作弊，即需要确保机制是抵制假名（false-name-proof）的。

一方面，已有许多用于云资源分配的诚信拍卖机制，但它们不是抵制假名的；另一方面，已有的抵制假名拍卖机制并不能直接应用于云拍卖，这是因为云拍卖的特殊性，即需要处理VM的异构性（有多种类型的VM实例、每种类型都有多个单元）和用户的多样性（用户对资源的需求偏好不同）。现有抵制假名拍卖机制通常假设用户是专一（single-minded）的，即用户所请求资源要么被全部满足，要么什么也没有。一旦考虑用户需求的多样性，将出现一种新的作弊方式——需求减少（Demand-Reduction， DR）作弊。该作弊方式将破坏机制的抵制假名属性，并严重影响拍卖系统性能。

为解决这一问题，本文考虑一个典型的VM实例拍卖场景，并设计一个既诚信又抵制假名投标的通用多元拍卖机制（General multi-unit FAlse-name-proof auction mechanism for vIrTual macHine allocation， GFAITH）。该系统中，投标人将他们的标价密封提交给拍卖师，以请求具有多个单元的不同类型的VM实例。GFAITH包括三个阶段算法：第一阶段对用户进行预处理；第二阶段对处理后的用户进行预分配和预定价；第三阶段基于预分配的结果阻止DR作弊操作。

本文的主要工作如下：

1）云拍卖场景下，考虑用户的多样性将出现新的作弊方式——DR作弊，证明了该作弊方式将破坏现有机制的抵制假名属性，并将严重影响系统性能。

2）设计一种更通用的多元云拍卖机制GFAITH，并从理论上证明它既能保证诚信，又是抵制假名的。

3）通过实验验证GFAITH能有效保证系统的性能。

1 相关工作

为更高效管理云资源，如何设计高效的拍卖机制问题吸引了广泛的研究兴趣［9］。Wang等［6］建议将信任的第三方作为拍卖人进行利润最大化的多轮拍卖；Samimi等［10］则提出了一个组合双向拍卖机制；Hosseinalipour等［5］利用拍卖机制研究了云提供商和云管理者之间的交互问题。然而，这些工作主要聚焦于分配的公平与效率，并未考虑用户的策略行为性。

Zhang等［11］针对ad-hoc Cloudlet场景，调度员和移动设备（Mobile Devices， MD）分别扮演拍卖师和投标人的角色，并提出了一种基于Lyapunov优化和VCG（Vickrey-Clarke-Groves）的在线拍卖机制。Patel等［12］提出在线双重拍卖，以实现基础设施即服务（Infrastructure as a Service， IaaS）云中能源、收入和性能之间的多目标权衡。他们采用基于加权二分匹配的算法来确定获胜者，并采用VCG驱动算法来确定支付方式。文献［5］中研究客户和云管理者之间的交互，并设计了基于期权的顺序拍卖。近年来，一些研究工作设计了较多的双向拍卖机制，如文献［2-4］；同时一些已经向移动边缘计算拓展，如文献［13-14］中设计了诚信拍卖机制。

然而，这些研究仅考虑了诚信属性，并不能应对假名投标的作弊。文献［15］中研究了经济学组合拍卖中的假名投标，分析了假名投标获利的形式和流行性，并在后续相关研究中提出了一些抵制假名的拍卖机制。但目前仍少有研究工作对云拍卖中的假名投标进行研究。文献［8］中首次提出了云计算中运行灵活高效的抵制假名拍卖机制——虚拟机分配的抵制假名拍卖机制（False-name-proof Auction for vIrTual macHine allocation， FAITH），但它仅适用用户是“专一”的情况，并未考虑用户需求的多样性。

不同于以往研究工作，本文考虑更通用的情况：即考虑了云资源的异构性（多种类型与多种数量）与用户的需求的多样性，用户参与拍卖需求不再是“专一”的，即可以被部分满足。在这种情况下，证明将出现一种新的作弊方式——DR作弊，并通过实验证明这一作弊形式将严重影响系统性能。据此，本文研究设计了更通用的拍卖机制GFAITH。

2 预备知识

2.1　系统模型

然而“专一性”假设与用户的多样性相悖：有些用户仅需要部分资源就能满足需求，如文本处理［18］。对此，本文考虑更一般的情况，即用户需求类型存在多种可能，并分别讨论所对应的估值函数。根据文献［18］的研究，通常将应用类型划分为三类：资源敏感型应用、资源不敏感型应用和介于两者之间的类型，分别对应以下估值类型：超加性（super-additive）、次加性（sub-additive）和一般性。

超加性意味着当投标人的要求不能完全满足时，他们的效用会降低。这是有道理的，因为当投标人需要资源应用于一些棘手的应用场景时（如实时视频流应用），他们希望所请求的资源全部满足，否则将影响服务质量。值得注意的是，用户是专一的情况可视为该类型的特殊情况。

次加性意味着当投标人的请求得到部分满足时，分配更多的资源并不会显著增加效用。这种类型与投标人对一些简单的应用程序（例如文件/文本传输应用程序）需要较低资源的情况相吻合。

类型Ⅲ：一般情况。此时估值函数既不是递增型也不是递减型。幸运的是，根据文献［19］的研究，一般情况下的估值函数可以表示为次加性的情况，但唯一的限制条件是估值函数是非递减的，且在自由处置的普遍假设下可以自动满足。

2.2　设计目标

首先给出拍卖设计的两个关键属性的定义：诚信和抵制假名，这是本文拍卖机制的主要设计目标。

3 挑战

本文首先会证明：当考虑用户的多样性时，即用户的需求可被部分满足时，将出现新的作弊形式，这种新作弊形式将使现有的抵制假名拍卖机制失效；其次，通过仿真实验证明这种新的作弊方式将大幅影响拍卖系统的性能。

3.1　研究方法

选择FAITH［8］作为典型的云拍卖机制进行研究。主要基于以下考虑：一是FAITH是典型的抵制假名拍卖机制；二是FAITH同样考虑了云拍卖的特殊属性（资源的异构性）。

首先简要地介绍FAITH机制的工作原理，包括定价算法和分配算法两部分，注意两个算法运行之前，需要按单位权重标价从高到低对所有用户进行排序。

3.2　新作弊方式

当用户不再是专一的，而可以接受需求被部分满足时，一种新的作弊方式出现了，称为DR作弊。换句话说，当用户的请求可以部分满足时，它可以选择需求欺骗以求获利。

3.3　新作弊方式对系统的影响

运行实验100次，并对结果求平均，图1绘制了DR作弊方式使投标人的效用增加，其中纵轴表示累积分布函数（Cumulative Distribution Function， CDF）。从图1中可观察到近20%的作弊用户可以通过DR作弊获利。进一步，图2通过显示拍卖系统性能损失率（包括利润损失和社会财富损失）与DR作弊用户数量的关系，表明了DR作弊影响FAITH的利润和社会财富。从图2可以看出，DR作弊不仅会激励投标人选择作弊，而且还会损害系统性能。这也促使我们设计新机制来应对DR作弊。

图1　用户通过DR作弊在FAITH里提升效用

基于上述分析，本文不再限制用户需求的类型，而是考虑用户需求的多样性，并引入虚拟用户的概念，完成用户的预处理，再通过控制DR作弊设计抵制假名拍卖机制。

图2　DR作弊影响FAITH的利润和社会财富

4 机制设计

4.1　用户类型分析

首先分析不同类型的用户，分别对应三种估值函数：

1）类型Ⅰ的用户。直观地说，对于类型Ⅰ的投标人，他们没有动机使用多个虚假名称单独请求VM实例，因为较低的请求总是会产生较低的投标估值。因此，只需要在这种情况下阻止DR作弊。

综上，以下分析只需要涵盖类型Ⅰ和类型Ⅱ的投标人即可。

图3　类型Ⅱ的估值函数

4.2　主要算法

算法1 GFAITH。

//阶段1：用户预处理

//阶段2：预分配

//阶段3：阻止DR作弊

阶段1：用户预处理。

阶段2：预分配与定价。

阶段3：抵制DR作弊。

4.3　性质证明

首先证明GFAITH的资源分配是可行的。

定理1GFAITH满足分配的可行性。

证明GFAITH分配是基于第二阶段预分配的结果进行的，而第二阶段的分配与定价算法与FAITH算法一致，因此GFAITH并不违背预分配的可行性。 证毕。

为证明GFAITH满足抵制假名投标属性，首先证明以下引理。

证明 类似地，根据文献［8］中引理1，易得以下两式：

分别考虑两类用户：

用户选择DR作弊的情况是类似的，此处证明过程省略。 证毕。

如果用户不选择DR作弊，分别考虑以下情况：

情况Ⅰ：降低报价获得更少的资源。由于最终要支付的价格计算与自身的报价无关。因此，这种情况下，因为获得分配的资源减少，效用将下降。

情况Ⅱ：降低报价获得更多的资源。这种情况不存在，因为虚拟用户中单位权重标价高的首先获得分配，而GFAITH从不释放资源再分配。

情况Ⅲ：提高报价获得更少的资源。由于待支付的定价计算与自身的报价高低无关，它的效用在获得更少的资源情况下也将下降。

综合上述所有情况，在没有DR作弊时，引理成立。

考虑DR作弊的情况，证明过程类似上述推导，故此处省略。 证毕。

定理2 GFAITH是抵制假名的。

证明 根据引理3和引理4，得证。

5 性能评估

5.1　实验方法

5.2　实验结果

为更好测试GFAITH性能，将GFAITH与经典方法FAITH比较。使用利润和社会财富作为性能评价指标：利润是所有赢家定价之和，社会财富是所有赢家的出价之和。

实验结果如图4、5所示。从图中可以看出，GFAITH比FAITH性能稍差，但差距控制在8%以内。这是因为DR作弊会减少分配的资源，从而减少所产生的社会福利和收入，这是控制DR作弊、减少其影响系统性能所做出的牺牲。相对于20%的性能损害，这是值得的。值得注意的是，当没有DR作弊时，GFAITH表现更好。

更进一步，通过计算机制的运行时间来评估评估机制的计算开销。在带有Intel Core i5-2520 CPU 2.5 GHz的Windows 7中，使用Matlab 2005b实现了这些机制，图6是实验结果，结果表明FAITH和Modified-IR具有相似的成本，因为它们具有相同规模的计算复杂度。Modified-IR是基于文献［21］提出的一种名为迭代缩减（Iterative Reducing， IR）的单项目多单元抵制假名机制［8］，它的性能严重依赖于保留价格（reservation price）。然而如果保留价格不能精细确定，拍卖机制的性能可能会非常差。

相比之下，为了支持更通用的范围请求投标，GFAITH消耗更多计算开销来防止DR作弊，但这种增加的开销仍然是线性的。

图4　GFAITH的社会财富随VM实例数量的变化趋势

图5　GFAITH的利润随VM实例数量的变化趋势

图6　GFAITH的时间开销

6 结语

本文研究了云计算环境下抵制假名拍卖机制设计问题。现有机制仅支持单一请求格式，当考虑用户需求多样性时，证明了新的作弊形式——DR作弊将破坏抵制假名属性和严重影响系统性能。基于此，研究设计了一种更通用的多元拍卖机制GFAITH，支持多种类型用户参与投标，并从理论上证明了GFAITH既满足诚信属性又能抵制假名，能在防DR作弊的情况下有效保证系统的性能。下一步工作，可研究允许投标人同时谎报总需求和估值函数的问题，或者扩展至双向拍卖机制。

[1] HASHEM I A T， YAQOOB I， ANUAR N B， et al. The rise of “big data” on cloud computing： review and open research issues［J］. Information Systems， 2015， 47： 98-115.

[2] BARANWAL G， VIDYARTHI D P. A fair multi-attribute combinatorial double auction model for resource allocation in cloud computing［J］. Journal of Systems and Software， 2015， 108： 60-75.

[3] KUMAR D， BARANWAL G， RAZA Z， et al. A systematic study of double auction mechanisms in cloud computing［J］. Journal of Systems and Software， 2017， 125： 234-255.

[4] KUMAR D， BARANWAL G， RAZA Z， et al. A truthful combinatorial double auction-based marketplace mechanism for cloud computing［J］. Journal of Systems and Software， 2018， 140： 91-108.

[5] HOSSEINALIPOUR S， DAI H. A two-stage auction mechanism for cloud resource allocation［J］. IEEE Transactions on Cloud Computing， 2021， 9（3）： 881-895.

[6] WANG Q， GUO S， LIU J， et al. Profit maximization incentive mechanism for resource providers in mobile edge computing［J］. IEEE Transactions on Services Computing， 2022， 15（1）： 138-149.

[7] YOKOO M， SAKURAI Y， MATSUBARA S. The effect of false-name declarations in mechanism design： towards collective decision making on the internet［C］// Proceedings of the 20th IEEE International Conference on Distributed Computing Systems. Piscataway： IEEE， 2000： 146-153.

[8] WANG Q， YE B， TANG B， et al. eBay in the clouds： false-name-proof auctions for cloud resource allocation［C］// Proceedings of the IEEE 35th International Conference on Distributed Computing Systems. Piscataway： IEEE， 2015： 153-162.

[9] SHARGHIVAND N， DERAKHSHAN F， SIASI N. A comprehensive survey on auction mechanism design for cloud/edge resource management and pricing［J］. IEEE Access， 2021， 9： 126502-126529.

[10] SAMIMI P， TEIMOURI Y， MUKHTAR M. A combinatorial double auction resource allocation model in cloud computing［J］. Information Sciences， 2016， 357： 201-216.

[11] ZHANG D， TAN L， REN J， et al. Near-optimal and truthful online auction for computation offloading in green edge-computing systems［J］. IEEE Transactions on Mobile Computing， 2020， 19（4）： 880-893.

[12] PATEL Y S， MALWI Z， NIGHOJKAR A， et al. Truthful online double auction based dynamic resource provisioning for multi-objective trade-offs in IaaS clouds［J］. Cluster Computing， 2021， 24（3）： 1855-1879.

[13] ZHOU H， WU T， CHEN X， et al. Reverse auction-based computation offloading and resource allocation in mobile cloud- edge computing［J］. IEEE Transactions on Cloud Computing， 2022（Early Access）： 1-15.

[14] SU Y， FAN W， LIU Y， et al. A truthful combinatorial auction mechanism towards mobile edge computing in Industrial Internet of Things［J］. IEEE Transactions on Cloud Computing， 2023， 11（2）： 1678-1691.

[15] YOKOO M， SAKURAI Y， MATSUBARA S. The effect of false-name bids in combinatorial auctions： new fraud in internet auctions［J］. Games and Economic Behavior， 2004， 46（1）：174-188.

[16] Microsoft. Azure［EB/OL］. ［2022-07-30］.https：//azure.microsoft.com/zh-cn/.

[17] LEHMANN D， O’CALLAGHAN L I， SHOHAM Y. Truth revelation in approximately efficient combinatorial auctions［J］. Journal of the ACM， 2002， 49（5）： 577-602.

[18] WANG Q， YE B， LU S， et al. A truthful QoS-aware spectrum auction with spatial reuse for large-scale networks［J］. IEEE Transactions on Parallel and Distributed Systems， 2014， 46（1）： 2499-2508.

[19] TERADA K， YOKOO M. False-name-proof multi-unit auction protocol utilizing greedy allocation based on approximate evaluation values［C］// Proceedings of the 2nd International Conference on Autonomous Agents and Multiagent Systems. Richland， SC： International Foundation for Autonomous Agents and Multiagent Systems， 2003： 337-344.

[20] MAS-COLELL A， WHINSTON M D， GREEN J R. Microeconomic Theory［M］. Oxford ： Oxford University Press， 1995： 493-502.

[21] YOKOO M， SAKURAI Y， MATSUBARA S. Robust multi-unit auction protocol against false-name bids［C］// Proceedings of the 17th International Joint Conference on Artificial Intelligence - Volume 2. San Francisco： Morgan Kaufmann Publishers Inc.， 2001： 1089-1094.

General multi-unit false-name-proof auction mechanism for cloud computing

YOU Kun1， WANG Qinhui2*， LI Xin3

（1，，211169，；2，，210045，；3，，211106，）

Aiming at the problem of resource auction mechanism in cloud environment， a more General multi-unit FAlse-name-proof auction mechanism for vIrTual macHine allocation （GFAITH） was studied and designed. First， the system model was formally defined. Then， around the design goals of being truthfulness and false-name-proof， it was proved that when considering the diversity of user demands， a new form of cheating， Demand-Reduction （DR） cheating， would emerge， which could destroy the truthful and false-name-proof properties， and the experimental results show that it would seriously affect the system performance. Based on the above， the GFAITH was proposed to achieve the design goals in three stages： user pre-processing， pre-allocation and pricing， and resisting demand reduction cheating. It is theoretical proved that the resource allocation of GFAITH is feasible and able to resist false-name-proof. Experimental results show that GFAITH can effectively guarantee the performance of the system from indicators such as revenue and social wealth， verifying the effectiveness and efficiency of the proposed mechanism.

cloud computing; mechanism design; truthfulness; false-name-proof; auction

1001-9081（2023）11-3351-07

10.11772/j.issn.1001-9081.2022111705

2022⁃11⁃04；

2023⁃01⁃04；

国家自然科学基金资助项目（61802182）。

游坤（1982—），女，山西沁源人，高级工程师，博士，CCF会员，主要研究方向：云计算、服务计算； 王钦辉（1985—），男，江西丰城人，副教授，博士，主要研究方向：云计算、无线网络； 李鑫（1987—），男，江西南昌人，副教授，博士，主要研究方向：云计算、边缘计算。

TP393

A

2023⁃01⁃16。

This work is partially supported by National Natural Science Foundation of China （61802182）.

YOU Kun， born in 1982， Ph. D.， senior engineer. Her research interests include cloud computing， service computing.

WANG Qinhui， born in 1985， Ph. D.， associate professor. His research interests include cloud computing， wireless networks.

LI Xin， born in 1987， Ph. D.， associate professor. His research interests include cloud computing， edge computing.