Distributed Potential-Game Optimization with Local Exchanges for Dynamic Maximum-Weight Independent Sets

Abstract

: Maximum-weight independent-set (MWIS) selection is a core primitive in distributed intelligent systems because interference-limited communication, collision-free sensing, task activation, and resource allocation can all be represented by weighted conflict graphs. Existing distributed maximal-independent-set routines scale well but can lock in low-weight choices, whereas centralized MWIS solvers require global information and become impractical on large or time-varying networks. This paper develops an exchange-refined adaptive distributed game algorithm (ADGA-X) for static and dynamic weighted conflict networks. Unlike a plain distributed greedy rule or an unconstrained potential-game iteration, ADGA-X uses a penalty threshold that makes conflict removal locally dominant, then couples certified parallel better responses with bounded-radius exchange refinement and dynamic repair. First, a penalty-dominant binary game is constructed whose local utilities admit an exact potential. A common upper bound on vertex weights gives a penalty choice implementable with distributed information, makes every pure Nash equilibrium a feasible maximal independent set, and makes every global potential maximizer an MWIS solution. Second, nonadjacent strict better responses are scheduled in parallel by lexicographic one-hop priorities, preserving additive potential improvement and finite convergence. Third, one-and two-vertex exchanges use bounded-radius proposal coordination to refine the equilibrium without a global controller. Exhaustive refinement terminates at full one-and two-vertex exchange stability; the practical candidate-and round-capped variant remains feasible, monotone, finitely convergent, and singleton-exchange stable, thereby retaining a degree-dependent approximation guarantee. Fourth, an explicit warm-start repair is introduced for topology and weight changes, together with bounds on newly created conflicts and potential drift. Paired 20-instance validation shows that ADGA-X significantly outperforms the tested belief-propagation (BP) decoder on Erdo˝s–Rényi (ER) and random geometric graph (RGG) instances but not on Barabási–Albert-type (BA) graphs, clarifying the topology-dependent tradeoff. Across these three graph families, ADGA-X improves the base potential-game equilibrium by 8.19%–11.61%, and every returned set is feasible by construction. On exact small instances, it reaches a mean optimality ratio of 0.990, and the repaired warm start reduces post-change recovery outer rounds by approximately 47.0% while maintaining a mean warm/cold final-weight ratio of 1.0020.