16 May 2024 in IEEE Control Systems Letters
We develop a best-response algorithm for solving constrained Markov games assuming limited violations for the potential game property. The limited violations of the potential game property mean that changes in value function due to unilateral policy alterations can be measured by the potential function up to an error α. We show the existence of stationary -approximate constrained Nash policy whenever the set of feasible stationary policies is non-empty. Our setting has agents accessing an efficient probably approximately correct solver for a constrained Markov decision process which they use for generating best-response policies against the other agents’ former policies. For an accuracy threshold >4α, the best-response dynamics generate provable convergence to -Nash policy in finite time with probability at least 1-δ at the expense of polynomial bounds on sample complexity that scales with the reciprocal of and δ.
29 November 2023 in IISE Transactions
20 September 2024 in SIAM Journal on Control and Optimization
We consider the control of decentralized learning dynamics for agents in an anticoordination network game. In the anticoordination network game, there is a preferred action in the absence of neighbors’ actions, and the utility an agent receives from the preferred action decreases as more of its neighbors select the preferred action, potentially causing the agent to select a less desirable action. The decentralized dynamics that are based on the synchronous best-response dynamics converge for the considered payoffs. Given a convergent action profile, we measure anticoordination by the number of edges in the underlying graph that have at least one agent in either end of the edge not taking the preferred action. A designer wants to find an optimal set of agents to control under a finite budget in order to achieve maximum anticoordination (MAC) on game convergence as a result of the dynamics. We show that the MAC is submodular in expectation over all realizations of the payoff interaction constants in bipartite networks. The proof relies on characterizing well-behavedness of MAC instances for bipartite networks, and designing a coupling between the dynamics and another distribution preserving selection protocol, for which we can show the diminishing returns property. Utilizing this result, we obtain a performance guarantee for the greedy optimization of MAC. Finally, we provide a computational study to show the effectiveness of greedy node selection strategies to solve MAC on general bipartite networks.