Strategic Contention Resolution in Multiple Channels

Christodoulou, George, Melissourgos, Themistoklis ORCID: 0000-0002-9867-6257 and Spirakis, Paul G ORCID: 0000-0001-5396-3749 (2018) Strategic Contention Resolution in Multiple Channels. In: 16th Workshop on Approximation and Online Algorithms (WAOA 2018), 2018-8-23 - 2018-8-24, Helsinki Finland.

Text WAOA2018_paper_21.pdf - Author Accepted Manuscript Download (938kB)

Abstract

We consider the problem of resolving contention in communication networks with selfish users. In a \textit{contention game} each of $n \geq 2$ identical players has a single information packet that she wants to transmit using one of $k \geq 1$ multiple-access channels. To do that, a player chooses 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 players try to transmit over the same channel (collision) then no transmission happens on that channel. Each player tries to minimize her own expected \textit{latency}, i.e. her expected time until successful transmission, by choosing her 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). All previous theoretical results on strategic contention resolution examine only the case of a single channel and show that the equilibrium protocols depend on the feedback that the communication system gives to the players. Here we present multi-channel equilibrium protocols in two main feedback classes, namely \textit{acknowledgement-based} and \textit{ternary}. In particular, we provide equilibrium characterizations for more than one channels, and give specific anonymous, equilibrium protocols with finite and infinite expected latency. In the equilibrium protocols with infinite expected latency, all players transmit successfully in optimal time, i.e. $\Theta(n/k)$, with probability tending to 1 as $n/k \to \infty$.

Item Type:	Conference or Workshop Item (Unspecified)
Additional Information:	The results of this work are included in the 11th International Symposium on Algorithmic Game Theory (SAGT 2018) and the 16th Workshop on Approximation and Online Algorithms (WAOA 2018)
Uncontrolled Keywords:	Contention resolution, Multiple channels Acknowledgement-based protocol, Ternary feedback, Game theory
Depositing User:	Symplectic Admin
Date Deposited:	26 Jul 2018 09:50
Last Modified:	19 Jan 2023 01:30
DOI:	10.1007/978-3-030-04693-4_11
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3024167