Strategic Contention Resolution with Limited Feedback
From MaRDI portal
Publication:4606299
DOI10.4230/LIPICS.ESA.2016.30zbMATH Open1397.68012arXiv1606.06580OpenAlexW2964195933MaRDI QIDQ4606299FDOQ4606299
George Christodoulou, Christoforos L. Raptopoulos, Sotiris E. Nikoletseas, P. G. Spirakis, Martin Gairing
Publication date: 2 March 2018
Abstract: In this paper, we study contention resolution protocols from a game-theoretic perspective. We focus on emph{acknowledgment-based} protocols, where a user gets feedback from the channel only when she attempts transmission. In this case she will learn whether her transmission was successful or not. Users that do not transmit will not receive any feedback. We are interested in equilibrium protocols, where no player has an incentive to deviate. The limited feedback makes the design of equilibrium protocols a hard task as best response policies usually have to be modeled as Partially Observable Markov Decision Processes, which are hard to analyze. Nevertheless, we show how to circumvent this for the case of two players and present an equilibrium protocol. For many players, we give impossibility results for a large class of acknowledgment-based protocols, namely emph{age-based} and emph{backoff} protocols with finite expected finishing time. Finally, we provide an age-based equilibrium protocol, which has infinite expected finishing time, but every player finishes in linear time with high probability.
Full work available at URL: https://arxiv.org/abs/1606.06580
Cited In (1)
This page was built for publication: Strategic Contention Resolution with Limited Feedback
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4606299)
