How to define an objective function that conveys the concept of selecting the best elements in a set

97 Views Asked by At

Consider a set of tasks $\mathcal{T} = \{t_1, \ldots, t_I\}$. Consider also a set of workers $\mathcal{W} = \{w^1, \ldots, w^J\}$, where each worker $w^j \in \mathcal{W}$ is associated with a value $a^j \in [0, 1]$ representing how much the annotator $w^j \in \mathcal{W}$ is appropriate for task $t_i \in \mathcal{T}$.

Each worker $w^j \in \mathcal{W}$ can be assigned at most once to any task $t_i \in \mathcal{T}$, while different workers can be assigned to the same task $t_i \in \mathcal{T}$. Namely, let $\mathcal{W}_i \subseteq \mathcal{W}$, $i = 1, \ldots, I$ denote the set of workers assigned to task $t_i$.

Consider the following constrained maximization problem:

$$\begin{align*} \max \min\{ s_i^0 &+ s(\mathcal{W}_i) \} \\ s.t.\\ \sum_i |\mathcal{W}_i| &\leq B \end{align*}$$

where $s: 2^{\mathcal{W}} \to \mathbb{R}$ denotes a score function, which evaluates how much appropriate the worker set $\mathcal{W}_i$ is for task $t_i \in \mathcal{T}$, and $s^0_i$, $i=1,\ldots,I$ denotes an initial score.

Let us now assume that $s(\cdot)$ is defined so that the optimal worker set $\mathcal{W}_i^*$ is comprised by the workers with the highest appropriateness $a^j$.

If we consider an oversimplified version of the afore-mentioned problem where only one task is present, a possible explicit form of $s(\cdot)$ is as follows: $$\begin{align*} s(\mathcal{W}_i) = \sum_{w^j \in \mathcal{W}_i} a^j \end{align*}$$

Nevertheless, in case several tasks are present, i.e., $|\mathcal{T}| > 1$, I do not think that the afore-mentioned explicit form for $s(\cdot)$ successfully conveys the concept of selecting the best possible workers. Specifically, my doubt is that it is possible to maximamize for a given task $t_i \in \mathcal{T}$ the combined quantity $s_i^0 + s(\mathcal{W}_i)$ by selecting many not-so-good workers (and consequently wasting the available budget $B$).

What do you think is a convenient explicit form for $s(\cdot)$ in the general case? Thanks.