Linear-time subgame detection in extensive form games via bridge finding

Kadnikov, Daniel A., Savani, Rahul and Turocy, Theodore L. ORCID: https://orcid.org/0000-0002-2265-844X (2026) Linear-time subgame detection in extensive form games via bridge finding. Information Processing Letters. ISSN 0020-0190 (In Press)

PDF (Subgames_as_Bridges__IPL_submission (4)) - Accepted Version Restricted to Repository staff only until 31 December 2099. Available under License Creative Commons Attribution. Request a copy

Abstract

A subgame of an extensive form game is a subtree that no information set straddles. We show that a non-root decision node is a subgame root exactly when the tree edge entering it is a bridge — an edge whose removal disconnects the graph — of the extended graph, obtained from the game tree by adding, for each information set, edges connecting its members. The game tree provides a spanning tree for this graph. The no-straddling condition admits two interpretations: a geometric one via bridges, and an algebraic one via XOR cancellation over per-node weights. The geometric view, specialized to information sets, adapts Tarjan’s interval bridge-finding condition to reduce reachability to containment between the intervals of leaf indices below each node. The resulting algorithm runs in linear time without materializing the extended graph, and discovers subgame roots in the reverse topological order required for backward induction. The algebraic view is realized by cycle-space sampling, which specializes in the same way to a single-pass randomized variant trading determinism for a constant-factor speed-up. Both algorithms handle imperfect recall, including absent-mindedness. The interval algorithm has been integrated into Gambit (release 16.6) as a linear-time replacement for the prior per-node test.

Item Type:	Article
Faculty \ School:	Faculty of Social Sciences > School of Economics
UEA Research Groups:	Faculty of Social Sciences > Research Groups > Environment, Resources and Conflict Faculty of Social Sciences > Research Groups > Economic Theory Faculty of Social Sciences > Research Groups > Behavioural Economics Faculty of Social Sciences > Research Centres > Centre for Competition Policy Faculty of Social Sciences > Research Centres > Centre for Behavioural and Experimental Social Sciences
Depositing User:	LivePure Connector
Date Deposited:	09 Nov 2026 11:45
Last Modified:	09 Nov 2026 11:45
URI:	https://ueaeprints.uea.ac.uk/id/eprint/105018
DOI:	issn:0020-0190

Actions (login required)

View Item