Abstract Congestion games are a well-studied class of games that has been used to model real-world systems such as Internet routing. In many congestion games, each player’s number of strategies can be exponential in the natural description of the game. Most existing algorithms for game theoretic computation, from computing expected utilities and best responses to finding Nash equilibrium and other solution concepts, all involve enumeration of pure strategies. As a result, such algorithms would take exponential time on these congestion games. In this work, we study congestion games in which each player’s strategy space can be described compactly using a set of linear constraints. For instance, network congestion games naturally fall into this subclass as each player’s strategy can be described by a set of flow constraints. We show that we can represent any mixed strategy compactly using marginals which specify the probability of using each resource. As a consequence, the expected utilities and the best responses can be computed in polynomial time. We reduce the problem of computing a best/worst symmetric approximate mixedstrategy Nash equilibrium in symmetric congestion games to a constraint optimization problem on a graph formed by the resources and the strategy constraints. As a result, we present a fully polynomial time approximation scheme (FPTAS) for this problem when the graph has bounded treewidth.