Research News: Adversarial Contention Resolution Games
Giorgos Chionas, Year 1 PhD student, shares research news about the paper he had published at Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI-23) August 2023.
Summary
We study contention resolution in a shared channel modelled as a game with selfish players. There are n agents attached to the channel and the adversary chooses some k ≤ n of them as players. Each agent participating as a player in a contention resolution game has a packet to transmit. A transmission is successful when 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, which incorporates adversarial selection of players. We develop efficient deterministic communication algorithms that are also, adversarial equilibria.
Importance of the research
This work came as an attempt to combine notions from distributed computing and game theory. We studied the problem of contention resolution in a shared channel. A shared channel, or a multiple access channel, is one of the fundamental communication models: it allows many autonomous computing entities to communicate over a shared medium and the main challenge is how to efficiently resolve collisions occurring when more than one entity attempts to access the channel at the same time. The channel also provides feedback in each round of communication, depending on the number of attempts in that round. In this work we assume minimal access to the feedback by the stations.
Moreover, there are two parameters that are known a priori, which is the total number of players We introduced a new solution concept of a non-cooperative game involving two or more agents. This concept combines a notion from classical worst-case adversary from distributed computing with the notion of Nash equilibrium and Pareto optimal solution concepts from game theory. The implications of our results are that by studying this model under a non-cooperative setting we show the overall efficiency is compromised. We quantify the loss in efficiency by calculating the Price of Anarchy, which is the ratio between the overall efficiency in the cooperative setting and the overall efficiency in the worst-case adversarial equilibria.
What comes next?
It is known that the social welfare, in our case total latency is compromised when we consider non-cooperative settings. We constructed optimal algorithms for small numbers of active agents. Gaps remain though for larger numbers of active agents, and this is certainly a future work. Another interesting direction is to explore our notion in channels with stronger feedback where the agents’ strategies will be adaptive to the feedback elicited. Finally, we are also interested in studying contention resolution by considering less risk averse behaviour of agents.
This paper was published as part of the Thirty-Second International Joint Conference on Artificial Intelligence (IJCAI-23) August 2023.