Algorithms for partially robust team formation

Algorithms for partially robust team formation

Schwind, Nicolas (National Institute of Advanced Industrial Science and Technology (AIST))
Demirović, E. (TU Delft Algorithmics)
Inoue, Katsumi (National Institute of Informatics; Graduate University for Advanced Studies (SOKENDAI))
Lagniez, Jean Marie (Université d’Artois)

2023

In one of its simplest forms, Team Formation involves deploying the least expensive team of agents while covering a set of skills. While current algorithms are reasonably successful in computing the best teams, the resilience to change of such solutions remains an important concern: Once a team has been formed, some of the agents considered at start may be finally defective and some skills may become uncovered. Two recently introduced solution concepts deal with this issue proactively: 1) form a team which is robust to changes so that after some agent losses, all skills remain covered, and 2) opt for a recoverable team, i.e., it can be "repaired" in the worst case by hiring new agents while keeping the overall deployment cost minimal. In this paper, we introduce the problem of partially robust team formation (PR–TF). Partial robustness is a weaker form of robustness which guarantees a certain degree of skill coverage after some agents are lost. We analyze the computational complexity of PR-TF and provide two complete algorithms for it. We compare the performance of our algorithms with the existing methods for robust and recoverable team formation on several existing and newly introduced benchmarks. Our empirical study demonstrates that partial robustness offers an interesting trade-off between (full) robustness and recoverability in terms of computational efficiency, skill coverage guaranteed after agent losses and repairability. This paper is an extended and revised version of as reported by (Schwind et al., Proceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’21), pp. 1154–1162, 2021).

Anytime algorithm
Computational complexity
Facility location
Partial robustness
Resilience
Robustness
Team formation

http://resolver.tudelft.nl/uuid:21582e32-0928-419c-b1de-ef59d037ad45

https://doi.org/10.1007/s10458-023-09608-7

2023-10-30

1387-2532

Autonomous Agents and Multi-Agent Systems, 37 (2)

Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Institutional Repository

journal article

© 2023 Nicolas Schwind, E. Demirović, Katsumi Inoue, Jean Marie Lagniez