WAOA 2018 Paper Abstract

TITLE: Strategic Contention Resolution in Multiple Channels
AUTHORS: George Christodoulou, Themistoklis Melissourgos and Paul Spirakis

Abstract:
In this work we study the problem of strategic contention resolution in communication networks when there are more than one multi-access transmission channels available. In our communication setting the users are selfish and try to minimize their own expected latency, i.e. the time until they successfully transmit a packet through any of the transmission channels. In such a \textit{contention game} a player is free to choose her own time-slotted transmission protocol, knowing the other users' protocols. We seek anonymous protocols in Nash equilibrium so as to be able to propose a common protocol to all players and create no incentive for them to deviate.

In general, equilibrium protocols depend on the feedback that the users get from the network. Here we focus on the setting with \textit{ternary feedback}, where a player at each time-step is informed about the number of players that have not transmitted successfully yet. For the case of 2 channels, we give a characterization of equilibria, and we present the asymptotic behaviour of the unique equilibrium when the users are memoryless. For the case of $k \geq 1$ channels we present a general, anonymous protocol in equilibrium that makes all $n \in \omega(k)$ players transmit successfully with high probability in time $\Theta(n/k)$, i.e. optimal time. This efficiency in time is gained, however, in exchange for infinite expected latency.