Adversarial Contention Resolution Games

Adversarial Contention Resolution Games

Giorgos Chionas, Bogdan S. Chlebus, Dariusz R. Kowalski, Piotr Krysta

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence
Main Track. Pages 2598-2606. https://doi.org/10.24963/ijcai.2023/289

We study contention resolution (CR) on a shared channel modelled as a game with selfish players. There are n agents and the adversary chooses some k smaller than n of them as players. Each participating player in a CR game has a packet to transmit. A transmission is successful if it is performed as the only one at a round. Each player aims to minimize its packet latency. We introduce the notion of adversarial equilibrium (AE), which incorporates adversarial selection of players. We develop efficient deterministic communication algorithms that are also AE. We characterize the price of anarchy in the CR games with respect to AE.
Keywords:
Game Theory and Economic Paradigms: GTEP: Noncooperative games
Agent-based and Multi-agent Systems: MAS: Agent theories and models
Game Theory and Economic Paradigms: GTEP: Mechanism design