Identifying the most influential communicators as an issue of maximizing influence has become one of the most notable topics in social network analysis, as it has achieved success in viral marketing. Only by understanding our opponent's way of thinking can we effectively defend against or attack them. We particularly focus on one type of such attacks called the weight stable set attack problem with budget constraint. Given a social network, each node has a weight and removal cost. This problem is to remove a subset of the nodes whose total removal cost does not exceed a given threshold, such that the maximum weight stable set in the resulting graph is minimized. We first propose a 2$\alpha$-approximation algorithm for this problem on the graph without odd cycles, where$\alpha$is the approximation ratio for the algorithm of the minimum knapsack problem. Interestingly, this algorithm can be extended to general graphs. We also design a genetic algorithm for general graphs. Finally, we conducted many experiments on both artificial networks and real-world networks. For the graph without odd cycles, the results show that our performance ratio is less than 1.21. For general graphs, we compare the algorithm that extends the idea of graphs without odd cycles with the genetic algorithm. The results show that this algorithm is better than the genetic algorithm in some settings.

Rapid advances in technology have endowed intelligent vehicles with increasing computing power and rich perception abilities. In this paper, we address the problem of computation offloading and resource sharing in vehicle computing, where the vehicle provides computing and sensing resources to users. Since sensing devices capture the same data at any given moment, multiple users can simultaneously share the sensing resources of the same vehicle. Building on this, we propose a novel resource-sharing model that, while allocating computing resources only to users, allows users to monopolize or share sensing resources. By serving more users, this resource-sharing model results in savings on vehicle costs. The proposed mechanism comprises three types of auctions: one-to-many, many-to-one, and one-to-one. While the one-to-many auction allocates resources of one vehicle to multiple users, the many-to-one auction allocates resources of multiple vehicles to one user. The one-to-one auction, on the contrary, restricts allocation of resources of one vehicle to one user. While being truthful for both users and vehicles, this mechanism also contributes to individual rationality, budget balance, and consumer sovereignty. Finally, simulation results confirm the efficiency of the mechanism, which achieves high performance while facilitating additional utility.

In this paper, we study multi-resource maximin share fair allocation with time discount in a cloud computing system with heterogeneous servers. It primarily focuses on the allocation of computing resources in cloud computing systems when users are dealing with time-sensitive tasks. If users delay handling these tasks, their utility will decrease over time. In addition, users do not always stay in the computing system in this problem. For this problem, we propose a mechanism called maximin share fairness with time discount (MMS-TD) in a heterogeneous cloud computing system. We prove theoretically that the allocation returned by the mechanism is lexicographically max-min optimal, that the allocation satisfies the maximin share fairness, and that the mechanism is Pareto efficiency, proportionality, and strategy-proofness. In addition, we designed an algorithm to realize this mechanism and conducted simulation experiments with Alibaba cluster traces. The experimental results show that regardless of resource utilization or user utility, the MMS-TD mechanism consistently outperforms the other three similar mechanisms.

Vehicle computing has emerged as a promising paradigm for delivering time-sensitive computing services to Internet of Things applications. Intelligent vehicles (IVs) offer onboard computing and sensing capabilities for delivering a wide range of services. In this paper, we propose a dynamic adaptability service model that leverages the swift mobility of vehicles to adjust the distribution of IVs to users’ dynamically changing locations. There are two types of areas in our model: the user area and the parking area. The former is where services are provided, while the latter serves as the preparation zone for backup IVs. IVs in the parking area are dispatched to service areas, where existing vehicle resources cannot meet user demand, and they return to the parking area after delivering the service. Multiple users share sensing resources, and our model allocates the costs among them. To ensure strategy-proofness, we introduce the concepts of no additional cost and allocation stability. We propose a strategy-proof cost-sharing mechanism for dynamic adaptability service. The proposed mechanism achieves no positive transfers, voluntary participation, individual rationality, consumer sovereignty, budget balance, no additional costs, and allocation stability. Moreover, the proposed mechanism’s approximation performance is analyzed. We further use comprehensive simulations to verify the effectiveness and efficiency of the proposed mechanism.

The resource allocation problem that is posed by cloud services has long been a popular research topic. The existing auction mechanisms focus primarily on maximizing social welfare, but they often result in lower revenue for cloud service providers. The virtual valuation-based combinatorial auction (VVCA) mechanism can increase the revenue that is obtained by service providers while satisfying dominant strategy incentive compatibility (DSIC). In this study, we innovatively apply the VVCA mechanism to address a time-varying resource allocation problem that involves heterogeneous servers (HTs) in cloud services and effectively increase the revenue that is received by cloud service providers. We begin by transforming the HT problem into an integer programming model with time-varying and resource constraint features. Afterward, we provide the theoretical basis for using the VVCA mechanism to solve the aforementioned problem and provide the DSIC proof. On this basis, we design three progressively more effective mechanisms using the VVCA mechanism. (1) We develop a random mechanism$\rm {HT\_{V}VC{A^{m}}}$and prove that it has a logarithmic approximation ratio, thus offering a better lower bound guarantee than the existing approach does. (2) We propose a gradient-based optimization mechanism$\rm {HT\_{V}VC{A^ * }}$to approximate the optimal revenue. (3) We design an optimal revenue algorithm called HT_VVCANET on the basis of the transformer architecture that is used in deep learning; this algorithm achieves a good balance between execution efficiency and effectiveness. In the experiments, we implement these mechanisms, which significantly increase the revenue that is received by cloud service providers over that yielded by other benchmark mechanisms.

ABSTRACT Finding a fair allocation is an important issue in many application areas. In a heterogeneous cloud computing system, users may have different requirements, and servers may also have different configurations. The first proposed fair allocation mechanism for heterogeneous cloud computing systems, called DRFH, is based on dominant resource fairness. However, the DRFH mechanism does not satisfy the properties of strong shared incentives and independence of dummy servers. In this article, we propose a simple mechanism, called the maximin share‐based mechanism in a heterogeneous cloud computing system (MMSH), which maximizes the minimum ratio of the user's utility to the maximin share. Because the MMSH mechanism can be formulated as a linear program, a MMSH allocation can be found in polynomial time. Moreover, we prove that MMSH satisfies all the desirable properties including Pareto efficiency, strong sharing incentives, envy‐freeness, group strategy‐proofness, and independence of dummy servers. Using the Alibaba trace to conduct data simulations, the experimental results indicate that in most cases, the allocation generated by the MMSH mechanism has a higher resource utilization rate.

Mobile edge computing (MEC) affords high computing power but lacks sensing capability. Furthermore, intelligent vehicles, which possess rich sensing resources, consume limited energy. Motivated by this, we propose edge-vehicle collaborative computing and investigate the task offloading and interaction problem (TOIP), in which MEC servers and vehicles collaborate to leverage their strengths and mitigate their weaknesses. Motivated by practical application requirements, we propose a task interaction model where a user’s computing and sensing subtasks are respectively offloaded onto the MEC servers and vehicles, which then collaborate to complete the tasks. Aiming to maximize group efficiency, we formulate the TOIP in an auction-based setting. To motivate MEC servers and vehicles, we propose a reverse auction where each user is an auctioneer, while MEC servers and vehicles are the bidders. Our reverse auction mechanism achieves budget feasibility, where the rewards received by MEC servers and vehicles cannot exceed the budget. The proposed mechanism proves to be truthful; that is, MEC servers or vehicles cannot obtain higher utility by declaring untrue values. We also demonstrate how to make the mechanism meet the truthfulness requirement in TOIP. In addition, the proposed mechanism achieves individual rationality, consumer sovereignty, and computation efficiency. We also theoretically analyze the approximate ratio. The simulation results show that the proposed mechanism exhibits exceptional performance in all the scenarios.

We consider the edge-vehicle computing system (EVCS), where the combination of edge computing and vehicle computing takes respective advantages to provide various services. We address the problem of computation offloading in EVSC, where the computing tasks and the sensing tasks with limited budgets are offloaded to edge servers and vehicles. The resource-sharing model is proposed, where sensing resources of one vehicle are shared by multiple tasks. We consider the vehicle hierarchy, where vehicles with different equipment accuracy are classified into different hierarchies. A sensing task has different values and different demands for different hierarchies. A budget-feasible mechanism based on the clock auction is proposed. We show our proposed mechanism is strategy-proof and group strategy-proof, this drives the system into an equilibrium. In addition, the proposed mechanism achieves individual rationality, budget balance, and consumer sovereignty. The proposed mechanism consists of two algorithms that are based on the idea of dominant resource and iteration to improve resource utilization and reduce costs. Furthermore, the approximate ratios of the two allocation algorithms are analyzed. Experimental results demonstrate that the proposed mechanism achieves the near-optimal value and brings higher utility for participants.

Mobile crowdsensing service (MCS) providers recruit users to complete data collection tasks by rewarding the users to obtain greater revenue. Therefore, maximizing revenue is a focus of the MCS provider. This article expresses this problem as a revenue maximization programming model with budget constraints and designs a reverse-auction mechanism based on the attention model to solve the task allocation and pricing problems. Specifically, we convert the programming model under multiple constraints into an augmented Lagrangian function, optimally solve it through a multilayer neural network on the basis of the attention interactive framework, and finally output the allocation and payment solution. Our design guarantees that the mechanism meets economic criteria such as truthfulness, individual rationality, and budget feasibility. Combining the revenue-optimal reverse-auction mechanism with deep learning provides a new approach to mechanism design. Compared with existing methods, our solution achieves very good results in terms of service provider revenue and generalization experiments.

Mobile crowdsensing service (MCS) providers recruit users to complete data collection tasks with an incentive mechanism. How to maximize the utility of service providers has long been a popular topic in MCS research. Applying the existing reverse auction mechanism to an MCS may result in excessively high payments, thereby reducing the utility of the MCS provider. The affine maximizer auction (AMA) mechanism increases the revenue of service providers and meets dominant-strategy incentive-compatible (DSIC) characteristics. However, the AMA mechanism is a forward auction mechanism and cannot be applied to MCSs. Inspired by the AMA mechanism, this paper innovatively proposes a reverse affine maximizer auction (RAMA) mechanism to solve the task allocation problem of MCSs, effectively improving the MCS provider utility. Specifically, we construct a RAMA theoretical model and prove that the mechanism satisfies DSIC characteristics. For the discrete MCS task allocation problem, we use the reverse virtual valuation combinatorial auction (RVVCA) mechanism, a subclass of RAMA, to design a random mechanism RVVCA$^{t}$and prove that the RVVCA$^{t}$has a logarithmic approximate ratio. For the differentiable MCS task allocation problem, we use the deep learning transformer framework to design RAMANet, which can fit an exponential number of allocation solutions and output the optimal allocation and payment. We experimentally compare the algorithms of the RAMA family we propose, which use affine maximization, with existing state-of-the-art algorithms, demonstrating that the proposed algorithms significantly improve MCS provider utility.

Multiresource allocation mechanisms have been studied in many scenarios. A new dynamic multiresource fair allocation model with time discount utility is proposed in this article, where users can arrive and depart at different time slots. We propose a newany price sharetime discount (APS-TD) mechanism for this model, which accounts for the users' time discount utility while maintaining desirable properties. We prove that the APS-TD mechanism satisfies cumulative incentive sharing (CSI), i.e., that the cumulative utility of each user is not lower than the cumulative utility generated by evenly allocating the available resources in each time slot; cumulative strategyproofness (CSP), where users cannot increase their cumulative utility by falsely reporting their demands in any time slot; cumulative Pareto optimality (CPO), i.e., where no allocation can increase the cumulative utility of one user without reducing the cumulative utility of another user in any time slot; cumulative envy-freeness (CEF), where users who arrive later should not prefer allocations from other users who arrive first in any time slot; time discount share fairness (TDSF), where users with higher time discount values occupy larger resource shares in each time slot unless the utility levels of both users are generated by evenly allocating resources; and bottleneck fairness (BF), where the allocation should satisfy max-min fairness with respect to the bottleneck resources contained in each time slot. We run the APS-TD mechanism on Alibaba trace-driven data to demonstrate the performance enhancement achieved by our proposed mechanism over the existing mechanism extensions. The results show that the APS-TD mechanism is superior to hybrid multiresource fairness (H-MRF) and stateful dominant resource fairness (SDRF) in many ways.

In contrast to traditional mechanism design, the posted pricing mechanism can quickly determine the winning user and ensure the revenue of the seller through a predetermined price. Additionally, the posted pricing mechanism inherently possesses economic properties such as truthfulness and individual rationality. These properties make it an ideal method for solving online task allocation problems for mobile crowdsensing services (MCSs). The challenge in posted pricing mechanism design is being able to find reasonable posted prices under complex MCS task constraints. This paper presents an innovative posted pricing mechanism to solve a general point of interest (POI)-based online MCS task allocation problem. We transform the problem into an integer programming model with the goal of maximizing the total utility of the system while satisfying various constraints. We prove that under any user arrival order, there must exist a posted price structure that can ensure that the total utility of the system is approximately optimal, with an approximation ratio of$1/(d+1)$in the worst case. With the support of theoretical analysis, the posted price calculation can be completed using only a simple gradient descent algorithm. Compared with existing methods, our solution achieves very good results in terms of total utility and the task completion ratio, indicating that it can effectively improve the efficiency and service quality of MCSs.

Abstract Let $T=(V,E)$ be a tree in which each edge is assigned a cost; let $\mathcal{P}$ be a set of source–sink pairs of vertices in V in which each source–sink pair produces a profit. Given a lower bound K for the profit, the K -prize-collecting multicut problem in trees with submodular penalties is to determine a partial multicut $M\subseteq E$ such that the total profit of the disconnected pairs after removing M from T is at least K , and the total cost of edges in M plus the penalty of the set of still-connected pairs is minimized, where the penalty is determined by a nondecreasing submodular function. Based on the primal-dual scheme, we present a combinatorial polynomial-time algorithm by carefully increasing the penalty. In the theoretical analysis, we prove that the approximation factor of the proposed algorithm is $(\frac{8}{3}+\frac{4}{3}\kappa+\varepsilon)$ , where $\kappa$ is the total curvature of the submodular function and $\varepsilon$ is any fixed positive number. Experiments reveal that the objective value of the solutions generated by the proposed algorithm is less than 130% compared with that of the optimal value in most cases.

In the context of the Internet of Things (IoT), resource-constrained mobile edge computing (MEC) can no longer fully meet the needs of the rapidly growing number of mobile users; hence, cloud-edge collaborative computing has been developed. This paper focuses on the total energy consumption of the system and heterogeneity of scenarios, and a collaborative cloud-edge computation offloading approach with near real-time decision making is proposed. First, a general cloud-edge collaborative computation offloading model is abstracted from typical applications, and the energy consumption for edge and cloud offloading is calculated separately by considering both transmission and computational energy consumption. The problem is formulated as an integer linear program (ILP) with multidimensional resource constraints and is proven to be NP-hard. Then, a novel primal-dual computation offloading (PDCO) algorithm is designed to make near real-time offloading decisions one by one based on the sequential arrival of task requests. The approximation ratio of PDCO is derived through the weak duality property and the price-resource increment relationship. The experimental results show that under the guidance of total cost influenced by marginal prices, PDCO not only avoids blindly making offloading decisions but also effectively alleviates the shortage of resources on edge servers (ESs), approaching the optimal performance in terms of total energy consumption and resource utilization.

Mobile crowdsensing services are divided into two categories: opportunistic and participatory. In opportunistic mobile crowdsensing services, users do not need to specify the crowdsensing tasks to be completed. Compared with participatory crowdsensing services, the application scope is wider and more user-friendly. In participatory crowdsensing, the service provider assumes that the user can successfully complete the data collection task. However, such an approach cannot work in an opportunistic crowdsensing service because in opportunistic crowdsensing, the user’s execution of the task is uncertain, which brings great challenges to the quality of the crowdsensing service. This article is based on the assumption of the user coverage probability model and transforms the opportunistic mobile crowdsensing value maximization problem into an ordered submodularity value function model with budget constraints. This model is also good at representing participatory crowdsourcing problems. To the best of our knowledge, this is the first study to apply the ordered submodularity feature to a mobile crowdsensing service. Furthermore, we combine the properties of ordered submodular and auction models and propose an ordered submodularity-proportional share mechanism (O-PSM) to solve the allocation and payment problems in opportunistic mobile crowdsensing services. Specifically, in the allocation stage, the winning users are selected based on the proportional share threshold, and in the payment stage, the payment price for the winning users is designed based on critical value theory. We prove that the mechanism satisfies the economic characteristics of individual rationality, truthfulness, and budget feasibility. In the experimental section, the mechanism design based on ordered submodularity is shown to enable the service provider to obtain a higher value and a lower payment.

In the context of mobile edge computing (MEC), it can be quite challenging to provide and allocate multiple resources from heterogeneous MEC servers for remote execution of tasks of mobile devices (MDs). However, obtaining more resources for tasks can save time and effort, and MDs are willing to pay higher prices for more resources. Motivated by these challenges, this study addresses the problem of heterogeneous resource allocation with multi-minded (HRAM) in MEC. Unlike other studies that have focused on MDs with single-minded demands, this study considers the multi-attribute demands of MDs. It considers cases where an MD declares multiple demands, each with a different bid attached to it. This multi-minded approach gives MDs more flexibility and control over the resources they receive, leading to increased satisfaction and better outcomes. However, MDs are self-interested and can misreport their preferences, which results in a low utilization rate of heterogeneous resources. Therefore, we have formulated this problem in an auction-based setting, and our objective is to allocate heterogeneous resources of heterogeneous MEC servers to maximize social welfare, which is the sum of MDs’ valuations. We demonstrate that the HRAM problem is NP-hard, proposing a randomized mechanism consisting of a second-price auction and a fixed-price auction. This study claims that the proposed randomized mechanism is universally truthful and that the MDs have no desire to misreport their demands. Additionally, we analyze the randomized mechanism’s time complexity and approximation ratio and present the experimental results to support our claim. We demonstrate that the randomized mechanism performs excellently in different environments, benefiting MDs and edge cloud providers.

Digital twin (DT) technology uses Internet of Things (IoT) devices to collect real-world data and build a virtual world in the DT cloud. However, many IoT devices collect data in harsh natural environments, and these data cannot be transmitted through fixed base stations. Thus, many DT services adopt dynamic data transmission methods, such as transmission through unmanned aerial vehicle base stations (UAV-BSs). However, UAV-BS approaches have many communication constraints, such as limitations on the transmission bandwidth, data throughput, and number of channels. In addition, when integrating a large amount of data submitted by IoT devices, DT service providers need a corresponding mechanism to select the most valuable device data, which can be described by a winner decision problem with the goal of maximizing utility. In this paper, we consider the problem of maximizing the utility of a DT model under UAV-BS network transmission, transform it into a mixed integer programming model with communication and computing constraints, and adopt a reverse auction mechanism to solve it. Specifically, we design an optimal reverse auction mechanism based on optimal allocation and Vickrey–Clarke–Groves (VCG) theory. Additionally, a reverse auction mechanism with polynomial execution time is designed based on monotonic allocation, network maximum flow and critical value theory. These two mechanisms are proven to satisfy individual rationality and truthfulness. Experimental results indicate the favorable performance of the designed mechanisms.

In this paper, we address the problem of heterogeneous physical machines resource management (HPMRM); that is, providing and allocating multiple virtual machine (VM) instances from heterogeneous physical machines to maximize social welfare. Although existing allocation mechanisms allocate VMs to users through the single-mapping mechanism, such allocations cannot guarantee maximum social welfare or efficient utilization of multiple types of resources for cloud providers. Thus, we consider the multi-mapping mechanism, which permits mapping VMs allocated to one user to physical machines for VM provisioning and allocation. This can result in improved social welfare and lead to less resource fragmentation. We formulate the HPMRM problem in an auction-based setting, and design optimal and approximate mechanisms to solve it. In addition, we show that our proposed mechanism is strategy-proof; that is, our proposed mechanism drives the system into an equilibrium where no users have incentives to maximize their own profit by untruthfully reporting their requests. Furthermore, we analyze the approximation ratio of our proposed approximation algorithm. We also perform experiments to investigate the performance of our proposed approximation mechanism compared to the optimal mechanism. Experimental results demonstrate that our proposed approximation mechanism can obtain near optimal solutions and significantly improve allocation efficiency, while generating greater social welfare.

In this paper, we design an efficient algorithm for the energy-aware profit maximizing scheduling problem, where the high performance computing system administrator is to maximize the profit per unit time. The running time of the proposed algorithm is depending on the number of task types, while the running time of the previous algorithm is depending on the number of tasks. Moreover, we prove that the worst-case performance ratio is close to 2, which maybe the best result. Simulation experiments show that the proposed algorithm is more accurate than the previous method.