Payoff Mechanism Design for Coordination
in Multi-Agent Task Allocation Games

To investigate the task allocation problem, we formalize the problem as a large population game in which the agents select strategies to perform jobs in the assigned tasks quantified by $q=(q_{1},\cdots,q_{m})$. The vector $q$ varies over time based on the agents’ strategy selection and changes in the environment. Hence, each agent needs to evaluate and adaptively select a strategy based on $q$.

Given $x(t)$ and $q(t)$, at each time $t$, the following ordinary differential equation describes the rate of change of $q(t)$.

$\displaystyle\dot{q}(t)$

$\displaystyle=-\underbrace{\mathcal{F}(q(t),x(t))}_{\text{reduction rate}}+\underbrace{w}_{\text{growth rate}},~{}q(0)=q_{0}\in\mathbb{R}^{m}_{+},$

(2)

where $\mathcal{F}:\mathbb{R}_{+}^{m}\times\mathbb{R}_{+}^{n}\to\mathbb{R}_{+}^{m}$ is a continuously differentiable mapping³³3To have the reduction rate mapping defined for any population mass $M$, we define the domain of $\mathcal{F}$ as $\mathbb{R}_{+}^{m}\times\mathbb{R}_{+}^{n}$. that defines the reduction rate, which quantifies how fast the agents adopting strategy profile $x$ reduce $q$, and the constant vector $w=(w_{1},\cdots,w_{m})\in\mathbb{R}^{m}_{+}$ represents the growth rate for $q$ due to environmental changes. To ensure that the positive orthant $\mathbb{R}_{+}^{m}$ is forward-invariant for $q(t)$ under (2), each $\mathcal{F}_{i}$ of $\mathcal{F}=(\mathcal{F}_{1},\cdots,\mathcal{F}_{m})$ satisfies $\mathcal{F}_{i}(q,x)\leq w_{i}\text{ if }q_{i}=0$. For notational convenience, let us define $\mathbb{O}$ as the set of stationary points of (2), i.e.,

$\displaystyle\mathbb{O}=\{(q,x)\in\mathbb{R}_{+}^{m}\times\mathbb{X}_{M}\,|\,\mathcal{F}(q,x)=w\}.$

(3)

We make the following assumption on the mapping $\mathcal{F}$.

According to Assumption 1, we represent the reduction rate as $\mathcal{F}(q,x)=(\mathcal{F}_{1}(q_{1},x),\cdots,\mathcal{F}_{m}(q_{m},x))$, where for fixed $x$, each $\mathcal{F}_{i}$ is an increasing function of $q_{i}$.

The following examples illustrate how the dynamic game model (2) can be adopted in control systems applications.

Our model is based on the evolutionary dynamics framework [13] in which the strategy revision protocol $\varrho_{i}^{\theta}:\mathbb{R}^{n}\to\mathbb{R}_{+}$ determines an agent’s strategy revision based on the payoff vector $p\in\mathbb{R}^{n}$, where $\theta=(\theta_{1},\cdots,\theta_{n})\in\mathbb{X}_{M}$ is a parameter of the protocol. We adopt the Kullback-Leibler Divergence Regularized Learning (KLD-RL) protocol [21, 22] to define $\varrho_{i}^{\theta}(p)$ as

$\displaystyle\varrho_{i}^{\theta}(p)=\frac{\theta_{i}\exp(\eta^{-1}p_{i})}{\sum_{l=1}^{n}\theta_{l}\exp(\eta^{-1}p_{l})},$

(6)

where $\eta>0$. The protocol $\varrho_{i}^{\theta}(p)$ describes the probability of an agent switching to strategy $i$ given $p$ and $\theta$. Note that the smaller the value of $\eta$, the more the strategy revision depends on the value of $p$.

Each agent is given an opportunity to revise its strategy selection at each jump time of an independent and identically distributed Poisson process, and uses the protocol to select a new strategy or keep its current strategy selection. Since the strategy revision of individual agents only depends on the payoff vector and takes place independently of each other, their decision-making is decentralized and the coordination among them occurs implicitly through their decision-making model. Based on discussions in [13, Chapter 4], as the number of agents in the population tends to infinity, the following ordinary differential equation describes how each component of $x(t)=(x_{1}(t),\cdots,x_{n}(t))$ evolves over time.

	$\displaystyle\dot{x}_{i}(t)$	$\displaystyle=\mathcal{V}_{i}^{\theta}(p(t),x(t))$
		$\displaystyle=\textstyle\sum_{j=1}^{n}x_{j}(t)\varrho_{i}^{\theta}(p(t))-x_{i}(t)\textstyle\sum_{j=1}^{n}\varrho_{j}^{\theta}(p(t)).$		(7)

We refer to (7) as the Evolutionary Dynamics Model (EDM).

Note that at an equilibrium state $(p^{\ast},x^{\ast})$ of the EDM (7) under the KLD-RL protocol (6), if $\theta=x^{\ast}$, the following implication holds:

$\displaystyle x_{i}^{\ast}>0\implies p_{i}^{\ast}=\max_{1\leq j\leq n}p_{j}^{\ast}.$

(8)

Eq. (8) means that every agent receives the highest payoff at $(p^{\ast},x^{\ast})$ if the parameter $\theta$ of (6) is the same as $x^{\ast}$.

Given the protocol $\varrho_{i}^{\theta}$ as in (6), we aim to design a payoff mechanism for the agents to asymptotically adopt the optimal strategy profile that minimizes a given cost $c(q)$. For instance, in Example 1, if we design the payoff mechanism as $p=q$, the robots would select strategy $i$ to take on task $i$ and asymptotically minimize $\lim_{t\to\infty}\max_{1\leq i\leq m}q_{i}(t)$, as discussed in [1]. However, in many applications, such one-to-one correspondence between tasks and available strategies may not exist, and depending on the cost we want to minimize, such a simple payoff mechanism would not be the best design choice as we illustrate in Figure 1.

In addition, since the payoff mechanism depends on the vector $q(t)$, the mechanism would incentivize the agents to take on the tasks with larger $q_{i}(t)$. Hence, compared to other models that directly control the population state $x(t)$ to the optimal state $x^{\ast}$ (for instance, the model proposed in [9]), our strategy revision model is more responsive to changes of $q(t)$ and hence reduces the task-associated variables $q(t)$ at a faster rate as we depict in Figure 1.

Two examples of the cost function we consider are

• •

  (square of) the 2-norm of $q$: $c(q)=\sum_{i=1}^{m}q_{i}^{2}$, and

• •

  the $\infty$-norm of $q$: $c(q)=\max_{1\leq i\leq m}q_{i}$.

For the payoff mechanism design, we consider a linear model defined by a matrix $G\in\mathbb{R}^{n\times m}$ as follows:

$\displaystyle p=Gq.$

(9)

Our main problem investigates finding the matrix $G$ that allows the agents to asymptotically minimize the cost $c(q(t))$. We formally state the problem as follows.

We explain the steps to compute $G$. First, note that (15a) is satisfied if $G$ has the following structures:

1. 1.

   For Example 1, $G_{ij}=0$ if $i\neq j$.

2. 2.

   For Example 2, $G_{ij}=0$ if $i\notin\mathbb{N}_{j}$ and $G_{ij}=G_{j}$ otherwise, where $G_{j}$ is a real number.

Then, we find $(q^{\ast},x^{\ast})\in\mathbb{O}$ that minimizes the cost function $c(q)$ using the following optimization.

$\displaystyle\min_{(q,x)\in\mathbb{R}_{+}^{m}\times\mathbb{X}_{M}}c(q)\text{ subject to }\mathcal{F}(q,x)=w.$

(16)

Note that since $\mathcal{F}$ is a nonlinear mapping, the optimization can be non-convex and the solution we find is locally optimal.

Once we find $(q^{\ast},x^{\ast})$, we compute the matrix $G$ satisfying (15) for which we first need to find the mapping $g$. Instead of explicitly finding $g$, we draw random samples $\{(q_{s},x_{s})\}_{s=1}^{S}\subset\mathbb{R}_{+}^{m}\times\mathbb{X}_{M}$ and find $y_{s}\in\mathbb{R}_{+}^{n}$ that minimizes $\|\mathcal{F}(q_{s},y_{s})-w\|_{2}^{2}$ for each sample $(q_{s},x_{s})$. Note that assuming $\nabla_{x}\mathcal{F}(q,x)$ has full rank at $(q_{s},y_{s})$, which is the case in both examples, the minimizer $y_{s}$ satisfies $\mathcal{F}(q_{s},y_{s})=w$.

As the last step, the design of $G$ can be formulated as the following linear programming:

		$\displaystyle\min_{G\in\mathbb{R}^{n\times m}}1$		(17)
		$\displaystyle\begin{aligned} \text{subject to }&(\mathcal{F}_{i}(q_{s,i},x_{s})-w_{i})\,(x_{s}-y_{s})^{T}G_{i}^{\tiny\text{col}}>0,\\ &\qquad\qquad~{}\forall i\in\{1,\cdots,m\},~{}\forall s\in\{1,\cdots,S\}\\ &(G_{i}^{\tiny\text{row}}-G_{j}^{\tiny\text{row}})x_{i}^{\ast}q^{\ast}\geq 0,~{}\forall i,j\in\{1,\cdots,n\},\end{aligned}$

where $q_{s,i}$ is the $i$-th element of $q_{s}=(q_{s,1},\cdots,q_{s,m})$. Since we evaluate the condition (15b) using a finite number of sampled points $\{(q_{s},x_{s})\}_{s=1}^{S}$, we would obtain an approximate solution satisfying (15) only at the sampled points. However, as the sample size $S$ tends to infinity, the solution $G$ is more likely to satisfy (15) over the entire state space $\mathbb{R}_{+}^{m}\times\mathbb{X}_{M}$.

Using the methods explained in Section IV-A, we compute the optimal state $(q^{\ast},x^{\ast})$ minimizing i) $c(q)=\sum_{i=1}^{m}q_{i}^{2}$ and ii) $c(q)=\max_{1\leq i\leq m}q_{i}$, where we use the fixed growth rate $w=(0.05,0.25,1.00,2.00)$ for both cases. Then, we design the payoff matrix $G$ using (17) as follows.

1. i.

   For $c(q)=\sum_{i=1}^{m}q_{i}^{2}$,

   $\displaystyle\footnotesize G=\begin{pmatrix}1.00&0.00&0.00&0.00\\ 0.00&0.66&0.00&0.00\\ 0.00&0.00&0.48&0.00\\ 0.00&0.00&0.00&0.40\end{pmatrix}.$

2. ii.

   For $c(q)=\max_{1\leq i\leq m}q_{i}$,

   $\displaystyle\footnotesize G=\begin{pmatrix}1.00&0.00&0.00&0.00\\ 0.00&1.00&0.00&0.00\\ 0.00&0.00&1.00&0.00\\ 0.00&0.00&0.00&1.00\end{pmatrix}.$

Note that when we use the $\infty$-norm to define the cost $c(q)$, the optimal design of $G$ equally incentivizes the agents proportional to the remaining jobs $q$. On the other hand, when the $2$-norm is used, given that the values of $q_{1}(t),\cdots,q_{4}(t)$ are equal, the payoff matrix $G$ assigns the highest payoff to strategy $1$ and the lowest payoff to strategy $4$. Recall that under the pre-selected growth rate $w$, task $1$ has the lowest growth rate and task $4$ has the highest, and hence maintaining lower $q_{1}(t)$ is easier – it needs a less number of agents – than $q_{4}(t)$. Hence, under the $2$-norm cost function, the agents prioritize to carry out the tasks with lower growth rates.

Figures 4 and 4 depict the resulting trajectories for $x(t)$ and $q(t)$. Notice that the population states at the equilibrium in the two cases are similar; however, the trajectories for $q(t)$ are different and, hence, so do the costs evaluated along the trajectories as we discussed in Figure 1. We observe that there is a large variation in the agent strategy revision at the beginning of the simulations as the agents repeatedly switch among the strategies to reduce $q_{i}(t)$ with a larger value.

We consider that there are 4 target states and 4 types of sensors each of which can measure a single state of the target. Each mobile unit can be equipped with two types of sensors and we define a strategy based on a pair of sensors employed on a mobile unit. According to the strategy definition, we can define the set $\mathbb{N}_{i}$ in (5) as the strategies that can measure the $i$-th target state: $\mathbb{N}_{1}=\{1,2,3\}$, $\mathbb{N}_{2}=\{1,4,5\}$, $\mathbb{N}_{3}=\{2,4,6\}$, and $\mathbb{N}_{4}=\{3,5,6\}$. We use the square of the $2$-norm to define the cost function, i.e., $c(q)=\sum_{i=1}^{m}q_{i}^{2}$.

We design $G$ with two distinct growth rates as follows.

1. i.

   For $w=(0.5,1.0,1.5,2.0)$,

   $\displaystyle\footnotesize G=\begin{pmatrix}1.00&0.81&0.00&0.00\\ 1.00&0.00&0.72&0.00\\ 1.00&0.00&0.00&0.67\\ 0.00&0.81&0.72&0.00\\ 0.00&0.81&0.00&0.67\\ 0.00&0.00&0.72&0.67\end{pmatrix}.$

2. ii.

   For $w=(0.1,0.5,1.0,2.0)$,

   $\displaystyle\footnotesize G=\begin{pmatrix}1.68&0.99&0.00&0.00\\ 1.68&0.00&0.80&0.00\\ 1.68&0.00&0.00&0.67\\ 0.00&0.99&0.80&0.00\\ 0.00&0.99&0.00&0.67\\ 0.00&0.00&0.80&0.67\end{pmatrix}.$

By comparing the above two payoff matrices, we can infer that the optimal $G$ assigns higher payoffs to the strategies as their respective growth rates become smaller. Figures 6 and 6 depict the resulting trajectories for $x(t)$ and $q(t)$. Notably, as the growth rate of the $4$-th target state becomes relatively higher than those of other target states, more agents adopt strategies $3,5$, and $6$, which can be used to measure the $4$-th state. Similar to the simulation results in Section IV-B, we can observe a large variation in the agent strategy revision at the beginning of the simulations as the agents responsively revise their strategies based on the value of $q_{i}(t)$.

From (12b) and (13b), we can derive

	$\displaystyle\frac{\mathrm{d}}{\mathrm{d}t}\left(\mathcal{S}^{\theta}(p(t),x(t))+\mathcal{L}(q(t),x(t))\right)$
	$\displaystyle=\nabla_{x}^{T}\mathcal{S}^{\theta}(p(t),x(t))\mathcal{V}^{\theta}(p(t),x(t))$
	$\displaystyle\qquad+\nabla_{q}^{T}\mathcal{L}(q(t),x(t))(-\mathcal{F}(q(t),x(t))+w)\leq 0,$		(18)

where by (12a) and (13a), the equality holds if and only if $\mathcal{S}^{\theta}(p(t),x(t))=\mathcal{L}(q(t),x(t))=0$. Therefore, by LaSalle’s invariance principle [23], if $q(t)$ is bounded, then the trajectory $(q(t),x(t)),\,t\geq 0$ converges to the equilibrium states of (10).

By the definition of the KLD-RL protocol [21, 22], with $\theta=x^{\ast}$, $(q^{\ast},x^{\ast})$ is an equilibrium state of (10) for any $\eta>0$ if it holds that $x^{\ast}\in\operatorname*{arg\,max}_{z\in\mathbb{X}_{M}}(z^{T}Gq^{\ast})$, which can be validated by (14). ∎

We define a $\delta$-antistorage function $\mathcal{L}:\mathbb{R}_{+}^{m}\times\mathbb{X}_{M}\to\mathbb{R}_{+}$ using a line integral along a curve $s$ from $g(q)$ to $x$:

$\displaystyle\mathcal{L}(q,x)=\int_{g(q)}^{x}G(\mathcal{F}(q,s)-w)\bullet\mathrm{d}s.$

(19)

Recall that $g(q)\in\mathbb{R}_{+}^{n}$ is such that $\mathcal{F}(q,g(q))=w$. By evaluating the line integral along the curve given by $s(\tau)=\tau x+(1-\tau)g(q),~{}\tau\in[0,1]$, we can derive

$\displaystyle\mathcal{L}(q,x)=(x-g(q))^{T}G\int_{0}^{1}\left(\mathcal{F}(q,s(\tau))-w\right)\mathrm{d}\tau.$

(20)

Note that for every $\tau$ in $(0,1)$, it holds that

		$\displaystyle(x-g(q))^{T}G\left(\mathcal{F}(q,s(\tau))-w\right)$
		$\displaystyle=\frac{1}{\tau}\sum_{i=1}^{m}(s(\tau)-g(q))^{T}G_{i}^{\tiny\text{col}}\left(\mathcal{F}_{i}(q_{i},s(\tau))-w_{i}\right).$		(21)

Hence, under (15b), we can verify that $\mathcal{L}(q,x)\geq 0$ where the equality holds if and only if $\mathcal{F}(q,x)=w$. In what follows, we show that $\mathcal{L}$ satisfies (13a) and (13b). To begin with, using (15a), we can establish

	$\displaystyle\nabla_{x}\mathcal{L}(q,x)$	$\displaystyle=G\int_{0}^{1}\left(\mathcal{F}(q,s(\tau))-w\right)\mathrm{d}\tau$
		$\displaystyle\quad+\int_{0}^{1}\nabla_{z}^{T}\mathcal{F}(q,z)\Big{|}_{z=s(\tau)}\tau\,\mathrm{d}\tau\,G^{T}(x-g(q))$
		$\displaystyle=G\int_{0}^{1}\frac{\mathrm{d}}{\mathrm{d}\tau}\tau\mathcal{F}(q,s(\tau))\,\mathrm{d}\tau-Gw$
		$\displaystyle=G\left(\mathcal{F}(q,x)-w\right).$		(22)

Hence, we can derive

$\displaystyle\nabla_{x}^{T}\mathcal{L}(q,x)\dot{x}=(\mathcal{F}(q,x)-w)^{T}G^{T}\dot{x}=-\dot{p}^{T}\dot{x}.$

(23)

Similarly, the partial derivative of $\mathcal{L}(q,x)$ with respect to $q$ can be computed as

	$\displaystyle\nabla_{q}\mathcal{L}(q,x)$
	$\displaystyle=-\nabla_{q}^{T}g(q)\int_{0}^{1}G\left(\mathcal{F}(q,s(\tau))-w\right)\mathrm{d}\tau$
	$\displaystyle\quad+\int_{0}^{1}\bigg{(}\nabla_{q}^{T}G\mathcal{F}(q,s(\tau))$
	$\displaystyle\qquad+\nabla_{q}^{T}g(q)\nabla_{z}^{T}G\mathcal{F}(q,z)\Big{|}_{z=s(\tau)}(1-\tau)\bigg{)}\mathrm{d}\tau\,(x-g(q))$
	$\displaystyle=\int_{0}^{1}\nabla_{q}^{T}\mathcal{F}(q,s(\tau))\,\mathrm{d}\tau\,G^{T}(x-g(q))$
	$\displaystyle\quad+\nabla_{q}^{T}g(q)\underbrace{\int_{0}^{1}G\bigg{(}\frac{\mathrm{d}}{\mathrm{d}\tau}\mathcal{F}(q,s(\tau))(1-\tau)+w\bigg{)}\mathrm{d}\tau}_{=0}.$		(24)

Therefore, we can derive

	$\displaystyle\nabla_{q}^{T}\mathcal{L}(q,x)\dot{q}$
	$\displaystyle=(x-g(q))^{T}\int_{0}^{1}\nabla_{q}G\mathcal{F}(q,s(\tau))\,\mathrm{d}\tau\,(-\mathcal{F}(q,x)+w).$

Then, the time derivative of $\mathcal{L}$ becomes

$$\frac{\mathrm{d}}{\mathrm{d}t}\mathcal{L}(q,x)=(x-g(q))^{T}\\ \times\int_{0}^{1}\nabla_{q}G\mathcal{F}(q,s(\tau))\,\mathrm{d}\tau\,(-\mathcal{F}(q,x)+w)-\dot{p}^{T}\dot{x}$$

(25)

Hence, for $\mathcal{L}$ to satisfy (13b), it suffices to show that the following inequality holds.

$\displaystyle(x\!-\!g(q))^{T}\!\int_{0}^{1}\nabla_{q}G\mathcal{F}(q,s(\tau))\mathrm{d}\tau(-\mathcal{F}(q,x)\!+\!w)\!\leq\!0.$

(26)