  In various online/offline multi-agent networked environments, it is very
popular that the system can benefit from coordinating actions of two
interacting agents at some cost of coordination. In this paper, we first
formulate an optimization problem that captures the amount of coordination gain
at the cost of node activation over networks. This problem is challenging to
solve in a distributed manner, since the target gain is a function of the
long-term time portion of the inter-coupled activations of two adjacent nodes,
and thus a standard Lagrange duality theory is hard to apply to obtain a
distributed decomposition as in the standard Network Utility Maximization. In
this paper, we propose three simulation-based distributed algorithms, each
having different update rules, all of which require only one-hop message
passing and locally-observed information. The key idea for being
distributedness is due to a stochastic approximation method that runs a Markov
chain simulation incompletely over time, but provably guarantees its
convergence to the optimal solution. Next, we provide a game-theoretic
framework to interpret our proposed algorithms from a different perspective. We
artificially select the payoff function, where the game's Nash equilibrium is
asymptotically equal to the socially optimal point, i.e., no Price-of-Anarchy.
We show that two stochastically-approximated variants of standard game-learning
dynamics overlap with two algorithms developed from the optimization
perspective. Finally, we demonstrate our theoretical findings on convergence,
optimality, and further features such as a trade-off between efficiency and
convergence speed through extensive simulations.
