Strategic Contention Resolution in Multiple Channels with Limited Feedback

20^th June 2018, 13:00
Themistoklis Melissourgos
University of Liverpool

Abstract

We consider a game-theoretic setting of contention in communication networks. In a contention game each of n >= 2 anonymous agents (with no IDs) has a single information packet that she wants to transmit using one of k >= 1 multi-access channels. An agent uses a slotted-time protocol that prescribes the probabilities with which at a given time-step she will attempt transmission at each channel. If more than one agents try to transmit over the same channel (collision) then no transmission happens on that channel.
Each agent is selfish and tries to minimize her own cost, i.e. her expected time until successful transmission, by freely choosing her own transmission protocol. The natural problem that arises in such a setting is, given n and k, to provide the players with a common, anonymous protocol (if it exists) such that no one would unilaterally deviate from it (equilibrium protocol).
So far, theoretical analysis in strategic contention resolution had only been done for the single-channel case. In this work, we find equilibrium characterizations for any k >= 1 in two important classes of protocols, where the classes are distinguished according to the system's feedback. We extend the already known results by giving equilibrium protocols for k = 2 and k = 3 channels, and by providing efficient protocols in equilibrium for any k >= 1 in both feedback classes.

Joint work with George Christodoulou and Paul Spirakis.