Designing Pairwise-Stable Agent Seating Arrangements
Source: arXiv:2607.27102 · Published 2026-07-29 · By Frederik Glitzner
TL;DR
This paper investigates a broad class of multi-agent arrangement problems where agents, possessing ordinal preference rankings over each other, must be assigned to positions on a target graph with stability guarantees. Classical problems such as stable marriage, seat arrangement, and coalition formation impose fixed target graphs and aim for strong stability criteria like exchange-stability or envy-freeness, which often do not exist or are computationally intractable in simple graph topologies. In contrast, the authors consider a central planner who can design the target graph itself, enabling new tractability results and flexibility. The introduction of a novel pairwise stability notion (also called runaway stability) requires no two agents prefer each other to their respective best neighbors on the graph, capturing scenarios where agents have incentives to form pairs outside the arrangement if dissatisfied locally. The paper develops a novel concept called (r1, r2, r3)-bundles as a compressed representation of preferences into small path components that can be combined into stable arrangements efficiently. Leveraging classical stable roommates theory, they devise polynomial-time algorithms to find bundles and construct stable seatings or teams that minimize tables/teams and sizes while respecting stability. They show that strong stability and envy-freeness remain computationally hard even in very restricted cases, but the flexibility in designing the seating graph grants efficient computability. The framework also extends to stable b-matchings with agent capacities. The work reveals tight boundaries between tractability and hardness and uncovers connections to subgraph isomorphism, disjoint path partitioning, and bin-packing problems.
Key findings
- Introducing pairwise stability focused on agents preferring each other to their best neighbour yields a tractable middle ground between strong intractable stability notions and trivial solutions.
- Any preference system admits a stable arrangement as a collection of P3 (paths of length 3) components, forming the basis for building bundles.
- Algorithm 1 computes (r1, r2, r3)-bundles compressing preference systems into stable arrangements of isolated vertices, P2, and P3 paths in O(n^2) time.
- Arranging bundles on a fixed graph G is NP-complete even if G is bipartite with max degree 3 (Theorem 1.1).
- When the designer can build the target graph, MinTablesMinSeats and MinSeatsMinTables seating problems are solvable in O((n^2 + s*^3) n^2) and O(s*^3 n^2) time respectively, where s* is minimal seats per table, and stable arrangements always exist for table sizes ≥ 3 (Theorem 1.2).
- Team formation problems (MinTeamsMinSize and MinSizeMinTeams) restricted to clique components have similar polynomial algorithms with runtime O((n^2 + s*^3) n^2) and O(s*^3 n^2), guaranteeing stable team formation for size ≥ 3 (Theorem 1.3).
- Best-Stable b-Matching with capacities ≥ 2 always admits a solution and can be solved in O(n^2) time (Theorem 1.4).
- The stability notion differs from exchange-stability and envy-freeness; it is robust to larger coalitions leaving since only pairwise deviations are considered.
Threat model
The adversary considered is conceptualized as any pair of agents who might prefer each other over their assigned neighbors in the seating or coalition arrangement, motivating them to coordinate and break away from the designed graph. The model assumes agents have ordinal preferences but have limited visibility or communication beyond local neighborhoods, preventing larger coalition deviations. The planner cannot prevent agents from leaving if such incentive pairs exist, so the design aims to eliminate such pairwise blocking pairs. No active malicious adversaries performing attacks are modeled.
Methodology — deep read
Threat Model & Assumptions: The adversary in this setting is implicit - dissatisfaction arises when two agents prefer each other over their assigned neighbors, incentivizing them to leave or re-pair outside the arranged seating or team. The model assumes agents express weak or strict ordinal preferences over all other agents (complete preference orders). The planner can design the underlying target graph (seating or coalition structure), rather than it being fixed. No assumptions on adversarial agents explicitly, stability is with respect to pairs having an incentive to defect.
Data: The input is a set of agents A and their ordinal preference system ≿ encoding the rankings over all other agents. No explicit external datasets are used; the input preference system generalizes stable roommates and similar classical problems. The agent count is n. Tie-breaking for weak preferences is done arbitrarily to reduce to strict preferences during computing stable partitions.
Architecture / Algorithmic Framework: The paper leverages classical stable roommates theory and the stable partition structure (Tan's algorithm) to decompose the preference system into stable partitions represented as permutations of agents forming cycles (including odd and even cycles). This structure is then 'cut up' into small path components: P1 (isolated vertices), P2 (paths of length 1), and P3 (paths of length 2), collectively called (r1, r2, r3)-bundles. Bundles compress the preference system while preserving stability. Algorithm 1 details the construction of bundles by computing stable partitions, decomposing cycles, and associating agents to path components. These bundles can be augmented by adding edges to form more complex stable graphs.
Key new notions include the definition of pairwise-stability: no pair of agents mutually prefers each other over their best neighbor in the assigned graph, and formally defining bundles as a stable arrangement on collections of small paths.
- Training regime / Computational procedures: The main computational procedures involve polynomial-time algorithms: computing reduced stable partitions in O(n^2) time (using Tan's algorithm), splitting cycles into bundle components, and solving optimization variants (MinTablesMinSeats, MinTeamsMinSize) by dynamic programming or combinatorial algorithms with runtimes polynomial in n and minimal table/team size s*. Algorithm 7 (not detailed) solves Best-Stable b-Matching in O(n^2).
A concrete example is the decomposition of a 15-agent stable roommates instance with preference ties broken arbitrarily, resulting in a stable partition consisting of cycles (a1 a2 a3 a4 a5)(a6 a7 a8 a9)(a10 a11 a12)(a13 a14)(a15). This is transformed into a bundle of P1, P2, and P3 components by removing edges from cycles to obtain stable paths. This bundle is then the basis for constructing a stable seating arrangement.
Evaluation Protocol: The evaluation is theoretical, consisting of proofs establishing NP-completeness of arranging bundles on fixed graphs, polynomial-time solvability when designing target graphs, existence proofs for stable arrangements of given sizes, and runtime analyses. There are no empirical experiments or statistical tests. The paper characterizes boundaries between tractability and hardness and compares stability notions.
Reproducibility: Code or datasets are not released, as the work is theoretical and algorithmic in nature. The core algorithms are described with pseudocode in Algorithm 1 and references to classical subroutines (Tan's algorithm). The preference systems and stable partitions are formal mathematical objects.
Technical innovations
- Introducing a new pairwise stability notion requiring no two agents to prefer each other over their assigned best neighbour, enabling tractable stable arrangements compared to classical stronger stability definitions.
- The (r1, r2, r3)-bundle framework compresses complex preference systems into collections of stable small path components, serving as building blocks for scalable stable graph design.
- Extending classical stable roommates theory by decomposing stable partitions into bundles that guarantee the existence of stable seating or team arrangements with minimal tables or team sizes.
- Developing polynomial-time algorithms to optimally design target graphs (e.g., seating graphs, clique formations) ensuring pairwise-stable arrangements, circumventing NP-hardness when the graph is fixed.
Baselines vs proposed
- Arranging Bundles on fixed graph G (bipartite,max deg 3): NP-complete; vs Designer chooses G: poly-time solved.
- MinTablesMinSeats: Baseline NP-hard (classical seat arrangement with fixed graph); Proposed: O((n^2 + s*^3)n^2) poly-time algorithm.
- MinTeamsMinSize: Known intractable when restricted; Proposed algorithm: O((n^2 + s*^3) n^2) solves with stable clique teams.
- Best-Stable b-Matching: Classical stable b-matching can be hard; Proposed specialized stability notion allows O(n^2) algorithm.
Limitations
- Stability notion only guarantees pairwise stability; larger coalitions potentially destabilizing are not prevented, though argued to be impractical due to coordination costs.
- Preference ties broken arbitrarily for computational tractability, which may not reflect original weak preferences leading to multiple stable partitions.
- The framework assumes complete ordinal preferences over all other agents; incompleteness or partial rankings are not considered.
- No empirical or simulation validation is provided to demonstrate applicability or performance on real-world preference data.
- Results assume central planner can fully design the target graph; scenarios with restricted graph design spaces are not addressed.
- Complexity results rely on classical stable roommates and do not resolve all open hardness questions for larger graph classes or weighted preferences.
Open questions / follow-ons
- How does the stability and tractability change under incomplete or partial preference lists rather than complete rankings?
- Can the bundle framework be extended to weighted or cardinal utilities instead of ordinal preferences?
- What approximation guarantees or heuristic methods exist when designing graphs under restricted structure classes or limited edge additions?
- Can empirical studies validate the practical relevance and agent behaviors under pairwise stability in real-world seating or team formation scenarios?
Why it matters for bot defense
Bot-defense and CAPTCHA systems often involve scenarios where multiple autonomous agents (e.g., users or bots) compete or interact under incentive constraints. This paper’s framework provides a novel lens into designing interaction graphs (such as session groupings or challenge assignments) that ensure pairwise stability — meaning no two agents prefer to break away and coordinate separately. For CAPTCHA and bot-defense engineers, the key insight is that allowing some flexibility in structuring interaction topologies (instead of fixed challenge assignments) can yield computationally efficient, stable configurations that frustrate pairwise collusion or evasion. Moreover, the bundle decomposition approach offers a compact representation to reason about agent preferences and potential instability, which could inspire new CAPTCHA challenge grouping or bot detection schemes that minimize incentive to defect. However, since this work is theoretical and abstract, applying it directly to dynamic, adversarial bot populations requires further research, including modeling more complex or partial preference scenarios and empirical validation.
Cite
@article{arxiv2607_27102,
title={ Designing Pairwise-Stable Agent Seating Arrangements },
author={ Frederik Glitzner },
journal={arXiv preprint arXiv:2607.27102},
year={ 2026 },
url={https://arxiv.org/abs/2607.27102}
}