Imagine you're seating guests at a wedding. You check every pair for awkward history and assume the table will be fine if all pairs get along. But three people who are individually fine in pairs might form a toxic trio — and your careful pairwise checks never saw it coming. That's the core mechanism this paper exposes in multi-robot planning: scoring joint plans by adding up singleton and pairwise contributions while ignoring the higher-order interactions that actually determine delivered coverage. The committed claim: pairwise approximations to submodular coverage functions produce enough ranking error to select the wrong multi-robot plan on most tested maps, with regret reaching 0.337 of total map coverage. This isn't a theoretical bound — it's an empirical measurement on frozen four-robot trajectories across seven indoor exploration maps. For each candidate plan, the authors replay all 16 robot subsets (the full power set of 4 robots) to compute the exact delivered-coverage set function F, then compare rankings under two pairwise approximations against the true ranking. The two approximations tested are the order-2 Möbius truncation F₂ (which keeps exact singleton and pairwise Möbius coefficients and zeros out everything else) and an equal-weight least-squares two-additive fit G. F₂ is the natural truncation from cooperative game theory; G is the practical least-squares variant you'd actually implement. Both belong to the family of k-additive set function approximations — the same mathematical scaffolding behind Shapley-value decompositions and multi-agent credit assignment. The key architectural property they lean on is that four robots make the full power-set enumeration tractable (16 subsets per plan), giving exact ground truth against which to measure approximation quality. The integrity story is unusually clean for a short workshop paper. Because the authors freeze trajectories and replay subsets exhaustively, there's no simulation-within-simulation circularity — the ground truth F is exact, not estimated. The benchmark is a publicly described indoor exploration environment with seven distinct maps, and two candidate-generation families (different planning ranges) provide replication across conditions. Code is released. The main limitation is scale: four robots keep the combinatorics manageable but leave open whether the regret patterns hold at 8 or 16 robots where exhaustive evaluation is infeasible. The most striking finding isn't the headline regret number — it's the paradox buried in the results. The additive (singleton-only) score F₁ actually selects the correct winner more often than the pairwise F₂: six of seven maps versus one of seven in one candidate family. Adding pairwise information makes the ranking worse, not better, because the Möbius truncation introduces systematic bias in the omitted higher-order terms. The least-squares fit G partially corrects this (three of seven maps wrong instead of six) but doesn't eliminate the problem. And the authors explicitly show that lower average reconstruction error (how well the approximation fits F across all subsets) does not predict lower selection regret (how often it picks the wrong plan). You can minimize fitting error and still maximize decision error. The practical upshot for anyone building multi-robot coordination systems: if you're using pairwise scoring to select among candidate plans — and most deployed multi-robot planners do exactly this — you should be worried about whether your approximation is selecting plans that look good on the surrogate but underperform on actual coverage. The singleton score may be a safer bet than the pairwise one in low-robot-count regimes, which is counterintuitive and worth testing in your own pipeline. What's missing is the scaling question. Four robots is the sweet spot where exhaustive ground truth is cheap, but real fleets are 8-50+ robots. The authors don't attempt any extrapolation of regret scaling with robot count, and they don't test approximate ground truth methods (e.g., sampling subsets rather than enumerating them). My read: this is a clean first result sized to fit a workshop paper, and the scaling study is the obvious next paper. Whether regret grows or shrinks with more robots is the open question that determines whether this finding is a curiosity or a field-wide problem.
