The Complexity of Robust and Resilient $k$-Partition Problems

In this paper, we study a $k$-partition problem where a set of agents must be partitioned into a fixed number of $k$ non-empty coalitions. The value of a partition is the sum of the pairwise synergies inside its coalitions. Firstly, we aim at computing a partition that is robust to failures from any set of agents with bounded size. Secondly, we focus on resiliency: when a set of agents fail, others can be moved to replace them. We settle the computational complexity of decision problem \textsc{Robust-$k$-Part} as complete for class $\Sigma_2^P$. We also conjecture that resilient $k$-partition is complete for class $\Sigma_3^P$ under simultaneous replacements, and for class PSPACE under sequential replacements.