Log parsing converts semi-structured logs into structured templates, forming a critical foundation for downstream analysis. Traditional syntax and semantic-based parsers often struggle with semantic variations in evolving logs and data scarcity stemming from their limited domain coverage. Recent large language model (LLM)-based parsers leverage in-context learning (ICL) to extract semantics from examples, demonstrating superior accuracy. However, LLM-based parsers face two main challenges: 1) underutilization of ICL capabilities, particularly in dynamic example selection and cross-domain generalization, leading to inconsistent performance; 2) time-consuming and costly LLM querying. To address these challenges, we present MicLog, the first progressive meta in-context learning (ProgMeta-ICL) log parsing framework that combines meta-learning with ICL on small open-source LLMs (i.e., Qwen-2.5-3B). Specifically, MicLog: i) enhances LLMs' ICL capability through a zero-shot to k-shot ProgMeta-ICL paradigm, employing weighted DBSCAN candidate sampling and enhanced BM25 demonstration selection; ii) accelerates parsing via a multi-level pre-query cache that dynamically matches and refines recently parsed templates. Evaluated on Loghub-2.0, MicLog achieves 10.3% higher parsing accuracy than the state-of-the-art parser while reducing parsing time by 42.4%.

With the construction of intelligent agents, coordinating a collection of agents to optimize long-term cumulative global reward is becoming increasingly important. To align individual agent actions with global rewards, the contribution of individual actions to global rewards needs to be determined, which is known as the structural credit assignment (SCA). Conventional SCA mechanisms are primarily based on neural networks, which lack theoretical foundations and preclude their application to model-based MAP tasks. Leveraging cooperative game theory, the main contribution of this study is to propose a novel Shapley value-based SCA (SV-SCA) that can be generalized to both MAP and MARL. Combining the distributed constraint optimization (DCOP) model and its reward structure, we propose a novel algorithm for computing the Shapley value while ensuring the efficiency and fairness of the SV-SCA. Particularly, based on SV-SCA, we design a coordinated Monte Carlo tree search (MCTS) for model-based MAP tasks and a fully-decentralized method for model-free MARL tasks. Theoretical analyses show that the proposed coordinated MCTS can guarantee the expected value of the global joint action, and that the proposed coordinated MARL is monotonic such that each agent optimizes its own rewards also optimize the system’s global reward. Finally, we conduct extensive experiments in typical sequential multiagent coordination domains. Our results demonstrate that the proposed coordinated MCTS and coordinated MARL outperform existing multiagent MCTS and MARL baselines in terms of solution quality and scalability.

Deep reinforcement learning (DRL) has emerged as a promising approach for the train trajectory optimization (TTO) problem in real-world high-speed rail (HSR) systems. However, there remain two issues with current DRL-based HSR operations: 1) the driver-centric markov decision process (MDP) with sparse rewards, and 2) optimizing a single rail trajectory (i.e., single task), but is less adaptable to practical HSR scenarios that require rapid responses to changing conditions (i.e., multiple tasks). In terms of sparse rewards, this paper first proposes a looped segment-wise gradient optimization (LSGO)-centric MDP that discards human-driving-pattern imitation, where the complete trajectory and terminal reward can be obtained at every agent’s action directly from the trajectory state. In terms of multiple tasks learning, meta-RL is promising to learn a policy that is capable of adapting to any new task with as little data as possible. Existing meta-RL algorithms directly use the meta parameters to train new tasks, overlooking task similarity and leading to a “lazy” agent issue with high training costs. In addressing the TTO problem, this paper finds that there exists a linear relationship between task-specific optimal policies. By fully exploiting the similarity policy between tasks, this paper proposes a policy deviation integral guided meta-reinforcement learning (PDIMRL) algorithm. It linearly adjusts and initializes new-task policies by integrating deviations between known task optima. Finally, experiments show that 1) LSGO achieves a$16.8\times $speedup in single-task training compared to driver-centric MDPs, and 2) based on LSGO-centric and driver-centric MDPs, PDIMRL only requires 41.29% and 14.74% meta-training times than benchmark meta-RL algorithms (e.g., Reptile), respectively.

By exploiting the correlation between the structure and the solution of Mixed-Integer Linear Programming (MILP), Machine Learning (ML) has become a promising method for solving large-scale MILP problems. Existing ML-based MILP solvers mainly focus on end-to-end solution learning, which suffers from the scalability issue due to the high dimensionality of the solution space. Instead of directly learning the optimal solution, this paper aims to learn a reduced and equivalent model of the original MILP as an intermediate step. The reduced model often corresponds to interpretable operations and is much simpler, enabling us to solve large-scale MILP problems much faster than existing commercial solvers. However, current approaches rely only on the optimal reduced model, overlooking the significant preference information of all reduced models. To address this issue, this paper proposes a preference-based model reduction learning method, which considers the relative performance (i.e., objective cost and constraint feasibility) of all reduced models on each MILP instance as preferences. We also introduce an attention mechanism to capture and represent preference information, which helps improve the performance of model reduction learning tasks. Moreover, we propose a SetCover based pruning method to control the number of reduced models (i.e., labels), thereby simplifying the learning process. Evaluation on real-world MILP problems shows that 1) compared to the state-of-the-art model reduction ML methods, our method obtains nearly 20% improvement on solution accuracy, and 2) compared to the commercial solver Gurobi, two to four orders of magnitude speedups are achieved.

Human-in-the-loop (HIL) imitation learning enables agents to learn complex behaviors safely through real-time human intervention. However, existing methods struggle to efficiently leverage agent-generated data due to dynamically evolving trajectory distributions and imperfections caused by human intervention delays, often failing to faithfully imitate the human expert policy. In this work, we propose Faithful Dynamic Imitation Learning (FaithDaIL) to address these challenges. We formulate HIL imitation learning as an online non-convex problem and employ dynamic regret minimization to adapt to the shifting data distribution and track high-quality policy trajectories. To ensure faithful imitation of the human expert despite training on mixed agent and human data, we introduce an unbiased imitation objective and achieve it by weighting the behavior distribution relative to the human expert's as a proxy reward. Extensive experiments on MetaDrive and CARLA driving benchmarks demonstrate that FaithDaIL achieves state-of-the-art performance in safety and task success with significantly reduced human intervention data compared to prior HIL baselines.

Efficient traffic signal control (TSC) has been one of the most useful ways for reducing urban road congestion. By modeling each intersection as an autonomous agent, multiagent reinforcement learning (MARL) shows remarkable performance in solving dynamic TSC. However, most of TSC methods based on MARL suffer from a non-stationarity problem since agents update their policies simultaneously. To resolve this issue, this paper considers multi-intersection TSC as a multi-agent sequential decision-making process with policy online learning. We utilize a sequential model such as Transformer architecture to learn the multi-agent joint policy. By carefully designing the advantage function of each agent, the monotonic improvement property can be guaranteed. Moreover, to fully exploit the advantages of both simultaneous and sequential MARL, we further propose a novel MARL network selection algorithm (MARL-NS) which selectively employs simultaneous MARL only at states that sequential MARL might fall into local optimum. Our theory proves that MARL-NS preserves cooperative MARL converge properties. Finally, we validate the proposed MARL-NS method on a unified TSC benchmark, LibSignal. Experimental results show that our method can outperform the baseline methods in network-level and arterial coordination.

Mobile crowdsourcing has emerged as a popular approach for organizations to leverage the collective intelligence of a crowd of users to obtain services. Considering users’ costs for providing services, it is vital for the requester to design incentive mechanisms to encourage users’ participation in crowdsourcing under the budget constraint. This aligns with the concept of budget-feasible mechanism design. Existing budget-feasible mechanisms often assume immediate user reachability and willingness of joining the crowdsourcing, which is unrealistic. To address this issue, a promising approach is to have participating users diffuse auction information to potential users in the social network. However, this brings another challenge in that participating users can be strategic and therefore hesitant to invite more potential competitors to join the crowdsourcing platform. In this paper, we focus on developing diffusion mechanisms that incentivize strategic users to actively diffuse auction information through the social network. This helps to attract more informed users and ultimately increases the value of the procured services. Specifically, we propose optimal budget-feasible diffusion mechanisms that simultaneously guarantee individual rationality, budget-feasibility, strong budget-balance, incentive-compatibility (i.e., users report real costs and diffuse auction information to all their neighbors) and approximation. Experiment results under real datasets further demonstrate the efficiency of proposed mechanisms.

Ride-hailing platforms have been facing the challenge of balancing demand and supply. Existing vehicle reposition techniques often treat drivers as homogeneous agents and relocate them deterministically, assuming compliance with the reposition. In this paper, we consider a more realistic and driver-centric scenario where drivers have unique cruising preferences and can decide whether to take the recommendation or not on their own. We propose i-Rebalance, a personalized vehicle reposition technique with deep reinforcement learning (DRL). i-Rebalance estimates drivers' decisions on accepting reposition recommendations through an on-field user study involving 99 real drivers. To optimize supply-demand balance and enhance preference satisfaction simultaneously, i-Rebalance has a sequential reposition strategy with dual DRL agents: Grid Agent to determine the reposition order of idle vehicles, and Vehicle Agent to provide personalized recommendations to each vehicle in the pre-defined order. This sequential learning strategy facilitates more effective policy training within a smaller action space compared to traditional joint-action methods. Evaluation of real-world trajectory data shows that i-Rebalance improves driver acceptance rate by 38.07% and total driver income by 9.97%.

Due to the increasing need to protect public security, this article studies the security traffic patrolling (STP) problem, where a collection of police officers plan to patrol around a city. In STP, the patrolling policy should not only take drivers’ opportunistic behaviors into consideration but also satisfy frequency constraints such that hot-spot regions are patrolled at least once every several periods. Existing randomized methods are efficient in reducing traffic law violations but can only satisfy the frequency constraints in a probabilistic manner. Traditional planning methods can be employed to meet the frequency constraints in a deterministic manner. However, it is difficult to find the deterministic patrolling paths for city-scale STP with hundreds of police officers and regions. Against this background, this article proposes a novel two-stage offline–online integration framework to guarantee frequency constraints while efficiently preventing traffic law violations of drivers. In the offline stage, a linear programming (LP)-based randomized policy is designed, where the patrolling efficiency is modeled as the objective and the frequency constraint is modeled in a probabilistic manner. Guided by the offline policy, in the online stage, by observing the real distribution of police officers, real-time planning is proposed to reschedule the police to guarantee the frequency constraints. Extensive empirical experiments on synthetic and real datasets are conducted to validate the proposed framework. The results demonstrate that compared with existing baseline solutions, the proposed two-stage STP framework can reduce the driver violation rate as much as possible, satisfy frequency constraints and scale well to STP in a real-time fashion.

Traffic signal control (TSC) has been one of the most useful ways for reducing urban road congestion. The challenge of TSC includes 1) real-time signal decision, 2) the complexity in traffic dynamics, and 3) the network-level coordination. Reinforcement learning (RL) methods can query policies by mapping the traffic state to the signal decision in real-time, however, are inadequate for different traffic flow environment. By observing real traffic information, online planning methods can compute the signal decisions in a responsive manner. Unfortunately, existing online planning methods either require high computation complexity or get stuck in local coordination. Against this background, we propose an explicit multiagent coordination (EMC)-based online planning methods that can satisfy adaptive, real-time and network-level TSC. By multiagent, we model each intersection as an autonomous agent, and the coordination efficiency is modeled by a cost function between neighbor intersections. By network-level coordination, each agent exchanges messages of cost function with its neighbors in a fully decentralized manner. By real-time, the message-passing procedure can interrupt at any time when the real time limit is reached and agents select the optimal signal decisions according to current message. Finally, we test our EMC method in both synthetic and real road network datasets. Experimental results are encouraging: compared to RL and conventional transportation baselines, our EMC method performs reasonably well in terms of adapting to real-time traffic dynamics, minimizing vehicle travel time and scalability to city-scale road networks.

Multiagent Markov decision processes (MMDPs) provide an expressive framework for multiagent planning in stochastic domains. However, exactly solving a large MMDP is often intractable due to the exponential space of joint action. Due to the trade-off nature of trading computation time for solution quality, decentralized subgoal-based tree search (Dec-SGTS) methods have shown great success for MMDPs. Existing Dec-SGTS methods rely on the predefined subgoals and the communication between agents to perform well, which might not hold in real-world MMDP domains where there is no expert knowledge on subgoals and communication resources are limited. In this paper, we relax these assumptions that arrive at an automated and communication-free Dec-SGTS. On the one hand, we first propose an upstream guided subgoal search (UGSS) technique to exploit historical search experience for subgoal discovery. On the other hand, in order to coordinate agents’ behaviors without communication, we further propose an expectation-alignment technique to proactively align agents’ policies with team’s expectations. Finally, we conduct extensive experiments on multirobot box-pushing tasks, and the results show that compared to multiagent planning benchmarks, the proposed communication-free Dec-SGTS method, which does not require any subgoal priors, achieves satisfactory rewards.

In a crowdsensing platform, users are invited to provide data services, and multiple requesters compete for desired services. Due to users' costs of providing services, it is critical to design incentive mechanisms to incentivize users with (monetary) rewards. Meanwhile, requesters may have individual budgets and compete for services with different procurement abilities. Such a setting falls into the budget-feasible mechanism design. However, most of the existing budget-feasible mechanisms focus on one-sided markets with a single requester rather than the two-sided markets with multiple requesters having different procurement abilities. Moreover, requesters and users can be selfish and strategic with their private information, which requires preventing information manipulation on both requesters' and users' sides. In this paper, we investigate budget-feasible mechanisms in two-sided crowdsensing markets where multiple strategic requesters come with private budgets to obtain services from the strategic users. We also consider the fairness on the requesters' side,i.e., a requester with more budget should obtain more service. We propose budget-feasible mechanisms for two models by distinguishing the types of services,i.e., the homogeneous or heterogeneous services. All proposed mechanisms satisfy fairness, budget feasibility, truthfulness on both users' and requesters' sides, and the constant approximation ratio. Numerical experiment results further demonstrate the efficiency of our proposed mechanisms.

With the increasing need of protecting public security, this paper studies the city-scale patrolling (CSP) problem, where hundreds of police officers are planned to patrol thousands of regions in a city. Given the stochastic nature with uncertain incident occurrence and travel time, the online CSP, where the patrolling policy should be determined sequentially, is of special interest. The online CSP aims at the omnipresence patrolling, which denotes that there are always police officers nearby that can respond timely when an incident occurs. Existing exact combinatorial optimization approaches are time-consuming and cannot scale to online CSP scenarios. On the other hand, within the dynamic CSP environments, existing decentralized multiagent coordination-based approaches always converge to the suboptimal solution without any performance guarantee. To achieve the omnipresence patrolling in a real-time fashion, a novel two-stage CSP framework is proposed. In the first stage, an offline model-based patrolling policy (OFFLINECSP) is designed, where the historical data is used to build the model and the linear programming (LP) technique is proposed for the coordination policy. Guided by the benchmark OFFLINECSP policy, an efficient online patrolling (ONLINECSP) policy is proposed in the second stage, where the police prefers to serve the critical incidents and to patrol hot-spot regions. The theoretical result shows that the competitive ratio of ONLINECSP can be guaranteed. Finally, extensive experiments on the synthetic and real datasets are conducted to validate the proposed framework. The results demonstrate that compared with existing benchmarks, the proposed two-stage CSP framework can not only maximize the incident service rate but also scale well to CSP in a real-time fashion.

Ride-hailing systems (RHSs) provide passengers with convenient and flexible mobility services, have played an important role in modern urban transportation. With the limited vehicles, RHSs wish to optimize the dispatch of vehicles to requests with the objective of serving as many requests as possible. To address such a city-scale vehicle dispatch problem with thousands of vehicles and requests in each epoch, existing algorithms always take a tradeoff between effectiveness (i.e., real-time) and efficiency (i.e., service rate), such as ignoring future demands to guarantee real-time or solving a complex combinatorial optimization to improve service rate. To guarantee the service rate in a real-time fashion, this paper proposes two novel network flow-based vehicle dispatch algorithms. A network flow-based algorithm (NFBA) is provided to deal with offline scenarios. By constructing the vehicle-shareability network, a min-cost flow is built to find the optimal dispatch of vehicles to requests. To improve the request service rate in real-time, an efficient multi-sample multi-network flow-based algorithm (MNFBA) is proposed for the online scenarios. Each min-cost flow is utilized for a sample of future requests, and online vehicle dispatch policy is averaged over these flows. Extensive simulations based on real-world trip datasets in New York City are conducted. The experimental results show that compared to the benchmarks, our proposed algorithm can generate the dispatch of vehicles to requests within seconds, but can greatly increase the daily request service rate.

This paper studies the budget-feasible mechanism design over graphs, where a buyer wishes to procure items from sellers, and all participants (the buyer and sellers) can only directly interact with their neighbors during the auction campaign. The problem for the buyer is to use the limited budget to incentivize sellers to propagate auction information to their neighbors, thereby more sellers will be informed of the auction and more item value will be procured. An impossibility result shows that the large-market assumption is necessary. We propose efficient budget-feasible diffusion mechanisms for large markets that simultaneously guarantee individual rationality, budget-feasibility, strong budget-balance, incentive-compatibility to report private costs and diffuse auction information. Moreover, the proposed mechanisms achieve logarithmic approximation that the total procured value is within a logarithmic factor of the optimal solution. Compared to most related budget-feasible mechanisms, which do not take the individual interactions among sellers into account, our mechanisms can incentivize sellers to further propagate auction information to other potential sellers. Meanwhile, existing related diffusion mechanisms only focus on seller-centric auctions and fail to satisfy the budget-feasibility of the buyer.

Motivated by the increasing need of the real-world patrolling, this paper studies a practical city-scale patrolling (CSP) variant. In CSP, the police are scheduled to patrol city regions, and the objective is not only to protect public security but also to respond to incidents timely. We use an integer program (IP) to formulate the CSP problem, with the objective of maximizing the police visibility rate (PVR) to improve public safety and the additional constraint of response time guarantee to handle incidents timely. For such an NP-hard problem, existing studies either cannot scale-up or do not provide a bound from optimum. To fill the research gap, we propose a decomposition and grafting approach. We first decompose the original CSP into two weakly-coupled subproblems, minimizing police problem (MinP) and maximizing PVR (MaxP) problem. By exploiting the subproblem structures, a polynomial time approximation algorithm is proposed for MinP, and a polynomial time optimal algorithm is proposed for MaxP. We prove that such a decomposition can provide the 1 - α approximation ratio, where α is the percentage of the police used in MinP. To further improve patrolling efficiency, a grafting mechanism is proposed to integrate the two subproblems' solutions. Finally, we conduct extensive experiments on the real dataset of Foshan, a modern Chinese city. The results demonstrate that compared with benchmarks, our approach scales well to city-scale problem instances with fine-grained periods, hundreds of regions, and hundreds of police officers.

Despite the salient feature of cloud computing, the cloud provider still suffers from electricity bill, which in part comes from 1) the power consumption of running physical machines (PMs) to guarantee the resource/time requirements of virtual machines (VMs), and 2) the dynamically varying electricity price offered by smart grids. In the literature, there exist viable solutions adaptive to electricity price variation to reduce the electricity bill. However, they are not applicable to serving time-sensitive VM requests. In serving time-sensitive VM requests, it is potential for the cloud provider to apply proper consolidation strategies to further reduce the electricity bill. Few prior works have provided theoretical solutions of VM consolidation strategies that are adaptive to electricity price variations in serving time-sensitive VM requests. In this work, to address this challenge, we develop electricity-price-aware consolidation algorithms for both the offline and online scenarios. For the offline scenario, we first develop a consolidation algorithm with constant approximation, which always approaches the optimal solution within a constant factor of 5. For the online scenario, we propose an$O(\log (\frac{L_{max}}{L_{min}}))$-competitive algorithm that is able to approach the optimal offline solution within a logarithmic factor, where$\frac{L_{max}}{L_{min}}$is the ratio of the longest length of the processing time requirement of VMs to the shortest one. Our trace-driven simulation results further demonstrate that the average performance of the proposed algorithms produce near-optimal electricity bill.

Peer grading is a natural crowdsourcing application, where dispersed students/peers resources are collected to evaluate others' assignments. Peer grading also offers a promising solution for scaling evaluation and learning to large-scale educational systems. A key challenge in peer grading is motivating peers to grade diligently and provide a high-quality evaluation. Spot-checking (SC) mechanisms, allowing instructors to check evaluations, can prevent peer collusion where peers grade arbitrarily and coordinate to report the uninformative grade. However, existing SC mechanisms unrealistically assume that peers have the same grading reliability and cost. This is limiting in practice, where we would expect peers to differ in reliability and cost. This article proposes the general Optimal SC (OptSC) model of determining the probability that each assignment needs to be checked to maximize assignments' evaluation accuracy aggregated from peers and takes into consideration: 1) peers' heterogeneous characteristics and 2) peers' strategic grading behaviors to maximize their own utility. We prove that the bilevel OptSC is NP-hard to solve. By exploiting peers' grading behaviors, we first formulate a single-level relaxation to approximate OptSC. By further exploiting structural properties of the relaxed problem, we propose an efficient algorithm to that relaxation, which also gives a good approximation of the original OptSC. Extensive experiments on both synthetic and real data sets show significant advantages of the proposed algorithm over existing approaches.

With the increasing complexity of tasks that are crowdsourced, requesters need to form teams of professional workers that can satisfy complex task skill requirements. Team crowdsourcing in social networks (SNs) provides a promising solution for complex task crowdsourcing, where the requester hires a team of professional workers that are also socially connected can work together collaboratively. Previous social team formation approaches have mainly focused on the algorithmic aspect for social welfare maximization; however, within the traditional objective of maximizing social welfare alone, selfish workers can manipulate the crowdsourcing market by behaving untruthfully. This dishonest behavior discourages other workers from participating and is unprofitable for the requester. To address this strategic social team crowdsourcing problem, truthful mechanisms are developed to guarantee that a worker's utility is optimized when he behaves honestly. This problem is proved to NP-hard, and two efficient mechanisms are proposed to optimize social welfare while reducing time complexity for different scale applications. For small-scale applications where the task requires a small number of skills, a binary tree network is first extracted from the social network, and a dynamic programming-based optimal team is formed in the binary tree. For large-scale applications where the task requires a large number of skills, a team is formed greedily based on the workers' social structure, skill, and working cost. For both mechanisms, the threshold payment rule, which pays each worker his marginal value for task completion, is proposed to elicit truthfulness. Finally, the experimental results of a real-world dataset show that compared to the benchmark exponential VCG truthful mechanism, the proposed small-scale-oriented mechanism can reduce computation time while producing nearly the same social welfare results. Furthermore, compared to other state-of-the-art polynomial heuristics, the proposed large-scale-oriented mechanism can achieve truthfulness while generating better social welfare outcomes.

Peer grading, allowing students/peers to evaluate others' assignments, offers a promising solution for scaling evaluation and learning to large-scale educational systems. A key challenge in peer grading is motivating peers to grade diligently. While existing spot-checking (SC) mechanisms can prevent peer collusion where peers coordinate to report the uninformative grade, they unrealistically assume that peers have the same grading reliability and cost. This paper studies the general Optimal Spot-Checking (OptSC) problem of determining the probability each assignment needs to be checked to maximize assignments' evaluation accuracy aggregated from peers, and takes into consideration 1) peers' heterogeneous characteristics, and 2) peers' strategic grading behaviors to maximize their own utility. We prove that the bilevel OptSC is NP-hard to solve. By exploiting peers' grading behaviors, we first formulate a single level relaxation to approximate OptSC. By further exploiting structural properties of the relaxed problem, we propose an efficient algorithm to that relaxation, which also gives a good approximation of the original OptSC. Extensive experiments on both synthetic and real datasets show significant advantages of the proposed algorithm over existing approaches.

In crowdsourcing markets, a requester announces a task and calls for contribution from potential participants. With strategic participants, the requester needs to reward the participants to introduce the incentives of participation. However, it is natural to ask whether it is worth introducing incentives if the total payment for eliciting incentives is too high. This paper addresses such a fundamental concern by designing a frugal mechanism with minimum payment used to procure the total amount of service contributions demanded. We design two mechanisms to provide the incentives of participation while minimizing the payment used by the requester. We first propose a frugal auction-based mechanism, which stimulates participants to truthfully report their information. We theoretically prove that the payment used is not more than the optimal cost (with no incentive considered) plus a bounded additive. We then design a Stackelberg-game-based mechanism, in which the requester fixes a certain total payment at the very beginning so as to encourage the participants to compete for it and participate in the task. We verify the existence of a unique Nash equilibrium (NE) and develop a novel algorithm to find the NE, as well as the optimal payment to extract the NE. Our simulation results show that the payment used in these mechanisms is close to the optimal solution with no incentive considered, while the extra payment caused by introducing truthfulness in auction-based mechanism is about twice that of the NE in Stakelberg-game-based mechanism.

Crowdsourcing has become a popular service computing paradigm for requesters to integrate the ubiquitous human-intelligence services for tasks that are difficult for computers but trivial for humans. This paper focuses on crowdsourcing complex tasks by team formation in social networks (SNs) where a requester connects to a large number of workers. A good indicator of efficient team collaboration is the social connection among workers. Most previous social team formation approaches, however, either assume that the requester can maintain information of all workers and can directly communicate with them to build teams, or assume that the workers are cooperative and be willing to join the specific team built by the requester, both of which are impractical in many real situations. To this end, this paper first models each worker as a selfish entity, where the requester prefers to hire inexpensive workers that require less payment and workers prefer to join the profitable teams where they can gain high revenue. Within the noncooperative SNs, a distributed negotiation-based team formation mechanism is designed for the requester to decide which worker to hire and for the worker to decide which team to join and how much should be paid for his skill service provision. The proposed social team formation approach can always build collaborative teams by allowing team members to form a connected graph such that they can work together efficiently. Finally, we conduct a set of experiments on real dataset of workers to evaluate the effectiveness of our approach. The experimental results show that our approach can: 1) preserve considerable social welfare by comparing the benchmark centralized approaches and 2) form the profitable teams within less negotiation time by comparing the traditional distributed approaches, making our approach a more economic option for real-world applications.

Cloud computing has emerged as a very flexible service paradigm by allowing users to require virtual machine (VM) resources on-demand and allowing cloud service providers (CSPs) to provide VM resources via a pay-as-you-go model. This paper addresses the CSP's problem of efficiently allocating VM resources to physical machines (PMs) with the aim of minimizing the energy consumption. Traditional energy-aware VM allocations either allocate VMs to PMs in a centralized manner or implement VM migrations for energy reduction without considering the migration cost in cloud computing systems. We address these two issues by introducing a decentralized multiagent (MA)-based VM allocation approach. The proposed MA works by first dispatching a cooperative agent to each PM to assist the PM in managing VM resources. Then, an auction-based VM allocation mechanism is designed for these agents to decide the allocations of VMs to PMs. Moreover, to tackle system dynamics and avoid incurring prohibitive VM migration overhead, a local negotiation-based VM consolidation mechanism is devised for the agents to exchange their assigned VMs for energy cost saving. We evaluate the efficiency of the MA approach by using both static and dynamic simulations. The static experimental results demonstrate that the MA can incur acceptable computation time to reduce system energy cost compared with traditional bin packing and genetic algorithm-based centralized approaches. In the dynamic setting, the energy cost of the MA is similar to that of benchmark global-based VM consolidation approaches, but the MA largely reduces the migration cost.

Team formation is an effective collaboration manner in social networks (SNs). Within teams, social individuals can work together to accomplish complex jobs that they are unable to perform individually. Due to its wide range of applications, team formation in SNs has been studied extensively and a number of approaches have been proposed. However, all of these proposals either build teams of individuals to accomplish jobs through a centralized manner or ignore the selfish nature of social individuals, or both. In this paper, we introduce a decentralized negotiation-based team formation model for non-cooperative SNs, where social individuals are self-interested. The proposed team formation model works by allowing the employer (i.e., Job initiator) to recruit a team of professional employees that demand small working remuneration and incur little communication overhead and allowing the employees to join the beneficial teams from which they can achieve a high financial remuneration. The simulation results show that our model achieves about 80% social welfare of the ideal centralized models on average. Moreover, compared to other conventional distributed models, our model can reduce team formation time significantly, making our model a better choice for the real-world time-sensitive applications.

In this paper, we propose a novel community-aware task allocation model for social networked multiagent systems (SN-MASs), where the agent' cooperation domain is constrained in community and each agent can negotiate only with its intracommunity member agents. Under such community-aware scenarios, we prove that it remains NP-hard to maximize system overall profit. To solve this problem effectively, we present a heuristic algorithm that is composed of three phases: 1) task selection: select the desirable task to be allocated preferentially; 2) allocation to community: allocate the selected task to communities based on a significant task-first heuristics; and 3) allocation to agent: negotiate resources for the selected task based on a nonoverlap agent-first and breadth-first resource negotiation mechanism. Through the theoretical analyses and experiments, the advantages of our presented heuristic algorithm and community-aware task allocation model are validated. 1) Our presented heuristic algorithm performs very closely to the benchmark exponential brute-force optimal algorithm and the network flow-based greedy algorithm in terms of system overall profit in small-scale applications. Moreover, in the large-scale applications, the presented heuristic algorithm achieves approximately the same overall system profit, but significantly reduces the computational load compared with the greedy algorithm. 2) Our presented community-aware task allocation model reduces the system communication cost compared with the previous global-aware task allocation model and improves the system overall profit greatly compared with the previous local neighbor-aware task allocation model.

In the past, many approaches have been devised to address the load balancing problem for social networked multiagent systems (SN-MASs). However, few of these approaches consider the migration cost incurred when migrating tasks for load balancing, moreover, current SN-MASs often consist of communities, and the migration costs of intra-community and intercommunity transfers are heterogeneous. To minimize the load imbalance of agents and to incur the least migration cost, this paper introduces a net profit-based load balancing mechanism. In this mechanism, each load balance process (i.e., migrating a task from one agent to another agent) is associated with a net profit value which depends on the benefit it gains by making a contribution to alleviating the system load unfairness and the cost of migrating the task. The agents always perform the optimal load balance process that has the maximum net profit value, thereby improving system performance, as well as reducing the migration cost. Our simulations show that our approach not only guarantees that agents can undertake fair loads but also reduces the overhead migration costs compared with the previous load balancing approaches that ignore the cost of migrating the task.

Task execution of multiagent systems in social networks (MAS-SN) can be described through agents' operations when accessing necessary resources distributed in the social networks; thus, task allocation can be implemented based on the agents' access to the resources required for each task and aimed to minimize this resource access time. Currently, in undependable MAS-SN, there are deceptive agents that may fabricate their resource status information during task allocation but not really contribute resources to task execution; although there are some game theory-based solutions for undependable MAS, but which do not consider minimizing resource access time that is crucial to the performance of task execution in social networks. To achieve dependable resources with the least access time to execute tasks in undependable MAS-SN, this paper presents a novel task allocation model based on the negotiation reputation mechanism, where an agent's past behaviors in the resource negotiation of task execution can influence its probability to be allocated new tasks in the future. In this model, the agent that contributes more dependable resources with less access time during task execution is rewarded with a higher negotiation reputation, and may receive preferential allocation of new tasks. Through experiments, we determine that our task allocation model is superior to the traditional resources-based allocation approaches and game theory-based allocation approaches in terms of both the task allocation success rate and task execution time and that it usually performs close to the ideal approach (in which deceptive agents are fully detected) in terms of task execution time.