Deviate or Not: Learning Coalition Structures with Multiple-bit Observations in Games
Preprint
Abstract
We consider the Coalition Structure Learning (CSL) problem in multi-agent systems, motivated by the existence of coalitions in many real-world systems, e.g., trading platforms and auction systems. In this problem, there is a hidden coalition structure within a set of $n$ agents, which affects the behavior of the agents in games. Our goal is to actively design a sequence of games for the agents to play, such that observations in these games can be used to learn the hidden coalition structure. In particular, we consider the setting where in each round, we design and present a game together with a strategy profile to the agents, and receive a multiple-bit observation -- for each agent, we observe whether or not they would like to deviate from the specified strategy. We show that we can learn the coalition structure in $O(\log n)$ rounds if we are allowed to design any normal-form game, matching the information-theoretical lower bound. For practicality, we extend the result to settings where we can only choose games of a specific format, and design algorithms to learn the coalition structure in these settings. For most settings, our complexity matches the theoretical lower bound up to a constant factor.
Keywords
All Related Versions
This publication has 4 references indexed in Scilit:
- Adversarial Attacks on Deep Reinforcement Learning-based Traffic Signal Control Systems with Colluding VehiclesACM Transactions on Intelligent Systems and Technology, 2023
- What Game Are We Playing? End-to-end Learning in Normal and Extensive Form Games2018
- Automating Collusion Detection in Sequential GamesProceedings of the AAAI Conference on Artificial Intelligence, 2013
- A class of games possessing pure-strategy Nash equilibriaInternational Journal of Game Theory, 1973