Learning the Scan: Linear-Time Coalition Formation by Interval Partitioning over a Learned Agent Order

Many real coordination problems ask a large group of agents to split into teams that are allowed only if their members are linked in some network. Examples include riders who share a car only with friends, sensors that fuse data only with those in radio range, and hospitals that collaborate only with non-rivals. Finding the best such split is NP-hard even on planar graphs. Exact solvers stop at a few dozen agents, and learned solvers have so far been shown at around a hundred. Vision models built on linear-complexity sequence architectures face a mirror-image problem. To read a 2D image in linear time, a state space model (a recurrent network whose hidden state is updated token by token along a one-dimensional "scan" through the data) must first flatten the image into a line. A large part of that literature is about choosing lines whose consecutive tokens are true spatial neighbors.

This note proposes to treat the scan order as the solver itself. If agents are laid out in a single sequence, then splitting that sequence into contiguous segments, and keeping only segments that are connected in the constraint graph, can be done exactly by a one-dimensional dynamic program. That program runs in time linear in the number of agents. The hard combinatorial problem then becomes a learning problem: produce an ordering of the agents in which the optimal coalitions sit contiguously. A linear-complexity sequence model is a natural tool for producing and refining such orderings at scales of thousands of agents.

Core Claim

Fix an order $\pi$ of the $n$ agents and a maximum coalition size $L$. The best coalition structure whose coalitions are contiguous in $\pi$ and connected in the graph $G$ is found exactly by

$$F(j) = \max_{\,j-L \le i < j,\;\; G[\pi_{i+1..j}] \text{ connected}} \; F(i) + v(\pi_{i+1..j}), \qquad F(0)=0,$$

where $F(j)$ is the best value achievable using the first $j$ agents in the order, $\pi_{i+1..j}$ is the block of agents at positions $i+1$ through $j$, and $v$ is the coalition value oracle. The program makes $O(nL)$ value queries and uses $O(n)$ memory. Connectivity is checked incrementally with a union-find structure as each block grows. The only thing lost is the value of optimal coalitions that $\pi$ splits apart. We call that loss the order gap of $\pi$.

The claim is that a model trained to emit orders can shrink the order gap to a few percent on graph-constrained instances with realistic, bounded coalition sizes. Car capacity is one source of such a bound; the vehicle limit in the ridesharing setting of Sharing Rides with Friends is the natural example. The model uses a linear-complexity backbone and is supervised by exact solutions on small instances. If this holds, the result is a feasible-by-construction, near-optimal coalition solver that runs in linear time and memory on instances far beyond the reach of exact search.

Two observations from the vision literature motivate the design. First, PlainMamba replaces raster scans with a continuous zigzag path in which every token is spatially adjacent to its predecessor. On a grid, that path is a Hamiltonian path of the grid graph, so every contiguous segment of it is automatically a connected coalition. A fixed zigzag scan is therefore already a valid, if crude, coalition solver for spatially embedded agents. Second, Adventurer shows that one scan direction per layer, with the direction flipped between layers and a prepended global-average token, can replace costly multi-direction scans. That makes a cheap iterative re-ordering loop plausible. PlainMamba and Adventurer use the scan only as a way to read pixels. Here the scan is the output, and it is scored by how well it lines up with the optimal teams.

Research Program

The system has three parts. The first is the ordering model. Each agent is given a feature vector: its position, its attributes (for example, origin and destination for a rider), its degree, and summaries of its neighbors. Agents are read in an initial space-filling order. The ordering model is a stack of Mamba-2 blocks with Adventurer-style layer flipping and heading tokens, and it outputs a scalar sort key per agent. Sorting the keys gives $\pi$. This is the step that removes the rigid-grid assumption that the linear vision models share: the initial scan does not need to follow graph edges, because feasibility is enforced by the decoder rather than by the scan geometry.

The second part is the exact interval decoder described by the equation above. It guarantees that every output coalition is feasible under the graph constraint.

The third part is a refinement loop. After decoding, each found coalition is collapsed into a single summary token, and the model re-orders the coalition tokens together with the unassigned agents. This lets coalitions that were split across the sequence be reunited in a second pass. We run $R$ rounds, with $R$ between 2 and 4, and keep the best structure found.

Training uses imitation of exact solutions. On instances small enough for exact solvers, we build target orders by concatenating the optimal coalitions, with each coalition internally ordered along a spanning path. Ties between orders are broken randomly. The model is then trained with a pairwise ranking loss so that its sort keys reproduce such orders. Small instances go up to about 27 agents with SMART, and larger sparse ones are solved with COP-GCCF. A second stage fine-tunes with REINFORCE, using the decoded value itself as the reward, so the model can learn beyond the scale of its supervision.

The analysis part asks when the order gap is small. For path graphs the gap is zero for every consistent order, because every connected set on a path is an interval. We expect the gap to grow with branching and cycles. This echoes the finding in Individually Stable Dynamics in Coalition Formation over Graphs that paths and trees are benign while cycles break convergence. We will measure the gap as a function of Barabási–Albert density ($m=1$ versus $m=2$), the regime where COP-GCCF reports its advantage collapsing. This matters because the interval decoder's cost does not depend on density, while bucket elimination's cost does.

Baselines

The naive reference point is the same interval decoder run on a fixed, unlearned order. We use a PlainMamba-style zigzag for spatial instances and a depth-first-search order of a breadth-first spanning tree for graph instances, and we take the best of several random restarts matched to the learned model's wall-clock time. This is the key ablation. It isolates whether learning the order adds anything beyond the decoder. The learned model beats it only if it reduces the order gap by a margin larger than the spread across restarts.

The strongest existing method at scale is the anytime approximation for social ridesharing from Sharing Rides with Friends, run on GeoLife trajectories overlaid with Twitter subgraphs. That paper reports solutions for 2,000 agents in under 100 seconds, a worst-case factor of 1.41, and travel-cost reductions of up to 36.22% relative to everyone driving alone. It is the strongest competitor because it is the only cited method that is purpose-built for graph-constrained coalitions and demonstrated at thousands of agents. We will run it on identical instances, on the same CPU budget, and with its own tuning. Beating it means a larger cost reduction at equal or lower wall-clock time for 2,000 agents or more.

For dynamic, learned coalition formation, the competitor is BRIDGE. It reports 8.7 seconds of inference at 100 agents, against 303 seconds for CSG-UCT, and over 97% of optimal value in zero-shot transfer from 3 to 5 agents on Modified Normal. BRIDGE has no graph constraint, so we will add a feasibility mask to its merge scorer and train it with the same instance budget and GPU hours as our model. We compare optimality gaps on its synthetic distributions at $n \le 27$, where optima are known, and runtime at 100 agents.

For sensor networks, the reference is the $O(n^2m)$ greedy of Overlapping Coalition Formation for Efficient Data Fusion in Multi-Sensor Networks, which stays within 1% of the optimal bound up to 20 agents. We restrict it to disjoint coalitions, since our decoder is disjoint. That restriction is itself a limitation we will report.

Exact solvers serve as oracles rather than competitors. These are SMART up to 27 agents, and COP-GCCF on sparse graphs, where the file reports up to four orders of magnitude speedup over DyCE and IDPG for $m=1$.

The backbone ablation holds the decoder and training fixed and swaps the Mamba ordering model for a message-passing graph neural network and for a quadratic Transformer.

Why not just…?

Why not just use a fixed scan order with the exact decoder? This is the most serious threat. On grid-embedded instances with small $L$, a zigzag scan might already capture most optimal coalitions. If the learned model's order gap is within restart noise of the best fixed order, we will conclude that the contribution is the decoder alone and reposition the work around that result. The density sweep is the setting where we expect fixed orders to fail, because cycles and hubs make contiguity in any fixed order a poor proxy for membership in the same team.

Why not just use greedy merging or the existing anytime approximations? On static sensor instances the greedy is within 1% of optimal (Overlapping Coalition Formation), but that evidence stops at 20 agents. In team formation, plain greedy loses by over 50% to ThresholdGreedy, which shows that greedy quality depends heavily on the domain. The ridesharing approximation carries only a 1.41 worst-case guarantee. Our experiments compare against both head to head at 2,000 agents and above. If greedy matches us there, the learned approach is not worth its training cost for static problems.

Why not just use a graph neural network instead of a state space model? Message passing is also linear in the number of edges and respects the graph natively. The case for the Mamba backbone is weaker than the case for the order-plus-decoder design, which is why the backbone is an ablation rather than the claim. A plausible advantage is that a sort key must encode global position, and a scan with heading tokens carries global context in one pass, whereas message passing needs depth proportional to the graph diameter. We will report the swap honestly whichever way it goes.

Why not just run exact tree-decomposition dynamic programming? Tree-decomposition dynamic programming is linear only for bounded treewidth, and its cost grows as $w^{w}$ with treewidth $w$ (Coalition Structure Generation over Graphs). The problem stays NP-complete on planar graphs. Social and road graphs quickly exceed single-digit treewidth, while the interval decoder's cost is independent of treewidth.

Proposed Experiments

The first decisive check measures the order gap at small scale. On SMART's synthetic distributions and on Barabási–Albert graphs with $m=1$ and $m=2$, at $n \le 27$, we compute exact optima and report the order gap for three orders: the learned order, the best fixed order, and the oracle order. The project succeeds on this check if the learned gap falls below the approximation gap that BRIDGE achieves under the same masking, and is well below the fixed-order gap at $m=2$.

The second check tests scaling on real data. On GeoLife with Twitter subgraphs, at 100, 500, 2,000 and 10,000 riders, we report travel-cost reduction and wall-clock time against the ridesharing anytime approximation. We also report exact optima at 100 agents, where that paper's exact solver finishes in about two hours. The target is to exceed the 36.22% reduction regime at equal time for 2,000 agents or more, and to remain feasible at 10,000, where no cited method reports results.

The third check covers sensor fields. We extend the 2D tracking simulation from 20 to 5,000 sensors, using sensor adjacency by radio range as the constraint graph. We compare Fisher-information value against the restricted greedy, and we check agreement with the exact optimum where branch-and-bound still terminates.

Across all three settings we report memory as $n$ grows. Linear memory against SMART's exponential tables is a claim that can be tested directly. We also run the backbone swap and the refinement-rounds ablation, so that the gain can be attributed to the decoder, to the learned order, or to the architecture.