Optimal agent cooperation: How many is enough?

In this paper, we study a simple though non-trivial agent cooperation problem on a structured partially unknown graph whereby the agents observe and share local environment information. We use a recently developed efficient algorithm to compute optimal two- and three-agent policies. We obtain rigorous results on the performance of agent groups as function of the group size. Furthermore, we propose to split up larger agent groups in smaller sized subgroups, each employing an optimal policy suited for its size. We obtain an estimate for the resulting optimality gap and illustrate that for some problem specifics, three-agent subgroups suffice for reasonably small optimality gaps.