Distributed Task Allocation for Self-Interested Agents with Partially Unknown Rewards

A prototypical multi-agent coordination problem aims to find an efficient assignment of group of agents to complete a collection of tasks. These tasks can range from abstract sets of objectives to specific physical jobs, the nature of which may not be completely known. In addition, the agents composing the group may have heterogeneous capabilities, and react to different sets of incentives that are being learned progressively. This necessitates of novel task-assignment algorithms that can adapt and react online as new information arises. Motivated by this, we study a discrete task allocation problem modeled as a game of self-interested agents that have partial knowledge of their rewards. This requires addressing the problem’s combinatorial nature, and designing provable-correct distributed dynamics that adapt to dynamic rewards revealed online. To the best of our knowledge, algorithms that combine all these features are not available in literature.

Here, we formalize the notations and briefly list some well-known concepts that are used to solve the problem formulated in the following section.

A group of agents $\mathcal{A}:=\{1,\cdots,n\}$ is to complete a set of tasks $\mathcal{Q}:=\{1,\cdots,m\}$, where $n\neq m$ possibly, in a distributed manner. For this purpose, each agent $i\in\mathcal{A}$ encodes via $\phi_{i}:\mathcal{Q}\to\mathbb{R}_{\geq 0}$ the importance of each task (the higher $\phi_{i}(q)$ the larger the agent’s capability/fondness on $q\in\mathcal{Q}$) and $r_{i}:\mathcal{Q}\to\mathbb{R}_{\geq 0}$ the reward for completing each task. For the sake of brevity, define $f_{i}(q):=r_{i}(q)\phi_{i}(q)\geq 0$, $\forall q\in\mathcal{Q}$, $\forall i\in\mathcal{A}$. An optimal task assignment is the solution to

Here, $\mathcal{V}_{i}\subseteq\mathcal{Q}$ is the set of tasks assigned to agent $i\in\mathcal{A}$ and $\mathcal{P}=(\mathcal{V}_{1},\cdots,\mathcal{V}_{n})$ is the ordered collection of sets that defines a partition of $\mathcal{Q}$ (as in 1b).

The group of agents is to compute an optimal partition of the task set $\mathcal{Q}$ on their own. Naturally, each agent $i\in\mathcal{A}$ aims to get the tasks $q\in\mathcal{Q}$ for which $f_{i}(q)$ is the largest. This motivates the following definition.

The collection of possible strategies for each agent is a combinatorial class, which grows exponentially as the number of tasks $m$ increases. To address this problem, we first assume that each $i\in\mathcal{A}$ measures the utility of a subset of tasks $\mathcal{V}_{i}\subseteq\mathcal{Q}$ via

This leads to the partition game

where the strategy of each agent is to choose a subset $\mathcal{V}_{i}$ of $\mathcal{Q}$ to maximize $H_{i}$. In this way, agent strategies are no-longer required to form a valid partition, but the utility in 2 penalizes each agent for taking tasks that others have chosen.

Second, we further relax this game by reducing the decision of each agent $i\in\mathcal{A}$ regarding task $q\in\mathcal{Q}$ to the computation of a weight $w^{q}_{i}\in[0,1]$. Briefly, this defines $\mathbf{W}\in[0,1]^{n\times m}$ as the matrix whose $(i,q)^{\text{th}}$ entry is $w^{q}_{i}$. Thus, $\mathbf{w}_{i}^{\top}\in[0,1]^{m}$ (resp. $\mathbf{w}^{q}\in[0,1]^{n}$) represents the weights that agent $i\in\mathcal{A}$ (resp. for task $q\in\mathcal{Q}$) gives to each task (resp. given by each agent). Agent $i\in\mathcal{A}$ is equipped with the utility function:

which collectively define the weight game

In this way, a product of weights in the second part of the sum in 3 relaxes the check on overlapping task in 2. In this paper, we ignore the trivial case where all agents get the same payoff for a task, as stated in the following.

The above framework allows us to deal with a case where the $f_{i}(q)$ are unknown to the agent, but where these values can be learned progressively by an external mechanism until convergence. More precisely, we assume the following.

In what follows, we first study the games when the reward parameters are known. Then we adapt the results for the case when only a converging reward sequence is available.

Now we formally state the goals of this work.

We start by addressing the first two problems above. Thus, we first characterize the NE of the partition game $\mathscr{G}_{P}$.

Proof. First, we show the necessity of Properties 1 and 2. Suppose that $(\widehat{\mathcal{V}}_{i},\widehat{\mathcal{V}}_{-i})\in\mathcal{NE}(\mathscr{G}_{P})$. We prove Property 1 by contradiction and assume $\exists\,q\in\mathcal{Q}$ such that $\forall i\in\mathcal{A}$ dominating for task $q$, $q\notin\widehat{\mathcal{V}}_{i}$. Pick one such agent $i$ and take $\mathcal{V}_{i}=\widehat{\mathcal{V}}_{i}\cup\{q\}$. Then,

The inequality is strict since $i$ is dominating and the max is over all agents that are not dominating for $q$ (by assumption). This is a contradiction with $(\widehat{\mathcal{V}}_{i},\widehat{\mathcal{V}}_{-i})\in\mathcal{NE}(\mathscr{G}_{P})$.

The necessity of Property 2 also follows from contradiction. Suppose $\exists\,q\in\mathcal{Q}$ and a $j\in\mathcal{A}$ not dominating for $q$ with $q\in\widehat{\mathcal{V}}_{j}$. From Property 1, there is an $i\in\mathcal{A}$ dominating for $q$ with $q\in\widehat{\mathcal{V}}_{i}$. Thus, with strategy $(\widehat{\mathcal{V}}_{j},\widehat{\mathcal{V}}_{-j})$,

Now, consider the strategy $\mathcal{V}_{j}=\widehat{\mathcal{V}}_{j}\setminus\{q\}$. It follows that $H_{j}(\mathcal{V}_{j},\widehat{\mathcal{V}}_{-j})-H_{j}(\widehat{\mathcal{V}}_{j},\widehat{\mathcal{V}}_{-j})>0$, which contradicts $(\widehat{\mathcal{V}}_{j},\widehat{\mathcal{V}}_{-j})\in\mathcal{NE}(\mathscr{G}_{P})$.

Now, we show the sufficiency of Properties 1 and 2. Let $(\widehat{\mathcal{V}}_{i},\widehat{\mathcal{V}}_{-i})$ satisfy Properties 1 and 2 and let $i\in\mathcal{A}$ be an arbitrary but fixed agent. Suppose that $\mathcal{V}_{i}\neq\widehat{\mathcal{V}}_{i}$ is any other strategy. Then, the proof follows from three cases:

Case (i): $\exists\,q\in\mathcal{V}_{i}$ such that $q\notin\widehat{\mathcal{V}}_{i}$ and $i$ is dominating for $q$. Then, since $\exists\,j\in\mathcal{A}$ dominating for $q$ with $q\in\widehat{\mathcal{V}}_{j}$,

Case (ii): $\exists\,q\in\mathcal{V}_{i}$ such that $q\notin\widehat{\mathcal{V}}_{i}$ and $i$ does not dominate $q$. Then, as $\exists\,j\in\mathcal{A}$ dominating for $q$ and $q\in\widehat{\mathcal{V}}_{j}$, we have

Case (iii): $\exists\,q\in\widehat{\mathcal{V}}_{i}$ such that $q\notin\mathcal{V}_{i}$. This can only happen if $i$ is dominating for $q$ (else, by Property 2, $q\notin\widehat{\mathcal{V}}_{j}$). Then,

From the above, it is easy to see that any deviation from $(\widehat{\mathcal{V}}_{i},\widehat{\mathcal{V}}_{-i})$ will not result in an increase in utility for $i$ since $H_{i}(\mathcal{V}_{i},\widehat{\mathcal{V}}_{-i})-H_{i}(\widehat{\mathcal{V}}_{i},\widehat{\mathcal{V}}_{-i})=f_{i}(q)-\max\limits_{k\neq i,\,q\in\widehat{\mathcal{V}}_{k}}f_{k}(q)$. $\blacksquare$

From the previous result, at least one of the dominating agents will be assigned to a task by means of a NE strategy of $\mathscr{G}_{P}$. However, this does not preclude that two dominating agents are assigned the same task. Next, we show that the NE of the relaxed game $\mathscr{G}_{W}$ are equivalent to the NE of $\mathscr{G}_{P}$.

Proof. First, we show the necessity of all properties. Suppose $(\widehat{\mathbf{w}}_{i},\widehat{\mathbf{w}}_{-i})\in\mathcal{NE}(\mathscr{G}_{W})$. We show Property 1 is necessary by contradiction. Consider an arbitrary $q\in\mathcal{Q}$ and suppose that for all dominating agents $i^{*}_{q}\in\mathcal{A}$ for task $q$, it holds that $\widehat{w}^{q}_{i^{*}_{q}}<1$. In particular, for any such $i^{*}_{q}$, we have $\max_{j\neq\{i^{*}_{q}\}}f_{j}(q)\widehat{w}^{q}_{j}<f_{i^{*}_{q}}(q)$. Now consider the strategy $\mathbf{w}_{i^{*}_{q}}$, where $w^{q}_{i^{*}_{q}}=1$ and $w^{i^{*}_{q}}_{p}=\widehat{w}^{i^{*}_{q}}_{p}$, $\forall p\neq q\in\mathcal{Q}$. Then,

This leads to a contradiction with $(\widehat{\mathbf{w}}_{i},\widehat{\mathbf{w}}_{-i})\in\mathcal{NE}(\mathscr{G}_{W})$.

We similarly show Property 2 is necessary by contradiction. Let $q\in\mathcal{Q}$ be an arbitrary task, and suppose that $\exists\,j\in\mathcal{A}$ which is not dominating for $q$ but for which $\widehat{w}^{q}_{j}>0$. Due to Property 1, let $i^{*}_{q}$ be the dominating agent for $q$ such that $\widehat{w}^{q}_{i^{*}_{q}}=1$. Now define a new strategy $\mathbf{w}_{j}$, with $w^{q}_{j}=0$ and $w^{j}_{p}=\widehat{w}^{j}_{p}$, $\forall p\neq q\in\mathcal{Q}$. Then,

where the inequality is because both terms are negative. This contradicts $(\widehat{\mathbf{w}}_{i},\widehat{\mathbf{w}}_{-i})\in\mathcal{NE}(\mathscr{G}_{W})$.

Next, we show sufficiency. Let $(\widehat{\mathbf{w}}_{i},\widehat{\mathbf{w}}_{-i})\in[0,1]^{n\times m}$ be a candidate strategy satisfying Properties 1- 2 and let $i\in\mathcal{A}$. Take any other $\mathbf{w}_{i}\neq\widehat{\mathbf{w}}_{i}$ and a task $q\in\mathcal{Q}$. The proof follows from the following cases.

Case (i): $i$ is a dominating agent for task $q$ and $\widehat{w}^{q}_{i}=1$. Then, from Definition 3.1,

Case (ii): $i$ is a dominating agent for task $q$ and ${\widehat{w}^{q}_{i}<1}$. Then, since $\exists\,j\in\mathcal{A}$ dominating for $q$ and $\widehat{w}^{q}_{j}=1$,

since $f_{i}(q)-f_{j}(q)=0$.

Case (iii): $i$ is not a dominating agent for task $q$ (and hence $\widehat{w}^{q}_{i}=0$). Again, $\exists\,j\in\mathcal{A}$ dominating for $q$ and $\widehat{w}^{q}_{j}=1$. Then,

since $f_{i}(q)<f_{j}(q)$. Now, using these three cases, it is easy to see that any deviation from $(\widehat{\mathbf{w}}_{i},\widehat{\mathbf{w}}_{-i})$ will not result in an increase the utility of $i$. $\blacksquare$

As a direct implication of Lemma 4.2, for any $\mathbf{W}\in[0,1]^{n\times m}$ we can define $C:[0,1]^{n\times m}\to(2^{\mathcal{Q}})^{n}$ as

where $\mathrm{tsupp}\,(\mathbf{w}_{i}):=\{q\in\mathcal{Q}\,|\,w^{q}_{i}=1\},\,\,\forall i\in\mathcal{A}$. Then,

Next, we relate the optimal partition and the NE of the two games through the following theorem.

Proof. By 5, we can equivalently show that $\mathcal{O}\subseteq\mathcal{NE}(\mathscr{G}_{P})$. Let $\mathcal{P}^{*}\in\mathcal{O}$. It is easy to see that $q\in\mathcal{V}^{*}_{i}$ only if $i\in\mathcal{A}$ is a dominating agent for task $q$. Moreover, if $j\in\mathcal{A}$ is not dominating for $q$, then $q\notin\mathcal{V}^{*}_{j}$. Then from Lemma 4.1, $\mathcal{P}^{*}\in\mathcal{NE}(\mathscr{G}_{P})$. The rest follows from 5. $\blacksquare$

The above result states that if an agent $i\in\mathcal{A}$ is assigned tasks using the translated support of the NE of $\mathscr{G}_{W}$, this set is a superset of the optimizers of 1. The extra solutions arise when there are non-unique dominating agents for a task. When there are unique dominating agents, the next result shows there is a unique NE for $\mathscr{G}_{W}$. This follows from Lemma 4.2 immediately, so we skip a formal proof.

In general, $\mathcal{NE}(\mathscr{G}_{W})$ is a superset of the set of optimal partitions. The next example makes this clear.

Next, we design a dynamical system using which the agents can figure out the optimal partition on their own.

From the previous section, we know that if the agents play the weight game $\mathscr{G}_{W}$, then the NE form a superset of the optimal task partition (with slight abuse of notation). Thus, here we let the agents update their weights (from any initial feasible weight) using the gradient of their utility while assuming the others do not change their weights. For such a dynamical system, we aim to relate its equilibria to the NE of $\mathscr{G}_{W}$ and hence also relate it to the set $\mathcal{O}$ of optimal solutions to 1. Now, from 3, it can be seen that,

Thus, the weights are updated using the following dynamics:

with $\gamma^{q}_{i}\in\mathbb{R}_{>0}$, $\forall i\in\mathcal{A},\forall q\in\mathcal{Q}$. We call this the projected best response ascending gradient dynamics (PBRAG). From 7 and 8, note that in order to compute the weight updates, each agent $i\in\mathcal{A}$ needs to know $f_{j}(q)w^{q}_{j}$, for all $j\neq i$. This requires that each agent must talk to every other agent to compute its own gradient. The equilibrium points of this dynamics is given by

For this, the following result can be stated immediately.

Proof. We prove this by showing that $\overline{\mathbf{W}}\in\mathcal{W}$ if and only if $\overline{\mathbf{W}}$ follows Properties 1 and 2 of Lemma 4.2. Suppose that $\overline{\mathbf{W}}\in\mathcal{W}$ and consider an arbitrary but fixed $q\in\mathcal{Q}$. We prove Property 1 by contradiction and assume that $\forall i\in\mathcal{A}$ dominating for $q$, $\overline{w}^{q}_{i}<1$. Now, for any dominating agent $i^{*}_{q}\in\mathcal{A}$, $\max_{j\in\mathcal{A}\setminus\{i^{*}_{q}\}}f_{j}(q)\overline{w}^{q}_{j}<f_{i^{*}_{q}}(q)$. Thus, $u^{q}_{i^{*}_{q}}(\overline{\mathbf{w}}^{q})>0$. Since $\overline{w}^{q}_{i^{*}_{q}}<1$ and $\gamma^{q}_{i^{*}_{q}}>0$, this contradicts $\overline{\mathbf{W}}\in\mathcal{W}$.

Next we prove Property 2 also by contradiction. Suppose that $\exists\,j\in\mathcal{A}$ not dominating for task $q$ but $\overline{w}^{q}_{j}>0$. Due to Property 1, let $i^{*}_{q}\in\mathcal{A}$ be the dominating agent for task $q$ such that $\overline{w}^{q}_{i^{*}_{q}}=1$. Then,

Again, as $\overline{w}^{q}_{j}>0$ and $\gamma^{q}_{j}>0$, this contradicts $\overline{\mathbf{W}}\in\mathcal{W}$.

To show sufficiency, let $\overline{\mathbf{W}}$ satisfy Properties 1 and 2. Then it is easy to see that for each task $q\in\mathcal{Q}$, $u^{q}_{i}(\overline{\mathbf{w}}^{q})\geq 0$ if $i\in\mathcal{A}$ is dominating for $q$ with $\overline{w}^{q}_{i}=1$, $u^{q}_{i}(\overline{\mathbf{w}}^{q})=0$ if $i\in\mathcal{A}$ is dominating for $q$ with $\overline{w}^{q}_{i}<1$, and $u^{q}_{j}(\overline{\mathbf{w}}^{q})<0$ if $j\in\mathcal{A}$ is not dominating for $q$ (hence $\overline{w}^{q}_{j}=0$). Then, $\overline{\mathbf{W}}\in\mathcal{W}$ follows since $\gamma^{q}_{j}>0$. $\blacksquare$

From Lemma 5.1, we can also infer that if there is a unique dominating agent, then the equilibrium set becomes a singleton and follows the same structure as in Corollary 4.4.

In what follows, we show that starting from any initial weights, the dynamics 8 converges to an equilibrium.

Proof. Notice that for the dynamics 8, the weight associated with each task evolves independently from the weights associated with other tasks. Thus, consider an arbitrary but fixed $q\in\mathcal{Q}$. Next, consider any $i\in\mathcal{A}$ that is dominating for $q$. From 7, $u^{q}_{i}(\mathbf{w}^{q})\geq 0$, $\forall\,\mathbf{w}^{q}\in[0,1]^{n}$. Thus, since $\gamma^{q}_{i}>0$, $\forall i\in\mathcal{A}$, $w^{q}_{i}(t)$ is non-decreasing. Hence, $w^{q}_{i}(t)\to\widehat{w}^{q}_{i}\in[0,1]$ as $t\to\infty$, since $[0,1]$ is compact. Now consider $\mathcal{I}^{q}:=\{j\in\mathcal{A}\,|\,j\,\,\mathrm{is\,\,dominating\,\,for}\,\,q\}$, the set $\mathcal{X}:=\{\mathbf{v}\in[0,1]^{|\mathcal{I}^{q}|}\,|\,v_{j}=1\,\,\mathrm{for\,\,some}\,\,j\in\mathcal{I}^{q}\}$ and define the continuous function $V(\mathbf{w}^{q}):=d(\{w^{q}_{i}\}_{i\in\mathcal{I}^{q}},\mathcal{X})$. It is clear that $V(\mathbf{w}^{q}(t+1))\leq V(\mathbf{w}^{q}(t))$ $\forall t\in\mathbb{Z}_{\geq 0}$. Applying the LaSalle invariance principle, there is convergence to the largest invariant set in $V(\mathbf{w}(t))=V(\mathbf{w}(t+1))$ for all $t$. We argue this set is necessarily $\mathcal{X}$. Otherwise, invariance implies that $u^{q}_{i}(\mathbf{w}^{q})=0$ for any dominating agent $i\in\mathcal{A}$. However, this occurs if and only if $\exists\,i^{\prime}\in\mathcal{A}$, $i\neq i^{\prime}$, another dominating agent for task $q$ such that $w^{q}_{i^{\prime}}=1$; otherwise, $u^{q}_{i}(\mathbf{w}^{q})>0$. Thus, $\{w^{q}_{i}(t)\}_{i\in\mathcal{I}^{q}}\to\mathcal{X}$ as $t\to\infty$ . This along with previous discussion proves that $\widehat{w}^{q}_{i}$ follows Property 1 of Lemma 4.2.

Next consider any $j\in\mathcal{A}$ that is not dominating for $q$. From the previous part of the proof, we know that there is a $i\in\mathcal{A}$ dominating for $q$ for which $w^{q}_{i}(t)\to 1$ and thus $f_{i}(q)w^{q}_{i}(t)\to f_{i}(q)$ as $t\to\infty$. This implies that $\exists\,\tau\in\mathbb{Z}_{\geq 0}$ such that $\max_{k\in\mathcal{A}\setminus\{j\}}f_{k}(q)w^{q}_{k}(t)\geq f_{j}(q)+\nu$, for some $\nu>0$ and $\forall t\geq\tau$. Then, as $u^{q}_{j}(\mathbf{w}^{q}(t))\leq-\nu<0$, $w^{q}_{j}(t)$ is a strictly decreasing sequence (after $\tau$ time steps). Thus, from the dynamics in 8, $w^{q}_{j}(t)\to\widehat{w}^{q}_{j}=0$ as $t\to\infty$. Hence, $\widehat{w}^{q}_{j}$ follows Property 2 of Lemma 4.2. $\blacksquare$

When there is a unique dominating agent for each task, we can guarantee finite-time convergence to an optimal partition.

Proof. From Lemma 5.1 and Corollary 4.4, it is clear that $\mathcal{W}$ is a singleton set. Let $\overline{\mathbf{W}}\in\mathcal{W}$ be the unique equilibrium point. From Theorem 5.2, we know that $\mathbf{W}(t)\to\overline{\mathbf{W}}$ as $t\to\infty$. From 7, $u^{q}_{i^{*}_{q}}(\mathbf{w}^{q}(t))\geq\delta>0,\forall t\in\mathbb{Z}_{\geq 0}$ and hence from 8, $\forall t\in\mathbb{Z}_{\geq 0}$, $w^{q}_{i^{*}_{q}}(t+1)\geq[w^{q}_{i^{*}_{q}}(t)+\gamma^{q}_{i^{*}_{q}}\,\delta]_{0}^{1}\geq[w^{q}_{i^{*}_{q}}(0)+(t+1)\,\gamma^{q}_{i^{*}_{q}}\,\delta]_{0}^{1}$. The inequality holds since $[\cdot]_{0}^{1}$ is a nondecreasing function. Thus, $w^{q}_{i^{*}_{q}}(t)=1$, for all $t\geq\left\lceil(\gamma\delta)^{-1}\right\rceil\geq(\gamma\delta)^{-1}\geq[1-w^{q}_{i^{*}_{q}}(0)][\gamma^{q}_{i^{*}_{q}}\delta]^{-1}$. Now define $\tau:=\left\lceil(\gamma\delta)^{-1}\right\rceil$ and consider any $j\neq i^{*}_{q}$ and notice from 7 that $u^{q}_{j}(\mathbf{w}^{q}(t))\leq-\delta<0,\forall t\geq\tau$. Thus, $w^{q}_{j}(t)\leq[w^{q}_{j}(\tau)-t\,\gamma^{q}_{j}\,\delta]_{0}^{1},\forall t\geq\tau.$ The inequality again holds since $[\cdot]_{0}^{1}$ is non decreasing. So, $w^{q}_{j}(t)=0$, for all $t\geq\tau+\left\lceil(\gamma\delta)^{-1}\right\rceil\geq\tau+[\gamma^{q}_{j}\delta]^{-1}\geq\tau+w^{q}_{j}(\tau)[\gamma^{q}_{j}\delta]^{-1}$. $\blacksquare$

In order to avoid all-to-all communication, it is possible to adapt 8 introducing a consensus subroutine. In the next section, we utilize this idea to handle decentralization together with unknown rewards.

Here, we provide a solution to Problem 3.4 (3). Recall that in Section 5, each agent $i\in\mathcal{A}$ computes $\max_{j\neq i}f_{j}(q)w^{q}_{j}$ using information from all other agents. Here, we introduce a communication graph $\mathcal{G}:=(\mathcal{A},\mathcal{E})$ with vertex set $\mathcal{A}$. The arc set $\mathcal{E}$ defines the connections between agents, with $(i,j)\in\mathcal{E}$ if and only if $i\in\mathcal{A}$ can send information to $j\in\mathcal{A}$. For the sake of brevity, let $\mathrm{d}:=\mathrm{diam}(\mathcal{G})$.

For such a setup, the following result gives a way to find the max and second unique max values in a distributed fashion. This is useful in providing a distributed PBRAG (d-PBRAG).