# adversarial_task_assignment__c4050fd2.pdf

Adversarial Task Assignment

Chen Hajaj and Yevgeniy Vorobeychik Electrical Engineering and Computer Science Vanderbilt University, Nashville, Tennses {chen.hajaj, yevgeniy.vorobeychik}@vanderbilt.edu

The problem of assigning tasks 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 where an attacker may target a set of workers in order to prevent the tasks assigned to these workers from being completed. When all tasks are homogeneous, we provide an efﬁcient 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 experiments showing the effectiveness of our algorithms.

1 Introduction

The problem of allocating a set of tasks among a collection of workers has been a fundamental research question in a broad array of domains, including distributed computing, robotics, and, recently, crowdsourcing [Alistarh et al., 2012; Stone and Veloso, 1999; Liu and Chen, 2017]. Despite the extensive interest in the problem, however, there is little prior work on task assignment in settings where workers may be attacked. Such adversarial task assignment problems can arise, for example, when tasks are of high economic or political consequence, such as in robotic rescue missions following terror activities, or crowdsourcing to determine which executables are malicious or benign, or which news stories constitute fake news. We investigate the adversarial task assignment problem in which a rational external attacker targets one or more workers after tasks have already been assigned. Equivalently, this can be viewed as a robust task assignment problem with unknown uncertainty about worker failures. We formalize the

interaction between the attacker and requester (defender) as a Stackelberg game in which the defender ﬁrst chooses an assignment, and the attacker subsequently attacks a set of workers so as to maximize the defender s losses from the attack. We seek a strong Stackelberg equilibrium (SSE) of this game and focus on computing an optimal robust assignment. Our analysis begins with a setting in which tasks are homogeneous, that is, all tasks have the same utility for the defender (e.g., rescue soldiers from a battleﬁeld, or label a large dataset of images). We characterize the optimal structure of a robust assignment, and use this insight to develop an algorithm that extracts this assignment in time linear in the number of tasks and targets, and quadratic in the number of workers. We show that this algorithm signiﬁcantly outperforms several baselines, and obtains a good solution even when no adversary is present. Next, we turn to heterogeneous task settings. This case, it turns out, is considerably more challenging. Speciﬁcally, we show that it may be beneﬁcial to assign more than a single worker to a task. Moreover, even if we impose a restriction that only a single worker can be assigned to a task (optimal when tasks are homogeneous), extracting the optimal assignment is strongly NP-Hard. To overcome this issue, we propose an integer programming approach for solving the restricted problem, as well as an algorithm for ﬁnding an approximately optimal assignment in the general case. Again, our experiments show that our approach signiﬁcantly outperforms several baselines.

Related Work The problem of task assignment in adversarial settings has been considered from several perspectives. One major stream of literature is about robots acting in adversarial environments. Alighanbari and How [2005] consider assigning weapons to targets, somewhat analogous to our problem, but do not model the decision of the adversary; their model also has rather different semantics than ours. Robotic soccer is another common adversarial planning problem, although the focus is typically on coordination among robots when two opposing teams are engaged in coordination and planning [Jones et al., 2006]. Another major literature stream which considers adversarial issues is crowdsourcing. One class of problems is a number of workers to hire [Carvalho et al., 2016], the issue of individual worker incentives in truthfully responding

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)

to questions [Singla and Krause, 2013], or in the amount of effort they devote to the task [Tran-Thanh et al., 2014; Elmalech et al., 2016; Liu and Chen, 2017], rather than adversarial reasoning per se. Another, more directly adversarial setting, considers situations where some workers simply answer questions in an adversarial way [Ghosh et al., 2011; Steinhardt et al., 2016]. However, the primary interest in this work is robust estimation when tasks are assigned randomly or exogenously, rather than task assignment itself. Similarly, prior research on machine learning when a portion of data is adversarially poisoned [Chen et al., 2011; Xu et al., 2010; Feng et al., 2014; Chen et al., 2013; Liu et al., 2017] focuses primarily on the robust estimation problem, and not task assignment; in addition, it does not take advantage of structure in the data acquisition process, where workers, rather than individual data points, are attacked. Other works [Gu et al., 2005; Alon et al., 2015] focus on the change of the system after the assignment process and the structure of the social network rather than the assignment process itself. Our work has a strong connection to the literature on Stackelberg security games [Conitzer and Sandholm, 2006; Korzhyk et al., 2010; Tambe, 2011]. However, the mathematical structure of our problem is quite different. For example, we have no protection resources to allocate, and instead, the defender s decision is about assigning tasks to potentially untrusted workers.

Consider an environment populated with a single requester (hereafter denoted by defender ), a set of n workers, W, a set of m tasks, T, and an adversary. Furthermore, each worker w W is characterized by a capacity constraint cw, which is the maximum number of tasks it can be assigned, and an individual proﬁciency or the probability of successfully completing a task, denoted by pw. Worker proﬁciencies are assumed to be common knowledge to both the defender and attacker. Such proﬁciencies can be learned from experience [Sheng et al., 2008; Dai et al., 2011; Manino et al., 2016]; moreover, in many settings, these are provided by the task assignment (e.g., crowdsourcing) platform, in the form of a reputation system [Mason and Suri, 2012]. For exposition purposes, we index the workers by integers i in decreasing order of their proﬁciency, so that P = (p1, . . . , pn) s.t. pi pj i < j, and denote the set of k most proﬁcient workers by W k. Thus, the capacity of worker i would be denoted by ci. Each task t T is associated with a utility ut that the defender obtains if this task is completed successfully. If the task is not completed successfully, the defender obtains zero utility from it. We focus on the common case where the defender faces a budget constraint of making at most B m assignments; the setting with B > m necessitates different algorithmic techniques, and is left for future work. The defender s fundamental decision is the assignment of tasks to workers. Formally, an assignment s speciﬁes a subset of tasks T (s) and the set of workers, Wt(s) assigned to each task t T (s). Suppose that multiple workers are assigned to a task t, and

let Lt(s) denote the labels returned by workers in Wt(s) for t (for example, these could simply indicate whether a worker successfully complete the task). Then the defender determines the ﬁnal label to assign to t (e.g., whether or not the task has been successfully completed) according to some deterministic mapping δ : Lt(s) l (e.g., majority label), such that L {1, . . . , jt}|Wt(s)| and l {1, . . . , jt}. Naturally, whenever a single worker w is a assigned to a task and returns a label lw, δ(lw) = lw. Let ιt be the (unknown) correct label corresponding to a task t; this could be an actual label, such as the actual object in the image, or simply a constant 1 if we are only interested in successful completion of the task. The defender s expected utility when assigning a set of tasks T (s) to workers and obtaining the labels is then

udef(s) = X

t T (s) ut Pr{δ(Lt(s)) = ιt}, (1)

where the probability is with respect to worker proﬁciencies (and resulting stochastic realizations of their outcomes). It is immediate that in our setting if there is no adversary and no capacity constraints for the workers, all tasks should be assigned to the worker with the highest pw. Our focus, however, is how to optimally assign workers to tasks when there is an intelligent adversary who may subsequently (to the assignment) attack a set of workers. In particular, we assume that there is an adversary (attacker) with the goal of minimizing the defender s utility udef; thus, the game is zero-sum. To this end, the attacker chooses a set of τ workers to attack, for example, by deploying a cyber attack against the corresponding computer nodes, physical attacks on search and rescue robots, or attacks against the devices on which the human workers performs their tasks. Alternatively, our goal is to be robust to τ-worker failures (e.g., N-τ-robustness [Chen et al., 2014]). We encode the attacker s strategy by a vector α where αw = 1 iff a worker w is attacked (and P w αw = τ since τ workers are attacked). The adversary s attack takes place after the tasks have already been assigned to workers, where the attacker knows the actual assignments of tasks to workers before deploying the attack, and the consequence of an attack on a worker w is that all tasks assigned to w fail to be successfully completed. Clearly, when an attacker is present, the policy of assigning all tasks to the most competent worker (when there are no capacity constraints) will yield zero utility for the defender, as the attacker will simply attack the worker to whom all the tasks are assigned. The challenge of how to split the tasks up among workers, trading off quality with robustness to attacks, is the subject of our inqury. Formally, we aim to compute a strong Stackelberg equilibrium of the game between the defender (leader), who chooses a task-to-worker assignment policy, and the attacker (follower), who attacks a single worker [Stackelberg, 1952].

3 Homogeneous Tasks We start by considering tasks which are homogeneous, that is, ut = ut for any two tasks t, t . Without loss of generality, suppose that all ut = 1. Note that since all tasks share the same utility, if B < m, the defender is indifferent regarding

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)

the identity of tasks being assigned. Further, it is immediate that we never wish to waste budget, since assigning a worker always results in non-negative marginal utility. Consequently, we can simply randomly subsample B tasks from the set of all tasks, and consider the problem with m = B. We overload the notation and use s = {s1, . . . , sn} to denote the number of tasks allocated to each worker. Although the space of deterministic assignments is large, we now observe several properties of optimal assignments which allow us to devise an efﬁcient algorithm for this problem. Proposition 1. Suppose that tasks are homogeneous. For any assignment s there is a weakly utility-improving assignment s for the defender which assigns each task to a single worker.

Proof. Consider an assignment s and the corresponding best response by the attacker, α, in which a worker w is attacked. Let a task t be assigned to a set of workers W t with |W t| = k > 2. Then there must be another task t which is unassigned. Now consider a worker w W t. Since utility is additive, we can consider just the marginal utility of any worker w to the defender and attacker; denote this by uw . Let Tw be the set of tasks assigned to a worker w under s. Let uw = P t Tw u M wt, where u M wt = ut Pr{δ(Lt(s)) = ιt} ut Pr{δ(Lt(s) \ Lw t ) = ιt} is the marginal utility of worker of w towards a task t. Clearly, uw u w, since the attacker is playing a best response. Suppose that we reassign w from t to t . If w = w, the attacker will still attack w (since the utility of w to the attacker can only increase), and the defender is indifferent. If w = w, there are two cases: (a) the attacker still attacks w after the change, and (b) the attacker now switches to attack w. Suppose the attacker still attacks w. The defender s net gain is pw u M w t 0. If, instead, the attacker now attacks w, the defender s net gain is u w uw 0.

Consequently, we can restrict the set of assignments to those which assign a single worker per task; we denote this restricted set of assignments by S. Given a assignment s S and the attack strategy α, the defender s expected utility is:

udef(s, α) = X

w W swpw(1 αw) (2)

Next, we show that there is always an optimal assignment that assigns tasks to the k most proﬁcient workers, for some k. Proposition 2. In an optimal assignment s, suppose that si > 0 for i > 1. Then there must be an optimal assignment in which si 1 > 0.

Proof. Consider an optimal assignment s and the attacker s best response α in which W is the set of workers being attacked. Now, consider moving 1 task from i to i 1. We denote the updated set of workers attacked (due to this change) as W . Suppose that i W, that is, the worker i was initially attacked. If i 1 W , there are two potions: 1) i W (i.e., i is still being attacked) and hence the net gain to the defender does not change, and 2) i / W and hence the net gain to the defender is pi(|Ti| 1) 0. If i 1 / W , the net gain is pi 1 > 0. Suppose that i / W. If i 1 is now attacked, the net gain is pw(|Tw| 1) 0 (where w W

and w / W ). Otherwise (i.e., i 1 / W ), the net gain is pi 1 pi 0.

We can now present an assignment algorithm for optimal assignment (Algorithm 1) which has complexity O(n2mτ). The intuition behind the algorithm is to consider each worker i as a potential target of an attack, and then compute the best assignment subject to a constraint that i is attacked (i.e., that pisi pjsj for all other workers j = i). Subject to this constraint, we consider all possible numbers of tasks that can be assigned to i, and then assign as many tasks as possible to the other workers in order of their proﬁciency (where the τ workers that contribute the most to the defender s utility are attacked). The only special case (Steps 7-10) is when assigning the last worker. In this case, it may be beneﬁcial to alternate the last two workers assignments to result in a more beneﬁcial overall assignment. Optimality follows from the fact that we exhaustively search possible targets and allocation policies to these, and assign as many tasks as possible to the most effective workers.1

Algorithm 1 Homogeneous assignment

input: The set of workers W, and their proﬁciencies P return: The optimal policy s

1: umax 0 2: for i {1, . . . , n} do 3: for si {1, . . . , ci} do 4: Υi sipi,B m si 5: for j {1, . . . , n} \ i do

6: sj min( j pi pj si k , B, cj), B B sj

7: if j < n B+1 min( j pi pj+1 si k 1, cj+1) then

8: s s, s j sj 1 9: if udef(s, α) udef(s , α ) + pj+1 then 10: sj sj 1, B B + 1

11: Υj sjpj 12: Sort Υ in ascending order 13: util Pn τ k=1 Υk 14: if util > umax then 15: umax util, s s 16: return s

4 Heterogeneous Tasks

It turns out that the more general problem in which utilities are heterogeneous is considerably more challenging than the case of homogeneous allocation. First, we show that even if the tasks utilities are slightly different, it may be beneﬁcial to assign the same task to multiple workers. Consider the case of an environment populated with 2 workers and 2 tasks. WLOG, we order the tasks by their utility, i.e., ut1 > ut2. Regardless of the workers proﬁciencies, assigning one worker per task will result in an expected utility of min(piut1, pjut2).

1A detailed proof of Algorithm 1 s optimality is available at: https://arxiv.org/abs/1804.11221

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)

On the other hand, assigning both workers to t1 will result in an expected utility of min(piut1, pjut1) which is promised to be equal or higher. Aside from the considerably greater complexity challenge associated with solving problems with heterogeneous utilities suggested by this example, there is the additional challenge of incorporating (non-linear) decision rules into the optimization problem to resolving disagreement among workers, should it arise. We begin by showing that if B m, there is an optimal assignment in which only the B tasks associated with the highest utility are included.

Proposition 3. Suppose that tasks are heterogeneous. For any assignment s there is a weakly utility-improving (i.e., results in the same or higher utility) assignment s for the defender which only assigns tasks from the set of tasks with the B highest utilities.

Proof. For readability, we assume that tasks are ordered based on their utility in decreasing order (i.e., ui uj, i j), and that a single worker is assigned per task; generalization is straightforward. Consider an assignment s and the corresponding best response by the attacker, α, in which the set of workers W is attacked. Let a task ti be s.t. i > B. Then there must be another task tj, s.t. j B, which is unassigned. Now consider a worker w Wti. Since utility is additive, we can consider just the marginal utility of any worker w to the defender and attacker; denote this by uw . Let Tw be the set of tasks assigned to a worker w under s. Let uw = P t Tw u M wt, where u M wt is the marginal utility of worker of w towards a task t. Suppose that we reassign w from ti to tj. If w W, the attacker will still attack w (since the utility of w to the attacker can only increase), and the defender is indifferent. If w / w, there are two cases: (a) the attacker still attacks W after the change, and (b) the attacker now switches to attack w. Suppose the attacker still attacks W. The defender s net gain is pwuj u M w t 0. If, instead, the attacker now attacks w, the defender s net gain is uw uw 0. Where w is the worker that is not being attacked anymore.

This allows us to restrict attention to the B highest-utility tasks, and assume that m = B. We now show that the defender s assignment problem, denoted Heterogeneous tasks assignment (HTA), is NP-Hard even if we restrict the strategies to assign only a single worker per task.

Proposition 4. HTA is strongly NP-Hard even when we assign only one worker per task.

Proof. We prove the proposition by reducing the decision version of the Bin packing problem (BP), which is a strongly NP-complete problem, to the decision version of the HTA problem. In the BP problem we are given a set {o1, o2, ..., om} of m objects of sizes {v1, v2, ..., vm} and a set of n containers {C1, C2, ..., Cn}, each of size γ, and we need to decide if all the objects can be ﬁtted into the given containers. Our transformation maps the set of m objects to a set of m + 1 tasks T = {t1, t2, ..., tm+1} with utilities {v1, v2, ..., vm, γ} and the set of n containers to a set of n+1

workers W = {w1, w2, ..., wn+1}. We consider the private case where all the workers have the same proﬁciency p (i.e. pw = p, w W). The decision version of the HTA problem asks if there exists an assignment of the m + 1 tasks to the n + 1 workers that achieves a utility of at least p V , where V = Pm i=1 vi. If we started with a YES instance of the BP problem, then there exists an assignment A that ﬁts all m objects into the n containers. Consider the following assignment of tasks to workers in the HTA problem. If A(oi) = Cj, we assign task ti to worker wj. Also, we assign task tm+1 (with utility γ) to worker wn+1. Note that no worker can achieve an individual utility greater than pγ, which is achieved by worker wn+1. Thus, the utility of the overall task assignment is Pm i=1 pvi + pγ pγ = p V , meaning that our transformation produced a YES instance of the HTA problem. Now suppose that we ended up with a YES instance of the HTA problem. Then there exists a task assignment B such that the sum of utilities (V ) minus the adversarial harm (γ ) is at least p V (i.e. V γ p V ). Note that V = P i = 1mpvi + pγ = p V + pγ (each task is assigned to some worker). This implies p V + pγ γ p V and γ /p γ. Thus the utility sum (before performance p is applied) of the tasks assigned to any single worker cannot exceed γ. This could only happen if task tm+1 (with utility γ) was the only task assigned to the corresponding player. WLOG let that worker be wn+1. All other tasks must have been assigned to workers {w1, w2, ..., wn}. It is easy to see that this implies a feasible assignment of objects to containers in the BP problem - if B(tj) = wi, for 1 j m, then we place object oj in container Ci. Thus the transformation must have started off with a YES instance of the BP problem.

We now propose an algorithm which computes an approximately optimal assignment. We begin by supposing that only one worker can be assigned per task (we relax this shortly). In this case, the optimal attack can be computed using the following linear integer program:

t T swtutpw (3a)

w W αw = τ (3b)

αw {0, 1}. (3c)

The objective (3a) aims to maximize the effect of the attack (i.e., the utility of the targets). Constraint (3b) ensures that the adversary attacks exactly τ workers. First, note that the extreme points of the constraint set are integral, which means we can relax the integrality constraint to αw [0, 1]. In order to plug this optimization into the defender s optimal assignment problem, we convert this relaxed program to its dual form:

min λ,β λτ + X

s.t. : λ + βw pw X

t T swtut w (4b)

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)

Thus, the optimal assignment can be computed using the following linear integer program:

max s,γ,λ,β

t T swtut γ (5a)

s.t. : γ λτ + X

t T swtutpw, w W (5c)

t T swt = m (5d)

w swt = 1, t T (5e)

t swt cw, w W (5f)

swt {0, 1}. (5g)

The objective (5a) aims to maximize the defender s expected utility given the adversary s attack (second term). Constraint (5b and 5c) validates that the adversary s targets are the workers who contribute the most to the defender s expected utility and Constraint (5d) ensures that each allocation assigns all the possible tasks among the different workers. Finally, Constraint (5e) ensures that only one worker is assigned for each task and Constraint (5f) ensures that no worker is assigned with more tasks than it can perform. Next, we propose a greedy algorithm that attempts to incrementally improve utility by shifting workers among tasks, now allowing multiple workers to be assigned to a task. Whenever more than one worker is assigned to a given task, the defender has to choose a deterministic mapping δ to determine the outcome. We consider a very broad class of weighted majority functions for this purpose (natural if successful completion of a task means that the worker returned the correct label). In this mapping, each worker w is assigned a weight θw, and the ﬁnal label is set according to the weighted majority rule, i.e., δ(Lt) = sgn(P w Wt(s) θwlw). In order to approximate the defender s expected utility, we use the sample average approximation (SAA) [Kleywegt et al., 2002] for solving stochastic optimization problems by using Monte-Carlo simulation. Using this approach, the defender s utility can be approximated by:

udef(CK, W ) = X

I{sgn P w W swtθw Cwtk}

(6) where CK is a set of K matrices, each of size n over m. Each cell Cwtk is a randomly sample based on pw represents whether or not the worker w successfully completed the task. That is, Cwtk = 1 if worker w successfully completed task t, and Cwtk = 0 otherwise. In a similar manner, swt = 1 if worker w is assigned to task t, and swt = 0 otherwise. Algorithm 2 formally describes the computation of this assignment. Given an optimal assignment extracted using the mixed-integer linear program in Equation (5), we iteratively alternate over all tasks in ascending order based on their utility. For each task, we reassign the worker associated with

this task to the most beneﬁcial task. If this reassignment improves the defender s utility, we label it as beneﬁcial (Steps 9 and 10). Finally, we commit to the reassignment that will maximize the defender s utility (Step 12).

Algorithm 2 Heterogeneous assignment

input: The set of workers W, and their proﬁciencies P return: The heuristic deterministic allocation

1: Extract the optimal 1-worker allocation using Equation 5 2: util udef(CK, α) 3: for t {1, . . . , m} do 4: for w {1, . . . , n} do 5: t = t 6: if swt = 1 then 7: for t {m, . . . , t + 1} do 8: swt = 1, swt = 0, Update α 9: if udef(CK, α) > util then 10: t = t , util udef(CK, α)

11: swt = 0, swt = 1 12: swt = 0, swt = 1

13: return s

5 Experiments

We now experimentally demonstrate the effectiveness of our proposed approaches. Workers proﬁciencies are sampled using two distributions: a uniform distribution over the [0.5, 1] interval and an exponential distribution with µ = 0.25 where proﬁciencies are truncated to be in this interval for the latter. We compare our adversarial assignment algorithms to three natural baselines: Split-k and two versions of Monte Carlo (involving random assignment of tasks to workers). Speciﬁcally, for the Split-k method, we divide tasks equally among the top k workers.2 For the Monte-Carlo approach, we consider a simple variant which randomly distributes tasks among all the workers, denoted by Monte-Carlo, and a variant of this which randomly distributes the tasks among the top n

2 workers, denoted by Top Monte-Carlo. In both cases, the assigned worker for each task is picked uniformly at random.

Homogeneous Tasks We begin by considering homogeneous tasks. For each experiment, we take an average of 5,000 sample runs. Figure 1 presents the results comparing our algorithm to baselines for 50 workers and tasks. As the ﬁgure shows, our algorithm outperforms the baselines, and the gap becomes particularly pronounced as the number of targets increases. Moreover, there doesn t appear to be a qualitative difference between uniform and exponential distribution in this regard. It is natural that we must trade off robustness with performance of robust algorithms in non-adversarial settings. We therefore conclude the homogeneous analysis by analyzing the loss incurred by allowing for robustness, compared to a solution which is optimal in non-adversarial settings. We vary

2The remainder is assigned in an iterative way from the least proﬁcient worker to the most proﬁcient one.

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)

1 2 3 4 5 6 7 8 9 10 Targets

Expected utility

Algorithm 1 Monte-Carlo Top Monte-Carlo Split-5 Split-7

(a) Uniform distribution

1 2 3 4 5 6 7 8 9 10 Targets

Expected utility

Algorithm 1 Monte-Carlo Top Monte-Carlo Split-5 Split-7

(b) Exponential distribution

Figure 1: Homogeneous tasks: comparison to baseline methods.

1 2 3 4 5 Targets

Expected utility

IP Split-5 Split-7 Monte-Carlo Top Monte-Carlo

(a) Uniform distribution

1 2 3 4 5 Targets

Expected utility

IP Split-5 Split-7 Monte-Carlo Top Monte-Carlo

(b) Exponential distribution

Figure 2: Heterogeneous tasks: comparison to baseline methods.

the number of workers from 2 to 50, and ﬁx the number of tasks at 100 and the number of targets optimized against at t = 1.

Workers 5 10 15 20 25 30 35 40 45 50 Exp. loss 24.9% 17.4% 15.27% 13.2% 11.6% 8.6% 5.8% 5.8% 6.5% 4.6%

Table 1: Expected loss of using adversarial assignment in nonadversarial settings.

Table 1 shows the expected loss of using adversarial task assignment in a non-adversarial settings. With only 5 workers, we pay a steep price (just under 25%), but as the number of workers increases, the loss shrinks; with 50 workers, we only lose 4.6% compared to optimal non-robust assignment.

Heterogeneous Tasks We used CPLEX version 12.51 to solve the integer linear program above. First, we analyze how the heterogeneous assignment given in mixed-integer linear program (MILP) (5) performs compared to the baselines when task utilities are sampled from U[0, 1] and worker proﬁciencies are samples from U[0.5, 1]. We use similar baseline methods to the ones used in studying homogeneous task assignment. Figure 2 depicts the expected utility for the defender when using each of the methods in an environment populated with 15 tasks and 10 workers where the number of targets the adversary attacks varies between 1 and 5 over 3, 000 runs. As is evident from the ﬁgure, even the baseline mixed-integer linear program (which assumes a single worker is assigned per task) signiﬁcantly outperforms the baselines, with the difference growing as we increase the number of workers attacked. Next, we evaluate how much more we gain by using Algorithm 2 after computing an initial assignment using MILP (5). In these experimets we use a natural weighted majority decision rule with θw = pw (i.e., workers proﬁciencies), and set K = 2500. We consider two uniform distributions for this study: U[0, 1] and U[0, 100]. Each marginal improvement is averaged over 3,000 runs.

Dist. Tasks n=2 n=3 n=4 n=5 n=6 U[0,1] 3 57.08% 37.10% U[0,1] 4 26.47% 9.88% 9.17% U[0,1] 5 22.03% 3.83% 3.39% 3.46% U[0,1] 6 19.98% 2% 1.79% 1.93% 1.66% U[0,100] 3 56.9% 37.92% U[0,100] 4 28.69% 9.59% 8.86% U[0,100] 5 20.02% 3.59% 3.51% 3.49% U[0,100] 6 17.41% 1.59% 1.71% 1.64% 1.77%

Table 2: Average improvement using Algorithm 2; τ = 1.

Dist. Tasks n=3 n=4 n=5 n=6 U[0,1] 3 1115.41% U[0,1] 4 46.27% 49.75% U[0,1] 5 19.52% 16.01% 21.68% U[0,1] 6 9.88% 7.49% 10.9% 12.18% U[0,100] 3 1130.13% U[0,100] 4 58.23% 64.45% U[0,100] 5 17.97% 14.62% 21.21% U[0,100] 6 8.62% 7.05% 9.83% 11.51%

Table 3: Average improvement using Algorithm 2; τ = 2.

The results are shown in Tables 2 and 3. We can see that there are cases where assigning multiple workers per task can offer a signiﬁcant beneﬁt. However, as the problem size increases, this beneﬁt signiﬁcantly attenuates, and it may sufﬁce to just rely on the assignment obtained from the MILP.

6 Conclusion

We consider the problem of assigning tasks to workers when workers can be attacked, and their ability to successfully complete assigned tasks compromised. We show that the optimal assignment problem (in the sense of Stackelberg equilibrium commitment), when the attack takes place after the tasks have been assigned to workers, can be found in pseudo-polynomial time. Furthermore, when tasks are heterogeneous, we show that the problem is more challenging, as it could be optimal to assign multiple workers to the same task. Even if we constrain the assignment such that only one worker is assigned per task, extracting the optimal assignment becomes strongly NP-Hard (we exhibit an integer linear program for the latter problem). Finally, we provide with an algorithm of converting this constraint assignment to one that allows multiple workers per task (and hence approximate optimal allocation). Acknowledgments

This research was partially supported by the National Science Foundation (CNS-1640624, IIS-1526860, IIS-1649972), Ofﬁce of Naval Research (N00014-15-1-2621), Army Research Ofﬁce (W911NF-16-1-0069), and National Institutes of Health (UH2 CA203708-01, R01HG006844-05).

References [Alighanbari and How, 2005] Mehdi Alighanbari and Jonathan P How. Cooperative task assignment of unmanned aerial vehicles in adversarial environments. In American Control Conference, 2005., pages 4661 4666. IEEE, 2005.

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)

[Alistarh et al., 2012] Dan Alistarh, Michael A Bender, Seth Gilbert, and Rachid Guerraoui. How to allocate tasks asynchronously. In IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 331 340. IEEE, 2012. [Alon et al., 2015] Noga Alon, Michal Feldman, Omer Lev, and Moshe Tennenholtz. How robust is the wisdom of the crowds? In Proceedings of the International Joint Conferences on Artiﬁcial Intelligence, pages 2055 2061, 2015. [Carvalho et al., 2016] Arthur Carvalho, Stanko Dimitrov, and Kate Larson. How many crowdsourced workers should a requester hire? Annals of Mathematics and Artiﬁcial Intelligence, 78(1):45 72, 2016. [Chen et al., 2011] Yudong Chen, Huan Xu, Constantine Caramanis, and Sujay Sanghavi. Robust matrix completion and corrupted columns. In International Conference on Machine Learning (ICML), pages 873 880, 2011. [Chen et al., 2013] Yudong Chen, Constantine Caramanis, and Shie Mannor. Robust sparse regression under adversarial corruption. In International Conference on Machine Learning (ICML), pages 774 782, 2013. [Chen et al., 2014] Richard Li-Yang Chen, Amy Cohn, Neng Fan, and Ali Pinar. Contingency-risk informed power system design. IEEE Transactions on Power Systems, 29(5):2087 2096, 2014. [Conitzer and Sandholm, 2006] Vincent Conitzer and Tuomas Sandholm. Computing the optimal strategy to commit to. In Proceedings of the ACM Conference on Electronic Commerce (EC), pages 82 90, 2006. [Dai et al., 2011] Peng Dai, Daniel Sabby Weld, et al. Artiﬁcial intelligence for artiﬁcial artiﬁcial intelligence. In Proceedings of AAAI, pages 1153 1159, 2011. [Elmalech et al., 2016] Avshalom Elmalech, David Sarne, Esther David, and Chen Hajaj. Extending workers attention span through dummy events. In Proceedings of HCOMP, 2016. [Feng et al., 2014] Jiashi Feng, Huan Xu, Shie Mannor, and Shuicheng Yan. Robust logistic regression and classiﬁcation. In NIPS, pages 253 261, 2014. [Ghosh et al., 2011] Arpita Ghosh, Satyen Kale, and Preston Mc Afee. Who moderates the moderators? crowdsourcing abuse detection in user-generated content. In Proceedings of the ACM Conference on Electronic Commerce (EC), pages 167 176, 2011. [Gu et al., 2005] Dazhang Gu, Frank Drews, and Lonnie Welch. Robust task allocation for dynamic distributed realtime systems subject to multiple environmental parameters. In Distributed Computing Systems, 2005. ICDCS 2005. Proceedings. 25th IEEE International Conference on, pages 675 684. IEEE, 2005. [Jones et al., 2006] Edward Gil Jones, Brett Browning, M Bernardine Dias, Brenna Argall, Manuela Veloso, and Anthony Stentz. Dynamically formed heterogeneous robot teams performing tightly-coordinated tasks. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pages 570 575. IEEE, 2006.

[Kleywegt et al., 2002] Anton J Kleywegt, Alexander Shapiro, and Tito Homem-de Mello. The sample average approximation method for stochastic discrete optimization. SIAM Journal on Optimization, 12(2):479 502, 2002. [Korzhyk et al., 2010] Dmytro Korzhyk, Vincent Conitzer, and Ronald Parr. Complexity of computing optimal stackelberg strategies in security resource allocation games. In Proceedings of AAAI, pages 805 810, 2010. [Liu and Chen, 2017] Yang Liu and Yiling Chen. Sequential peer prediction: Learning to elicit effort using posted prices. In Proceedings of AAAI, pages 607 613, 2017. [Liu et al., 2017] Chang Liu, Bo Li, Yevgeniy Vorobeychik, and Alina Oprea. Robust linear regression against training data poisoning. In ACM Workshop on Artiﬁcial Intelligence and Security, 2017. [Manino et al., 2016] Edoardo Manino, Long Tran-Thanh, and Nicholas R Jennings. Efﬁciency of active learning for the allocation of workers on crowdsourced classiﬁcation tasks. ar Xiv preprint ar Xiv:1610.06106, 2016. [Mason and Suri, 2012] Winter Mason and Siddharth Suri. Conducting behavioral research on amazon s mechanical turk. Behavior research methods, 44(1):1 23, 2012. [Sheng et al., 2008] Victor S Sheng, Foster Provost, and Panagiotis G Ipeirotis. Get another label? improving data quality and data mining using multiple, noisy labelers. In Proceedings of ACM SIGKDD, pages 614 622, 2008. [Singla and Krause, 2013] Adish Singla and Andreas Krause. Truthful incentives in crowdsourcing tasks using regret minimization mechanisms. In Proceedings of the international conference on World Wide Web, pages 1167 1178. ACM, 2013. [Stackelberg, 1952] Heinrich von Stackelberg. Theory of the market economy. 1952. [Steinhardt et al., 2016] Jacob Steinhardt, Gregory Valiant, and Moses Charikar. Avoiding imposters and delinquents: Adversarial crowdsourcing and peer prediction. In NIPS, pages 4439 4447, 2016. [Stone and Veloso, 1999] Peter Stone and Manuela Veloso. Task decomposition, dynamic role assignment, and lowbandwidth communication for real-time strategic teamwork. Artiﬁcial Intelligence, 110(2):241 273, 1999. [Tambe, 2011] Milind Tambe. Security and game theory: algorithms, deployed systems, lessons learned. Cambridge University Press, 2011. [Tran-Thanh et al., 2014] Long Tran-Thanh, Trung Dong Huynh, Avi Rosenfeld, Sarvapali D Ramchurn, and Nicholas R Jennings. Budgetﬁx: budget limited crowdsourcing for interdependent task allocation with quality guarantees. In Proceedings of AAMAS, pages 477 484, 2014. [Xu et al., 2010] Huan Xu, Constantine Caramanis, and Sujay Sanghavi. Robust PCA via outlier pursuit. In NIPS, pages 2496 2504, 2010.

Proceedings of the Twenty-Seventh International Joint Conference on Artiﬁcial Intelligence (IJCAI-18)