License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2016.30
URN: urn:nbn:de:0030-drops-63813
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6381/
Go to the corresponding LIPIcs Volume Portal

Christodoulou, George ; Gairing, Martin ; Nikoletseas, Sotiris ; Raptopoulos, Christoforos ; Spirakis, Paul

Strategic Contention Resolution with Limited Feedback

pdf-format:
LIPIcs-ESA-2016-30.pdf (0.5 MB)

Abstract

In this paper, we study contention resolution protocols from a game-theoretic perspective. We focus on 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 age-based and 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.

BibTeX - Entry

@InProceedings{christodoulou_et_al:LIPIcs:2016:6381,
  author =	{George Christodoulou and Martin Gairing and Sotiris Nikoletseas and Christoforos Raptopoulos and Paul Spirakis},
  title =	{{Strategic Contention Resolution with Limited Feedback}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{30:1--30:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Piotr Sankowski and Christos Zaroliagis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6381},
  URN =		{urn:nbn:de:0030-drops-63813},
  doi =		{10.4230/LIPIcs.ESA.2016.30},
  annote =	{Keywords: contention resolution, acknowledgment-based protocols, game theory}
}

Keywords: contention resolution, acknowledgment-based protocols, game theory
Collection: 24th Annual European Symposium on Algorithms (ESA 2016)
Issue Date: 2016
Date of publication: 18.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI