In October 2026 two independent groups claimed deterministic algorithms that count the satisfying assignments of a k-CNF formula in time 2^{o(n)}, refuting the Exponential Time Hypothesis (ETH). We ask what these claims imply for the exact analysis of equilibria in games where each player interacts with a bounded number of others. Conditional on the claimed … Read more
We study weighted, capacitated cost-sharing games on parallel-link networks, also known as bin packing games. We focus on an integer-splittable variant in which items of varying sizes can be divided into integer units and assigned to bins with heterogeneous capacities and costs. Although this setting has practical relevance, it remains largely unexplored in the context … Read more
We investigate a new class of congestion games, called Totally Unimodular Congestion Games, in which the strategies of each player are expressed as binary vectors lying in a polyhedron defined using a totally unimodular constraint matrix and an integer right-hand side. We study both the symmetric and the asymmetric variants of the game. In the … Read more