Decentralized Local Search in Near-Potential Binary Games

We study decentralized binary programming games in which agents make constrained binary decisions under coupled costs, limited computation, and unreliable communication. We propose Decentralized Local Search (DLS), which replaces exact best-response optimization with randomized local search and uses locally maintained empirical-frequency estimates over a random time-varying network. Communication may become increasingly sparse, provided successful information propagation persists over time. For near-potential games, we establish finite-time belief-tracking guarantees and almost-sure convergence to an approximate Nash equilibrium set. Under a best-response margin condition, DLS reaches the pure Nash equilibrium set in finite time almost surely; if equilibria are strict, the joint decisions eventually stabilize at a pure Nash equilibrium. Numerical experiments show that DLS preserves equilibrium-seeking performance while substantially reducing the cost of repeated exact optimization.