![[2407.00575] Learning to Control Unknown Strongly Monotone Games](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2407.00575] Learning to Control Unknown Strongly Monotone Games
Summary
This article presents a novel algorithm for controlling unknown strongly monotone games, focusing on adjusting Nash equilibria to meet linear constraints without requiring full knowledge of player rewards or action sets.
Why It Matters
Understanding how to effectively manage multi-agent systems is crucial in various applications, from economics to robotics. This research addresses the challenge of controlling game dynamics in large-scale networks while preserving user privacy, making it relevant for advancing AI and game theory.
Key Takeaways
- The proposed algorithm shifts Nash equilibria to satisfy linear constraints.
- It operates without needing complete knowledge of player rewards or action sets.
- The algorithm converges with high probability to the desired generalized Nash equilibrium.
- An L2 convergence rate of near-$O(t^{-1/4})$ is established.
- This approach enhances control in multi-agent systems while addressing privacy concerns.
Computer Science > Multiagent Systems arXiv:2407.00575 (cs) [Submitted on 30 Jun 2024 (v1), last revised 24 Feb 2026 (this version, v3)] Title:Learning to Control Unknown Strongly Monotone Games Authors:Siddharth Chandak, Ilai Bistritz, Nicholas Bambos View a PDF of the paper titled Learning to Control Unknown Strongly Monotone Games, by Siddharth Chandak and 2 other authors View PDF HTML (experimental) Abstract:Consider a strongly monotone game where the players' utility functions include a reward function and a linear term for each dimension, with coefficients that are controlled by the manager. Gradient play converges to a unique Nash equilibrium (NE) that does not optimize the global objective. The global performance at NE can be improved by imposing linear constraints on the NE, also known as a generalized Nash equilibrium (GNE). We therefore want the manager to control the coefficients such that they impose the desired constraint on the NE. However, this requires knowing the players' rewards and action sets. Obtaining this game information is infeasible in a large-scale network and violates user privacy. To overcome this, we propose a simple algorithm that learns to shift the NE to meet the linear constraints by adjusting the controlled coefficients online. Our algorithm only requires the linear constraints violation as feedback and does not need to know the reward functions or the action sets. We prove that our algorithm converges with probability 1 to the set of GN...