Ronghui Yang, Jie Liu, Jiajie Zeng, Jiexin Wang, Jiuchuan Jiang, Bo An, Yi Cai, Mengchen Zhao. Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2026.

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.

In industrial production processes, disruptions within the industrial chain can severely affect the collaborative capabilities of production agents. A notable example occurred during the COVID-19 pandemic, when many agents faced interruption risks and were unable to participate in coordinated production. Ensuring continuity under such conditions requires migrating tasks from disrupted agents to viable alternatives. Designing effective task migration strategies, however, must account for the emergent multiplex nature of modern industrial chains. In these multiplex networked industrial chains, disruption risk in one layer can propagate to others, generating cascading failures across the system. This introduces two key challenges: (1) disruption risk creates mismatches not only between product agents and tasks but also across network layers, enlarging the problem dimensionality; and (2) simultaneous disruptions across multiple agents and layers increase the volume of tasks needing migration, greatly expanding the solution space. To address these challenges, we introduce the notion of a multiplex potential field, which captures cross-layer interdependencies and system-level dynamics in multiplex industrial chains. Building on this concept, we develop a hierarchical contextual task migration algorithm that exploits the multiplex potential field to guide both inter-layer and intra-layer task reallocations. Extensive experiments show that our approach consistently achieves superior utility, markedly improves task completion ratios, and reduces execution costs compared to benchmark algorithms. Furthermore, it attains solution quality comparable to that of the optimal CPLEX solver while requiring substantially less computation time. Finally, a case study on the FAO international food trade network demonstrates that the proposed framework is not only theoretically robust but also practically effective when deployed on large-scale real-world multiplex systems.

Sybil attacks are a prevalent concern within the realm of crowdsourcing, underscoring the significance of quality control in this domain. Truth discovery has been extensively studied to deduce the most trustworthy information from conflicting data based on the principle that reliable workers yield reliable answers. However, existing truth discovery approaches overlook the metric of workers' reputations, e.g., workers' historical approval rates on crowdsourcing platforms, despite being inflated and noisy, they offer a rough indication of workers' ability. In this paper, we first refine the approval rate using Wilson Lower Bound to enhance its confidence, and then mitigate its noise and inflation through a method based on ranking similarity. Specifically, we propose a method called RCTD (Reputation-Constrained Truth Discovery), which introduces a similarity metric between the rankings of workers' weights and the refined approval rates. This metric serves as a penalizing factor in the objective function of the truth discovery, restricting workers' weights to avoid excessively deviating from their historical reputation during the weight estimation process. We solve the objective function by introducing the block coordinate descent coupled with heuristics approach method. Experimental results on real-world datasets demonstrate that our approach achieves more accurate inference of true results in the Sybil attack environment compared to the state-of-the-art methods.

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.

Multiple-instance learning (MIL) solves the problem where training instances are grouped in bags, and a binary (positive or negative) label is provided for each bag. Most of the existing MIL studies need fully labeled bags for training an effective classifier, while it could be quite hard to collect such data in many real-world scenarios, due to the high cost of data labeling process. Fortunately, unlike fully labeled data, triplet comparison data can be collected in a more accurate and human-friendly way. Therefore, in this article, we for the first time investigate MIL from only triplet comparison bags , where a triplet (X a , X b , X c ) contains the weak supervision information that bag X a is more similar to X b than to X c . To solve this problem, we propose to train a bag-level classifier by the empirical risk minimization framework and theoretically provide a generalization error bound. We also show that a convex formulation can be obtained only when specific convex binary losses such as the square loss and the double hinge loss are used. Extensive experiments validate that our proposed method significantly outperforms other baselines.

Knowledge-based clustering algorithms can improve traditional clustering models by introducing domain knowledge to identify the underlying data structure. While there have been several approaches to clustering with the guidance of knowledge tidbits, most of them mainly focus on numeric knowledge without considering the uncertain nature of information. To capture the uncertainty of information, pure numeric knowledge tidbits are expanded to knowledge granules in this article. Then, two questions arise: how to obtain granular knowledge and how to use those knowledge granules in clustering. To the end, a novel knowledge extraction and granulation (KEG) method and a granular knowledge-based fuzzy clustering model are proposed in this study. First, inspired by the concept of natural neighbors, an automatic KEG is developed. In KEG, high-density points are filtered from the dataset and then merged with their natural neighbors to form several dense areas, i.e., granular knowledge. Furthermore, the granular knowledge expressed by interval or triangular numbers is leveraged into the clustering algorithm, which is the framework of fuzzy clustering with granular knowledge. To concretize this model into clustering algorithms, the classical fuzzy C-Means clustering algorithm has been selected to incorporate the granular knowledge produced by KEG. Then, the corresponding fuzzy C-Means clustering with interval knowledge granules (IKG-FCM) and triangular knowledge granules (TKG-FCM) are proposed. Experiments on synthetic and real-world datasets demonstrate that IKG-FCM and TKG-FCM always achieve better clustering performance with less time cost, especially on imbalanced data, compared with state-of-the-art algorithms.

As an essential problem in robotics, foraging means that robots collect objects from a given environment and return them to a specified location. On many occasions, robots are required to perform foraging tasks in adversarial environments, such as battlefield rescue, where potential adversaries may damage robots with a certain probability. The longer an individual robot moves through adversarial environments, the higher the probability of being damaged by adversaries. The robot system can gain utility only when the robot brings carried objects back to a predetermined home station. Such a risk of being damaged makes returning home at different locations potentially relevant to the expected utility produced by the robot. Thus, the individual robot faces a dilemma when it responds to the potential risks in adversarial environments: whether to return the carried resources home or continue foraging tasks. In this article, two fundamental environment settings are discussed, homogeneous cases and heterogeneous cases. The former is analyzed as having both the optimal substructure property and the non-aftereffect property. Then, we present a dynamic programming (DP) algorithm that can find an optimal solution with polynomial time complexity. For the latter, it is proven that finding an optimal solution is \( \mathcal {NP} \) -hard. We then propose a heuristic algorithm: A division hierarchical path planning (DHPP) algorithm that is based on the idea of dividing the foraging routes generated initially into a certain number of subroutes to dilute risks. Finally, these algorithms are extensively evaluated in simulations, concluding that in adversarial environments, they can significantly improve the productivity of an individual robot before it is damaged.

Team formation has been extensively studied for complex task crowdsourcing in E-markets, in which a set of workers are hired to form a team to complete a complex task collaboratively. However, existing studies have two typical drawbacks: 1) each team is created for only one task, which may be costly and cannot accommodate crowdsourcing markets with a large number of tasks; and 2) most existing studies form teams in a centralized manner by the requesters, which may place a heavy burden on requesters. In fact, we observe that many complex tasks at real-world crowdsourcing platforms have similar skill requirements and workers are often connected through social networks. Therefore, this paper explores distributed team formation-based batch crowdsourcing for complex tasks to address the drawbacks in existing studies, in which similar tasks can be addressed in a batch to reduce computational costs and workers can self-organize through their social networks to form teams. To solve such an NP-hard problem, this paper presents two approaches: one is to form a fixed team for all tasks in the batch; the other is to form a basic team that can be dynamically adjusted for each task in the batch. In comparison, the former approach has lower computational complexity but the latter approach performs better in reducing the total payments by requesters. With the experiments on a real-world dataset comparing with previous benchmark approaches, it is shown that the presented approaches have better performance in saving the costs of forming teams, payments by requesters, and communication among team members; moreover, the presented approaches have higher success rate of tasks and much better scalability.

Existing studies on the multirobot foraging problem often assume safe settings, in which nothing in an environment hinders the robots’ tasks. In many real-world applications, robots have to collect objects from hazardous environments like earthquake rescue, where possible risks exist, with possibilities of destroying robots. At this stage, there are no targeted algorithms for foraging robots in hazardous environments, which can lead to damage to the robot itself and reduce the final foraging efficiency. A motivating example is a rescue scenario, in which the lack of a suitable solution results in many victims not being rescued after all available robots have been destroyed. Foraging robots face a dilemma after some robots have been destroyed: whether to take over tasks of the destroyed robots or continue executing their remaining foraging tasks. The challenges that arise when attempting such a balance are twofold: (1) the loss of robots adds new constraints to traditional problems, complicating the structure of the solution space, and (2) the task allocation strategy in a multirobot team affects the final expected utility, thereby increasing the dimension of the solution space. In this study, we address these challenges in two fundamental environmental settings: homogeneous and heterogeneous cases. For the former case, a decomposition and grafting mechanism is adopted to split this problem into two weakly coupled problems: the foraging task execution problem and the foraging task allocation problem. We propose an exact foraging task allocation algorithm, and graft it to another exact foraging task execution algorithm to find an optimal solution within the polynomial time. For the latter case, it is proven \( \mathcal {NP} \) -hard to find an optimal solution in polynomial time. The decomposition and grafting mechanism is also adopted here, and our proposed greedy risk-aware foraging algorithm is grafted to our proposed hierarchical agglomerative clustering algorithm to find high-utility solutions with low computational overhead. Finally, these algorithms are extensively evaluated through simulations, demonstrating that compared with various benchmarks, they can significantly increase the utility of objects returned by robots before all the robots have been stopped.

Previous crowdsourcing studies often adopted the individual-oriented approach that outsources a task to an individual worker or team formation-based approach that outsources a task to an artificially formed team of workers. Nowadays, workers are often naturally organized into groups through social networks. To address such common issue of grouped workers in real crowdsourcing systems, this article explores a novel crowdsourcing paradigm in which the task allocation targets are naturally existing worker groups but not individual workers or artificially formed teams as before. Because a natural group might not possess all required skills and needs to coordinate with other groups in the social network contexts for performing a complex task, a concept of contextual crowdsourcing value is presented to measure a group's capacity to complete a task by coordinating with its contextual groups, which determines the priority that the group is assigned the task; then, the task allocation algorithms, including the allocations of groups and the workers actually participating in executing the task, are designed. The experiments on a real-world dataset show that our presented group-oriented approach can nearly always achieve better synergy performance, consistency performance, conflict performance, adaptability, and effectiveness on reducing costs, as compared with previous benchmark individual-oriented and team formation approaches.

There are two problems in the traditional crowdsourcing systems for handling complex tasks. First, decomposing complex tasks into a set of micro-subtasks requires the decomposition capability of the requesters; thus, some requesters may abandon using crowdsourcing to accomplish a large number of complex tasks since they cannot bear such heavy burden by themselves. Second, tasks are often assigned redundantly to multiple workers to achieve reliable results, but reliability may not be ensured when there are many malicious workers in the crowd. Currently, it is observed that the workers are often connected through social networks, a feature that can significantly facilitate task allocation and task execution in crowdsourcing. Therefore, this paper investigates crowdsourcing in social networks and presents a novel context-aware reliable crowdsourcing approach. In our presented approach, the two problems in traditional crowdsourcing are addressed as follows: 1) the complex tasks can be performed through autonomous coordination between the assigned worker and his contextual workers in the social network; thus, the requesters can be exempt from a heavy computing load for decomposing complex tasks into subtasks and combing the partial results of subtasks, thereby enabling more requesters to accomplish a large number of complex tasks through crowdsourcing, and 2) the reliability of a worker is determined not only by the reputation of the worker himself but also by the reputations of the contextual workers in the social network; thus, the unreliability of transient or malicious workers can be effectively addressed. The presented approach addresses two types of social networks including simplex and multiplex networks. Based on theoretical analyses and experiments on a real-world dataset, we find that the presented approach can achieve significantly higher task allocation and execution efficiency than the previous benchmark task allocation approaches; moreover, the presented contextual reputation mechanism can achieve relatively higher reliability when there are many malicious workers in the crowd.

Existing studies on crowdsourcing often adopt the retail-style allocation approach, in which tasks are allocated individually and independently. However, such retail-style task allocation has the following problems: 1) each task is executed independently from scratch, thus the execution of one task seldom utilize the results of other tasks and the requester must pay in full for the task; 2) many workers only undertake a very small number of tasks contemporaneously, thus the workers' skills and time may not be fully utilized. We observe that many complex tasks in real-world crowdsourcing platforms have similar skill requirements and long deadlines. Based on these real-world observations, this paper presents a novel batch allocation approach for tasks with overlapping skill requirements. Requesters' real payment can be discounted because the real execution cost of tasks can be reduced due to batch allocation and execution, and each worker's real earnings may increase because he/she can undertake more tasks contemporaneously. This batch allocation optimization problem is proved to be NP-hard. Then, two types of heuristic approaches are designed: layered batch allocation and core-based batch allocation. The former approach mainly utilizes the hierarchy pattern to form all possible batches, which can achieve better performance but may require higher computational cost since all possible batches are formed and observed; the latter approach selects core tasks to form batches, which can achieve suboptimal performance with lower complexity and significantly reduce computational cost. With the theoretical analyses and experiments on a real-world Upwork dataset in which the proposed approaches are compared with the previous benchmark retail-style allocation approach, we find that our approaches have better performances in terms of total payment by requesters and average income of workers, as well as maintaining close successful task completion probability and consuming less task allocation time.

One of the greatest advancements of the modern era is the evolution of smart grid (SG), which integrates information communication technologies with advanced power electronic technologies to cope with the global energy shortage. The users in SGs are often called the “prosumers,” who not only consume energy but also generate the energy and share it with the utility grid or with other energy consumers. In order to promote sustainable prosumer management in SGs, one of the feasible strategies is to aggregate the prosumers from different locations, but with similar energy behaviors and cohesive interconnections, such groups of prosumers are also called the prosumer-community groups (PCGs). The contribution of this paper is threefold. First, we provide a generalized definition of individual prosumer's energy density, which can be used to detect the underlying leader prosumers in SGs. Second, we formulate the PCG detection (PCG-D) as a multiobjective optimization problem, and present a novel dynamic game model to find the locally Pareto-optimal PCG structure. Third, we propose a partially visible multiagent system (PVMAS), where the viewing angles of both prosumers and PCGs are mutually restricted. The significance of our PVMAS is that it can nicely lead itself to parallelization for PCG-D, due to the fact that the feature updating of each agent is independent of each other. We conduct a series of comprehensive experiments on the simulated SG datasets to validate the performance of PVMAS through comparing it with existing community detection approaches in the literature.

Crowdsourcing has recently been significantly explored. Although related surveys have been conducted regarding this subject, each has mainly consisted of a review of a single aspect of crowdsourcing systems or on the application of crowdsourcing in a specific application domain. A crowdsourcing system is a comprehensive set of multiple entities, including various elements and processes. Multiagent computing has already been widely envisioned as a powerful paradigm for modeling autonomous multi-entity systems with adaptation to dynamic environments. Therefore, this article presents a novel multiagent perspective and approach to understanding crowdsourcing systems, which can be used to correlate the research on crowdsourcing and multiagent systems and inspire possible interdisciplinary research between the two areas. This article mainly discusses the following two aspects: (1) The multiagent perspective can be used for conducting a comprehensive survey on the state of the art of crowdsourcing, and (2) the multiagent approach can bring about concrete enhancements for crowdsourcing technology and inspire future research directions that enable crowdsourcing research to overcome the typical challenges in crowdsourcing technology. Finally, this article discusses the advantages and disadvantages of the multiagent perspective by comparing it with two other popular perspectives on crowdsourcing: the business perspective and the technical perspective.

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.

In the complex software systems, software agents always need to negotiate with other agents within their physical and social contexts when they execute tasks. Obviously, the capacity of a software agent to execute tasks is determined by not only itself but also its contextual agents; thus, the number of tasks allocated on an agent should be directly proportional to its self-owned resources as well as its contextual agents' resources. This paper presents a novel task allocation model based on the contextual resource negotiation. In the presented task allocation model, while a task comes to the software system, it is first assigned to a principal agent that has high contextual enrichment factor for the required resources; then, the principal agent will negotiate with its contextual agents to execute the assigned task. However, while multiple tasks come to the software system, it is necessary to make load balancing to avoid overconvergence of tasks at certain agents that are rich of contextual resources. Thus, this paper also presents a novel load balancing method: if there are overlarge number of tasks queued for a certain agent, the capacities of both the agent itself and its contextual agents to accept new tasks will be reduced. Therefore, in this paper, the task allocation and load balancing are implemented according to the contextual resource distribution of agents, which can be well suited for the characteristics of complex software systems; and the presented model can reduce more communication costs between allocated agents than the previous methods based on self-owned resource distribution of agents.