Adversarial Task Assignment

Adversarial Task Assignment

Chen Hajaj, Yevgeniy Vorobeychik

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 3783-3789. https://doi.org/10.24963/ijcai.2018/526

The problem of task assignment to workers is of long-standing fundamental importance. Examples of this include the classical problem of assigning computing tasks to nodes in a distributed computing environment, assigning jobs to robots, and crowdsourcing. Extensive research into this problem generally addresses important issues such as uncertainty and incentives. However, the problem of adversarial tampering with the task assignment process has not received as much attention.  We are concerned with a particular adversarial setting in task assignment where an attacker may target a set of workers in order to prevent the tasks assigned to these workers from being completed. For the case when all tasks are homogeneous, we provide an efficient algorithm for computing the optimal assignment. When tasks are heterogeneous, we show that the adversarial assignment problem is NP-Hard, and present an algorithm for solving it approximately. Our theoretical results are accompanied by extensive simulation results showing the effectiveness of our algorithms.
Keywords:
Multidisciplinary Topics and Applications: Security and Privacy
Agent-based and Multi-agent Systems: Economic Paradigms, Auctions and Market-Based Systems
Agent-based and Multi-agent Systems: Resource Allocation