A Task-Driven Multi-UAV Coalition Formation Mechanism (aamas24-00148)

Given rational \(\mu\in\mathbb{Q}^{\tau}\), efficiencies \(e_{t,i}\), task parameters \(V_i,Q_i,p_i,\beta_i,\alpha\), and \(\varepsilon\ge0\), find \(x_{t,i}\ge0\) with \(\sum_i x_{t,i}=\mu_t\) such that every feasible infinitesimal transfer from an occupied source task \(i\) to a destination task \(j\) satisfies \(D^+\mathcal{W}(x;\mathbf e_{t,j}-\mathbf e_{t,i})\le\varepsilon\), where \(q_i=\sum_t x_{t,i}\), \(E_i=\sum_t e_{t,i}x_{t,i}\), \(\mathcal{W}(x)=\sum_i v_i(x_i)\), \(v_i(x_i)=R_i(E_i)-\alpha Q_iq_i/E_i\) for \(E_i>0\), \(v_i(0)=0\), and \(R_i\) is the paper's piecewise revenue function.

A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Type \(t\) has task efficiencies \(e_{t,i}>0\). There are \(m\ge2\) tasks, and total mass \(S=\sum_t\mu_t\ge m\) is not normalized to one.
All numerical inputs are binary rationals: \(V_i,Q_i,\alpha>0\), \(0<\beta_i<p_i\), \(V_i\beta_i^2\ge\alpha Q_i(p_i-\beta_i)\), and \(\varepsilon\ge0\). Let \(L\) be their total encoding length.
An assignment has \(x_{t,i}\ge0\), \(\sum_i x_{t,i}=\mu_t\), \(q_i=\sum_t x_{t,i}>0\), and \(E_i=\sum_t e_{t,i}x_{t,i}\le p_i\); thus every task has positive mass.
Define \(R_i(E)=V_iE/\beta_i\) for \(0<E\le\beta_i\), and \(R_i(E)=V_i(p_i-E)/(p_i-\beta_i)\) for \(\beta_i<E\le p_i\). Set \(v_i(x_i)=R_i(E_i)-\alpha Q_iq_i/E_i\) and \(\mathcal W(x)=\sum_i v_i(x_i)\); the empty-task convention is \(v_i(0)=0\).
Let \(b_{t,i}\) denote the unit vector of assignment coordinate \((t,i)\). A transfer direction \(d=b_{t,j}-b_{t,i}\), with \(i\ne j\) and \(x_{t,i}>0\), is feasible if \(x+hd\) satisfies all assignment constraints for every sufficiently small \(h>0\).
Call \(x\) \(\varepsilon\)-stable if every feasible transfer satisfies \(D^+\mathcal W(x;d)=\lim_{h\downarrow0}[\mathcal W(x+hd)-\mathcal W(x)]/h\le\varepsilon\); equality permits indifference, and threshold derivatives are taken in the transfer direction.
The computational problem is to find an exact real algebraic \(\varepsilon\)-stable assignment, or report that none exists.

Is this computational problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard, including when \(\varepsilon=0\)?

For finite agents, strict marginal-utility improvements are proved to terminate at a Nash equilibrium after finitely many iterations; no polynomial bound is established. [Source](https://arxiv.org/html/2403.05108v1#S4.SS5)
No result settling the complexity of this exact mass-transfer problem was located in the literature search.

NP-hardness, including at $\varepsilon=0$

The problem is NP-hard even when $\varepsilon=0$ and the support size is $\tau=3$. This follows from a polynomial-time reduction from PARTITION. Every constructed instance is feasible, and every stable assignment in the construction is rational.

1. Directional marginal formula

Write $c_i=\alpha Q_i$. Define the revenue slopes for removal and addition by

$$ s_i^-(E)= \begin{cases} V_i/\beta_i,&E\le\beta_i,\\ -V_i/(p_i-\beta_i),&E>\beta_i, \end{cases} $$

$$ s_i^+(E)= \begin{cases} V_i/\beta_i,&E<\beta_i,\\ -V_i/(p_i-\beta_i),&E\ge\beta_i. \end{cases} $$

For a positive feasible assignment, put

$$ M_{t,i}^{\pm} = s_i^\pm(E_i)e_{t,i} + c_i\frac{q_i e_{t,i}-E_i}{E_i^2}. $$

Suppose $x_{t,i}>0$ and $i\ne j$. The transfer from $i$ to $j$ is feasible exactly when $E_j<p_j$: sufficiently small transfers preserve source nonnegativity and task positivity, decrease the source efficiency, and increase the destination efficiency by $he_{t,j}>0$.

For addition of type $t$ to task $i$, the cost derivative is

$$ \left.\frac{d}{dh} \left(-c_i\frac{q_i+h}{E_i+he_{t,i}}\right) \right|_{h=0} = c_i\frac{q_i e_{t,i}-E_i}{E_i^2}. $$

Removal gives the negative of this expression. Using the appropriate one-sided revenue slopes therefore gives

$$ D^+\mathcal W(x;b_{t,j}-b_{t,i}) = M_{t,j}^+-M_{t,i}^-. $$

Consequently, $0$-stability is equivalent to

$$ x_{t,i}>0,\quad i\ne j,\quad E_j<p_j \quad\Longrightarrow\quad M_{t,j}^+\le M_{t,i}^-. $$

In particular, removal at $E_i=\beta_i$ uses the positive revenue slope, while addition uses the negative slope.

2. Reduction from PARTITION

We use the standard NP-completeness of PARTITION: given positive integers $a_1,\ldots,a_n$ in binary, decide whether some subset has sum half their total. This is one of the problems established NP-complete in [Karp’s original paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).

Let

$$ A=\sum_{i=1}^n a_i, \qquad n\ge1. $$

Construct three types with masses

$$ \mu_1=A+1,\qquad \mu_2=\frac{A+1}{2},\qquad \mu_3=1. $$

There are $n$ item tasks, indexed by $i=1,\ldots,n$, and three reference tasks, denoted $r_1,r_2,r_3$. Thus

$$ \tau=3,\qquad m=n+3,\qquad S=\frac{3A+5}{2}. $$

Set $\alpha=1$ and $\varepsilon=0$.

For each item task, choose

$$ \beta_i=2a_i,\qquad p_i=\beta_i+1,\qquad V_i=\beta_i,\qquad Q_i=2\beta_i, $$

and efficiencies

$$ (e_{1,i},e_{2,i},e_{3,i})=(1,2,3). $$

Define

$$ K_1=1,\qquad K_2=2,\qquad K_3=4, \qquad H=4S+1=6A+11. $$

Each reference task $r_u$ has parameters

$$ \beta_{r_u}=H,\qquad p_{r_u}=H+1,\qquad V_{r_u}=H,\qquad Q_{r_u}=1, $$

and efficiencies

$$ e_{t,r_u} = \begin{cases} K_u,&t=u,\\ 1/2,&t\ne u. \end{cases} $$

Validity and encoding size

Every mass and numerical parameter is a positive binary rational, and every threshold is strictly below its capacity. Since $A\ge n$,

$$ S=\frac{3A+5}{2} \ge \frac{3n+5}{2} \ge n+3=m. $$

For an item task, $\beta_i\ge2$, so

$$ V_i\beta_i^2=\beta_i^3 \ge2\beta_i = \alpha Q_i(p_i-\beta_i). $$

For a reference task,

$$ V_{r_u}\beta_{r_u}^2=H^3 \ge1 = \alpha Q_{r_u}(p_{r_u}-\beta_{r_u}). $$

The construction uses only sums and multiplication or division by fixed constants. All resulting numbers have bit length polynomial in the PARTITION input length.

Every constructed instance is feasible, independently of whether a partition exists. For example, put all of types $1$ and $2$ in their respective reference tasks. Put mass $1/(2n)$ of type $3$ in each item task and its remaining mass $1/2$ in $r_3$. Each item then has efficiency $3/(2n)<2\le\beta_i$. Reference efficiencies are below $H$, because all efficiencies in the construction are at most $4$ and their masses sum to at most $S$.

3. Reference tasks impose marginal lower bounds

Consider any feasible assignment. Every reference task satisfies

$$ 0<E_{r_t}\le4S<H, $$

so it lies strictly below its threshold and capacity. Its addition and removal revenue slopes are both $1$.

At $r_t$, type $t$ has the largest efficiency, namely $K_t$. Hence

$$ q_{r_t}K_t-E_{r_t}\ge0, $$

and therefore

$$ M_{t,r_t}^+ = K_t+\frac{q_{r_t}K_t-E_{r_t}}{E_{r_t}^2} \ge K_t. $$

Now suppose the assignment is $0$-stable. For any occupied coordinate outside type $t$’s own reference task, a transfer to $r_t$ is feasible. Stability consequently implies

$$ x_{t,i}>0,\quad i\ne r_t \quad\Longrightarrow\quad M_{t,i}^-\ge K_t. $$

We repeatedly use this necessary condition.

Reference tasks contain only their designated types

If $u\ne t$, type $t$’s efficiency at $r_u$ is $1/2$. Every efficiency at $r_u$ is at least $1/2$, so

$$ q_{r_u}/2-E_{r_u}\le0. $$

Thus

$$ M_{t,r_u}^- = \frac12+\frac{q_{r_u}/2-E_{r_u}}{E_{r_u}^2} \le\frac12<K_t. $$

The necessary condition above rules out $x_{t,r_u}>0$.

Therefore $r_u$ contains only type $u$. Since every task must have positive mass,

$$ x_{u,r_u}>0 \qquad\text{for }u=1,2,3. $$

On each such pure reference task, the cost derivative vanishes and the resident type’s removal marginal is exactly $K_u$.

4. Every item task is pure and reaches its threshold

Mixed item tasks are impossible

Suppose an item task contains at least two types. Let $t$ be its occupied type with smallest efficiency. The item efficiencies are $1,2,3$, so $t\in\{1,2\}$ and $e_{t,i}=K_t$.

Because a strictly more efficient type also has positive mass,

$$ q_i e_{t,i}-E_i<0. $$

The item’s removal revenue slope is at most $1$. Consequently,

$$ M_{t,i}^- \le e_{t,i} + 2\beta_i\frac{q_i e_{t,i}-E_i}{E_i^2} < e_{t,i}=K_t. $$

This contradicts the necessary marginal lower bound. Thus every item task is pure.

Type $3$ cannot occupy an item task

On a pure item task, the resident type’s cost derivative is zero. If its resident were type $3$, its removal marginal would be at most $3$, because the removal revenue slope is at most $1$.

But an occupied item coordinate of type $3$ must have removal marginal at least $K_3=4$. This is impossible.

Therefore every item task contains only type $1$ or only type $2$.

Item efficiencies cannot exceed their thresholds

If an item task is pure in type $t\in\{1,2\}$ and $E_i>\beta_i$, its removal marginal is

$$ M_{t,i}^- = -\beta_i e_{t,i}<0<K_t, $$

again a contradiction. Hence $E_i\le\beta_i$.

Item efficiencies cannot lie below their thresholds

Type $3$ occupies no item task and no other type’s reference task. Thus its entire mass is in $r_3$, where its removal marginal is $4$.

Suppose an item task is pure in type $t\in\{1,2\}$ and $E_i<\beta_i$. Then $q_i=E_i/e_{t,i}$. The addition marginal of type $3$ is

$$ M_{3,i}^+ = 3+ 2\beta_i\frac{3/e_{t,i}-1}{E_i}. $$

If $t=1$, this becomes

$$ M_{3,i}^+=3+\frac{4\beta_i}{E_i}>4. $$

If $t=2$, it becomes

$$ M_{3,i}^+=3+\frac{\beta_i}{E_i}>4. $$

The transfer from $r_3$ to this item task is feasible and has strictly positive welfare derivative. This contradicts stability.

We have proved that every item task satisfies

$$ E_i=\beta_i $$

and contains exactly one of types $1$ and $2$.

5. A stable assignment yields a partition

Let $I_t$ be the set of item tasks occupied by type $t$, for $t=1,2$, and define

$$ C_t=\sum_{i\in I_t}\beta_i. $$

These are integers satisfying

$$ C_1+C_2=2A. $$

Type $1$ uses mass $C_1$ on its item tasks. Its reference task must retain positive mass, so

$$ C_1<\mu_1=A+1. $$

Integrality gives $C_1\le A$.

Type $2$ uses mass $C_2/2$ on its item tasks. Positivity of its reference task gives

$$ \frac{C_2}{2}<\mu_2=\frac{A+1}{2}, $$

hence $C_2<A+1$, and therefore $C_2\le A$.

Together with $C_1+C_2=2A$, these inequalities force

$$ C_1=C_2=A. $$

Because $\beta_i=2a_i$,

$$ \sum_{i\in I_1}a_i=\frac A2. $$

Thus the original PARTITION instance is positive.

6. A partition yields a stable assignment

Conversely, suppose $I\subseteq\{1,\ldots,n\}$ satisfies

$$ \sum_{i\in I}a_i=\frac A2. $$

For each $i\in I$, assign mass $\beta_i$ of type $1$ to item task $i$. For each $i\notin I$, assign mass $\beta_i/2$ of type $2$ to item task $i$.

Place the remaining masses in the respective reference tasks:

$$ x_{1,r_1}=1,\qquad x_{2,r_2}=\frac12,\qquad x_{3,r_3}=1. $$

All other coordinates are zero.

The type masses are correct. Every item has efficiency $\beta_i<p_i$, and the reference efficiencies are $1,1,4$, all below $H$. Hence the assignment is feasible and every task is positive.

We verify every transfer inequality.

Every occupied source coordinate of type $t$ has removal marginal $K_t$:

• Its reference task is pure and below threshold.
• Its item tasks, when present, are pure and exactly at threshold, where removal uses slope $1$.

For a reference destination, type $t$’s addition marginal equals $K_t$ at its own reference task. At any other reference task it is at most $1/2<K_t$, by the calculation in Section 3.

For an item destination with resident type $r\in\{1,2\}$, addition at the threshold uses slope $-\beta_i$. Thus

$$ M_{t,i}^+ = -\beta_i e_{t,i} + 2\left(\frac{e_{t,i}}{e_{r,i}}-1\right). $$

Since $e_{r,i}\ge1$ and $\beta_i\ge2$,

$$ M_{t,i}^+ \le (2-\beta_i)e_{t,i}-2 \le-2<K_t. $$

Therefore every destination addition marginal is at most the corresponding occupied source removal marginal. The directional marginal formula proves that every feasible transfer has derivative at most zero.

This assignment is $0$-stable.

7. Computational consequence

The polynomial-time construction satisfies

$$ \text{PARTITION has a solution} \quad\Longleftrightarrow\quad \text{the constructed instance has a }0\text{-stable assignment}. $$

Thus stable-assignment existence is NP-hard already for $\tau=3$ and $\varepsilon=0$. Any algorithm that finds an exact stable assignment or correctly reports nonexistence would decide this existence problem, so the requested computational problem is NP-hard.

The reduction also avoids any algebraic-output complication: Sections 3–5 force every stable assignment in a constructed instance to have rational coordinates, and Section 6 gives witnesses of polynomial encoding length. Rationals can be represented by binary numerator-denominator pairs, or as algebraic numbers using their linear defining polynomials.

Consequently, a polynomial-time algorithm in $m,\tau,L$ for the stated problem would imply $\mathrm P=\mathrm{NP}$.

⟨structured verdict parsed — rendered above⟩

The proof is correct and resolves the assigned question. It establishes $\mathrm{NP}$-hardness of the exact assignment-or-nonexistence problem, already for $\varepsilon=0$ and support size $\tau=3$. I found no major or minor issues requiring repair.

• Directional derivatives and transfer feasibility

Since every task has positive mass and all efficiencies are positive, $E_i>0$. Thus all denominators in the marginal formula are well defined.

For an occupied source coordinate, sufficiently small transfers preserve coordinate nonnegativity and source-task positivity. They decrease source efficiency, so they preserve its upper capacity constraint. Destination efficiency increases strictly because $e_{t,j}>0$. Consequently, the stated feasibility condition is exact:
$$ E_j<p_j. $$
In particular, transfers into a task at capacity are correctly excluded.

The cost differentiation is correct:
$$ \left.\frac{d}{dh}\left(-c_i\frac{q_i+h}{E_i+he_{t,i}}\right)\right|_{h=0} = c_i\frac{q_i e_{t,i}-E_i}{E_i^2}. $$
Removal contributes its negative. At $E_i=\beta_i$, removal enters the increasing revenue branch, while addition enters the decreasing branch. The definitions of $s_i^-$ and $s_i^+$ correctly implement these directions.

Therefore the identity
$$ D^+\mathcal W(x;b_{t,j}-b_{t,i}) = M_{t,j}^+-M_{t,i}^- $$
and the resulting characterization of $0$-stability are valid.

• Source problem and input validity

The cited theorem concerns precisely the binary-encoded positive-integer PARTITION problem used here. Its $\mathrm{NP}$-completeness is an appropriate starting point. [Karp’s paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf)

All three masses are strictly positive, so the support size is exactly $\tau=3$. The task count is $m=n+3\ge4$, and the total mass calculation is correct:
$$ S=\frac{3A+5}{2}. $$
Because $A\ge n\ge1$,
$$ S\ge\frac{3n+5}{2}\ge n+3=m. $$
The final inequality also holds at the boundary case $n=1$.

All constructed efficiencies and required parameters are positive rationals, and $p_i-\beta_i=1$ for every task. The imposed parameter inequalities are verified correctly:
$$ \beta_i^3\ge2\beta_i $$
for item tasks, since $\beta_i\ge2$, and
$$ H^3\ge1 $$
for reference tasks.

The identity $H=4S+1=6A+11$ is correct. Although $A$ can be numerically large, its binary encoding length is polynomial in the source input length. The construction therefore has polynomial encoding size and can be produced in polynomial time.

• Feasibility independent of PARTITION

The supplied assignment uses total type-$3$ mass
$$ n\frac{1}{2n}+\frac12=1. $$
Every item receives positive mass and has efficiency
$$ \frac{3}{2n}<2\le\beta_i. $$
Every reference task also receives positive mass. Its efficiency is at most $4S<H$, hence below its threshold and capacity.

Thus every constructed instance is feasible, including instances whose PARTITION answer is negative. The reduction does not obtain hardness merely through assignment infeasibility.

• Reference-task marginal bounds

The bound
$$ 0<E_{r_t}\le4S<H $$
holds for every feasible assignment. Hence reference tasks always have revenue slope $1$, and transfers into them are feasible.

At its own reference task, type $t$ has maximum efficiency $K_t$, giving
$$ q_{r_t}K_t-E_{r_t}\ge0 $$
and therefore $M_{t,r_t}^+\ge K_t$. The necessary stability condition for every occupied coordinate outside that reference task follows correctly.

At another reference task, type $t$ has minimum efficiency $1/2$. Therefore
$$ q_{r_u}/2-E_{r_u}\le0, $$
so its removal marginal is at most $1/2<K_t$. Stability excludes such occupancy.

Because all tasks must remain positive, each reference task consequently contains positive mass of its designated type. Its resident removal marginal is exactly $K_t$. There is no circular dependence in this reasoning: the lower bound is established before purity is inferred.

• Item-task characterization

For a mixed item, the least efficient occupied type is either type $1$ or type $2$, and its efficiency equals $K_t$. The presence of a strictly more efficient occupied type makes
$$ q_i e_{t,i}-E_i<0. $$
Since the removal revenue slope is at most $1$, its removal marginal is strictly below $K_t$. This contradicts the previously established necessary condition. Thus item purity is proved.

On a pure item, the resident cost derivative vanishes. Type $3$ would then have removal marginal at most $3<K_3$, so it cannot occupy an item.

For a pure item occupied by type $1$ or type $2$, efficiency above threshold gives removal marginal $-\beta_i e_{t,i}<K_t$. Thus $E_i\le\beta_i$.

Type $3$ must consequently place its entire mass in $r_3$, where its removal marginal is $4$. If an item lies strictly below threshold, the computed type-$3$ addition marginals are correct:
$$ 3+\frac{4\beta_i}{E_i}>4 $$
for a type-$1$ item, and
$$ 3+\frac{\beta_i}{E_i}>4 $$
for a type-$2$ item. Such a destination is below capacity, making the violating transfer feasible.

Therefore every stable assignment has each item pure in type $1$ or type $2$, with $E_i=\beta_i$.

• Stable assignment implies PARTITION

The item efficiency totals satisfy $C_1+C_2=2A$. Positivity of the designated reference tasks yields the strict inequalities
$$ C_1<A+1,\qquad C_2<A+1. $$
Both totals are integers, so $C_1\le A$ and $C_2\le A$. Their sum forces $C_1=C_2=A$, giving the required subset sum.

This also correctly handles odd $A$: the resulting subset equality would be impossible, so no stable assignment exists in that case. Strict reference-task positivity is used exactly as required by the task.

• PARTITION implies stable assignment

The proposed assignment conserves each type’s mass. All tasks have positive mass, items are at threshold below capacity, and references are below threshold.

Every occupied source has removal marginal $K_t$. Reference destinations satisfy the claimed addition bounds. At an item destination, the threshold-direction calculation is correct:
$$ M_{t,i}^+ = -\beta_i e_{t,i} +2\left(\frac{e_{t,i}}{e_{r,i}}-1\right). $$
Using $e_{r,i}\ge1$ and $\beta_i\ge2$ gives
$$ M_{t,i}^+\le(2-\beta_i)e_{t,i}-2\le-2<K_t. $$
These checks cover every occupied source type and every distinct destination. Equality at a designated reference destination is permitted by the stability definition. The assignment is therefore $0$-stable.

• Computational conclusion and output representation

Both directions of the reduction are established. An algorithm that returns a stable assignment or correctly reports nonexistence would decide PARTITION on the constructed instances.

The rational-output claim is also justified: item occupancies are forced to be $\beta_i$ or $\beta_i/2$, and reference occupancies are determined by mass conservation. The resulting coordinates have polynomial encoding length.

The proof establishes the requested $\mathrm{NP}$-hardness. It does not claim general $\mathrm{NP}$ membership or strong $\mathrm{NP}$-hardness, and neither is needed to answer the task. No additional clarification is required.

⟨structured verdict parsed — rendered above⟩